🚀 go-pugleaf

On Sat, 09 Jan 2010 08:10:11 +0100
wodzik <wodzik@noreply.com> wrote:

> Witam
> 
> Jakiś czas temu napisałem sobie zadanko na SI z rozwiązywania n-puzzli, 
> czyli klasyczny A*. Wsio fajnie działa i zajmuje mało miejsca (3x mniej 
> niż kod w javie). Jedyny problem, że stany do rozpatrzenia i rozpatrzone 
> trzymam w liście. Przy dużej ilości stanów przeszukanie czy mamy taki 
> obiekt na liście zajmuje sporo czasu, więc fajnie by było jak bym 
> trzymał to w jakiejś hashmapie. I w tym miejscu zaczynają się schody, bo 
> nie bardzo mogę znaleźć jak w pythonie się coś takiego implementuje.

hashmapa = {'a' : 1, 'n': 3}
print hashmapa['a']

-- 

On 2010-01-09 10:23, Michal wrote:

> hashmapa = {'a' : 1, 'n': 3}
> print hashmapa['a']

czyli rozumiem, że operacje wstawiania - wyszukiwania mają złożoność 
obliczeniową równą 1?

On 2010-01-09, wodzik <wodzik@noreply.com> wrote:
> On 2010-01-09 10:23, Michal wrote:
>
>> hashmapa = {'a' : 1, 'n': 3}
>> print hashmapa['a']
>
> 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.

-- 
Secunia non olet.
Stanislaw Klekot

wodzik <wodzik@noreply.com> writes:

> On 2010-01-09 10:23, Michal wrote:
>
>> hashmapa = {'a' : 1, 'n': 3}
>> print hashmapa['a']
>
> czyli rozumiem, że operacje wstawiania - wyszukiwania mają złożoność
> obliczeniową równą 1?

Tu masz to ładnie wyjaśnione:
http://wiki.python.org/moin/TimeComplexity

RW

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. 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.

Pozdrawiam wodzik

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)

On 2010-01-09 22:28, Jan Kaliszewski wrote:

> "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,

Tak wiem, ale już się jakoś do niego przyzwyczaiłem. Nawet część 
prowadzących używa tej nazwy ;)

> 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.

Będzie się trzeba dokształcić z zbiorów.

> 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)].

Sprawdzam czy są na liście czymś w stylu: "if (not tmp in self.dzieci) & 
(not tmp in self.rozpatrzone):", a funkcja do porównania wygląda tak:

def __cmp__(self,plansza):
     if isinstance(plansza, Plansza):
         tmp = cmp(self.h, plansza.h)
         if tmp:
             return tmp
         return cmp(self.tablica, plansza.tablica)
     else:
         return cmp(self.h, plansza)

Bo za pomocą zwykłego porównania porównuje chyba samo id obiektu, a tu 
chodziło o to, że ma sprawdzić czy h jest takie samo, a jeśli tak 
porównać jeszcze tablice. W ogóle zastanawiam się jak zrobić, żeby z 
zbioru wyciągał najpierw obiekty o jak najmniejszym h. Na liście daje 
jakieś sortowanie przy wstawianiu i problem z głowy. Przy zbiorach chyba 
by dać listę zbiorów, a w każdym elementy o innym h. Sprawdziło by się 
takie co, czy macie inne pomysły?

> Pozdr.
> *j

Pozdrawiam wodzik

On 2010-01-09, wodzik <wodzik@noreply.com> wrote:
> 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.

To ze szkoły powinieneś wiedzieć że to nie do końca daje złożoność O(1).

> 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.

-- 
Secunia non olet.
Stanislaw Klekot

On 2010-01-09 23:24, Stachu 'Dozzie' K. wrote:

> To ze szkoły powinieneś wiedzieć że to nie do końca daje złożoność O(1).

Powiedz to moim wykładowcom, albo chociaż by Thomasowi Cormenowi. 
Cytując z książki "Wprowadzenie do algorytmów":
-"Przy rozsądnych założeniach można wykazać, że oczekiwany czas 
wyszukiwania elementu z tablicy z haszowaniem wynosi O(1)."
czy:
-"średni czas działania podstawowych operacji słownikowych na tablicy z 
haszowaniem wynosi O(1)."

Oczywiście można czepiać się, że czasami w przypadku kilku elementów o 2 
takich samych kluczach będzie trzeba wykonać jakąś dodatkową operacje, 
jednak w porównaniu z złożonością liniową O(n) dla większej ilości 
elementów jest to na tyle nieistotne, że przyjmuje się, że złożoność 
jest O(1), a nie np. O(1.3)

Pozdrawiam wodzik

On Sat, 09 Jan 2010 23:15:10 +0100, wodzik <wodzik@noreply.com> wrote:

>> 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)].
>
> Sprawdzam czy są na liście czymś w stylu: "if (not tmp in self.dzieci) &  
> (not tmp in self.rozpatrzone):",

W tym kontekście prawidłowo jest użyć 'and' (operator logiczny) a nie '&'  
(operator bitowy).

> a funkcja do porównania wygląda tak:
>
> def __cmp__(self,plansza):
>      if isinstance(plansza, Plansza):
>          tmp = cmp(self.h, plansza.h)
>          if tmp:
>              return tmp
>          return cmp(self.tablica, plansza.tablica)
>      else:
>          return cmp(self.h, plansza)

* Jeżeli obiekty są niezmienne (niemutowalne, ang. immutable), a więc  
jeżeli atrybuty 'h' i 'tablica' używane do testowania równości nie  
zmieniają się (ich wartości są niezmienne i nie są zastępowane innymi), to  
po prostu zaimplementuj metodę __hash__, np. tak:

     def __hash__(self):
         return hash(self.h) ^ hash(self.tablica)
         # oczywiście (skoro są niezmienne) można tę wartość wyliczyć
         # raz, zapamiętać np. jako self._hasz i tu dać tylko:
         # return self._hasz

I teraz Twoje obiekty mogą być już spokojnie kluczami w słownikach lub  
elementami słowników.

Zastrzeżenie: obiekty traktowane jako równe powinny mieć równe hasze, więc  
przy takiej implementacji __hash__() -- powinno się usunąć z __cmp__()  
"else: return cmp(self.h, plansza)" (zastępując je np. "else: raise  
TypeError('Porównujemy tylko z instancjami klasy Plansza!')"); alternatywą  
jest oparcie __hash__ wyłącznie na hash(self.h) -- nieuwzględniając  
self.tablica co jednak nie jest najlepszym rozwiązaniem z punktu widzenia  
wydajności, ze względu na obiekty o równym 'h' a różnym 'tablica'...

Zob. http://docs.python.org/reference/datamodel.html#object.__hash__


* Jeżeli obiekty są zmienne, ale masz gwarancję, że każdy ma atrybut 'h'  
lub 'tablica' zawsze różny niż mają pozostałe -- cała implementacja  
__cmp__() i __hash__() jest niepotrzebna, bo możesz polegać na  
standardowym mechanizmie porównywania i haszowania dla klas zdefiniowanych  
przez użytkownika (jak słusznie się domyśliłeś -- opartym na id obiektu).


* Jeżeli obiekty są zmienne i nie masz powyższej gwarancji unikatowości  
'h' lub 'tablica'... No cóż, udawanie, że obiekty mutowalne są  
niemutowalne i implementowanie __hash__() na siłę, to proszenie się o  
kłopoty -- czyli o nieprzewidziane efekty przy późniejszych próbach  
używania takich obiektów jako kluczy słownikowych lub elementów zbiorów.  
Więc lepiej explicite dać w tejże klasie: __hash__ = None (od Pythona 2.6;  
w starszych wersjach: def __hash__(self): raise TypeError), by zaznaczyć,  
że obiekty te są niehaszowalne.

A na potrzeby tej jednej operacji -- tu wracamy do punktu wyjścia --  
używać słowników posługując się kluczami określonymi np. jako pary  
(plansza.h, tuple(plansza.tablica)) (a właściwymi obiektami jako  
słownikowymi wartościami). Oczywiście ma to sens, jeżeli przynajmniej na  
czas używania takiego słownika zawartość klucza odpowiada zawartości  
obiektu (a więc atrybuty 'h' i 'tablica' są chociaż czasowo  
"niemututowalne").

Albo może lepiej -- ze względów wydajnościowych (patrz też niżej...) --  
użyłbym słownika, w którym kluczami są plansza.h zaś wartościami słowniki,  
w których kluczami są tuple(plansza.tablica), a wartościami właściwe  
obiekty Plansza().

[Domyślam się, że h to liczba?]


> Bo za pomocą zwykłego porównania porównuje chyba samo id obiektu, a tu  
> chodziło o to, że ma sprawdzić czy h jest takie samo, a jeśli tak  
> porównać jeszcze tablice. W ogóle zastanawiam się jak zrobić, żeby z  
> zbioru wyciągał najpierw obiekty o jak najmniejszym h. Na liście daje  
> jakieś sortowanie przy wstawianiu i problem z głowy. Przy zbiorach chyba  
> by dać listę zbiorów, a w każdym elementy o innym h. Sprawdziło by się  
> takie co, czy macie inne pomysły?

Jeżeli przyjmiemy ten ostatni wariant -- że posługujemy się słownikiem z  
kluczami plansza.h itd. -- to ja bym chyba użył "zsynchronizowanej" z nim  
posortowanej listy tychże kluczy, obsługiwanej za pomocą funkcji z modułu  
bisect. (Przy czym tę "synchronizację" można zapewniać albo po prostu  
"ręcznie", wszędzie gdzie jest zmiana słownika zmieniając też tę listę,  
albo też tworząc własną klasę SortedDict [lub wyszukując gotowiec w  
necie]).

Pozdr.
*j

-- 
Jan Kaliszewski (zuo)

> albo też tworząc własną klasę SortedDict [lub wyszukując gotowiec w  
> necie]).

