🚀 go-pugleaf

wodzik <wodzik@noreply.com> napisał:

> On 2010-01-09 13:03, Stachu 'Dozzie' K. wrote:
>>> czyli rozumiem, że operacje wstawiania - wyszukiwania mają złożoność
>>> obliczeniową równą 1?
>>
>> A widziałeś kiedyś strukturę spełniającą te kryteria? Z wyjątkiem
>> tablicy indeksowanej liczbami.
>
> Oczywiście że widziałem. Nazywa się to hashmapa. Działa to tak, że  
> rezerwujemy sobie pamięć, a potem na podstawie jakiejś funkcji  
> mieszającej określamy gdzie dany element powinien znajdować się w  
> tablicy i tam go wstawiamy. Jeśli dla różnych obiektów mamy taki sam  
> adres wyszukujemy mu nowy, albo robimy listę w tym miejscu. Tyle z  
> szkoły.

"Hashmapa" to jakiś potworek językowy. Po polsku na ogół mówimy o tablicy  
mieszającej (lub haszującej), bądź ogólniej o tablicy asocjacyjnej lub  
słowniku -- ang. dictionary, w Pythonie po prostu dict. Przy czym  
pythonowa implementacja słownika należy do jednej z najlepiej wykonanych i  
zoptymalizowanych -- nie dziwne, skoro Python wewnętrznie używa tej  
struktury prawie na każdym kroku (do obsługi przestrzeni nazw, do  
argumentów nazwanych...).¹

Podobną do słowników strukturą są w Pythonie zbiory (set). Można je  
traktować jako słowniki z samymi kluczami (bez wartości) + wygodnymi  
metodami do typowych operacji na zbiorach.

> Ale link który podał Rob Wolfe chyba wyjaśnia sprawę dostatecznie. Przy  
> zastosowaniu słownika średnia złożoność pobrania elementu wynosi O(1).  
> Teraz pozostaje mi tylko napisać funkcje która w jakiś sensowny sposób  
> będzie tworzyła klucz na podstawie mojej klasy.

A według jakiego kryterium określasz "tożsamość" elementów w  
dotychczasowym rozwiązaniu opartym na listach? Bo jeżeli wg tożsamości  
(id) samego obiektu (lub równości, gdy nie jest specjalnie definiowana, co  
również oznacza test tożsamości), to prawdopodobnie nie musisz żadnej  
specjalnej funkcji pisać -- zastąp listy zbiorami i już [test ,,x in set''  
daje średnio O(1)].

Pozdr.
*j

¹ Ciekawy artykuł na ten temat można przeczytać w książce "Piękny k0d.  
Tajemnice mistrzów programowania" (tyt. oryg. "Beatiful Code: Leading  
Programmers Explain How They Think") [wyd. Helion 2008]

-- 
Jan Kaliszewski (zuo)