GoldenLine
Zaloguj się
Adam Borowiecki

Adam Borowiecki Programista,
analityk,
wdrożeniowiec,...

Temat: Zagadka/i ;)

Paweł K.:
Inne zadanie, moje ulubione z "Perełek oprogramowania" (jeśli ktoś czytał, to proszę nie podpowiadać, jeśli ktoś nie czytał - mam nadzieję, że zachęci do książki):

Z ciągu N elementów (nie mieszczącego się w pamięci, odcztywanego sekwencyjnie) wylosować w jednym przebiegu M elementów (M < N). Dostępny jest generator losowy o
> rozkładzie jednostajnym. Jako utrudnienie bądź podpowiedź
powiem, że nie używamy żadnej dodatkowej pamięci.

1. nie czytalem!
2. może przeskalować generator.

A jakbym chcial sie czepiac jak rzep psiego ogona nie da sie nic
zaprogramowac nie zużywajac pamieci; nawet wywolac funkcji (bo stos)
ani wyliczyc wyrażenia,...
Link do wypowiedziLink

konto usunięte

Temat: Zagadka/i ;)

Adam Borowiecki:
[...]
Zliozonosc obliczeniowa STALA i mala!

P.S.

1. Świat algorytmów jest swiatem idealnym i dlatego pytanie o dostępne zasoby
uważam za nietakt :)
2. Jeśli kogoś nie zadowala pkt. 1 to małe zużycie pamięci może zrekompensować
złożonoscią obliczeniową albo na odwrót. W życiu jest zwykle cóś z cóś.

No i tu jest pies pogrzebany. W świecie algorytmów należy podawać złożoność zarówno obliczeniową jak i pamięciową - darmowych obiadów i nieskończonych zasobów nie ma.
Link do wypowiedziLink

konto usunięte

Temat: Zagadka/i ;)

Adam Borowiecki:
[...]
2. może przeskalować generator.

Konkretnie - jak?
A jakbym chcial sie czepiac jak rzep psiego ogona nie da sie nic
zaprogramowac nie zużywajac pamieci; nawet wywolac funkcji (bo stos)
ani wyliczyc wyrażenia,...

Wystarczy tyle, ile wymaga wyciągnięcie kolejnej wartości losowej i - tak 8-) - przeskalowanie wartości oraz bufor na element przepisywany z wejścia na wyjście.
Link do wypowiedziLink
Adam Borowiecki

Adam Borowiecki Programista,
analityk,
wdrożeniowiec,...

Temat: Zagadka/i ;)

Paweł K.:
Adam Borowiecki:
[...]
Zliozonosc obliczeniowa STALA i mala!

P.S.

1. Świat algorytmów jest swiatem idealnym i dlatego pytanie o dostępne zasoby
uważam za nietakt :)
2. Jeśli kogoś nie zadowala pkt. 1 to małe zużycie pamięci może zrekompensować
złożonoscią obliczeniową albo na odwrót. W życiu jest zwykle cóś z cóś.

No i tu jest pies pogrzebany. W świecie algorytmów należy podawać złożoność zarówno obliczeniową jak i pamięciową - darmowych obiadów i nieskończonych zasobów nie ma.


W tym konkretnym przypadku zlozonosc pamieciowa jest stala (lub
ograniczona przez stala) choć moze i duża :)

A odnosnie zadania drugiego to na razie mysle. i nic.
Link do wypowiedziLink
Adam Borowiecki

Adam Borowiecki Programista,
analityk,
wdrożeniowiec,...

Temat: Zagadka/i ;)

Kazdy kolejny element ze strumienia wejsciowego przenoszę
do strumienia wyjściowego z prawdopodobieństwem wyliczanym
w kazdym kroku

ilosc elementow brakujacych w zb. wyjsciowym
------------------------------------------------
wielkosc zb. wejsciowego

(jakos brzydko wyswietlilo - poobcinalo mi spacje)

P = (M-ilosc)/N // ilosc - ilosc dotychczas przeniesionych

( czyli skalowanie generatora ani dodatkowa pamiec nie sa potrzebne :) )Adam Borowiecki edytował(a) ten post dnia 04.10.10 o godzinie 10:50
Link do wypowiedziLink

konto usunięte

Temat: Zagadka/i ;)

Adam Borowiecki:
Kazdy kolejny element ze strumienia wejsciowego przenoszę
do strumienia wyjściowego z prawdopodobieństwem wyliczanym
w kazdym kroku

ilosc elementow brakujacych w zb. wyjsciowym
------------------------------------------------
wielkosc zb. wejsciowego

(jakos brzydko wyswietlilo - poobcinalo mi spacje)

P = (M-ilosc)/N // ilosc - ilosc dotychczas przeniesionych

( czyli skalowanie generatora ani dodatkowa pamiec nie sa potrzebne :) )Adam Borowiecki edytował(a) ten post dnia 04.10.10 o godzinie 10:50

No i gratuluję 8-) A książkę polecam tak czy inaczej.
Link do wypowiedziLink
Maciej Hehl

