Сравнение всех элементов из двух хешей более эффективно

Question

У меня есть два хэша в perl, каждый из которых содержит около 250000 элементов. Я должен сравнить каждый элемент из обоих хэшей друг с другом и выполнить другую операцию над элементами, которые равны друг другу. У меня есть следующий код, который делает ~ 60 миллиардов сравнений, поэтому для его завершения требуется слишком много времени:

foreach $key1 (keys %large_hash_1)
    {
    foreach $key2 (keys %large_hash_2)
        {
        if($some_other_var{$key1} == $some_other_var{$key2}) # so actually I compare another hash variable, using the keys from %large_hash_1 and %large_hash_2
             {
             # I print some stuff here to an output file using the $key1 and $key2 variables
             }
        }
    }

Есть ли способ сделать это быстрее?

Answer 1

Возможно. Похоже, вы можете переформулировать проблему как

Найти все пары ключей K1 и K2, для которых:

• $some_other_hash{K1} == $some_other_hash{K2}
• K1 существует в %hash1, а K2 существует в %hash2

так что давайте попробуем подход, в котором вы сначала найдете решения для первого условия, а затем посмотрим, удовлетворяют ли они второму условию. Итерация по всем парам ключей - это O (n ² ), но у нас уже есть стратегия для нахождения ключей, которые быстро сопоставляются с тем же значением хеш-функции: используйте другой хеш!

Давайте создадим «обратный хеш» %some_other_hash, чтобы $hash7{VAL} создавал список всех ключей в %some_other_hash, так что $some_other_hash{KEY} == VAL:

push @{$hash7{ $some_other_hash{$_} }, $_ for keys %some_other_hash;

Это была операция O (n). Затем нам нужно найти значения, которые соответствуют нескольким ключам.

foreach my $v (keys %hash7) {
    @k = @{$hash7{$v}};
    next if @k < 2;
    ...
}

Если вы найдете такое значение, проверьте, находятся ли некоторые ключи в %hash1, а некоторые в %hash2.

foreach my $v (keys %hash7) {
    @k = @{$hash7{$v}};
    next if @k < 2;
    @k1 = grep { exists $hash1{$_} } @k;
    @k2 = grep { exists $hash2{$_} } @k;
    if (@k1 && @k2) {
        foreach my $k1 (@k1) {
            foreach my $k2 (@k2) {
                print "$k1 from %hash1 and $k2 from %hash2 ",
                      "have the same value $v in %some_other_hash\n";
                ...
            }
        }
    }
}

В худшем случае, когда в %some_other_hash обычно встречаются значения, которые отображаются более чем одним ключом, этот цикл равен O (mn). В зависимости от ваших данных этот поиск может быть значительно быстрее, чем итерация по всем парам ключей в %hash1 и %hash2.