Какой самый быстрый способ сравнить два словаря?

Question

Я пытаюсь найти самый быстрый способ сопоставить два словаря в Actionscript-3.Это то, что я получил до сих пор.

function compareDictionaries(p0:Dictionary, p1:Dictionary):Boolean 
{
    if(p0 == p1) {
        return true;
    } else {

        const matched:Dictionary = new Dictionary();
        for(var k0:Object in p0) {
            matched[k0] = k0;
            if(p0[k0] != p1[k0]) {
                return false;
            }
        }

        for(var k1:Object in p1) {
            if(matched[k1]) {
                continue;
            } else {
                if(p1[k1] != p0[k1]) {
                    return false;
                }
            }
        }

        return true;
    }
}

Очевидно, что не идеально создавать новый словарь с ключом для элемента, но я действительно не хочу повторно тестировать соответствующий элемент (не этоЯ знаю, если это будет медленнее или нет!).Это, конечно, можно обойти, если иметь длину в классе словаря, что сделает второй цикл for избыточным.

Какие-нибудь лучшие идеи по этому поводу?

РЕДАКТИРОВАТЬ

Я создал gist эталонного теста, чтобы показать результаты дляуспешное совпадение (используйте проигрыватель релиза)

(вывод результатов в (мс)) true 43 true 497 true 22 true 16

EDIT 2 Я создал еще один Суть показывает промах равенства.

(вывод результатов в (мс)) false 1 false 472 false 0 false 0

Answer 1

Что-то простое, как это должно работать - никаких новых массивов / словарей и т. Д .:

public function compareDictionaries( d1:Dictionary, d2:Dictionary ):Boolean
{
    // quick check for the same object
    if( d1 == d2 )
        return true;

    // check for null
    if( d1 == null || d2 == null )
        return false;

    // go through the keys in d1 and check if they're in d2 - also keep a count
    var count:int = 0;
    for( var key:* in d1 )
    {
        // check if the key exists
        if( !( key in d2 ) )
            return false;

        // check that the values are the same
        if( d1[key] != d2[key] )
            return false;

        count++;
    }

    // now just make sure d2 has the same number of keys
    var count2:int = 0;
    for( key in d2 )
        count2++;

    // return if they're the same size
    return ( count == count2 );
}

Технически вы можете просто сделать прямое сравнение со значениями (как в случае не проверять наличие ключав d2) как если бы вы искали ключ, которого там нет, он должен разрешиться до null (или undefined, я не уверен на 100%), но я оставил его там в случае, когда значение в d1 равно нулю и не существует в d2

Answer 2

Начните со сравнения строгого равенства.Затем проверьте равенство ключей в обоих словарях:

• Переберите свойства и верните все ключи в массивах
• Проверьте на одинаковую длину массива
• Сортируйте массивы
• Итерация еще раз для сравнения

Только если все эти тесты пройдены, сравните фактические значения:

public function areEqualDictionaries( dict1:Dictionary, dict2:Dictionary ):Boolean {
    if(dict1 === dict2) return true;

    var keys:Array = equalKeysArrayOrNull( dict1, dict2 ); 
    if(keys) 
        return haveEqualValues( keys, dict1, dict2 );
    else
        return false;
}

private function equalKeysArrayOrNull( dict1:Dictionary, dict2:Dictionary ):Array {
    var keys1:Array = enumerateKeys( dict1 ).sort();
    var keys2:Array = enumerateKeys( dict2 ).sort();
    if( keys1.length != keys2.length ) return null;

    var i:int = -1;
    while(++i < keys1.length) 
        if(keys1[i] !== keys2[i]) return null;

    return keys1;
}

private function haveEqualValues ( keys:Array, dict1 : Dictionary, dict2:Dictionary) :Boolean {
    for each (var key:* in keys) 
        if (dict1[key] != dict2[key]) return false;
    return true;
}

private function enumerateKeys( dict:Dictionary ):Array {
    var keys:Array = [];
    for(var key:* in dict) 
        keys.push( key );
    return keys;
}

Обратите внимание, что словари используют тождество (строгоравенство) для сопоставления ключей, что делает необходимым использование !== для их сравнения.Я полагаю, что можно использовать != для сравнения значений.

РЕДАКТИРОВАТЬ: Сравнение для против для каждого

Вот мой собственный тест for против for each:

var dict : Dictionary = new Dictionary();
var keys : Array = [];
for (var i : int = 0; i < 1000000; i++) {
    var n : Object = { index:i };
    dict[n] = n;
    keys.push (n);
}

trace ("benchmark:");

trace ("----------");
var start : int = getTimer();

for each (var key:* in keys) {
    var m:* = dict[key];
}
var elapsed : int = getTimer() - start;
trace ("for each:" + elapsed);

trace ("----------");
start = getTimer();

for (var j:int = 0; j < keys.length; j++) {
    var o:* = dict[keys[j]];
}
elapsed = getTimer() - start;
trace ("for:" + elapsed);

возвращается на мою машину:

for each:213
----------
for:274