http://code.activestate.com/recipes/576998/ :)

Pozdr.
*j

On 2010-01-09, wodzik <wodzik@noreply.com> wrote:
> On 2010-01-09 23:24, Stachu 'Dozzie' K. wrote:
>
>> To ze szkoły powinieneś wiedzieć że to nie do końca daje złożoność O(1).
>
> Powiedz to moim wykładowcom, albo chociaż by Thomasowi Cormenowi. 
> Cytując z książki "Wprowadzenie do algorytmów":
> -"Przy rozsądnych założeniach można wykazać, że oczekiwany czas 
> wyszukiwania elementu z tablicy z haszowaniem wynosi O(1)."
> czy:
> -"średni czas działania podstawowych operacji słownikowych na tablicy z 
> haszowaniem wynosi O(1)."
>
> Oczywiście można czepiać się, że czasami w przypadku kilku elementów o 2 
> takich samych kluczach będzie trzeba wykonać jakąś dodatkową operacje, 

...a gdy tych elementów o jednakowych kluczach robi się bardzo dużo, to
szlag trafia gwarancje czasowe, czyli dokładnie to co mówię...

> jednak w porównaniu z złożonością liniową O(n) dla większej ilości 
> elementów jest to na tyle nieistotne, że przyjmuje się, że złożoność 
> jest O(1), a nie np. O(1.3)

O(1.3) jest w ogóle bez sensu dla kogokolwiek, kto wie co to jest
złożoność obliczeniowa, bo to jest dokładnie O(1).

A przypadek jest dość istotny, bo wpływa i na pesymistyczną, i na
zamortyzowaną złożoność obliczeniową, tylko zwyczajowo się zakłada że
nie występuje.

-- 
Secunia non olet.
Stanislaw Klekot

On 2010-01-10 13:19, Stachu 'Dozzie' K. wrote:

>> Oczywiście można czepiać się, że czasami w przypadku kilku elementów o 2
>> takich samych kluczach będzie trzeba wykonać jakąś dodatkową operacje,
>
> ...a gdy tych elementów o jednakowych kluczach robi się bardzo dużo, to
> szlag trafia gwarancje czasowe, czyli dokładnie to co mówię...

Tyle, że jeśli mamy za dużo elementów to alokujemy nową pamięć, mieszamy 
listę na nowo i dalej mamy złożoność 1. Tak powinna działać każda dobrze 
zaimplementowana hashmapa, a wydaje mi się, że ta w pythonie właśnie 
taka jest.

>> jednak w porównaniu z złożonością liniową O(n) dla większej ilości
>> elementów jest to na tyle nieistotne, że przyjmuje się, że złożoność
>> jest O(1), a nie np. O(1.3)
>
> O(1.3) jest w ogóle bez sensu dla kogokolwiek, kto wie co to jest
> złożoność obliczeniowa, bo to jest dokładnie O(1).

No właśnie pisze, że nawet jeśli wykonujemy średnio kilka operacji 
złożoność to dajek jest O(1), bo jest to jakaś stała.

> A przypadek jest dość istotny, bo wpływa i na pesymistyczną, i na
> zamortyzowaną złożoność obliczeniową, tylko zwyczajowo się zakłada że
> nie występuje.

A spotkałeś się kiedyś z przypadkiem w którym hashmapa miała złożoność 
chociaż zbliżoną do O(n)? W jakimś realnym programie, a nie w 
akademickich dyskusjach.

Pozdrawiam wodzik

On Jan 10, 1:38 pm, wodzik <wod...@noreply.com> wrote:
> On 2010-01-10 13:19, Stachu 'Dozzie' K. wrote:
>
> >> Oczywiście można czepiać się, że czasami w przypadku kilku elementów o 2
> >> takich samych kluczach będzie trzeba wykonać jakąś dodatkową operacje,
>
> > ...a gdy tych elementów o jednakowych kluczach robi się bardzo dużo, to
> > szlag trafia gwarancje czasowe, czyli dokładnie to co mówię...
To zależy jak rozwiązujesz kolizję. Jeśli zamiast listy, użyjesz
drzewa AVL, to w średnim pesymistycznym przypadku dostaniesz Ο(log
n).

>
> Tyle, że jeśli mamy za dużo elementów to alokujemy nową pamięć, mieszamy
> listę na nowo i dalej mamy złożoność 1. Tak powinna działać każda dobrze
> zaimplementowana hashmapa, a wydaje mi się, że ta w pythonie właśnie
> taka jest.
To jest oczywiście tylko przy wstawianiu. Operacja taka kosztuję Ο(n)
i dlatego koszt wstawiania jest pesymistycznie Ο(n), ale średni
*zamortyzowany* koszt jest Ο(1). Przehashowanie wszystkie oczywiście
rozluźnia trochę kolizje, ale nie ma to wpływu na oszacowanie kosztu
pojedyńczego wyszukiwania.

>
> >> jednak w porównaniu z złożonością liniową O(n) dla większej ilości
> >> elementów jest to na tyle nieistotne, że przyjmuje się, że złożoność
> >> jest O(1), a nie np. O(1.3)
>
> > O(1.3) jest w ogóle bez sensu dla kogokolwiek, kto wie co to jest
> > złożoność obliczeniowa, bo to jest dokładnie O(1).
Ο(1) = Ο(1.3) = O(100), ale wszystkie trzy napisy mają sens.

>
> No właśnie pisze, że nawet jeśli wykonujemy średnio kilka operacji
> złożoność to dajek jest O(1), bo jest to jakaś stała.
Średni koszt wykonania operacji, to nie średnia kosztów wykonania
kilku operacji, tylko średnia z kosztów dla wszystkich możliwych
danych wejściowych. Dlatego w Cormenie jest napisane, że *przy
sensownych założeniach* (czyli np. przy utrzymywaniu sensownego
zapełnienia) średni czas wyszukiwania jest Ο(1).

> > A przypadek jest dość istotny, bo wpływa i na pesymistyczną, i na
> > zamortyzowaną złożoność obliczeniową, tylko zwyczajowo się zakłada że
> > nie występuje.
Wpływa na pesymistyczną, bo to jest ten pesymistyczny przypadek. Na
koszt wstawiania elementów, przy implementacji z listą, nie ma wpływu.
O zamortyzowanym koszcie wyszukiwania, to raczej nie ma co mówić, bo
wyszukiwanie nic nie zmienia z strukturze.

>
> A spotkałeś się kiedyś z przypadkiem w którym hashmapa miała złożoność
> chociaż zbliżoną do O(n)? W jakimś realnym programie, a nie w
> akademickich dyskusjach.
Tak, jak ktoś źle dobrał funkcję hashującą dla swoich elementów. Wtedy
bardzo szybko ilość kolizji staję się rzędu n.


> Pozdrawiam wodzik

Ogólnie wygląda to tak, że tablica się nie zmienia, a h jest wyliczane w 
zależności od stany planszy (czyli tablicy) i liczby ruchów. W związku z 
tym chyba zastosuje krotki, bo hash(self.tablica) nie przejdzie. Ogólnie 
i h i tablica są przypisywane już w funkcji __init__, a potem już się 
nie zmieniają. W sumie przydała by mi się teraz jakaś multimapa. Mógł 
bym dla jednej wartości h trzymac wiele różnych stanów gry i dość prosto 
na tym operować. Bo h będzie gdzieś w zakresie 1-kilkadziesiąt, a plansz 
(stanów gry) będzie już kilka(naście/dziesiąt w zależności od rozmiaru) 
tysięcy, a żeby rozwiązanie było optymalne, trzeba wybierać z stanów do 
rozpatrzenia stan o najmniejszym możliwym h.

