有效记忆对象参数

Efficient memoization of object arguments

本文关键字：参数 对象 记忆 有效      更新时间：2023-09-26

>摘要：有没有比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( 时间才能找到值的标识符？

如果你想通过身份(而不是内容(来记忆你的对象，那么你需要使用一个专门为此目的而设计的WeakMap。但是，它们不适用于原始值，因此您需要为此类参数提供不同的解决方案。

使用@Bergi的WeakMap建议，我发现了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永远不会返回 falsey 值(null、undefined、false、NaN、0、""(。更安全的代码行如下所示：

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

如果您只需要记住对象，那么为您的对象分配一些唯一 ID 是有意义的。

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

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

这将是最快，最不贪婪的解决方案。

更新：

如果希望该 id 属性不与现有属性冲突然后，您可以使用标准 ES5.1 Object.createProperty(((具有一些唯一名称(或使用 ES6 符号来创建不可枚举的属性：

var gID = 0;
var gUidSym = Symbol("uid"); 
function getUidOf(obj) {
  return obj[gUidSym] 
      || (obj[gUidSym] = (++gID).toString());
}
相关文章：