W dniu sobota, 30 marca 2013 13:55:31 UTC+1 użytkownik Roman W napisał:
> Czyli jednak bedziesz przetwarzal plik dwukrotnie. Ma byc tylko raz.
W takim razie nie wiem co to znaczy przetwarzanie.
Pozdrawiam

do góry

On Sat, 30 Mar 2013 06:06:02 -0700 (PDT), "M.M." <m...@g...com>
wrote:
> W takim razie nie wiem co to znaczy przetwarzanie.

No zarówno indeksowanie linii jak i wybor n-tej linii sie
kwalifikuje. Moze zle ooisalem zadanie. Zalozmy ze ktos Ci wysle
Bardzo Duzy plik jako strumien danych przez siec. Nie mozesz zapisac
pliku po swojej stronie. Wiesz ze plik jest skonczony ale nie wiesz
ile ma linii. Dowiesz sie o tym ze dostales komplet danych jak
otrzymasz na wejsciu umowiony znak ASCII. Wybierz z pliku losowa
linie z jednorodnym rozkladem prawdopodobieństwa.

RW

do góry

Dnia 30-03-2013 o 17:20:48 Roman W <b...@g...pl>
napisał(a):

> Moze zle ooisalem zadanie. Zalozmy ze ktos Ci wysle Bardzo Duzy plik
> jako strumien danych przez siec. Nie mozesz zapisac pliku po swojej
> stronie. Wiesz ze plik jest skonczony ale nie wiesz ile ma linii.
> Dowiesz sie o tym ze dostales komplet danych jak otrzymasz na wejsciu
> umowiony znak ASCII. Wybierz z pliku losowa linie z jednorodnym
> rozkladem prawdopodobieństwa.

taki algorytm się nada?

Listy L1,L256,L64K,L16M,L4G,... są puste.
dla każdej nadchodzącej linii l:
dopisz l do L1.
jeśli długość L1 osiągneła 256:
wybierz losową linie z L1 i dopisz do L256.
wyczyść L1.
jeśli długość L256 osiągneła 256:
wybierz losową linie z L256 i dopisz do L64K.
wyczyść L256.
jeśli długość L64K osiągneła 256:
#i tak dalej dla wszystkich list
dla sygnału końca pliku:
zwróc losową linie z linii w listach, biorąc elementy L1 z wagą 1, L256 z
wagą 256, L64K z wagą 65536, ...
Koniec.


--
Jordan Szubert

do góry

On Sat, 30 Mar 2013 17:41:49 +0100, "Jordan Szubert"
<u...@j...us.to> wrote:
> taki algorytm się nada?


> Listy L1,L256,L64K,L16M,L4G,... są puste.
> dla każdej nadchodzącej linii l:
> dopisz l do L1.
> jeśli długość L1 osiągneła 256:
> wybierz losową linie z L1 i dopisz do L256.
> wyczyść L1.
> jeśli długość L256 osiągneła 256:
> wybierz losową linie z L256 i dopisz do L64K.
> wyczyść L256.
> jeśli długość L64K osiągneła 256:
> #i tak dalej dla wszystkich list
> dla sygnału końca pliku:
> zwróc losową linie z linii w listach, biorąc elementy L1 z wagą=
> 1, L256 z =


> wagą 256, L64K z wagą 65536, ...
> Koniec.

Nada sie i pewnie w praktyce zadziala, ale wymaga O(log N) pamieci.
Mozna to zrobic w O(1).

RW

do góry

On 30.03.2013 18:39, Roman W wrote:
>
> Nada sie i pewnie w praktyce zadziala, ale wymaga O(log N) pamieci.
> Mozna to zrobic w O(1).

Wybierasz pierwszą. W każdym kroku z prawdopodobieństwem P zależącym od
ilości wczytanych linii wybierasz bieżącą a z (1-P) zostajesz przy
poprzednim wyborze. Tylko trzeba mieć dobry generator dla takich
sekwencji i nie nadziać się na zaokrąglenia.

--
Pozdrawiam
Michoo

do góry

Dnia 30-03-2013 o 19:25:40 Michoo <m...@v...pl> napisał(a):

> On 30.03.2013 18:39, Roman W wrote:
>>
>> Nada sie i pewnie w praktyce zadziala, ale wymaga O(log N) pamieci.
>> Mozna to zrobic w O(1).
>
> Wybierasz pierwszą. W każdym kroku z prawdopodobieństwem P zależącym od
> ilości wczytanych linii wybierasz bieżącą a z (1-P) zostajesz przy
> poprzednim wyborze. Tylko trzeba mieć dobry generator dla takich
> sekwencji i nie nadziać się na zaokrąglenia.

moje prawie wszytkie losowania robi dla zakresu 256, więc o zaokrąglenia
nie trzeba się martwić, i pewnie szybciej działa, robiąc ok. n/255
prostych losowań, a nie n trudniejszych

--
Jordan Szubert

do góry

W dniu sobota, 30 marca 2013 17:20:48 UTC+1 użytkownik Roman W napisał:
> No zarówno indeksowanie linii jak i wybor n-tej linii sie
> kwalifikuje. Moze zle ooisalem zadanie. Zalozmy ze ktos Ci wysle
> Bardzo Duzy plik jako strumien danych przez siec. Nie mozesz zapisac
> pliku po swojej stronie. Wiesz ze plik jest skonczony ale nie wiesz
> ile ma linii. Dowiesz sie o tym ze dostales komplet danych jak
> otrzymasz na wejsciu umowiony znak ASCII. Wybierz z pliku losowa
> linie z jednorodnym rozkladem prawdopodobieństwa.
Nie znam rozwiązania, ale mogę na głos pomyśleć.

