Powoli zbieram się do uczciwego przeczytania "Wprowadzenia do algorytmów"
Cormena. W mojej wersji po rozdziale 1.2 znajduje się m.in. takie zadanie:

"Rozważmy problem wykrywania powtarzających się elementów w ciągu n liczb
<x_1, x_2, ... , x_n>. Pokaż, że można rozwiązać ten problem w czasie
Theta(nlgn), gdzie lgn oznacza logarytm n przy podstawie 2."

Jeśli dobrze rozumiem, chodzi o sprawdzenie czy wszystkie liczby w danym ciągu
są różne, czy też może którakolwiek z nich występuje w nim więcej niż raz.

Niby można rozwiązać to tak: posortować ciąg w czasie nlgn (np. Mergesortem),
a później, zaczynając od drugiego elementu ciągu, przejrzeć go liczba po
liczbie sprawdzając czy przypadkiem któraś wartość nie jest równa wartości
występującej tuż przed nią. Daje to żądany czas nlgn, ale czy rzeczywiście o
takie rozwiązanie chodziło autorowi? Zadanie pochodzi praktycznie z samego
początku książki, przed nim opisany jest jedynie algorytm sortowania przez
wstawianie działający w czasie kwadratowym, więc przy założeniu, że problem da
się rozwiązać bez wiedzy wykraczającej poza dotychczas przedstawioną teorię,
powołując się na opisane dalej sortowanie przez scalanie raczej nie znalazłem
rozwiązania, które "autor miał na myśli". A może zadania w tej książce są
jednak ułożone tak, że czasami trzeba do nich wracać dopiero po przeczytaniu
dalszych rozdziałów?

Pytanie do Was: jak Wy byście rozwiązali podany problem?



--
Wysłano z serwisu OnetNiusy: http://niusy.onet.pl

do góry

On 8 Paź, 21:16, "Piotrek" <p...@p...onet.pl> wrote:
> Powoli zbieram się do uczciwego przeczytania "Wprowadzenia do algorytmów"
> Cormena. W mojej wersji po rozdziale 1.2 znajduje się m.in. takie zadanie:
>
> "Rozważmy problem wykrywania powtarzających się elementów w ciągu n liczb
> <x_1, x_2, ... , x_n>. Pokaż, że można rozwiązać ten problem w czasie
> Theta(nlgn), gdzie lgn oznacza logarytm n przy podstawie 2."

> Pytanie do Was: jak Wy byście rozwiązali podany problem?

W czasie N, liniowy jednoprzebiegowy algorytm. Dodajemy do hash-
table,
a potem wyświetlamy te elementy które zostały dodane więcej niż jeden
raz.
Pozdrawiam

do góry

On 9 Paź, 18:38, Mariusz Marszałkowski <m...@g...com> wrote:

> W czasie N, liniowy jednoprzebiegowy algorytm. Dodajemy do hash-
> table,
> a potem wyświetlamy te elementy które zostały dodane więcej niż jeden
> raz.

Gorzej, jeśli chodzi nam o czas pesymistyczny, a nie średni.
Jeśli rozkłąd liczb jest nieprzyzwoity, to i nad funkcja haszującą
trzeba się nagłowić.

@Piotrek: Wydaje mi się, ze Cormenowi chodziło o sortowanie.

pozdrawiam
bartekltg

do góry

W dniu 09.10.2010 18:38, Mariusz Marszałkowski pisze:
> On 8 Paź, 21:16, "Piotrek"<p...@p...onet.pl> wrote:
>> Powoli zbieram się do uczciwego przeczytania "Wprowadzenia do algorytmów"
>> Cormena. W mojej wersji po rozdziale 1.2 znajduje się m.in. takie zadanie:
>>
>> "Rozważmy problem wykrywania powtarzających się elementów w ciągu n liczb
>> <x_1, x_2, ... , x_n>. Pokaż, że można rozwiązać ten problem w czasie
>> Theta(nlgn), gdzie lgn oznacza logarytm n przy podstawie 2."
>
>> Pytanie do Was: jak Wy byście rozwiązali podany problem?
>
> W czasie N, liniowy jednoprzebiegowy algorytm. Dodajemy do hash-
> table,
> a potem wyświetlamy te elementy które zostały dodane więcej niż jeden
> raz.
Łooo!