Co do mojej funkcji __cmp__. Fragment "else: return cmp(self.h, 
plansza)" dałem, bo w każdym stanie gry zapisuje adres jego rodzica, 
żeby móc wygodnie znaleźć ścieżkę od rozwiązania do stanu początkowego. 
Działa to tak, że w stanie początkowym rodzic jest równy None i 
wyświetlam rekurencyjnie od rozwiązania do czasu, aż rodzic jest różny 
od None. Bez takiego czegoś nie chciało to zadziałać. Zawsze mógł bym 
zrobić obsługę błędów w tej funkcji, ale tak wydawało mi się jakoś prościej.

W ogóle to chyba zajmę się tym jutro, bo właśnie skończyłem pisać 
bdrzewo i chwilowo mam dość kodowania i myślenia ;)

Pozdrawiam wodzik

Chwila myślenia nad multimapa i wymyśliłem, że mogę zrobić coś takiego:

a = { 1:set(), 2:set(), .... }

gdzie liczba będzie moim h. Przy każdym stanie który chcę umieścić daje kod:
if h in a:
     a[h].add(obiekt)
else:
     a[h] = set()
     a[h].add(obiekt)

i mam zbiór zbiorów posortowanych wg h automatycznie. W dodatku nie 
muszę się martwić o powtarzające się obiekty, bo jeśli chce dodać obiekt 
który już jest nic się nie dzieje. Ogólnie wydaje mi się, że takie coś 
będzie bardzo prosto działać.

Pozdrawiam wodzik

On Jan 11, 1:40 am, wodzik <wod...@noreply.com> wrote:
> Chwila myślenia nad multimapa i wymyśliłem, że mogę zrobić coś takiego:
>
> a = { 1:set(), 2:set(), .... }
>
> gdzie liczba będzie moim h. Przy każdym stanie który chcę umieścić daje kod:
> if h in a:
>      a[h].add(obiekt)
> else:
>      a[h] = set()
>      a[h].add(obiekt)
>
> i mam zbiór zbiorów posortowanych wg h automatycznie. W dodatku nie
> muszę się martwić o powtarzające się obiekty, bo jeśli chce dodać obiekt
> który już jest nic się nie dzieje. Ogólnie wydaje mi się, że takie coś
> będzie bardzo prosto działać.
>
> Pozdrawiam wodzik

Skąd niby bierze ci się to posortowanie ? Nie wiesz pod, którym w
słowniku a jest pierwszy niepusty zbiór. Musiałbyś je przechodzić po
kolei i patrzeć czy są niepuste. Do takich rzeczy należy używać kopcy:
http://pypi.python.org/pypi/HeapDict

On 2010-01-11 03:28, Łukasz Rekucki wrote:

> Skąd niby bierze ci się to posortowanie ? Nie wiesz pod, którym w
> słowniku a jest pierwszy niepusty zbiór. Musiałbyś je przechodzić po
> kolei i patrzeć czy są niepuste. Do takich rzeczy należy używać kopcy:
> http://pypi.python.org/pypi/HeapDict

Hmm... Wczoraj dodałem kilka pozycji do takiego czegoś i wydawało mi 
się, że były po kolei, ale zmęczony już byłem. W każdym razie 
dokształcam się dalej z wszelkich możliwych struktur w pythonie ;)

Pozdrawiam wodzik

Całkiem fajny ten kopiec, tylko nie da się odnieść do pierwszej 
wartości bez kombinowania. Przy dodawaniu kod będzie taki sam, ale już 
przy usuwaniu będziemy mieli:

tmp = a.keys()[0]
a[tmp].pop()
if not a[tmp]:
     a.pop(tmp)

Kod co prawda banalny, ale po pythonie spodziewał bym się metody w stylu 
first(), czy jakoś tak. W każdym razie dzięki wszystkim za naprowadzenie.

Pozdrawiam wodzik

Ok program działa, wzrost wydajności to kilkaset procent, tyle że 
zastanawia mnie jedna rzecz. Mimo, że w klasie Plansza mam 
zaimplementowaną metodę __hash__(), przy dodawaniu do zbioru, dalej 
używa id obiektu, żeby sprawdzić czy już tam jest:

 >>> a= Plansza(3, (0, 4, 3, 6, 2, 5, 8, 1, 7))
 >>> b = Plansza(3,(0, 4, 3, 6, 2, 5, 8, 1, 7))
 >>> c = Plansza(3,(0, 4, 3, 6, 2, 5, 8, 1, 7))
 >>> d = set()
 >>> d.add(a)
 >>> d.add(b)
 >>> a
<npuzzle_heap.Plansza object at 0x01693E50>
 >>> b
<npuzzle_heap.Plansza object at 0x01685730>
 >>> c
<npuzzle_heap.Plansza object at 0x01685AB0>
 >>> a in d
True
 >>> b in d
True
 >>> c in d
False
 >>> c.tablica
(0, 4, 3, 6, 2, 5, 8, 1, 7)
 >>> b.tablica
(0, 4, 3, 6, 2, 5, 8, 1, 7)
 >>> hash(c)
-1951000095
 >>> hash(b)
-1951000095

czyli metoda hash działa, ale zbiór jej nie używa. Żeby nie było, że coś 
źle zaimplementowałem:

def __hash__(self):
     return hash(self.tablica)

Ktoś wie o co z tym biega?

Chyba działa to na takiej zasadzie, że hash ustala miejsce gdzie ma być 
wstawione, a cmp sprawdza, czy to co już jest wstawione nie jest takie 
samo, jak to co chcemy wstawić i dlatego musimy mieć oba... Coś nie mogę 
się dokopać do tego w dokumentacji.

On Jan 11, 8:15 pm, wodzik <wod...@noreply.com> wrote:
> Chyba działa to na takiej zasadzie, że hash ustala miejsce gdzie ma być
> wstawione, a cmp sprawdza, czy to co już jest wstawione nie jest takie
> samo, jak to co chcemy wstawić i dlatego musimy mieć oba... Coś nie mogę
> się dokopać do tego w dokumentacji.

http://docs.python.org/reference/datamodel.html#object.__hash__
http://docs.python.org/3.1/reference/datamodel.html#object.__hash__

"""If a class does not define a __cmp__() or __eq__() method it should
not define a __hash__() operation either;"""

(przy okazji, __cmp__ jest wycofywane i nie będzie dostępne w py3k,
lepiej użyć __eq__)

wodzik wrote:
> On 2010-01-09 23:24, Stachu 'Dozzie' K. wrote:
> 
>> To ze szkoły powinieneś wiedzieć że to nie do końca daje złożoność O(1).
> 
> Powiedz to moim wykładowcom, albo chociaż by Thomasowi Cormenowi. 
> Cytując z książki "Wprowadzenie do algorytmów":
> -"Przy rozsądnych założeniach można wykazać, że oczekiwany czas 
> wyszukiwania elementu z tablicy z haszowaniem wynosi O(1)."
> czy:
> -"średni czas działania podstawowych operacji słownikowych na tablicy z 
> haszowaniem wynosi O(1)."

Co jest w ogólności kłamstwem. Choć w realnych sytuacjach jest OK (choć 
w realnych sytuacjach można by formalnie poprawnie napisać że dostęp do 
dowolnego elementu do realnej listy to O(1) tylko stała czasowa duża :) 
  (Pamięć komputerów jest ograniczona przez stałą, przeszukanie jest 
jest więc formalnie O(1) -- oczywiście mało to przydatne do 
czegokolwiek, ale formalnie jest OK. :) )

Wszystkie te O(1) działają tylko i wyłącznie dzięki temu, że pamięć jest 
skończona, więc długość reprezentacji dowolnego indeksu / hasha itp jest 
twardo ograniczona z góry niewielką stałą (w dzisiejszych czasach stałą 
to jest 64).


Bo tan ka prawdę to zarówno odwołanie do tablicy hashującej czy nawet do 
dowlonej pozycji w zwykłej tablicy to ma koszt nie O(1) tylko O(log n). 
Bo nie ma cudów i zapis dowolnego indeksu do struktury długości n musi 
mieć zająć log n. A że sięgnięcie pod dany indeks w większości 
przypadków wymaga "obejrzenia" całości jego zapisu to jest ograniczone z 
dołu przez O(log n).

W dzisiejszych komputerach korzystamy z tego, że podstawa tego log jest 
duża (2**32 lub 2**64) i dlatego w praktyce zwija się to do O(1).


> Oczywiście można czepiać się, że czasami w przypadku kilku elementów o 2 
> takich samych kluczach będzie trzeba wykonać jakąś dodatkową operacje, 
> jednak w porównaniu z złożonością liniową O(n) dla większej ilości 
> elementów jest to na tyle nieistotne, że przyjmuje się, że złożoność 
> jest O(1), a nie np. O(1.3)

Jak już inni napisali, O(1) == O(1.3) == O(103453123)

Nawet i przy rozsądnych założeniach można mieć pecha i dostać O(n).

To O(1) o jakim pisze Cormen to koszt zamortyzowany