Maciej Hehl w teorii Automatyk i
Robotyk (po wydziale
mechanicznym), ...

Temat: Zagadka/i ;)

P = (M-ilosc)/N // ilosc - ilosc dotychczas przeniesionych


Perełek jeszcze nie czytałem, ale we wzór powyżej nie wierzę. Nie może być poprawny. Prawdopodobieństwo, że element z ciągu wejściowego trafi do ciągu wyjściowego powinno być dla każdego elementu z ciągu wejściowego takie samo i wynosić M/N. Warunek ten w powyższym przypadku nie jest spełniony.

Podejrzewam, że prawdopodobieństwo powinno wynosić raczej

P = (M - ilość_przeniesionych) / (N - ilość_przetworzonych)

Prawdopodobieństwo, że pierwszy element trafi do ciągu wyjściowego jest oczywiście równe M/N

Dla elementu drugiego: p = M/N * (M-1)/(N-1) + (N-M)/N * M/(N-1) = M/N

Dla elementu trzeciego:

p = M/N * (M-1)/(N-1) * (M-2)/(N-2)
+ M/N * (N-M)/(N-1) * (M-1)/(N-2)
+ (N-M)/N * M/(N-1) * (M-1)/(N-2)
+ (N-M)/N * (N-M-1)/(N-1) * M/(N-2)

Bardzo wytrwali mogą sprawdzić że to też jest równe M/N

I ogólnie dla elementu K+1 przez indukcję.

Zakładamy, że dla wszystkich elementów do K-tego włącznie prawdopodobieństwo wylądowania w ciągu wyjściowym wynosi p = M/N

Prawdopodobieństwo, że w ciągu wyjściowym wylądowało n elementów spośród pierwszych K jest równe liczbie n sukcesów w procesie K prób Bernoulliego

(K po n) * p^n * (1-p)^(K-n) // p=M/N

Dla elementu K+1

p = suma po n = 0 do K { (K po n) * p^n * (1-p)^(K-n) * (M-n)/(N-K) }

Jak ktoś ma zacięcie do takich sum, to może sprawdzić, że p = M/N :)

Jak już jesteśmy przy zagadnieniach tego typu, to pozwolę sobie polecić rozważania na temat odrobinę innego problemu. M jest na tyle małe, że możemy ciąg wynikowy umieścić w tablicy i operować na tej tablicy wymieniając elementy jeśli trzeba. N natomiast jest bardzo duże i nie znane. Problem jest oczywiście opisany i można znaleźć rozwiązania szukając "Reservoir Sampling". Podobno są dowcipnisie, którzy zadają takie zadanka na rozmowach kwalifikacyjnych.Maciej Hehl edytował(a) ten post dnia 29.10.10 o godzinie 18:53
Link do wypowiedziLink
Adam Borowiecki

Adam Borowiecki Programista,
analityk,
wdrożeniowiec,...

Temat: Zagadka/i ;)

Masz Pan rację.
Link do wypowiedziLink
Mateusz Herych

Mateusz Herych Arch Linux TU,
Student PK

Temat: Zagadka/i ;)

Ping?
Macie więcej zagadek?
Link do wypowiedziLink

konto usunięte

Temat: Zagadka/i ;)

Dosyć prostę, ale dobre bo nie wymaga rysowania ;)

Napisać taki program który implementuję ICharacterReader (posiada metodę read(), zwracającą kolejny znak lub NULL jak już nie ma więcej znaków), który dla danego tekstu wypisze listę unikatowych wyrazów które w tym tekście wystąpiły + ilość wystąpień każdego wyrazu posortowane malejąco wg wystąpień.

np, dla tekstu: It was the best of times, it was the worst of times.
zwróci:

it - 2
of - 2
the – 2
times - 2
was - 2
best - 1
worst – 1

Następnie, zrobić wielowątkową wersję tego algorytmu, która dostaję tablicę interfejsów ICharacterReader, z których czyta w sposób równoległy i wypisuję tą listę co 10 sekund.Karim A. edytował(a) ten post dnia 28.01.11 o godzinie 13:32
Link do wypowiedziLink
Piotr Głudkowski

Piotr Głudkowski Rzucam się na
wszystko to, co jest
ciekawe i wymaga
rusze...

Temat: Zagadka/i ;)

A gdzie jest kruczek?
Dynamiczna hashtable indeksowana wyrazami, zawierająca ilość wystąpień, z synchronizacją dostępu przez różne wątki. Jeden wątek na jeden reader + wątek główny.
A jeśli wątków jest dużo i musiałyby często czekać na dostęp do hashtable (wyszukiwanie elementu tabeli indeksowane wyrazem może trochę trwać - zależy jak sprytnie się to zrobi), to dodać kolejkę wyrazów: wątki czytają teksty, wydzielają z nich wyrazy i wrzucają do wspólnej kolejki FIFO (synchronizacja!), a wątek główny co 10s pobiera wyrazy z kolejki, aktualizuje hashtable i wypisuje wyniki.
Link do wypowiedziLink