Rozumiem pisząc hashtable masz na myśli hashtable a nie hashtree (które
by przez swoją "drzewowatość" dawałoby nlog n).

A klasyczne hashtable o rozmiarze k realizowane funkcją modulo k wymaga
obsługi powtarzających się haszy. i te powtarzające się hasze będzie się
obługiwać albo w ulog u przy uży7ciu stosu/drzewa (gdzie u to ilość
haszy kolidujących) albo w u^2 przy naiwnej implementacji z listą.


--
Pozdrawiam
Michoo

do góry

On 9 Paź, 21:35, Michoo <m...@v...pl> wrote:
> W dniu 09.10.2010 18:38, Mariusz Marszałkowski pisze:> On 8 Paź, 21:16,
"Piotrek"<p...@p...onet.pl>  wrote:
> >> Powoli zbieram się do uczciwego przeczytania "Wprowadzenia do algorytmów"
> >> Cormena. W mojej wersji po rozdziale 1.2 znajduje się m.in. takie zadanie:
>
> >> "Rozważmy problem wykrywania powtarzających się elementów w ciągu n liczb
> >> <x_1, x_2, ... , x_n>. Pokaż, że można rozwiązać ten problem w czasie
> >> Theta(nlgn), gdzie lgn oznacza logarytm n przy podstawie 2."
>
> >> Pytanie do Was: jak Wy byście rozwiązali podany problem?
>
> > W czasie N, liniowy jednoprzebiegowy algorytm. Dodajemy do hash-
> > table,
> > a potem wyświetlamy te elementy które zostały dodane więcej niż jeden
> > raz.
>
> Łooo!
>
> Rozumiem pisząc hashtable masz na myśli hashtable a nie hashtree (które
> by przez swoją "drzewowatość" dawałoby nlog n).
>
> A klasyczne hashtable o rozmiarze k realizowane funkcją modulo k wymaga
> obsługi powtarzających się haszy. i te powtarzające się hasze będzie się
> obługiwać albo w ulog u przy uży7ciu stosu/drzewa (gdzie u to ilość
> haszy kolidujących) albo w u^2 przy naiwnej implementacji z listą.

No dobra, ale po co brać pod uwagę pesymistyczny przypadek który
zdarza się tak rzadko, że ciężko policzyć? To się w praktyce dla
dużych danych nie zdarzy, a dla małych najszybciej zadziała algorytm o
małym narzucie liniowym.
Pozdrawiam

do góry

On 9 Paź, 21:20, bartekltg <b...@g...com> wrote:
>
> Gorzej, jeśli chodzi nam o czas pesymistyczny, a nie średni.
No tak, ale tak z ciekawości, jak maleje prawdopodobieństwo
że ze wzrostem danych N, trafiliśmy na przypadek pesymistyczny
i czas jest większy niż 1/C * N^2 ?

> Jeśli rozkłąd liczb jest nieprzyzwoity, to i nad funkcja haszującą
> trzeba się nagłowić.
Czasami używam hash-table i z reguły nie mam czasu zastanowić
się nad dobrym kluczem. Z reguły robię odmiany czegoś takiego:

mk_key( data ) {
const xor[256] = { rand };
key = 0;
for( i=0 ; i < sizeof(data) ; i++ )
key ^= xor[ (byte(data,i)+i)&0xff ];
return key;
}

Pozdrawiam

do góry

On 9 Paź, 22:09, Mariusz Marszałkowski <m...@g...com> wrote:
> On 9 Paź, 21:20, bartekltg <b...@g...com> wrote:
>
> > Gorzej, jeśli chodzi nam o czas pesymistyczny, a nie średni.
>
> No tak, ale tak z ciekawości, jak maleje prawdopodobieństwo
> że ze wzrostem danych N,  trafiliśmy na przypadek pesymistyczny
> i czas jest większy niż 1/C * N^2 ?

ALe skąd podejrzenie, ze będą to dane o jednostajnym
rozkładzie po całym int. A moze to będzie 10^6 losowych
danych z przedziału 1235:1359 ;)
W ten sposob wpadamy w prawdziwy problem, czyli to, co zauważył
Michoo.

