Python a hashmapa
wodzik
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.
pozdrawiam wodzik
Michal
hashmapa = {'a' : 1, 'n': 3}
print hashmapa['a']
--
wodzik
> hashmapa = {'a' : 1, 'n': 3}
> print hashmapa['a']
czyli rozumiem, �e operacje wstawiania - wyszukiwania maj� z�o�ono��
obliczeniow� r�wn� 1?
Stachu 'Dozzie' K.
A widzia�e� kiedy� struktur� spe�niaj�c� te kryteria? Z wyj�tkiem
tablicy indeksowanej liczbami.
--
Secunia non olet.
Stanislaw Klekot
Rob Wolfe
Tu masz to �adnie wyja�nione:
http://wiki.python.org/moin/TimeComplexity
RW
wodzik
>> 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
Jan Kaliszewski
> 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)
wodzik
> "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
Stachu 'Dozzie' K.
>>> 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.
--
wodzik
> 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
Jan Kaliszewski
>> 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)
Jan Kaliszewski
> necie]).
http://code.activestate.com/recipes/576998/ :)
Pozdr.
*j
Stachu 'Dozzie' K.
>
>> 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.
wodzik
>> 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
Łukasz Rekucki
> On 2010-01-10 13:19, Stachu 'Dozzie' K. wrote:
>
> >> 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
wodzik
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
wodzik
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
Łukasz Rekucki
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
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
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
wodzik
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
wodzik
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?
wodzik
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.
Łukasz Rekucki
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__)
Sebastian Kaliszewski
> 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)
Łukasz Rekucki
> 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 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)
Sebastian Kaliszewski
>> Co jest w og�lno�ci k�amstwem. Cho� w realnych sytuacjach jest OK (cho�
>> dowolnego elementu do realnej listy to O(1) tylko sta�a czasowa du�a :)
>> (Pami�� komputer�w jest ograniczona przez sta��, przeszukanie jest
>> czegokolwiek, ale formalnie jest OK. :) )
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)
Łukasz Rekucki
> >> 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. :) )
>
> 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)
Sebastian Kaliszewski
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)
Łukasz Rekucki
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)
Bart Ogryczak
> On 2010-01-09 23:24, Stachu 'Dozzie' K. wrote:
>
>
> 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:
> 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).
Sebastian Kaliszewski
> 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)
Sebastian Kaliszewski
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ďż˝.