Zadanie uproscimy do podania numeru "nr" poczatkowego znaku, powrot
do oryginalnej wersji zadania bedzie banalny.

Poczatkowo
nr=0 - znaki liczymy od zera.
curr_byte=0 - numer wczytanego znaku, inkrementujemy po kazdym znaku
cnt_rows=1 - ilosc wierszy, inkrementujemy po kazdym wierszu


Czytamy po jednym znaku. Gdy poprzednim znakiem byl inny znak niz
znak nowej linii to nie robimy nic. Wiec algorytm dziala poprawnie
dla pierwszego wiesza - w nr jest poprawna wartosc.

Teraz sprobujemy krok indukcyjny na kolejne wiersze:

Jesli porzednim znakiem byl znak konca wiersza, to mamy poprawne wartosci:

nr - bajt rozpoczynajacy poprzednio wylosowany wiersz
curr_byte - bajt rozpoczynajacy ten wiersz
cnt_row - ilosc rozpoznanych wierszy do tej pory


Generujemy calkowita liczbe losowa z przedzialu otwartego od 1 do cnt_row.
Bylo do tej pory wczytanych cnt_row wierszy. Czyli prawdopodobienstwo ze
liczba losowa bedzie rowna 1 jest rowna 1/cnt_row. Jesli liczba losowa
rowna jest 1 to do zmiennej nr przypisujemy curr_byte. A wiec w zmiennej
nr po tym kroku bedzie poprawny (zgodny z rozkladem rownomiernym) wiersz,
wiec krok mozna powtarzac do konca.

Co konczy dowod - o ile sie nie myle :D

Pozdrawiam

do góry

On 29.03.2013 13:07, firr kenobi wrote:
>

>
> Dokonałem pewnych prostych testów i wyniki mnie zszokowały :U (mam w
domu naprawde starego kompa i stary dysk tak ze to sa dane dla mojego
sprzetu, mam nadzieje ze nic z testem nie zbabrałem ale chyba nie)
>
> wczytanie pilku 1MB przec fgetc - mw 11 milisekund (powtarzane kilka
> razy, wiec z cache)

Co w tym dziwnego? Każdy wie, że często czytane pliki są buforowane.


>
>
> pierwszy szok bo mz jest to nieslychanie szybko, wydawalo mi sie ze
> to powinno byc z 10 razy wolniej

Jak byś poczytał chwilę żeby się czegoś dowiedzieć a nie tylko pisał to
życie nie byłoby dla ciebie ciągłym pasmem zaskoczeń. :\


>
> wczytanie pilku 300 bajtow przec fgetc - mw 0.2 milisekundy
>
>
>
> wczytanie pilku 10MB przec fgetc - mw 120 milisekundy (kolene
> uruchomienia) - pierwsze uruchomienie 1.2 sekundy
>
>
> szybko, widac ze z cache działa 10x szybciej niz bez

Spaprany pomiar - np zamulasz czytaniem za pomocą mikroskopijnych
rozmiarów a na każdy blok masz 2 zmiany kontekstu i kilkanaście wywołań.

Dostęp RAM-RAM to jest kilka GB/s, dysk (zwykły, nie SSD, czy serwerowe)
to maksymalnie kilkadziesiąt MB/s.


>
> wczytanie pilku 1MB przec fread - mw 3 ms (kolene uruchomienia)
>
>
> kojejny szok, wczytywanie przez fread jest 3-4 razy szybsze niz
> przezfgetc - w zyciu bym sie nie spodziewal bo przeciez wydaje sie ze fgetc
> mozna zrobic jako b lekki wrapper na fread i powinno byc to samo a tu
> tymczasem jednak nie :/

A jaki rozmiar podałeś dla fread? też jeden bajt?

--
Pozdrawiam
Michoo

do góry

W dniu sobota, 30 marca 2013 19:38:28 UTC+1 użytkownik Michoo napisał:

> > kojejny szok, wczytywanie przez fread jest 3-4 razy szybsze niz
> > przezfgetc - w zyciu bym sie nie spodziewal bo przeciez wydaje sie ze fgetc
> > mozna zrobic jako b lekki wrapper na fread i powinno byc to samo a tu
> > tymczasem jednak nie :/
> A jaki rozmiar podałeś dla fread? też jeden bajt?

Wszystko zalezy od rozmiaru bufora. Jesli bufor jest duzy, to mnie tez
dziwi ze jest az 3-4 razy wolniejsze. Jesli bufor jest maly, to nic
dziwnego, bo przelaczanie sie w tryb jadra jest czasochlonne.

Pozdrawiam

do góry

Może nie jest takie dziwne bo to pewnie jednak roznica tylko dla wersji z cache
3ms/11ms na MB to są pewnie różnice między jakimś trochę wolnym memcopy a loopem z
procedurami. Teraz większy problem mam z wykonaniem asynchronicznego wczytywania ,
chciałem to zrobić z głównego wątku nie stopujac gry ale okazuje się że aby odebrać
callbacka readfinished trzeba chyba zawiesić wątek tak że nie wiem jak to zrobić

do góry