pzdr
\SK
-- 
"Never underestimate the power of human stupidity" -- L. Lang
-- 
http://www.tajga.org -- (some photos from my travels)

> Co jest w ogólności kłamstwem. Choć w realnych sytuacjach jest OK (choć
> w realnych sytuacjach można by formalnie poprawnie napisać że dostęp do
> dowolnego elementu do realnej listy to O(1) tylko stała czasowa duża :)
>   (Pamięć komputerów jest ograniczona przez stałą, przeszukanie jest
> jest więc formalnie O(1) -- oczywiście mało to przydatne do
> czegokolwiek, ale formalnie jest OK. :) )
Nie, nie można by, bo zależy on od ilości elementów w tej liście. I
nie jest to formalnie ok, bo poprostu liczysz zupełnie coś innego.

>
> Wszystkie te O(1) działają tylko i wyłącznie dzięki temu, że pamięć jest
> skończona, więc długość reprezentacji dowolnego indeksu / hasha itp jest
> twardo ograniczona z góry niewielką stałą (w dzisiejszych czasach stałą
> to jest 64).
Prawię, 2**64, to tylko 1TB - w linux'ie spokojnie możesz mieć 4TB
pamięci wirtualnej.

> Bo tak na prawdę to zarówno odwołanie do tablicy hashującej czy nawet do
> dowlonej pozycji w zwykłej tablicy to ma koszt nie O(1) tylko O(log n).
> Bo nie ma cudów i zapis dowolnego indeksu do struktury długości n musi
> mieć zająć log n. A że sięgnięcie pod dany indeks w większości
> przypadków wymaga "obejrzenia" całości jego zapisu to jest ograniczone z
> dołu przez O(log n).

Niby masz rację, ale po drodze zmieniasz model obliczeń. Długość
liczby na takim przyziemnym komputerze jak mój jest stała, a procesor
wykonuję na niej operację w jednym albo kilku taktach - niezależnie od
jej wartości. Długość struktury zupełnie go jakoś nie obchodzi.

> W dzisiejszych komputerach korzystamy z tego, że podstawa tego log jest
> duża (2**32 lub 2**64) i dlatego w praktyce zwija się to do O(1).
NIE, NIE, NIE - Dla dowolnego C i dowolnej funkcji stałej g, Istnieje
n, t. że log_C(n) > g(n), więc nigdy log_C(n) nie będzie O(1). Nigdy.
To są dwie różne klasy funkcji.

Powodem nie jest jakieś *magiczne* oszacowanie, czy zwijanie się,
tylko model obliczeń. Poprostu mnie nie interesuję ile kosztują
operację na liczbach!

Mam:
 1) pamięć RAM o stałym czasie dostępu
 2) Maszynę, która umie wykonywać arytmetykę na liczbach w czasie
stałym.
 I pytam się jaka jest zależność ilości takich operacji od ilości
danych?

To nie jest model uniwersalny, ale się tutaj sprawdza.

> > Oczywiście można czepiać się, że czasami w przypadku kilku elementów o 2
> > takich samych kluczach będzie trzeba wykonać jakąś dodatkową operacje,
> > jednak w porównaniu z złożonością liniową O(n) dla większej ilości
> > elementów jest to na tyle nieistotne, że przyjmuje się, że złożoność
> > jest O(1), a nie np. O(1.3)
>
> Jak już inni napisali, O(1) == O(1.3) == O(103453123)
>
> Nawet i przy rozsądnych założeniach można mieć pecha i dostać O(n).
>
> To O(1) o jakim pisze Cormen to koszt zamortyzowany

Nie. Co ma wyszukanie do amortyzacji! Wikipedia to może nie jest
najlepsze źródło, ale tu akurat jest ok:

http://en.wikipedia.org/wiki/Best,_worst_and_average_case

Sensowne założenia ~ średni przypadek.

>
> pzdr
> \SK
> --
> "Never underestimate the power of human stupidity" -- L. Lang
> --http://www.tajga.org-- (some photos from my travels)

Łukasz Rekucki wrote:
>> Co jest w ogólności kłamstwem. Choć w realnych sytuacjach jest OK (choć
>> w realnych sytuacjach można by formalnie poprawnie napisać że dostęp do
>> dowolnego elementu do realnej listy to O(1) tylko stała czasowa duża :)
>>   (Pamięć komputerów jest ograniczona przez stałą, przeszukanie jest
>> jest więc formalnie O(1) -- oczywiście mało to przydatne do
>> czegokolwiek, ale formalnie jest OK. :) )
> Nie, nie można by, bo zależy on od ilości elementów w tej liście.

I co z tego? Jest zawsze ograniczony z góry przez stałą. Przeczytaj 
sobie definicję zapisu O(x).

> I
> nie jest to formalnie ok, bo poprostu liczysz zupełnie coś innego.

Jest formalnie ok. Mało przydatne, ale OK.

> 
>> Wszystkie te O(1) działają tylko i wyłącznie dzięki temu, że pamięć jest
>> skończona, więc długość reprezentacji dowolnego indeksu / hasha itp jest
>> twardo ograniczona z góry niewielką stałą (w dzisiejszych czasach stałą
>> to jest 64).
> Prawię, 2**64, to tylko 1TB 

Ależ skąd. To 16EB -- Pomylileś się "jedynie" 2**24 krotnie.

>- w linux'ie spokojnie możesz mieć 4TB
> pamięci wirtualnej.

Nie szkodzi. To i tak 2**22 razy mniej niż limit.


>> Bo tak na prawdę to zarówno odwołanie do tablicy hashującej czy nawet do
>> dowlonej pozycji w zwykłej tablicy to ma koszt nie O(1) tylko O(log n).
>> Bo nie ma cudów i zapis dowolnego indeksu do struktury długości n musi
>> mieć zająć log n. A że sięgnięcie pod dany indeks w większości
>> przypadków wymaga "obejrzenia" całości jego zapisu to jest ograniczone z
>> dołu przez O(log n).
> 
> Niby masz rację, ale po drodze zmieniasz model obliczeń. Długość
> liczby na takim przyziemnym komputerze jak mój jest stała, a procesor
> wykonuję na niej operację w jednym albo kilku taktach - niezależnie od
> jej wartości. Długość struktury zupełnie go jakoś nie obchodzi.

Oczywiście, że go obchodzi. Dłuższa się nie zmieści. To dosyć kluczowe 
ograniczenie.

> 
>> W dzisiejszych komputerach korzystamy z tego, że podstawa tego log jest
>> duża (2**32 lub 2**64) i dlatego w praktyce zwija się to do O(1).
> NIE, NIE, NIE - Dla dowolnego C i dowolnej funkcji stałej g, Istnieje
> n, t. że log_C(n) > g(n), więc nigdy log_C(n) nie będzie O(1). Nigdy.
> To są dwie różne klasy funkcji.
> 
> Powodem nie jest jakieś *magiczne* oszacowanie, czy zwijanie się,
> tylko model obliczeń. Poprostu mnie nie interesuję ile kosztują
> operację na liczbach!
> 
> Mam:
>  1) pamięć RAM o stałym czasie dostępu
>  2) Maszynę, która umie wykonywać arytmetykę na liczbach w czasie
> stałym.
>  I pytam się jaka jest zależność ilości takich operacji od ilości
> danych?
> 
> To nie jest model uniwersalny, ale się tutaj sprawdza.

To się robi trochę inaczej. Przyjmuje się nie jakąś jednostkę czasu, 
tylko liczbę operacji określonych typów -- wtedy się zgadza i nie zależy 
od wielkości pamięci.


>>> Oczywiście można czepiać się, że czasami w przypadku kilku elementów o 2
>>> takich samych kluczach będzie trzeba wykonać jakąś dodatkową operacje,
>>> jednak w porównaniu z złożonością liniową O(n) dla większej ilości
>>> elementów jest to na tyle nieistotne, że przyjmuje się, że złożoność
>>> jest O(1), a nie np. O(1.3)
>> Jak już inni napisali, O(1) == O(1.3) == O(103453123)
>>
>> Nawet i przy rozsądnych założeniach można mieć pecha i dostać O(n).
>>
>> To O(1) o jakim pisze Cormen to koszt zamortyzowany
> 
> Nie. Co ma wyszukanie do amortyzacji!

To, że łączny koszt wyszukań wszystkich elementów jest ograniczony z 
góry liniowo.

> Wikipedia to może nie jest
> najlepsze źródło, ale tu akurat jest ok:
>

Nie musisz mnie tego uczyć. Zamortyzowany znaczy średni po wszystkich 
wyszukiwaniach.

> Sensowne założenia ~ średni przypadek.

Ale stwierdzenie stały koszt zamortyzowany jest lepsze niż średni koszt 
stały, bo nie bardzo wiadomo co to czas średni -- średnia po czym liczona?

pzdr
\SK

