Bezdepbonusu7Программирование: статьи и ответы
Меню

Вопрос

Сравнение строк или поиск хеша быстрее в Perl?

Автор вопроса: user105033Ответов: 5

У меня есть код, который в какой-то части будет выполняться много раз, и мне интересно, какой способ реализации более эффективен. Я буду использовать цикл for для имитации части, которая часто выполняется:

вариант А:

my %sections = (
    'somestring1' => 1,
    'somestring2' => 1,
    'somestring3' => 1,
    'somestring4' => 1
);

for (0..10000)
{
    # $element is chosen at random
    $namespace = $element if $sections{$element};
}

вариант Б:

for (0..10000)
{
    # $element is chosen at random
    $namespace = $element if ($element eq'somestring1' ||
                            $element eq'somestring2' ||
                            $element eq'somestring3' ||
                            $element eq'somestring4');
}

Может ли кто-нибудь сравнить это или узнать ответ, поскольку я не знаком с инструментами сравнительного анализа.

Этот код, вероятно, не имеет смысла в этом контексте, но на самом деле это то, что мне нужно использовать.

  • Сначала заставьте его работать, затем сделайте его быстрым. Decio Lira 15.09.2009

hashperl

Ответы

Ответ 1 · рейтинг 17 · Michael Carman

Используйте функцию cmpthese из модуля Benchmark.

use strict;
use warnings;
use Benchmark qw'cmpthese';

my %sections = (
    somestring1 => 1,
    somestring2 => 1,
    somestring3 => 1,
    somestring4 => 1
);

my @elements = map { 'somestring' . int(1 + rand(10)) } 1 .. 100;

my $namespace;

cmpthese(100000, {
    hash_value => sub {
        foreach my $element (@elements) {
            $namespace = $element if $sections{$element};
        }
    },
    hash_exists => sub {
        foreach my $element (@elements) {
            $namespace = $element if exists $sections{$element};
        }
    },
    string_cmp => sub {
        foreach my $element (@elements) {
            $namespace = $element if (
                $element eq'somestring1' ||
                $element eq'somestring2' ||
                $element eq'somestring3' ||
                $element eq'somestring4');
        }
    },
});

Мои результаты (запуск Perl 5.10 на WinXP):

               Rate  string_cmp  hash_value hash_exists
string_cmp  18932/s          --        -44%        -50%
hash_value  33512/s         77%          --        -12%
hash_exists 38095/s        101%         14%          --

Таким образом, поиск по хешу на 77 % быстрее, чем каскадное сравнение строк, а проверка существования хэша вместо значения (как предложил Адам Беллер) еще на 14 % быстрее.

Ответ 2 · рейтинг 5 · Adam Bellaire

Я предполагаю, что первая версия с exists будет быстрее, не говоря уже о более читабельной и удобной в сопровождении.

for (0..10000)
{
    # $element is chosen at random
    $namespace = $element if exists $sections{$element};
}

Простая проверка существования хэш-ключа быстрее, чем получение его значения для сравнения, поэтому используйте exists.

Ответ 3 · рейтинг 4 · chaos

Механизм поиска хеша значительно быстрее.

Ответ 4 · рейтинг 3 · Ether

Возможно, сейчас самое время познакомиться с инструментами сравнительного анализа, такими как модуль CPAN Benchmark.

Ответ 5 · Ecuador

Тест Майкла Кармана хорош, но его результаты уже устарели, поэтому люди, не запускающие его на своей машине, могут получить неправильное представление. Итак, точно такой же тест (всего в 10 раз больше случаев, чтобы получить более стабильные результаты) на Mac Pro с Mac OS X и Perl 5.24.1:

               Rate  string_cmp hash_exists  hash_value
string_cmp  54142/s          --        -28%        -32%
hash_exists 74850/s         38%          --         -7%
hash_value  80192/s         48%          7%          --

Однако на AWS с CentOS 7/Perl 5.24.0 мы получаем:

string_cmp  70373/s          --        -24%        -25%
hash_value  92851/s         32%          --         -1%
hash_exists 93545/s         33%          1%          --

Итак, я бы сказал, протестируйте свою собственную машину, но существующая в настоящее время не дает преимуществ (на моем Mac с последней версией Perl она даже заметно медленнее в этом конкретном тесте - и даже в других тестах).

Что мне не нравится в тесте, так это то, что он довольно произвольно выбирает сравнение 4 равенств с проверкой хэша. Не путайтесь, если у нас есть только один элемент в хеше, поэтому мы сравниваем с единственным равенством, которое мы получаем (на моем Mac Pro/Perl 5.24.1):

hash_value  119474/s          --         -1%        -14%        -34%
hash_exists 121065/s          1%          --        -12%        -33%
grep        138122/s         16%         14%          --        -23%
string_cmp  180180/s         51%         49%         30%          --

Я добавил туда один grep, который избегает цикла foreach для сравнения. Таким образом, одно равенство, очевидно, быстрее, чем хеш-проверка, но не в два раза быстрее, поэтому, если вы можете заменить только два равенства хэш-проверкой, вы получите преимущество:

string_cmp  104167/s          --        -15%        -17%
hash_value  121951/s         17%          --         -2%
hash_exists 125000/s         20%          2%          --

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

Перевод вопроса и ответов сообщества Stack Overflow, лицензия CC BY-SA. Оригинал на Stack Overflow.

Похожие материалы