高效地记忆化对象参数

Question

摘要: 除了使用 JSON.stringify，是否有更快的哈希对象的方法？

详情: 我有一个Ruby和JavaScript库（NeatJSON），它提供了JavaScript值的漂亮打印。最近，我修复了一个问题，深度嵌套的对象导致 O(n!) 性能问题（n 是嵌套级别），使用基于被序列化的对象和缩进量的备忘录。

在Ruby中，修复非常容易，因为您可以通过独特对象集合的数组索引散列表：

build = ->(object,indent) do
  memoizer[[object,indent]] ||= <all the rest of the code>
end

然而，在JavaScript中，我无法通过另一个对象（以独特的方式）对对象进行索引。在多篇在线文章的指导下，我决定使用JSON.stringify在函数的所有参数上创建一个唯一的键来进行通用修复问题：

function memoize(f){
  var memo  = {};
  var slice = Array.prototype.slice;
  return function(){
    var args = slice.call(arguments);
    var mkey = JSON.stringify(args);
    if (!(mkey in memo)) memo[mkey] = f.apply(this,args);
    return memo[mkey];
  }
}

function rawBuild(o,indent){ .. }
var build = memoize(rawBuild);

这种方法可行，但 (a) 比我想要的稍微慢一些，而且 (b) 执行（天真）序列化每个对象和值似乎非常低效（和不优雅）。对具有许多值的大型对象进行序列化，将为整个对象中的每个唯一值（而不仅仅是叶子值）存储字符串和格式化结果。

是否有现代 JavaScript 技巧可以让我唯一地标识一个值？例如，某种访问内部 ID 或以 O(1) 时间找到值的唯一整数的方式来关联复杂对象？

- Phrogz

---

非常类似于（不完全是复制）JavaScript对象ID。不完全是复制，因为我需要找到大多数类型值（字符串、布尔、数字、数组、对象）的唯一表示，而不仅仅是对象。 - Phrogz

你想按对象值还是引用进行记忆化？换句话说：var a = {b:1}; var c = memoizedFn(a); a.b = 2; var d = memoizedFn(a); 第二次调用应该使用记忆化的值吗？ - Tamas Hegedus

@TamasHegedus 通过引用完全足够。 - Phrogz

Answer 1

如果您想按标识（而不是内容）进行对象的备忘录，则需要使用WeakMap，它专门为此目的设计。但对于原始值，它们无法工作，因此您需要针对这些参数采用不同的解决方案。

- Bergi

---

看起来非常有帮助。是的，在这种情况下，通过身份进行记忆化就足够了，因为我只是在同一棵树中上下爬行值。 - Phrogz

由于我需要支持原始值，因此似乎Map比WeakMap更合适。 - Phrogz

@Phrogz：是的，这取决于使用情况。如果一些对象在您仍然保留（或运行）记忆化函数时已经可以进行垃圾回收，则WeakMap可能具有更好的内存效率。 - Bergi

我会给你点赞，因为如果没有你提供的WeakMap链接，我就不会发现Map。此外，WeakMap与问题的标题（对象）相匹配，尽管并非我试图描述序列化任何值的实际需求。我鼓励其他人查看我的答案，以获取我最终采用的实际解决方案。 - Phrogz

这个库似乎使用了所描述的方法（使用 Maps/WeakMaps 进行记忆化 - 取决于传递的参数类型）：https://github.com/StarryInternet/map-memo - Venryx

我最终发现了几个其他使用WeakMap的库：https://dev59.com/CLroa4cB1Zd3GeqPmpCm#61402805（查看已选中“o-hash”的条目） - Venryx

Answer 2

使用@Bergi的建议，我了解到了Map，它允许使用任何值类型作为键（不仅限于对象）。因为我需要一个复合键——唯一地记忆传递给和缩进字符串的组合值——所以我创建了一个分层的记忆结构：

function memoizedBuild(){
  var memo = new Map;
  return function(value,indent){
    var byIndent=memo.get(value);
    if (!byIndent) memo.set(value,byIndent={});
    if (!byIndent[indent]) byIndent[indent] = rawBuild(value,indent);
    return byIndent[indent];
  }
}

这证明在序列化一个大的270kB JSON对象时，与我之前使用的记忆化代码相比，速度提高了约4倍。 请注意，在上面的代码中，我能够仅使用!byIndent[indent]，因为我知道rawBuild永远不会返回假值（null，undefined，false，NaN，0，""）。更安全的代码行看起来可能像这样：

if (!(indent in byIndent)) byIndent[indent] = rawBuild(value,indent);

- Phrogz

Answer 3

如果您只需要对对象进行备忘录，则将一些唯一的ID分配给您的对象是有意义的。

var gID = 0;

function createNode() {
  var obj = ...
  obj.id = (++gID).toString();
}

使用这些obj.id作为您的memo集合中的键，这将是最快和最不贪婪的解决方案。

更新：

如果您希望id属性不与现有属性冲突，则可以使用标准ES5.1 Object.createProperty()（使用一些唯一名称）创建非可枚举属性或使用ES6 symbols：

var gID = 0;
var gUidSym = Symbol("uid"); 

function getUidOf(obj) {
  return obj[gUidSym] 
      || (obj[gUidSym] = (++gID).toString());
}

- c-smile

---

两个问题：1）我无法控制被创建的对象。这是一个JSON序列化器，人们将他们的对象传递给我进行处理。2）因为我正在序列化对象的属性，所以您在此提出的“id”属性将被包含在序列化中（并可能与现有属性冲突）。 - Phrogz

请查看“更新：”部分。 - c-smile

创建属性（无论是字符串命名还是符号命名）存在一个问题，即它无法在封闭的对象上工作。 - Bergi