-- 
"Never underestimate the power of human stupidity" -- L. Lang
-- 
http://www.tajga.org -- (some photos from my travels)

On Jan 15, 12:48 pm, Sebastian Kaliszewski
<s.bez_sp...@remove.this.informa.and.that.pl> wrote:
> ukasz Rekucki wrote:
> >> Co jest w og lno ci k amstwem. Cho w realnych sytuacjach jest OK (cho
> >> w realnych sytuacjach mo na by formalnie poprawnie napisa e dost p do
> >> dowolnego elementu do realnej listy to O(1) tylko sta a czasowa du a :)
> >>   (Pami komputer w jest ograniczona przez sta , przeszukanie jest
> >> jest wi c formalnie O(1) -- oczywi cie ma o to przydatne do
> >> czegokolwiek, ale formalnie jest OK. :) )
> > Nie, nie mo na by, bo zale y on od ilo ci element w w tej li cie.
>
> I co z tego? Jest zawsze ograniczony z g ry przez sta . Przeczytaj
> sobie definicj zapisu O(x).
Nie jest ograniczony przez stałą, bo model obliczeń o którym
rozmawiamy, nie ma takich ograniczeń jak pamięć! Definicja klas o(x), O
(x) i theta(x) to już w ogóle nie widzą co to jest "pamięć". Jaki jest
sens notacji granicznej do nieskończoności, jeśli ograniczasz z góry
argumenty ?! żaden.

> > I
> > nie jest to formalnie ok, bo poprostu liczysz zupe nie co innego.
>
> Jest formalnie ok. Ma o przydatne, ale OK.
Nie w  tym modelu obliczeń. W innym może tak, ale nie w tym.

> >> Wszystkie te O(1) dzia aj tylko i wy cznie dzi ki temu, e pami jest
> >> sko czona, wi c d ugo reprezentacji dowolnego indeksu / hasha itp jest
> >> twardo ograniczona z g ry niewielk sta (w dzisiejszych czasach sta
> >> to jest 64).
> > Prawi , 2**64, to tylko 1TB
>
> Ale sk d. To 16EB -- Pomylile si "jedynie" 2**24 krotnie.
Ok, pomyliłem się.

>
> >- w linux'ie spokojnie mo esz mie 4TB
> > pami ci wirtualnej.
>
> Nie szkodzi. To i tak 2**22 razy mniej ni limit.
Niż 2**64 taj, ale do tego nie trzeba mieć architektury 64-bitowej.
Jeśli masz tylko 32-bitowe adresy, to każdy proces jest ograniczony do
4GB, ale cały może alokować więcej. Technika jest prosta - należy
używać tablic wielopoziomowych.

> >> Bo tak na prawd to zar wno odwo anie do tablicy hashuj cej czy nawet do
> >> dowlonej pozycji w zwyk ej tablicy to ma koszt nie O(1) tylko O(log n).
> >> Bo nie ma cud w i zapis dowolnego indeksu do struktury d ugo ci n musi
> >> mie zaj log n. A e si gni cie pod dany indeks w wi kszo ci
> >> przypadk w wymaga "obejrzenia" ca o ci jego zapisu to jest ograniczone z
> >> do u przez O(log n).
>
> > Niby masz racj , ale po drodze zmieniasz model oblicze . D ugo
> > liczby na takim przyziemnym komputerze jak m j jest sta a, a procesor
> > wykonuj na niej operacj w jednym albo kilku taktach - niezale nie od
> > jej warto ci. D ugo struktury zupe nie go jako nie obchodzi.
>
> Oczywi cie, e go obchodzi. D u sza si nie zmie ci. To dosy kluczowe
> ograniczenie.
Twój komputer ma widać dużo zmartwień. Co nie zmienia faktu, że 1 +1
działa tak samo szybko jak 10000 + 10000.

> >> W dzisiejszych komputerach korzystamy z tego, e podstawa tego log jest
> >> du a (2**32 lub 2**64) i dlatego w praktyce zwija si to do O(1).
> > NIE, NIE, NIE - Dla dowolnego C i dowolnej funkcji sta ej g, Istnieje
> > n, t. e log_C(n) > g(n), wi c nigdy log_C(n) nie b dzie O(1). Nigdy.
> > To s dwie r ne klasy funkcji.
>
> > Powodem nie jest jakie *magiczne* oszacowanie, czy zwijanie si ,
> > tylko model oblicze . Poprostu mnie nie interesuj ile kosztuj
> > operacj na liczbach!
>
> > Mam:
> >  1) pami RAM o sta ym czasie dost pu
> >  2) Maszyn , kt ra umie wykonywa arytmetyk na liczbach w czasie
> > sta ym.
> >  I pytam si jaka jest zale no ilo ci takich operacji od ilo ci
> > danych?
>
> > To nie jest model uniwersalny, ale si tutaj sprawdza.
>
> To si robi troch inaczej. Przyjmuje si nie jak jednostk czasu,
> tylko liczb operacji okre lonych typ w -- wtedy si zgadza i nie zale y
> od wielko ci pami ci.
Inaczej, czyli tak jak napisałem. Interesuje mnie ilość dostępów do
pamięci i operacji arytmetyki.

> >>> Oczywi cie mo na czepia si , e czasami w przypadku kilku element w o 2
> >>> takich samych kluczach b dzie trzeba wykona jak dodatkow operacje,
> >>> jednak w por wnaniu z z o ono ci liniow O(n) dla wi kszej ilo ci
> >>> element w jest to na tyle nieistotne, e przyjmuje si , e z o ono
> >>> jest O(1), a nie np. O(1.3)
> >> Jak ju inni napisali, O(1) == O(1.3) == O(103453123)
>
> >> Nawet i przy rozs dnych za o eniach mo na mie pecha i dosta O(n).
>
> >> To O(1) o jakim pisze Cormen to koszt zamortyzowany
>
> > Nie. Co ma wyszukanie do amortyzacji!
>
> To, e czny koszt wyszuka wszystkich element w jest ograniczony z
> g ry liniowo.
I co ma to wspólnego z amortyzacją ? Koszt znalezienia pojedyńczego
elementu, też się szacuję z góry przez ilość elementów. I co nagle do
tego mają wszystkie elementy?

