VPF::использования хэша для проверки уникальности строк

ochnev

Дата 29.7.2006, 01:15 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 253
Регистрация: 27.3.2006

Репутация: нет
Всего: нет

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

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

Это сообщение отредактировал(а) ochnev - 29.7.2006, 01:29

nitr

Дата 29.7.2006, 03:08 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Участник Клуба
Сообщений: 2543
Регистрация: 10.2.2006
Где: Россия :)

Репутация: 2
Всего: 84

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

--------------------

I love ArchLinux

amg

Дата 4.8.2006, 14:29 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1145
Регистрация: 3.8.2006
Где: Новосибирск

Репутация: 9
Всего: 50

Ради интереса проверил эффективность обращения к хешу. Результаты любопытны.
Хэш состоял из 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 млн гигабайта оперативки уже мало, прихватывается своп.

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Perl: Системное программирование \| Следующая тема »