>
> > Jeśli rozkłąd liczb jest nieprzyzwoity, to i nad funkcja haszującą
> > trzeba się nagłowić.
>
> Czasami używam hash-table i z reguły nie mam czasu zastanowić
> się nad dobrym kluczem. Z reguły robię odmiany czegoś takiego:

Ci, co nie maja czasu sie zastanawiać nad algorytmem, nie
mają czasu, bo potrzebują go zachować na długie obliczenia;-)

pozdr
bartekltg

do góry

On 9 Paź, 22:14, bartekltg <b...@g...com> wrote:

> ALe skąd podejrzenie, ze będą to dane o jednostajnym
> rozkładzie po całym int. A moze to będzie 10^6 losowych
> danych z przedziału 1235:1359 ;)
> W ten sposob wpadamy w prawdziwy problem, czyli to, co zauważył
> Michoo.
Ale w jaki problem? Na moje w ten sposób sprawa się upraszcza.
Najlepiej jakby wylosowało się 10^6 takich samych liczb.

> Ci, co nie maja czasu sie zastanawiać nad algorytmem, nie
> mają czasu, bo potrzebują go zachować na długie obliczenia;-)
No dobrze, o ile lepszą można napisać funkcję hash od xorów
losowych liczby?

Pozdrawiam

do góry

On 9 Paź, 22:41, Mariusz Marszałkowski <m...@g...com> wrote:
> Ale w jaki problem? Na moje w ten sposób sprawa się upraszcza.
> Najlepiej jakby wylosowało się 10^6 takich samych liczb.

Problem jest taki, że jeśli dane musimy pamietać (a nie np zliczać
krotność wystąpień danej liczby) to i tak mamy nlogn.
Michoo własnie o tym pisał.

> > Ci, co nie maja czasu sie zastanawiać nad algorytmem, nie
> > mają czasu, bo potrzebują go zachować na długie obliczenia;-)
>
> No dobrze, o ile lepszą można napisać funkcję hash od xorów
> losowych liczby?

Zalezy od danych. I od tego, co sie wylosuje;)
W wiekszosci przypadków powinno być niezle.

pozdrawiam
bartekltg

do góry

W dniu 09.10.2010 21:57, Mariusz Marszałkowski pisze:
> On 9 Paź, 21:35, Michoo<m...@v...pl> wrote:
>> A klasyczne hashtable o rozmiarze k realizowane funkcją modulo k wymaga
>> obsługi powtarzających się haszy. i te powtarzające się hasze będzie się
>> obługiwać albo w ulog u przy uży7ciu stosu/drzewa (gdzie u to ilość
>> haszy kolidujących) albo w u^2 przy naiwnej implementacji z listą.
>
> No dobra, ale po co brać pod uwagę pesymistyczny przypadek który
> zdarza się tak rzadko, że ciężko policzyć?
Ale to zadanie z książki o teorii algorytmów. Nie podręcznika sprytnego
programisty.

> To się w praktyce dla
> dużych danych nie zdarzy, a dla małych najszybciej zadziała algorytm o
> małym narzucie liniowym.
Dla dużych danych nie możemy mieć za dużego hashtable, bo wylecimy z
cache i wszystko znacznie zwolni. tak więc dla n danych i k kubełków (w
przypadku optymistycznym):
- n/k danych w kubełku
- n/k * ln(n/k) lub n/k * (n/k)^2 czas wstawiania do jednego kubełka
- mamy k kubełków, więc k*(n/k * ln(n/k)) = n * ln(n/k) lub k*(n/k *
(n/k)^2) = n*(n/k)^2 na wstawienie do wszystkich
- tak czy tak wychodzi trochę gorzej niż liniowo, ten sam rząd co dla
sortowania (może mniejsza stała np o 1/2 będzie), ale rząd złożoności
ten sam.

P.S.
Ja bym w c++ użył mapy - bo się najszybciej pisze.
std::map<int,int> count;
count.insert(data.begin(),data.end());
for(auto i=count.begin();i!=count.end();++i)
if(i->second != 1)
std::cout <<i->first<<std::endl;

--
Pozdrawiam
Michoo

do góry