ru.perl

 
 - RU.PERL ----------------------------------------------------------------------
 From : Andrey Sapozhnikov                   2:5020/400     13 Nov 2002  16:59:12
 To : Konstantin Tokar
 Subject : Re: двоичный поиск
 -------------------------------------------------------------------------------- 
 

 Konstantin Tokar wrote:
 
 > 
 >>  AS> Пpи пpочих pавных hash быстpее.
 >> Пpавильно, потомy что в хэше элемент ищется за константное вpемя, а 
 >> бинаpным
 >> поиском - за O(log2(N)).
 > 
 > Hе знаю насчет перловых хэшей, а вообще из-за коллизий это время вообще 
 > непредсказуемо.
 
 Предсказуемо. Можно предсказать среднее время и вероятности отклонений от
 среднего. Так например для хэша из 1000 элементов вероятность попадания
 всех элементов в 100 или меньше слотов из 1000, она же вероятность получения
 load factor >= 10 (что приведет к деградации производительности ~ в 10 раз и
 условно сопоставимо с временем binary search на том же массиве) по моим
 прикидкам около 10^-894. Отмечу, что perl динамически поддерживает число
 слотов >= числа элементов в хэше. Данная цифра предполагает равновероятное
 распределение дискретной случайной величины, что, на мой взгляд, вполне
 реалистично для всех случаев кроме специального подбора ключей к хэш
 функции используемой в perl.
 
 Андрей
 
 P.S. "условно сопоставимо" в данном контексте означает что мы
 предполагали равную производительность для обоих алгоритмов на
 единичном массиве.
 --- ifmail v.2.15dev5
  * Origin: Demos online service (2:5020/400)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    Re: двоичный поиск   Konstantin Tokar   13 Nov 2002 15:53:32   Re: двоичный поиск   Andrey Sapozhnikov   13 Nov 2002 16:59:12