konto usunięte

Temat: Zagadka/i ;)

Karim A.:
Napisać taki program który implementuję ICharacterReader (posiada metodę read(), zwracającą kolejny znak lub NULL jak już nie ma więcej znaków), który dla danego tekstu wypisze listę unikatowych wyrazów które w tym tekście wystąpiły + ilość wystąpień każdego wyrazu posortowane malejąco wg wystąpień.

:-)Karim A. edytował(a) ten post dnia 28.01.11 o godzinie 14:54
Link do wypowiedziLink
Mateusz Herych

Mateusz Herych Arch Linux TU,
Student PK

Temat: Zagadka/i ;)

Jedna mapa <string,int>, druga multimapa <int,string>.
W pierwszej mapie słowo to klucz, int to liczba jego wystąpień, w drugiej liczba wystąpień i słowo. Na koniec iterujemy po multimapie od końca, możemy użyć naszej pierwszej mapy do zaznaczania, które słowa z multimapy już wypisaliśmy (bo będzie w niej kilka egzemplarzy jednego słowa).



int main() {

        map<string,int> mapa;

        multimap<int,string> mapa2;

        while(1) {

                string slowo;

                cin >> slowo;

                if(cin.eof()) break;

                mapa[slowo]++;

                mapa2.insert(pair<int,string>(mapa[slowo],slowo));

        }

        multimap<int,string>::const_iterator it = mapa2.end();

        for(;;--it) {

                if(mapa[it->second] == -1) continue;

                mapa[it->second]=-1;

                cout << it->first << " - " << it->second << "\n";

                if(it == mapa2.begin()) break;

        }

        return 0;

}


Kwestia tylko małych i dużych słów.

edit: mały mod.Mateusz Herych edytował(a) ten post dnia 28.01.11 o godzinie 16:00
Link do wypowiedziLink
Piotr Głudkowski

Piotr Głudkowski Rzucam się na
wszystko to, co jest
ciekawe i wymaga
rusze...

Temat: Zagadka/i ;)

Karim A.:
/../ dla danego tekstu wypisze listę unikatowych wyrazów które w tym tekście wystąpiły + ilość wystąpień każdego wyrazu posortowane malejąco wg wystąpień.

:-)Karim A. edytował(a) ten post dnia 28.01.11 o godzinie 14:54

Jasne :)
Link do wypowiedziLink

konto usunięte

Temat: Zagadka/i ;)

Można też spróbować zaprzęgnąć do wersji równoległej drzewo prefixowe troszku zmodyfikowane aby nie trzymać całego prefixu. Jak wątki pójdą w oddzielne gałęzie mogą pracować równolegle bez synchronizacji. W przypadku tablicy haszującej zawsze jest kwestia obsługi kolizji i ewentualnie przebudowanie drzewa/indexu a wtedy wszystkie wątki czekają. W przypadku wersji równoległej trzeba optymalizować wstawianie bo wypisywanie jest znacznie rzadziej.
Link do wypowiedziLink

konto usunięte

Temat: Zagadka/i ;)

Blisko :)
Fajna byłaby kombinacja Hashtable/Dictionary/Map/etc + Sorted set (czyli drzewko samosortujące się).
Link do wypowiedziLink
Mateusz Herych

Mateusz Herych Arch Linux TU,
Student PK

Temat: Zagadka/i ;)

To może coś ode mnie, nietrudnego.
Stwórz strukturę listy jednokierunkowej przechowującej wartości całkowite, zapełnij ją liczbami od 0 do 9, a następnie odwróć ją używając O(1) dodatkowej pamięci.
Link do wypowiedziLink
Piotr Głudkowski

Piotr Głudkowski Rzucam się na
wszystko to, co jest
ciekawe i wymaga
rusze...

Temat: Zagadka/i ;)

Lista ma dokładnie 10 elementów, czy więcej, a liczby się powtarzają? I zasugerowałeś, że liczby są od 0 do 9 - czy to oznacza, że w kolejnym elemencie jest liczba nie mniejsza niż w danym?
Link do wypowiedziLink
Mateusz Herych

Mateusz Herych Arch Linux TU,
Student PK

Temat: Zagadka/i ;)

0-9 to tylko przykład danych. Żeby było łatwo zobaczyć, że odwracanie listy działa.
Algorytm ma działać dla teoretycznie dowolnej ilości danych. Nie jest też powiedziane, że elementy listy są w jakiś sposób posortowane.
Link do wypowiedziLink
Piotr Głudkowski

Piotr Głudkowski Rzucam się na
wszystko to, co jest
ciekawe i wymaga
rusze...

Temat: Zagadka/i ;)

Ok. A więc warunki brzegowe ustalone. Czas pomyśleć.
Link do wypowiedziLink
« Wróć do tematów
Odpowiedz

Podobne tematy


Następna dyskusja:

Kolejna zagadka algorytmicz...




Wyślij zaproszenie do
Anuluj