Użytkownik "PK" <P...@n...com> napisał w wiadomości grup
dyskusyjnych:s...@n...notb-home.
..
> Mówiąc inaczej. Zaproponowany problem jest de facto równoważny
> posortowaniu zbioru wejściowego.

Nie jest.

1. Dla pliku 1GB i 16 bajtowych "sekwencji" musiałbyś najpierw wygenerować
plik 16 GB i dopiero potem go sortować. Czyli z N, M robi się N*M. W
mikroskali:

ABCDEFGHIJKLBCD

daje (przy M = 3)

ABC, BCD, CDE, DEF, EFG, FGH, GHI, HIJ, IJK, JKL, KLCB LBC, BCD

Da się zauważyć, że BCD występuje najczęściej, bo 2 razy.


2. Oczywiście - jeżeli posortujesz - to znalezienie tej najczęściej
występującej będzie łatwe. Ale przy sortowaniu robić będziesz mnóstwo
zbytecznej roboty.

3. Najmocniejszym "ficzerem" jest to, że te "sekwencje" się nakładają.
Badając jedną badasz - częściowo - sąsiednie. I że jest ich N-M+1, z czego
różnych być może jeszcze mniej, a zawsze znacznie mniej niż liczb M-bitowych
(których jest 2^M). A "naprawdę pamiętać" wystarczy tylko najlepszy
rezultat.

do góry

On 24.11.2012 12:36, bartekltg wrote:
>
> Mając dodatkową pamięć dysku równo pierwotnej tablicy
> (a tak naprawdę 0.5) możemy posortować tablicę
> w 4 przebiegach _sekwencyjnego_ odczytu/zapisu.

slawek się potem "poprawił", że plik jest "dużo" (10x) większy niż ram.

Nie do końca rozumiem to 0.5 nawet przy założeniu dane 4 razy większe od
tablicy - mergesort potrzebuje na każdy merge drugie tyle miejsca.
Wychodzi więc mi minimum 1.5 zakładając, że nie robimy ostatniego
scalania. (Mamy 4 bloki po 1/4 n zajmujące na dysku n i żeby dwa z nich
scalić potrzebujemy dodatkowe 0.5n na wynik.)
>
>
> Kołaczą mi się sztuczki ze statystyką i nie jestem pewien,
> czy nie da się tego zrobić lepiej. Ale ciężko będzie,
> 5 przbiegów po dysku to podejrzewam minimum.
> W koncu nawet log(n) jest większe.

W praktycznym przypadku (a nie maksymalnie złośliwym) spróbowałbym z
drzewem prefiksowym w ramie a jak by się przestało mieścić to dopiero
fallback do sortowania. Daje jeden dodatkowy odczyt sekwencyjny i
złożoność k*log(k) w RAMie gdzie k to liczba różnych wartości.


--
Pozdrawiam
Michoo

do góry

Użytkownik "Michoo" <m...@v...pl> napisał w wiadomości grup
dyskusyjnych:k8qe1s$9fo$...@m...internetia.pl...
> Tak, ale nie chciałem tego nazywać wprost - liczyłem, że slawek coś powie
> (bo obstawiam, że nie znał rozwiązania).

Nie jest. Oczywiście - sortowanie to w pewnym sensie "brute force" - da się
i sortując a potem zliczając, tyle że nie wydaje się, aby to był najlepszy
algorytm (delikatnie rzecz ujmując).

do góry

On 2012-11-24, Michoo <m...@v...pl> wrote:
> Tak, ale nie chciałem tego nazywać wprost - liczyłem, że slawek coś
> powie (bo obstawiam, że nie znał rozwiązania).

Też liczyłem, że coś powie (przecież dałem mu całą noc!). Ale świat
toczy się dalej, więc lepiej to przyciąć od razu i bujać się z czymś
innym :).

pozdrawiam,
PK

do góry

W dniu 2012-11-24 13:39, Michoo pisze:
> On 24.11.2012 12:36, bartekltg wrote:
>>
>> Mając dodatkową pamięć dysku równo pierwotnej tablicy
>> (a tak naprawdę 0.5) możemy posortować tablicę
>> w 4 przebiegach _sekwencyjnego_ odczytu/zapisu.
>
> slawek się potem "poprawił", że plik jest "dużo" (10x) większy niż ram.

Aj, wszytko liczyłem dla 4GB, czyli 8 razy większego.

Problem jest gdzie indziej, nie zauważyłem, że ciągi
na siebie nachodzą. To powiększa mój bufor 16 razy;)
Zaczyna być nieprzyjemnie, ale nadal robialnie.

Zwłaszcza, że w normalnych warunkach ma się 12GB z czego 8 wolne;)
niech będzie 10GB danych, *16. 160GB.
RAMu niech będize 41GB, to daje ok 7 cykli, czyli
powiedzmy 13 (odczytów+zapisów=13)
Trzeba przewalić. 2TB


Powiedzmy, ze nie korzystamy ze sprzętu za 60k$ typu
dysk na PCI-16 6GB transger 4GB/s.
Jakiś dysk SSD na szybko zerknięty na Agito, odczyt/zapis 500MB/s.
Dysk maagnetyczny: "Szybkość przesyłu danych sformatowanych: 6 Gbit/s"
Cokolwiek to znaczy;)

W każdym razie naszą operację szacujemy na 15-20 minut.
Długo, trzeba by poprawić.

Ale zaczyna być ciekawie:)


> Nie do końca rozumiem to 0.5 nawet przy założeniu dane 4 razy większe od
> tablicy - mergesort potrzebuje na każdy merge drugie tyle miejsca.

