Можно ли использовать Perl-хэш таким образом, чтобы поиск и вставка `O (log (n))`?

Question

Можно ли использовать Perl-хэш таким образом, чтобы O(log(n)) осуществлял поиск и вставку?

По умолчанию я предполагаю, что поиск O(n), поскольку он представлен в несортированном списке.

Я знаю, что мог бы создать структуру данных для удовлетворения этого (например, дерево и т. Д.), Однако, было бы лучше, если бы он был встроен и мог использоваться как обычный хеш (т. Е. С%)

Answer 1

Ассоциативные массивы в Perl 5 реализованы с помощью хеш-таблиц , которые амортизируют вставку и поиск O (1) (то есть с постоянным временем). Вот почему мы склонны называть их хэшами, а не ассоциативными массивами.

Трудно найти документацию, в которой говорится, что Perl 5 использует хеш-таблицу для реализации ассоциативных массивов (помимо того, что мы называем ассоциативные массивы "хешами"), но по крайней мере это есть в perldoc perlfaq4

What happens if I add or remove keys from a hash while iterating over it?
   (contributed by brian d foy)

   The easy answer is "Don't do that!"

   If you iterate through the hash with each(), you can delete the key
   most recently returned without worrying about it.  If you delete or add
   other keys, the iterator may skip or double up on them since perl may
   rearrange the hash table.  See the entry for "each()" in perlfunc.

Еще лучше цитата из perldoc perldata:

   If you evaluate a hash in scalar context, it returns false if the hash
   is empty.  If there are any key/value pairs, it returns true; more
   precisely, the value returned is a string consisting of the number of
   used buckets and the number of allocated buckets, separated by a slash.
   This is pretty much useful only to find out whether Perl's internal
   hashing algorithm is performing poorly on your data set.  For example,
   you stick 10,000 things in a hash, but evaluating %HASH in scalar
   context reveals "1/16", which means only one out of sixteen buckets has
   been touched, and presumably contains all 10,000 of your items.  This
   isn't supposed to happen.  If a tied hash is evaluated in scalar
   context, a fatal error will result, since this bucket usage information
   is currently not available for tied hashes.

Конечно, O (1) - только теоретическая производительность. В реальном мире у нас нет совершенных хеш-функций, поэтому хеши замедляются по мере их увеличения, и есть некоторые вырожденные случаи, которые превращают хеш в O (n), но Perl делает все возможное, чтобы этого не произошло. Вот эталон Perl-хэшей с ключами 10, 100, 1000, 10000, 100000:

Perl version 5.012000
               Rate 10^5 keys 10^4 keys 10^3 keys 10^2 keys 10^1 keys
10^5 keys 5688029/s        --       -1%       -4%       -7%      -12%
10^4 keys 5748771/s        1%        --       -3%       -6%      -11%
10^3 keys 5899429/s        4%        3%        --       -4%       -9%
10^2 keys 6116692/s        8%        6%        4%        --       -6%
10^1 keys 6487133/s       14%       13%       10%        6%        --

Вот код теста:

#!/usr/bin/perl

use strict;
use warnings;

use Benchmark;

print "Perl version $]\n";

my %subs;
for my $n (1 .. 5) {
    my $m = 10 ** $n;
    keys(my %h) = $m; #preallocated the hash so it doesn't have to keep growing
    my $k = "a";
    %h = ( map { $k++ => 1 } 1 .. $m );
    $subs{"10^$n keys"} = sub {
        return @h{"a", $k};
    }
};

Benchmark::cmpthese -1, \%subs;

Answer 2

Perl-хэш - это хеш-таблица , поэтому он уже имеет O (1) вставку и поиск.

Answer 3

Любой, кто считает, что время вставки хэша или времени поиска равно O (1) на современном оборудовании , чрезвычайно наивно. Измерение при одинаковом значении просто неправильно . Следующие результаты дадут вам гораздо лучшее представление о том, что происходит.

Perl version 5.010001
            Rate 10^6 keys 10^5 keys 10^1 keys 10^4 keys 10^3 keys 10^2 keys
10^6 keys 1.10/s        --      -36%      -64%      -67%      -68%      -69%
10^5 keys 1.73/s       57%        --      -43%      -49%      -50%      -52%
10^1 keys 3.06/s      177%       76%        --      -10%      -12%      -15%
10^4 keys 3.40/s      207%       96%       11%        --       -3%       -5%
10^3 keys 3.49/s      216%      101%       14%        3%        --       -3%
10^2 keys 3.58/s      224%      107%       17%        6%        3%        --

Приведенный выше результат измеряется в системе с 5 МБ кэш-памяти процессора. Обратите внимание, что производительность значительно падает с 3,5 М / с до 1 М / с поисков. В любом случае, это все еще очень быстро, и в некоторых случаях вы можете обойти даже такие системы, как RDBMS, если знаете, что делаете. Вы можете измерить вашу систему, используя следующий код:

#!/usr/bin/perl

use strict;
use warnings;

use Benchmark;

print "Perl version $]\n";

my %subs;
for my $n ( 1 .. 6 ) {
    my $m = 10**$n;
    keys( my %h ) = $m;    #preallocated the hash so it doesn't have to keep growing
    my $k = "a";
    %h = ( map { $k++ => 1 } 1 .. $m );
    my $l = 10**( 6 - $n );
    my $a;
    $subs{"10^$n keys"} = sub {
        for ( 1 .. $l ) {
            $a = $h{$_} for keys %h;
        }
    };
}

Benchmark::cmpthese -3, \%subs;

Не следует также забывать, что время поиска хеша зависит от длины ключа. Просто нет реальной технологии с O (1) временем доступа. Каждая известная реальная технология имеет O (logN) время доступа в лучшем случае. Есть только системы, которые имеют время доступа O (1), потому что ограничивают их максимальное N и ухудшают его производительность для низких N. Это то, как все работает в реальном мире, и это причина, почему кто-то создает алгоритмы, такие как Judy Array и эволюция становится все хуже и хуже.