对象参数的高效记忆

Question

总结：有没有比JSON.stringify更快的散列对象的方法？

详细信息：我有一个 Ruby 和 JavaScript 库 (NeatJSON)，它提供 JavaScript 的漂亮打印值。我最近解决了一个问题，即深度嵌套对象导致 O(n!) 性能（n 是嵌套级别）使用基于被序列化的对象和缩进量的记忆。

在 Ruby 中，the fix 真的很容易，因为您可以通过唯一对象集的数组索引散列：

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

但是，在 JavaScript 中，我无法通过另一个对象（以独特的方式）为一个对象编制索引。根据我在网上找到的几篇文章，我决定一般地 fix the problem，在函数的完整参数集上使用 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) 时间来查找值的标识符？

Answer 1

如果您希望通过标识（而不是内容）来记忆您的对象，那么您需要使用专为此目的而设计的 WeakMap。但是它们不适用于原始值，因此您需要针对此类参数的不同解决方案。

Answer 2

如果你只需要记忆 objects 那么给你的 objects 分配一些唯一的 ID 是有意义的。

var gID = 0;

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

并将这些 obj.id 用作 memo collection 中的键。

那将是最快且最不贪婪的解决方案。

更新：

如果您希望该 ID 属性不与现有属性发生冲突然后您可以使用标准 ES5.1 Object.createProperty() (with some unique name) or to use ES6 symbols:

创建 non-enumerable 属性

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

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

Answer 3

使用@Bergi 对 WeakMap 的建议，我发现了 Map，它允许使用 any 值类型作为键（不仅仅是对象） .因为我需要一个复合键——唯一地记忆 中传递的值和 缩进字符串的组合——我创建了一个分层记忆结构：

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 对象时，这被证明比 memoization code I had been using 快大约 4 倍。

请注意，在上面的代码中我能够使用 !byIndent[indent] 只是因为我知道 rawBuild 永远不会 return 一个错误的值（null，undefined、false、NaN、0、""）。更安全的代码行看起来像：

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

对象参数的高效记忆

Efficient memoization of object arguments

javascript

memoization