|
ru.perl
- RU.PERL ----------------------------------------------------------------------
From : Andrey Sapozhnikov 2:5020/400 01 Feb 2002 20:17:26
To : Artem Chuprina
Subject : Re: Как из списка @list удалить скаляр $num
--------------------------------------------------------------------------------
Artem Chuprina wrote:
> Здравствуй, Andrey Sapozhnikov.
> AS> выясняем, что перлу пофиг на теорию. Он ищет перебором, O(N).
>
> Hе от N, а от длины ячейки хэша. В исходники я не лазил, но Advanced Perl
> Programming утверждает, что ширина оного хэша (xhv->xhv_max, если я правильно
> понял код) растет, если длина списка в ячейке вырастает больше, чем хотелось
> бы. После чего цепочки растаскиваются по другим корзинкам. Для чего,
> собственно, и хранятся хэш-значения, помимо ускорения сравнения. Чтобы при
> смене размера не пересчитывать. Тем самым то, от чего O(), определяется этим
> "хотелось бы". Мои эксперименты показывают, что средний размер корзинки - 2-3
> элемента, больше при росте хэша не лезет. Тем самым таки O(1). Правда, за счет
> накладных расходов на разрастание хэша.
Ты прав, детальнее расмотрев код, я нашел те кусочки. Размер таблицы удваивается
если число ключей превышает размер таблицы, а индексация в таблице делается
по остатку от деления хэш-значения на размер таблицы.Кстати, таблица не
ужимается
обратно при удалении элементов хэша. Функция близка к O(1), хотя статистика чуть
портится с разрастанием. Hо операции вставки периодически приводят к тяжелым
перестройкам таблицы (все же я бы реализовал через splay-tree, заодно привнеся
упорядоченность по значению ключа, ну да поздно уже). Так что будем считать
O(const)
(которое кстати, частный случай O(log) :-)) Мои извинения Ларри Уоллу, если он
вруг прочел предыдущее письмо и обиделся :-)
Андрей
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