> > Wikipedia to mo e nie jest
> > najlepsze r d o, ale tu akurat jest ok:
>
> Nie musisz mnie tego uczy . Zamortyzowany znaczy redni po wszystkich
> wyszukiwaniach.(
Nie. Zamortyzowany znaczy średni w ciągu N operacji np. N razy znajdź
liczbę 8. Jeśli 8 było na końcu listy kollzji długości n/2, to
jednostkowy koszt będzie O(n) i zamortyzowany też będzie O(n). Jeśli
bardzo się upierasz przy znajdowaniu wszystkich, to wystarczy wziąć
tablicę z K elementami, gdzie wszystkie są w kolizji. Wyszukanie ich
wszystkich zajmię ci ~ K^2.

> > Sensowne za o enia ~ redni przypadek.
>
> Ale stwierdzenie sta y koszt zamortyzowany jest lepsze ni redni koszt
> sta y, bo nie bardzo wiadomo co to czas redni -- rednia po czym liczona?
średni koszt = koszt w średnim przypadku. Bardziej po polsku pewnie by
było "typowym" przypadku, ale tak już jakoś jest. To co jest typowym
przypadkiem oczywiście jest bardzo względne. Dlatego w Cormenie jest
"sensowne założenia"!

>
> pzdr
> \SK
>
> --
> "Never underestimate the power of human stupidity" -- L. Lang
> --http://www.tajga.org-- (some photos from my travels)

Uważam, że dalsza dyskusja z tobą nie ma sensu, bo mylisz pojęcia
matematyczne i ich zastosowanie do analizy asymptotycznej złożoności
algorytmów z jakimiś swoimi wyobrażeniami.

On Jan 18, 12:21 pm, Sebastian Kaliszewski
<s.bez_sp...@remove.this.informa.and.that.pl> wrote:
> Psujesz polskie literki.
>
> Łukasz Rekucki wrote:
> > On Jan 15, 12:48 pm, Sebastian Kaliszewski
> > <s.bez_sp...@remove.this.informa.and.that.pl> wrote:
> >> ukasz Rekucki wrote:
> >>>> Co jest w og lno ci k amstwem. Cho w realnych sytuacjach jest OK (cho
> >>>> w realnych sytuacjach mo na by formalnie poprawnie napisa e dost p do
> >>>> dowolnego elementu do realnej listy to O(1) tylko sta a czasowa du a :)
> >>>>   (Pami komputer w jest ograniczona przez sta , przeszukanie jest
> >>>> jest wi c formalnie O(1) -- oczywi cie ma o to przydatne do
> >>>> czegokolwiek, ale formalnie jest OK. :) )
> >>> Nie, nie mo na by, bo zale y on od ilo ci element w w tej li cie.
> >> I co z tego? Jest zawsze ograniczony z g ry przez sta . Przeczytaj
> >> sobie definicj zapisu O(x).
> > Nie jest ograniczony przez stałą,
>
> Oczywiście że jest. Ba, komputer stojący na twoim biurku można spokojnie
> przedstawić jako automat skończony (trochę duży, ale skończony).
>
> > bo model obliczeń o którym
> > rozmawiamy, nie ma takich ograniczeń jak pamięć!
>
> Oczywiście że ma.
>
> > Definicja klas o(x), O
> > (x) i theta(x) to już w ogóle nie widzą co to jest "pamięć"
>
> Oczywiście że wiedzą. Liczba symboli nie blank na taśmie maszyny Turinga
> to jest pamięć.
>
> >. Jaki jest
> > sens notacji granicznej do nieskończoności, jeśli ograniczasz z góry
> > argumenty ?! żaden.
>
> Dlatego nie należy ich ograniczać. Ale wtedy indeks tablicy też nie jest
> ograniczony. Jeśli ograniczyłeś długość indeksów do stałej to
> ograniczyłeś również do stałej wielkość tablicy.
>
> >>> I
> >>> nie jest to formalnie ok, bo poprostu liczysz zupe nie co innego.
> >> Jest formalnie ok. Ma o przydatne, ale OK.
> > Nie w  tym modelu obliczeń. W innym może tak, ale nie w tym.
>
> W tym, w tym.
>
> >>>> Wszystkie te O(1) dzia aj tylko i wy cznie dzi ki temu, e pami jest
> >>>> sko czona, wi c d ugo reprezentacji dowolnego indeksu / hasha itp jest
> >>>> twardo ograniczona z g ry niewielk sta (w dzisiejszych czasach sta
> >>>> to jest 64).
> >>> Prawi , 2**64, to tylko 1TB
> >> Ale sk d. To 16EB -- Pomylile si "jedynie" 2**24 krotnie.
> > Ok, pomyliłem się.
>
> >>> - w linux'ie spokojnie mo esz mie 4TB
> >>> pami ci wirtualnej.
> >> Nie szkodzi. To i tak 2**22 razy mniej ni limit.
> > Niż 2**64 taj, ale do tego nie trzeba mieć architektury 64-bitowej.
> > Jeśli masz tylko 32-bitowe adresy, to każdy proces jest ograniczony do
> > 4GB, ale cały może alokować więcej. Technika jest prosta - należy
> > używać tablic wielopoziomowych.
>
> Czyli wydłużyć indeksy. Jak używasz "tablicy wielopoziomowej" to dla
> nieograniczonej pamięci trzeba w sposób nieograniczony zwiększyć liczbę
> poziomów -- i z tablicy mamy drzewo :)
>
> >>>> Bo tak na prawd to zar wno odwo anie do tablicy hashuj cej czy nawet do
> >>>> dowlonej pozycji w zwyk ej tablicy to ma koszt nie O(1) tylko O(log n).
> >>>> Bo nie ma cud w i zapis dowolnego indeksu do struktury d ugo ci n musi
> >>>> mie zaj log n. A e si gni cie pod dany indeks w wi kszo ci
> >>>> przypadk w wymaga "obejrzenia" ca o ci jego zapisu to jest ograniczone z
> >>>> do u przez O(log n).
> >>> Niby masz racj , ale po drodze zmieniasz model oblicze . D ugo
> >>> liczby na takim przyziemnym komputerze jak m j jest sta a, a procesor
> >>> wykonuj na niej operacj w jednym albo kilku taktach - niezale nie od
> >>> jej warto ci. D ugo struktury zupe nie go jako nie obchodzi.
> >> Oczywi cie, e go obchodzi. D u sza si nie zmie ci. To dosy kluczowe
> >> ograniczenie.
> > Twój komputer ma widać dużo zmartwień. Co nie zmienia faktu, że 1 +1
> > działa tak samo szybko jak 10000 + 10000.
>
> ale nie tak samo szybko jak
> 12391823712345189374918743198374+1290348571028761782645245412454.
>
> BTW rozszerzenie 32bity -> 64bit nie jest za darmo, procesor 32bit
> wykonany w dokładnie tym samym procesie będzie kilka procent szybszy.
>
>
>
>
>
> >>>> W dzisiejszych komputerach korzystamy z tego, e podstawa tego log jest
> >>>> du a (2**32 lub 2**64) i dlatego w praktyce zwija si to do O(1).
> >>> NIE, NIE, NIE - Dla dowolnego C i dowolnej funkcji sta ej g, Istnieje
> >>> n, t. e log_C(n) > g(n), wi c nigdy log_C(n) nie b dzie O(1). Nigdy.
> >>> To s dwie r ne klasy funkcji.
> >>> Powodem nie jest jakie *magiczne* oszacowanie, czy zwijanie si ,
> >>> tylko model oblicze . Poprostu mnie nie interesuj ile kosztuj
> >>> operacj na liczbach!
> >>> Mam:
> >>>  1) pami RAM o sta ym czasie dost pu
> >>>  2) Maszyn , kt ra umie wykonywa arytmetyk na liczbach w czasie
> >>> sta ym.
> >>>  I pytam si jaka jest zale no ilo ci takich operacji od ilo ci
> >>> danych?
> >>> To nie jest model uniwersalny, ale si tutaj sprawdza.
> >> To si robi troch inaczej. Przyjmuje si nie jak jednostk czasu,
> >> tylko liczb operacji okre lonych typ w -- wtedy si zgadza i nie zale y
> >> od wielko ci pami ci.
> > Inaczej, czyli tak jak napisałem. Interesuje mnie ilość dostępów do
> > pamięci i operacji arytmetyki.
>
> Nie. Ilość dostępów do pamięci rośnie (logarytmicznie) wraz wielkością
> adresowanej pamięci.
>
> Przyjmuje się liczbę odwołań (być może złożonych) pod podany adres
>
>
>
>
>
>
>
> >>>>> Oczywi cie mo na czepia si , e czasami w przypadku kilku element w o 2
> >>>>> takich samych kluczach b dzie trzeba wykona jak dodatkow operacje,
> >>>>> jednak w por wnaniu z z o ono ci liniow O(n) dla wi kszej ilo ci
> >>>>> element w jest to na tyle nieistotne, e przyjmuje si , e z o ono
> >>>>> jest O(1), a nie np. O(1.3)
> >>>> Jak ju inni napisali, O(1) == O(1.3) == O(103453123)
> >>>> Nawet i przy rozs dnych za o eniach mo na mie pecha i dosta O(n).
> >>>> To O(1) o jakim pisze Cormen to koszt zamortyzowany
> >>> Nie. Co ma wyszukanie do amortyzacji!
> >> To, e czny koszt wyszuka wszystkich element w jest ograniczony z
> >> g ry liniowo.
> > I co ma to wspólnego z amortyzacją ? Koszt znalezienia pojedyńczego
> > elementu, też się szacuję z góry przez ilość elementów. I co nagle do
> > tego mają wszystkie elementy?
>
> >>> Wikipedia to mo e nie jest
> >>> najlepsze r d o, ale tu akurat jest ok:
> >> Nie musisz mnie tego uczy . Zamortyzowany znaczy redni po wszystkich
> >> wyszukiwaniach.(
> > Nie. Zamortyzowany znaczy średni w ciągu N operacji np. N razy znajdź
> > liczbę 8. Jeśli 8 było na końcu listy kollzji długości n/2, to
> > jednostkowy koszt będzie O(n) i zamortyzowany też będzie O(n). Jeśli
> > bardzo się upierasz przy znajdowaniu wszystkich, to wystarczy wziąć
> > tablicę z K elementami, gdzie wszystkie są w kolizji. Wyszukanie ich
> > wszystkich zajmię ci ~ K^2.
>
> >>> Sensowne za o enia ~ redni przypadek.
> >> Ale stwierdzenie sta y koszt zamortyzowany jest lepsze ni redni koszt
> >> sta y, bo nie bardzo wiadomo co to czas redni -- rednia po czym liczona?
> > średni koszt = koszt w średnim przypadku.
>
> Co to jest średni przypadek?
>
> > Bardziej po polsku pewnie by
> > było "typowym" przypadku, ale tak już jakoś jest. To co jest typowym
> > przypadkiem oczywiście jest bardzo względne. Dlatego w Cormenie jest
> > "sensowne założenia"!
>
> pzdr
> \SK
> --
> "Never underestimate the power of human stupidity" -- L. Lang
> --http://www.tajga.org-- (some photos from my travels)

Psujesz polskie literki.

Łukasz Rekucki wrote:
> On Jan 15, 12:48 pm, Sebastian Kaliszewski
> <s.bez_sp...@remove.this.informa.and.that.pl> wrote:
>> ukasz Rekucki wrote:
>>>> Co jest w og lno ci k amstwem. Cho w realnych sytuacjach jest OK (cho
>>>> w realnych sytuacjach mo na by formalnie poprawnie napisa e dost p do
>>>> dowolnego elementu do realnej listy to O(1) tylko sta a czasowa du a :)
>>>>   (Pami komputer w jest ograniczona przez sta , przeszukanie jest
>>>> jest wi c formalnie O(1) -- oczywi cie ma o to przydatne do
>>>> czegokolwiek, ale formalnie jest OK. :) )
>>> Nie, nie mo na by, bo zale y on od ilo ci element w w tej li cie.
>> I co z tego? Jest zawsze ograniczony z g ry przez sta . Przeczytaj
>> sobie definicj zapisu O(x).
> Nie jest ograniczony przez stałą,

