🚀 go-pugleaf

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)