> Wychodzi więc mi minimum 1.5 zakładając, że nie robimy ostatniego
> scalania. (Mamy 4 bloki po 1/4 n zajmujące na dysku n i żeby dwa z nich
> scalić potrzebujemy dodatkowe 0.5n na wynik.)

Moja pomyłka. +1 w dobrą stronę i -4 w złą;)

>> Kołaczą mi się sztuczki ze statystyką i nie jestem pewien,
>> czy nie da się tego zrobić lepiej. Ale ciężko będzie,
>> 5 przbiegów po dysku to podejrzewam minimum.
>> W koncu nawet log(n) jest większe.
>
> W praktycznym przypadku (a nie maksymalnie złośliwym) spróbowałbym z
> drzewem prefiksowym w ramie a jak by się przestało mieścić to dopiero
> fallback do sortowania. Daje jeden dodatkowy odczyt sekwencyjny i
> złożoność k*log(k) w RAMie gdzie k to liczba różnych wartości.

To drzewo dużo miejsca nam nie oszczędza, ale zawsze.
Nie zaszkodzi spróbować, ale dla losowego ta heurystyka
zadziała?

pzdr
bartekltg

do góry

On 2012-11-24, slawek <s...@h...pl> wrote:
>> Mówiąc inaczej. Zaproponowany problem jest de facto równoważny
>> posortowaniu zbioru wejściowego.
>
> Nie jest.
>
> 1. Dla pliku 1GB i 16 bajtowych "sekwencji" musiałbyś najpierw wygenerować
> plik 16 GB i dopiero potem go sortować. Czyli z N, M robi się N*M. W
> mikroskali:

"Równoważny" nie oznacza, że trzeba posortować to wejście. Chodzi tylko
o klasę problemów i klasę złożoności. W szczególności: rozwiązanie
Twojego problemu będzie miało złożoność nie mniejszą niż sortowanie,
więc nie da się go rozwiązać przy narzuconych przez Ciebie
ograniczeniach.

> różnych być może jeszcze mniej, a zawsze znacznie mniej niż liczb M-bitowych
> (których jest 2^M). A "naprawdę pamiętać" wystarczy tylko najlepszy
> rezultat.

Och zdecydowanie nie. Wariant pesymistyczny: dominantą w zbiorze jest
element, który występuje na pierwszym i na X ostatnich elementów (X
odpowiednio duże).
Dominanta jest statystyką upierdliwą, bo prawie zawsze trzeba brać
pod uwagę cały zbiór wartości. Algorytmy upraszczające wchodzą w grę
wtedy, gdy element występuje naprawdę często (np. stanowi połowę
wszystkich).

pozdrawiam,
PK

do góry

Użytkownik "bartekltg" <b...@g...com> napisał w wiadomości grup
dyskusyjnych:k8qdu2$o5m$...@n...news.atman.pl...
> Ojtam, od miesiąca siedzi nad tym w robocie, niech ma.

Poczytaj sobie np. to

http://www.mathcs.emory.edu/~cheung/papers/StreamDB/
Frequency-count/FrequentStream.pdf

I drobiazg - nie, to nie jest mi do niczego potrzebne - to tylko przykład,
moim zdaniem, dobrego "informatycznego" problemu.

do góry

On 24.11.2012 13:16, e...@g...com wrote:

> podejrzewasz klase spoleczna
> callcenterowcow o jeansy w pracy?

Znajoma robiła na słuchawce i jeżeli dobrze pamiętam jej opowieści to
tylko niektórzy kierownicy mieli jakiś zajob z garniturami.


> Nie pasowalbys tam, to jest
> praca _w biurowcu_.

Pracowałem w czymś o nazwie "WestPoint Business Centre". Dojeżdżałem
rowerem, trzymałem go w naszym openspace, nie byłem jedyny. Fakt, że
pracownicy banku(?chyba banku,już nie pamiętam), który był piętro niżej
czasami w windzie dziwnie patrzyli, ale szybko przywykli.

W drugim biurowcu rower już trzeba było parkować na parkingu podziemnym
i tam jak usłyszałem w windzie oburzony komentarz jakiegoś garnitura do
innych garniturów, że "jak ochrona mogła pozwolić na naklejenie w
windzie informacji o zbiórce charytatywnej" to rzeczywiście poczułem, ze
tam nie pasuję.


--
Pozdrawiam
Michoo

do góry

Użytkownik "PK" <P...@n...com> napisał w wiadomości grup
dyskusyjnych:s...@n...notb-home.
..
> o klasę problemów i klasę złożoności. W szczególności: rozwiązanie
> Twojego problemu będzie miało złożoność nie mniejszą niż sortowanie,

Jeżeli będziemy upierali się aby porównywać dane - oczywiście. A czy to na
pewno trzeba robić? Ot, pytanie!

do góry

On 24.11.2012 13:02, Roman W wrote:
> W dniu sobota, 24 listopada 2012 09:22:15 UTC użytkownik Marek Borowski napisał:
>
>> Nienarzucony ubior swiadczy o charakterze i predyspozycjach danej osoby
>> do pracy. Jak programista przychodzi sam z siebie do pracy w marynarce
>> to wiadomo iz pracuje wylacznie dla kasy
>
> ... czyli ma normalna hierarchie wartosci. Dla idei to pracuje w domu nad wlasnymi
> projektami.

Wolę pracować nad ciekawymi rzeczami i dostawać za to K kpln niż
zarabiać K+1 kpln pracując nad czymś mniej ciekawym/irytującym/żmudnym i
jeszcze musieć uzyskać pozwolenie od przełożonego na pracę nad własnymi
projektami (w czasie wolnym) jeżeli myślę o jakiejkolwiek ich publikacji.


--
Pozdrawiam
Michoo

do góry