Oczywiście że jest. Ba, komputer stojący na twoim biurku można spokojnie 
przedstawić jako automat skończony (trochę duży, ale skończony).

> bo model obliczeń o którym
> rozmawiamy, nie ma takich ograniczeń jak pamięć!

Oczywiście że ma.

> Definicja klas o(x), O
> (x) i theta(x) to już w ogóle nie widzą co to jest "pamięć"

Oczywiście że wiedzą. Liczba symboli nie blank na taśmie maszyny Turinga 
to jest pamięć.

>. Jaki jest
> sens notacji granicznej do nieskończoności, jeśli ograniczasz z góry
> argumenty ?! żaden.

Dlatego nie należy ich ograniczać. Ale wtedy indeks tablicy też nie jest 
ograniczony. Jeśli ograniczyłeś długość indeksów do stałej to 
ograniczyłeś również do stałej wielkość tablicy.


>>> I
>>> nie jest to formalnie ok, bo poprostu liczysz zupe nie co innego.
>> Jest formalnie ok. Ma o przydatne, ale OK.
> Nie w  tym modelu obliczeń. W innym może tak, ale nie w tym.

W tym, w tym.

> 
>>>> Wszystkie te O(1) dzia aj tylko i wy cznie dzi ki temu, e pami jest
>>>> sko czona, wi c d ugo reprezentacji dowolnego indeksu / hasha itp jest
>>>> twardo ograniczona z g ry niewielk sta (w dzisiejszych czasach sta
>>>> to jest 64).
>>> Prawi , 2**64, to tylko 1TB
>> Ale sk d. To 16EB -- Pomylile si "jedynie" 2**24 krotnie.
> Ok, pomyliłem się.
> 
>>> - w linux'ie spokojnie mo esz mie 4TB
>>> pami ci wirtualnej.
>> Nie szkodzi. To i tak 2**22 razy mniej ni limit.
> Niż 2**64 taj, ale do tego nie trzeba mieć architektury 64-bitowej.
> Jeśli masz tylko 32-bitowe adresy, to każdy proces jest ograniczony do
> 4GB, ale cały może alokować więcej. Technika jest prosta - należy
> używać tablic wielopoziomowych.

Czyli wydłużyć indeksy. Jak używasz "tablicy wielopoziomowej" to dla 
nieograniczonej pamięci trzeba w sposób nieograniczony zwiększyć liczbę 
poziomów -- i z tablicy mamy drzewo :)

> 
>>>> Bo tak na prawd to zar wno odwo anie do tablicy hashuj cej czy nawet do
>>>> dowlonej pozycji w zwyk ej tablicy to ma koszt nie O(1) tylko O(log n).
>>>> Bo nie ma cud w i zapis dowolnego indeksu do struktury d ugo ci n musi
>>>> mie zaj log n. A e si gni cie pod dany indeks w wi kszo ci
>>>> przypadk w wymaga "obejrzenia" ca o ci jego zapisu to jest ograniczone z
>>>> do u przez O(log n).
>>> Niby masz racj , ale po drodze zmieniasz model oblicze . D ugo
>>> liczby na takim przyziemnym komputerze jak m j jest sta a, a procesor
>>> wykonuj na niej operacj w jednym albo kilku taktach - niezale nie od
>>> jej warto ci. D ugo struktury zupe nie go jako nie obchodzi.
>> Oczywi cie, e go obchodzi. D u sza si nie zmie ci. To dosy kluczowe
>> ograniczenie.
> Twój komputer ma widać dużo zmartwień. Co nie zmienia faktu, że 1 +1
> działa tak samo szybko jak 10000 + 10000.

ale nie tak samo szybko jak 
12391823712345189374918743198374+1290348571028761782645245412454.


BTW rozszerzenie 32bity -> 64bit nie jest za darmo, procesor 32bit 
wykonany w dokładnie tym samym procesie będzie kilka procent szybszy.


>>>> W dzisiejszych komputerach korzystamy z tego, e podstawa tego log jest
>>>> du a (2**32 lub 2**64) i dlatego w praktyce zwija si to do O(1).
>>> NIE, NIE, NIE - Dla dowolnego C i dowolnej funkcji sta ej g, Istnieje
>>> n, t. e log_C(n) > g(n), wi c nigdy log_C(n) nie b dzie O(1). Nigdy.
>>> To s dwie r ne klasy funkcji.
>>> Powodem nie jest jakie *magiczne* oszacowanie, czy zwijanie si ,
>>> tylko model oblicze . Poprostu mnie nie interesuj ile kosztuj
>>> operacj na liczbach!
>>> Mam:
>>>  1) pami RAM o sta ym czasie dost pu
>>>  2) Maszyn , kt ra umie wykonywa arytmetyk na liczbach w czasie
>>> sta ym.
>>>  I pytam si jaka jest zale no ilo ci takich operacji od ilo ci
>>> danych?
>>> To nie jest model uniwersalny, ale si tutaj sprawdza.
>> To si robi troch inaczej. Przyjmuje si nie jak jednostk czasu,
>> tylko liczb operacji okre lonych typ w -- wtedy si zgadza i nie zale y
>> od wielko ci pami ci.
> Inaczej, czyli tak jak napisałem. Interesuje mnie ilość dostępów do
> pamięci i operacji arytmetyki.

Nie. Ilość dostępów do pamięci rośnie (logarytmicznie) wraz wielkością 
adresowanej pamięci.

Przyjmuje się liczbę odwołań (być może złożonych) pod podany adres

