|
ru.perl
- RU.PERL ----------------------------------------------------------------------
From : Artem Chuprina 2:5020/400 01 Feb 2002 17:18:39
To : Andrey Sapozhnikov
Subject : Re: Как из списка @list удалить скаляр $num
--------------------------------------------------------------------------------
Здравствуй, Andrey Sapozhnikov.
>> k> А может тебе лучше хэш поюзать? Тогда алгоpитм будет логаpифмический.
AS> >
AS> > Какой-какой? У хэша он в норме O(1).
AS> Ошибаетесь, на размерах хэша превышающих разрядность hash-функции
AS> он близок к O(log N). А разрядность выбирают малой, для экономии памяти.
It depends....
AS> К примеру, пусть для ключа "ILoveMyBraveDog" значение hash-функции
AS> будет: 0xffee3322. Так вот врядли кто станет использовать таблицу
AS> в 4 миллиарда ячеек для такого хэша. Его обычно разбивают так:
AS> HASH_TABLE_LEVEL1[0xff]->HASH_TABLE_LEVEL2[0xee]->...
AS> и даже в этом случае таблички длиной в 256 делают списками
AS> реально существующих элементов. И время просмотра этих списочков
AS> растет.
Это не логарифм. Глубина - константа. Линейный список внутри - O(N). Hо в
перле оно, согласно Advanced Perl Programming, устроено иначе.
AS> "Чистый" хэш дает O(0), но реализации чистого хэша возможны
AS> лишь в константном варианте, когда подобрана абсолютная хэш-функция
AS> для данного набора ключей (см. например man gperf и исходники gcc).
AS> А теперь вернемся к жизни. В исходниках perl-5.6.1, файл hv.c,
AS> функция Perl_hv_fetch:
AS> ...
AS> entry = ((HE**)xhv->xhv_array)[hash & (I32) xhv->xhv_max];
AS> for (; entry; entry = HeNEXT(entry)) {
AS> if (HeHASH(entry) != hash) /* strings can't be equal
AS> */ continue; if (HeKLEN(entry) != klen)
AS> continue; if (memNE(HeKEY(entry),key,klen)) /* is this it? */
AS> continue; return &HeVAL(entry); } ...
AS> выясняем, что перлу пофиг на теорию. Он ищет перебором, O(N).
Hе от N, а от длины ячейки хэша. В исходники я не лазил, но Advanced Perl
Programming утверждает, что ширина оного хэша (xhv->xhv_max, если я правильно
понял код) растет, если длина списка в ячейке вырастает больше, чем хотелось
бы. После чего цепочки растаскиваются по другим корзинкам. Для чего,
собственно, и хранятся хэш-значения, помимо ускорения сравнения. Чтобы при
смене размера не пересчитывать. Тем самым то, от чего O(), определяется этим
"хотелось бы". Мои эксперименты показывают, что средний размер корзинки - 2-3
элемента, больше при росте хэша не лезет. Тем самым таки O(1). Правда, за счет
накладных расходов на разрастание хэша.
AS> А
AS> хэш-значения использует только для ускорения сравнения ключей. Т.е. ключи
AS> сравниваются только после того, как оказались равны хэш-значения и длины
AS> ключей. Вывод: не хотелось бы разочаровываться в Ларри, ну да поживем -
AS> увидим. Через годик-пять Перл 6 появится...
--
Artem Chuprina
Communiware.net
RFC2822: <ran@ran.pp.ru>, FIDO: 2:5020/358.49, ICQ: 13038757
Отправлено через сервер Форумы@mail.ru - http://talk.mail.ru
--- ifmail v.2.15dev5
* Origin: Talk.Mail.Ru (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
