Re: [elmo-users] box_selection a sprawa polska

[rzyjontko]

W swoim poprzednim liście napisałeś:
>
> > Tutaj mamy dużą szansę zrobić to milion razy lepiej niż u konkurencji.
> 
> Jak prawie wszystko do tej pory :)  Tak czuję, że wisi jeszcze nade
> mną przyspieszenie addressbooka.

Pomyślałem sobie, że się pochwalę.  Elmo ma prawdopodobnie jedną z
najbardziej wyżyłowanych implementacji tablic hashujących.  Siedziałem
trochę przy tym i okazało się, że przy wypełnieniu = 140% średnia
długość niepustej listy = 1.6, albo coś koło tego.  To jeszcze o
niczym nie świadczy bo to mógł być przypadek.  Trzebaby przebadać dużo
większą próbkę, ale stawiam na to, że oczekiwana długość listy w
trakcie działania programu nie przekracza 2.5.

Wniosek: tablice hashujące w elmo działają w czasie stałym z *małą*
stałą, a tablice hashujące w mutt'cie działają w czasie liniowym (to z
powodu stałego rozmiaru tablicy).
Ale to co robi pine, to już jest dramat!  Zajrzałem do źródeł i
przeczytałem tam coś takiego:

 "This is a standard hash function that should be as evenly
  distributed as possible.  I haven't done much research to find a
  good one."

No to gratulacje.  Patrzymy w kod, a tam się okazuje, że pomijane są
białe znaki, litery są przekształcane na małe, a funkcja po prostu
dosumowuje wartość znaku przesuniętą o różne wartości (co ósmy znak
tak samo).

----                                ----
rzyjontko         <rzyj # plusnet () pl>
http://www.student.ii.uni.wroc.pl/~rzyj/
----                                ----