Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Perl: Системное программирование > использования хэша для проверки уникальности строк

Автор: ochnev 29.7.2006, 01:15

Входные данные - десятки тысяч строк (URL сайтов или страниц).
Делается хэш, в него вставляются пары ключ-значение, ключи - адреса страниц или сайтов ("http://" обрезаны), значение - что угодно (пусть будет число 1).
Задача - проверять, есть ли у нас уже такой адрес или нет. Есть желание не заморачиваться собственной реализацией словаря.
Вопрос:
Насколько это корректно и эффективно? И почему?

P.S.:
Sorry, не туда написал, не заметил с первого взгляда, что не тот раздел.

Автор: nitr 29.7.2006, 03:08

exists $hash{$url};
Возвращает true, если существует указанный ключ хеша, даже если не определено его значение.

Автор: amg 4.8.2006, 14:29

Ради интереса проверил эффективность обращения к хешу. Результаты любопытны.
Хэш состоял из N элементов с ключами из примерно 16 знаков (числа). Процессор Sempron 2600+. 1 GB оперативки.

Код

#!/usr/bin/perl -w

use Time::HiRes qw( time );

my $N = $ARGV[0];
my ($key,$key1,%hash);

foreach (1..$N) {
    $key = rand;
    $key1 = $key if $_==$N/2;
    $hash{$key} = 0;
}

print 'Hash from ', scalar(keys %hash), ' elements', "\n\n";

if_exist('aaa');
if_exist($key);
if_exist('1234567890');
if_exist($key1);

sub if_exist {
    my $k = $_[0];
    my $time0 = time();
    my $exist = exists $hash{$k};
    my $time1 = time();
    print "Key $k", $exist ? ' exists' : " doesn't exist", "\n";
    print "Time ", $time1 - $time0, "\n\n";
}

Интересно (и неожиданно для меня), что время обращения к элементу уже созданного хеша (время, за которое отрабатывает функция exists $hash{$key}) пренебрежимо мало и не зависит от N (и при N=10, и при N=10000000 оно составляет менее 1e-5 с). Зато растет потребляемая под хеш память: при N = 10 млн гигабайта оперативки уже мало, прихватывается своп.