Эффективное запоминание аргументов объекта

Question

Резюме: Есть ли более быстрый способ для хэш-объектов, чем JSON.stringify?

Подробности: У меня есть библиотека Ruby и JavaScript (NeatJSON), которая обеспечивает довольно-типографию значений JavaScript. Недавно я исправил проблему, когда глубоко вложенные объекты вызывают производительность O (n!) (n - уровень вложенности) с использованием memoization на основе сериализуемого объекта и суммы отступа.

В 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); 

Это работает, но (а) это немного медленнее, чем мне хотелось бы, и (б) кажется дико неэффективным (и неэлегантным) выполнять (наивную) сериализацию каждого объекта и ценности, которые я собираюсь сериализовать. Акт сериализации большого объекта со многими значениями будет хранить строку и результат форматирования для КАЖДОГО уникального значения (а не только значений листа) всего объекта.

Есть ли современный трюк JavaScript, который позволил бы мне однозначно идентифицировать ценность? Например, какой-то способ доступа к внутреннему идентификатору или связывание сложных объектов с уникальными целыми числами, которые принимают O (1) раз, чтобы найти идентификатор для значения?

Answer 1

Если вы хотите сохранить меморандум о своих объектах по идентификационной информации (а не по содержанию), то вы захотите использовать WeakMap, который предназначен именно для этой цели. Однако они не работают для примитивных значений, поэтому для таких аргументов вам понадобится другое решение.

Answer 2

Если вам просто нужно запоминать объекты, тогда имеет смысл назначить уникальный идентификатор вашим объектам.

var gID = 0; 

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

и использовать эти obj.id «S в качестве ключей в вашей memo коллекции.

Это было бы самым быстрым и наименее жадным решением.

Update:

Если вы хотите, чтобы свойство идентификатора, чтобы не конфликтовать с существующими свойствами , то вы можете создать несчетное свойство, используя стандартные ES5.1 Object.createProperty() (с некоторым уникальным именем) или использовать ES6 symbols:

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

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

Answer 3

Использование @ предложение BERĢI о более WeakMap я узнал о Map, что позволяет использовать любого типа значение в качестве ключа (а не только объекты).Потому что мне нужен ключ-однозначно memoizing сочетание значения, переданного в и отступы соединение струнной-я создал иерархическую структуру запоминанием:

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]; 
    } 
} 

Это оказалось около 4 × быстрее memoization code I had been using при сериализации большой объект JSON 270 КБ.

Обратите внимание, что в приведенном выше коде я могу использовать !byIndent[indent] только потому, что я знаю, что rawBuild никогда не будет возвращать значение falsey (null, undefined, false, NaN, 0, ""). Безопаснее строка кода будет выглядеть примерно так:

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