🚀 go-pugleaf

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)