|
ru.perl
- RU.PERL ----------------------------------------------------------------------
From : Andrey Sapozhnikov 2:5020/400 01 Feb 2002 16:06:30
To : Artem Chuprina
Subject : Re: Как из списка @list удалить скаляр $num
--------------------------------------------------------------------------------
Artem Chuprina wrote:
> Здравствуй, kan.
>
> k> А может тебе лучше хэш поюзать? Тогда алгоpитм будет логаpифмический.
>
> Какой-какой? У хэша он в норме O(1).
Ошибаетесь, на размерах хэша превышающих разрядность hash-функции
он близок к O(log N). А разрядность выбирают малой, для экономии памяти.
К примеру, пусть для ключа "ILoveMyBraveDog" значение hash-функции
будет: 0xffee3322. Так вот врядли кто станет использовать таблицу
в 4 миллиарда ячеек для такого хэша. Его обычно разбивают так:
HASH_TABLE_LEVEL1[0xff]->HASH_TABLE_LEVEL2[0xee]->...
и даже в этом случае таблички длиной в 256 делают списками
реально существующих элементов. И время просмотра этих списочков
растет. "Чистый" хэш дает O(0), но реализации чистого хэша возможны
лишь в константном варианте, когда подобрана абсолютная хэш-функция
для данного набора ключей (см. например man gperf и исходники gcc).
А теперь вернемся к жизни. В исходниках perl-5.6.1, файл hv.c,
функция Perl_hv_fetch:
...
entry = ((HE**)xhv->xhv_array)[hash & (I32) xhv->xhv_max];
for (; entry; entry = HeNEXT(entry)) {
if (HeHASH(entry) != hash) /* strings can't be equal */
continue;
if (HeKLEN(entry) != klen)
continue;
if (memNE(HeKEY(entry),key,klen)) /* is this it? */
continue;
return &HeVAL(entry);
}
...
выясняем, что перлу пофиг на теорию. Он ищет перебором, O(N). А хэш-значения
использует только для ускорения сравнения ключей. Т.е. ключи сравниваются только
после того, как оказались равны хэш-значения и длины ключей. Вывод: не хотелось
бы разочаровываться в Ларри, ну да поживем - увидим. Через годик-пять Перл 6
появится...
Андрей
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