> 
>>>>> Oczywi cie mo na czepia si , e czasami w przypadku kilku element w o 2
>>>>> takich samych kluczach b dzie trzeba wykona jak dodatkow operacje,
>>>>> jednak w por wnaniu z z o ono ci liniow O(n) dla wi kszej ilo ci
>>>>> element w jest to na tyle nieistotne, e przyjmuje si , e z o ono
>>>>> jest O(1), a nie np. O(1.3)
>>>> Jak ju inni napisali, O(1) == O(1.3) == O(103453123)
>>>> Nawet i przy rozs dnych za o eniach mo na mie pecha i dosta O(n).
>>>> To O(1) o jakim pisze Cormen to koszt zamortyzowany
>>> Nie. Co ma wyszukanie do amortyzacji!
>> To, e czny koszt wyszuka wszystkich element w jest ograniczony z
>> g ry liniowo.
> I co ma to wspólnego z amortyzacją ? Koszt znalezienia pojedyńczego
> elementu, też się szacuję z góry przez ilość elementów. I co nagle do
> tego mają wszystkie elementy?
> 
>>> Wikipedia to mo e nie jest
>>> najlepsze r d o, ale tu akurat jest ok:
>> Nie musisz mnie tego uczy . Zamortyzowany znaczy redni po wszystkich
>> wyszukiwaniach.(
> Nie. Zamortyzowany znaczy średni w ciągu N operacji np. N razy znajdź
> liczbę 8. Jeśli 8 było na końcu listy kollzji długości n/2, to
> jednostkowy koszt będzie O(n) i zamortyzowany też będzie O(n). Jeśli
> bardzo się upierasz przy znajdowaniu wszystkich, to wystarczy wziąć
> tablicę z K elementami, gdzie wszystkie są w kolizji. Wyszukanie ich
> wszystkich zajmię ci ~ K^2.
> 
>>> Sensowne za o enia ~ redni przypadek.
>> Ale stwierdzenie sta y koszt zamortyzowany jest lepsze ni redni koszt
>> sta y, bo nie bardzo wiadomo co to czas redni -- rednia po czym liczona?
> średni koszt = koszt w średnim przypadku.

Co to jest średni przypadek?

> Bardziej po polsku pewnie by
> było "typowym" przypadku, ale tak już jakoś jest. To co jest typowym
> przypadkiem oczywiście jest bardzo względne. Dlatego w Cormenie jest
> "sensowne założenia"!

pzdr
\SK
-- 
"Never underestimate the power of human stupidity" -- L. Lang
-- 
http://www.tajga.org -- (some photos from my travels)

On Jan 10, 12:11 am, wodzik <wod...@noreply.com> wrote:
> On 2010-01-09 23:24, Stachu 'Dozzie' K. wrote:
>
> > To ze szkoły powinieneś wiedzieć że to nie do końca daje złożoność O(1).
>
> Powiedz to moim wykładowcom, albo chociaż by Thomasowi Cormenowi.
> Cytując z książki "Wprowadzenie do algorytmów":
> -"Przy rozsądnych założeniach można wykazać, że oczekiwany czas
> wyszukiwania elementu z tablicy z haszowaniem wynosi O(1)."
> czy:
> -"średni czas działania podstawowych operacji słownikowych na tablicy z
> haszowaniem wynosi O(1)."
>
> Oczywiście można czepiać się, że czasami w przypadku kilku elementów o 2
> takich samych kluczach będzie trzeba wykonać jakąś dodatkową operacje,

Całość opiera się tu na "przy rozsądnych założeniach". Przy
dostatecznie krótkich haszach i dostatecznie dużej liczbie elementów,
kolizje będą zdarzały się zbyt często.

> jednak w porównaniu z złożonością liniową O(n) dla większej ilości
> elementów jest to na tyle nieistotne, że przyjmuje się, że złożoność
> jest O(1), a nie np. O(1.3)

Nie ma czegoś takiego jak O(1.3), jest O(1).

Łukasz Rekucki wrote:
> Uważam, że dalsza dyskusja z tobą nie ma sensu, bo mylisz pojęcia
> matematyczne i ich zastosowanie do analizy asymptotycznej złożoności
> algorytmów z jakimiś swoimi wyobrażeniami.

Whatever. Chciałeś powiedzieć, że nie masz argumentów. Rozumiem.
Przy okazji musiałeś zacytować cały post wraz z sygnaturką i odpisać nad 
cytatem.

Przypomnę tylko kilka faktów...
1. Pamięć każdego komputera, w odróżnieniu od maszyny Tuninga czy 
maszyny RAM, *jest* ograniczona.
2. Jeśli pamięć jest ograniczona to wszelkie obliczenia albo zakończą 
się albo zapętlą się w czasie 2^M gdzie M to wielkość pamięci w bitach.
3. Czas ten dla realnych komputerów jest oczywiście absurdalnie wielki, 
więc takiego podejścia się nie stosuje, bo nie ma praktycznego sensu. 
Dlatego napisałem: "oczywiście mało to przydatne do czegokolwiek, ale 
formalnie jest OK.". Niezależnie od przyjętego formalizmu *można* tak 
powiedzieć, choćbyś tupał i zatykał uszy.
3a. Algorytm sprawdzania czy wśród pierwszych C (C stałe) elementów 
tablicy (czy listy) nie ma wybroanego elementu X, realizuje się w 
koszcie stałym. Prawda?
4. Jako bardziej użytecznego formalizmu używa się (abstrakcyjnej) 
maszyny RAM której cechą charakerycztyczną nie tylko jest nieskończona 
liczba komórek pamięci, ale nieskończona pojemność każdej komórki. W tym 
modelu rozpatruje się normalnie używane algorytmy, a nie w modelu 
realnego komputera który jest skończony.
5. Alternatywnie do 4 koszt liczy się w liczbie "operacji dominujących" 
koszt pozosytałych uznając za zerowy.


Na marginesie:
Co do tablic haszujących to założenie kosztu stałego opiera się na 
założeniu że wyliczenie hasha ma koszt stały -- i z tym założeniem też 
trzeba sobie poradzić.

\SK
-- 
"Never underestimate the power of human stupidity" -- L. Lang
-- 
http://www.tajga.org -- (some photos from my travels)

Jako że grupę czytują również "dzieci" (np. takie co to właśnie uczą się 
o złożoności asymptotycznej, itd). to rozwinę.

Żeby w ogóle mówić o (nietrywalnej) złożoności asymptotycznej (czyli dla 
rozmiaru danych dążącego do nieskończoności) realizowany (abstrakcyjny) 
algorytm nie może mieć ograniczenia na wielkość danych. Jeśli wielkość 
danych jest ograniczona (przez stałą), to mówienie o złożoności dla 
dowolnie wielkich danych jest bez sensu, w najlepszym razie mamy 
przypadek trywialny, czyli złożoność (asymptotycznie) stałą -- O(1).

Należy pamiętać że jeśli gdzies jest mowa o stałej to to może byc 1, 2, 
3, 100, 0.000001, ale także 2**35, albo i 2**(2**35) albo i dowolnie gorzej.

Jeśli już przejdziemy do dowolnie wielkich danych to złożoność różnych 
teoretycznie prostych algorytmów będzie różna w zależności od użytego 
modelu. Np. banalne odwołanie do k-tego indeksu w zwykłej tablicy w 
zależności od modelu będzie miało złożoność O(1), O(log n) albo i O(n) 
lub gorzej, to ostatnie dotyczy zwykłej maszyny Turinga choćby i z 
wieloma taśmami -- bo w niej dostęp jest sekwencyjny i już. Przy czym w 
modelach o dostępie swobodnym może być zarówno O(log n) jak i O(1) 
zależnie od tego czy mamy model z ograniczonymi rejestrami[*] (mamy 
alfabet symboli rejestrowych i nieskończenie wiele rejestrów) czy też, 
jam maszyna RAM z nieograniczonymi rejestrami (każda "komórka pamięci" 
tej abstrakcyjnej maszyny przechowuje dowolną liczbę naturalną, czyli ma 
nieograniczoną pojemność i tych komórek znowu jest nieskończenie wiele).
Pozostaje jeszcze liczenie liczby tzw. operacji dominujących, np. liczby 
porównań, kopiowań, dostępów do pamięci itd. Ale to również musi być 
zanużone w jakimś modelu abstrakcyjnej maszyny. Oczywiście, jeśli np. 
będziemy liczyli liczbę kopiowań przechowywanych danych, czy np. liczę 
odwołań do tablicy to można mieć trywialnie koszt O(1), ale to i w wielu 
opeacjach drzewiastych liczba kopiowań na wstawienie jest stała (równa 
1). Zatem z operacjami dominującymi trzeba uważać -- muszą być 
rzeczywiście dominujące.

[*] ograniczone są wszystkie rejestry poza jednym -- trzeba jakoś 
zaindeksować dowolny rejestr.


Zatem... w zależności od tego co nas interesuje stosujemy różne modele. 
Ale nie wolno zapomnieć o powyższym (różnych złożonościach tego samego 
rozwiązania). Różnice złożoności między różnymi modelami (Turing 
complete, nie wliczamy tu zliczania operaci dominujących bo to trochę co 
innego) mogą być duże, ale też zwykle nie przekraczają O(n**3) a i też 
gwarantuje się że ogólna klasa O(wielomian(n)) czy O(2**wielomian(n)) 
itd jest zachowana. Wynika to z tego, że każdy z tych modeli może 
zasymulować inny z narzutem wielomianowym (i ten wielomian jest 
konkretny, zwykle nie gorszy niż 3 stopnia).


Co do samego hashowania i jego liniowości nawet w modelu RAM 
(nieskończenie wiele nieograniczonych rejestrów z dostępem swobodnym) to 
jest jeszcze problem zasadniczy (o którym napisałem na górze) -- funkcja 
mieszająca ma po pierwsze bardzo często stałej wielkości wyniki (dotyczy 
zdecydowanej większości realnie używanych hashy, czy to różnych prostych 
xor/shift/mod czy crc, czy md4, czy md5 czy sha1, itd) więc dla 
odpowiednio dużych danych przestaje działać (co z tego, że mamy 2**36 
pozycji w tablicy skoro użyty hash crc32 da 2**32 różnych wyników). Po 
drugie nawet na maszynie RAM z dodatkami (typu operacje arytmetyczne i 
bitowe a nie tylko inkrementacja) typowy sensowny hash liczy się w 
czasie liniowo zależnym od wielkości hashowanych danych a nie w czasie 
stałym.

W innych modelach maszyn niż RAM-podobne (nieskończenie wiele 
nieograniczonych rejestrów) w ogóle nie ma co mówić o stałym koszcie 
liczenia hasha. No chyba że używamy zliczania operacji dominujących i za 
taką uznajemy policzenie hasha, ale to jest masło maślane.


Do tego nie wolno zapomnieć, że w dzisiejszych rzeczywistych komputerach 
(poza drobnymi komputerkami wbudowanymi (embedded)) dostęp do pamięci 
nie jest jednolity -- nawet bez swapowania różnice w czasie dostępu 
sięgają 3 rzędów wielkości (do ok. 1000 razy) i zależą nie tylko od 
trafień w cache ale np. dostęp sekwencyjny do większych bloków średnio 
bywa kilkanaście-kilkadziesiąt razy szybszy niż stricte swobodny. Ale to 
już temat na osobną bajkę.

\SK

-- 
"Never underestimate the power of human stupidity" -- L. Lang
-- 
http://www.tajga.org -- (some photos from my travels)