🚀 go-pugleaf

A.L. wrote:
> ...
:-) O gdzieś to wszystko już spotkałem :-)

+ jeszcze moje ulubione:
	"To jak wg Pana wygląda reużywanie kodu?"
  	"No przecież jasne ! copy-paste."
-- 
jarekr

Jarek Ratajski wrote (tak! stara dobra wrotka!):

> reużywanie kodu

Straszne! :|

-- 
Zbigniew Malec Ustronie:104 gg:2756100

A.L. <alewando@kapturek62.com> writes:

[...]

> Mamy 10 milionow liczb integer w pamieci. Jak jest najszybszy sposob
> zeny znalezc 5 najwieksza? Nalezy wczytac wszystkei liczby do bazy
> danych i napisac skrypt w SQL

:^)

Dnia Tue, 15 Nov 2005 08:17:00 -0600, A.L. skrobie:
> Chyba zaczne lykac proszki jakies... Firma zatrudnia pare osob, i
> przyszlo mi interwiuowac. Zatrudnia doswiaczonych, minimum 5 lat,
> "contract to hire".

> Ciekawe odpowiedzi na rozne pytania.

> Exceptions?.. Nieeee.. To zla praktyka. Zaciemniaja kod. Handlers
> nalezy umieszczac tylko w "main"

> Synchronized blocks?  Keyword "synchronized" moze byc uzyty tylko w
> metodach.

> "Finalize"?... Nei slyszalem...

> "Weak pointers"?... Nie slyszalem.

> Czym sie rozni interfejs od klasy? Nnooo... Interfejs nie ma
> methods, wiec jak ktos potrzebuje klase bez methods to moze uzyc
> interfejs

> Czy sa jakies narzedzia na poziomie jezyka ktore wspieraja
> programowanie wielowatkowe? Nei ma, sa rozne takie biblioteki.

> Mamy 10 milionow liczb integer w pamieci. Jak jest najszybszy sposob
> zeny znalezc 5 najwieksza? Nalezy wczytac wszystkei liczby do bazy
> danych i napisac skrypt w SQL

> Co to jest zlozonosc algorytmu?... Nnooo chodzi o to ile czasu
> tzreba spedzic zeby go zprogramwoac?...

> To jest magazyn, prosze naszkicowac prosty model obiektowy. Nnnooo,
> na przykald "wziac z polki". Ja: konkretnie? "No taka klasa musi
> byc: wziac z poki". Ja: I jakie jeszcze? "Noo, polozyc na polce,
> zaladowac sanmochod" Ja: a w ogolnosci? "Nnooo Kazda klasa to jakas
> czynnosc"

> Czym sie rozni OO analysis od OO modeling? Nnooo, w zasadzie to
> samo. Jak napisac klasy.

Mam gdzieś skitrane pańskie poprzednie. Może by to gdzieś wystawić?
;)

-- 
//  _    ___         Michal "Sektor" Malecki <sektor(whirl)kis.p.lodz.pl>
\\ L_ |/ `|  /^\ ,()                         <ethourhs(O)wp.pl>
// \_ |\  \/ \_/ /\ C++ bez cholesterolu: http://www.intercon.pl/~sektor/cbx
"I am allergic to Java because programming in Java reminds me casting spells"

On Tue, 15 Nov 2005 16:33:46 +0000 (UTC), Sektor van Skijlen
<ethouris@pl.wp.spamu.lubie.nie.invalid> wrote:
 
 
>
>Mam gdzie¶ skitrane pañskie poprzednie. Mo¿e by to gdzie¶ wystawiæ?
>;)

Gdzie?...

A.L.

Dnia Tue, 15 Nov 2005 10:36:40 -0600, A.L. skrobie:
> On Tue, 15 Nov 2005 16:33:46 +0000 (UTC), Sektor van Skijlen
> <ethouris@pl.wp.spamu.lubie.nie.invalid> wrote:
>  
>  
> >
> >Mam gdzie? skitrane pa?skie poprzednie. Mo?e by to gdzie? wystawi??
> >;)

> Gdzie?...

Jak odgrzebię te poprzednie, to bym sobie np. powiesił na stronce ;)


-- 
//  _    ___         Michal "Sektor" Malecki <sektor(whirl)kis.p.lodz.pl>
\\ L_ |/ `|  /^\ ,()                         <ethourhs(O)wp.pl>
// \_ |\  \/ \_/ /\ C++ bez cholesterolu: http://www.intercon.pl/~sektor/cbx
"I am allergic to Java because programming in Java reminds me casting spells"

A.L. (alewando@kapturek62.com) napisał(a):
> Mamy 10 milionow liczb integer w pamieci. Jak jest najszybszy sposob
> zeny znalezc 5 najwieksza?

Jaki? Pytam z ciekawości.
Abstrahując od szczegółów implementacyjnych wg mnie na szybko
i po prostu można by:
a) przelecieć raz tablicę tych liczb tworząc tabliczkę pięciu największych
i przeglądając ją prawie 10 milionów razy (w większości przypadków
nie całą, przy losowym rozrzucie liczb)
b) przelecieć 5 razy tablicę tych 10 milionów liczb

Co byłoby szybsze, a czy b?

A jakie jest prawidłowe rozwiązanie? Czy jest rozwiązanie zawsze
najlesze, tzn niezależne od wielkości tablicy do przeszukania
i kolejnej wartości jaką trzeba znaleźć (tutaj 5)?

Przyznam, że na kilka z tych pytań nie znam odpowiedzi i nawet się
nie zetknąłem z ww terminami. Ale to pewnie dlatego, że nie znam
ani odrobinę javy i C++, a styl mojego programowania (narzucony
niejako przez Delphi) mocno odbiega od obiektowości.

-- 
Pozdrawiam
Miroo
Teoria względności: "Pracownik jest zbędny w firmie gdy prosi o
podwyżkę, lecz niezastąpiony gdy prosi o urlop" 

"Miroo" <miroo75@REMOVEIT.o2.pl> writes:

> A.L. (alewando@kapturek62.com) napisał(a):
>> Mamy 10 milionow liczb integer w pamieci. Jak jest najszybszy
>> sposob zeny znalezc 5 najwieksza?

[...]

> A jakie jest prawidłowe rozwiązanie?

Najpierw trzeba spytać, czy te liczby są posortowane.

"Piotr Dembiński" (pdemb@gazeta.pl) napisał(a):
> "Miroo" <miroo75@REMOVEIT.o2.pl> writes:
>> A.L. (alewando@kapturek62.com) napisał(a):
>>> Mamy 10 milionow liczb integer w pamieci. Jak jest najszybszy
>>> sposob zeny znalezc 5 najwieksza?
> [...]
>> A jakie jest prawidłowe rozwiązanie?
> Najpierw trzeba spytać, czy te liczby są posortowane.

Skoro nie było zaznaczone w zadaniu tzn że nie były.
Przy posortowanych nie ma w zasadzie  mowy o jakimkolwiek
zadaniu i "naszybszym sposobie".

-- 
Pozdrawiam
Miroo
Teoria względności: "Pracownik jest zbędny w firmie gdy prosi o
podwyżkę, lecz niezastąpiony gdy prosi o urlop" 

Dnia Wed, 16 Nov 2005 13:48:21 +0100, Miroo skrobie:
> A.L. (alewando@kapturek62.com) napisał(a):
> > Mamy 10 milionow liczb integer w pamieci. Jak jest najszybszy sposob
> > zeny znalezc 5 najwieksza?

> Jaki? Pytam z ciekawości.
> Abstrahując od szczegółów implementacyjnych wg mnie na szybko
> i po prostu można by:
> a) przelecieć raz tablicę tych liczb tworząc tabliczkę pięciu największych
> i przeglądając ją prawie 10 milionów razy (w większości przypadków
> nie całą, przy losowym rozrzucie liczb)
> b) przelecieć 5 razy tablicę tych 10 milionów liczb

> Co byłoby szybsze, a czy b?

> A jakie jest prawidłowe rozwiązanie? Czy jest rozwiązanie zawsze
> najlesze, tzn niezależne od wielkości tablicy do przeszukania
> i kolejnej wartości jaką trzeba znaleźć (tutaj 5)?

Moim zdaniem najsensowniejszym sposobem jest zapamiętywać 5 ostatnich liczb z
analizy. Trzymać coś w rodzaju ograniczonej kolejki 5 elementów (ograniczonej,
tzn. jak się doda nowy element, to ostatni w kolejce wylatuje), jak się
znajdzie liczbę większą od tej na szczycie, to spuszczamy wszystko o jeden, a
znalezioną liczbę umieszczamy na szczycie. Jako wynik zwracamy liczbę na samym
dole.


-- 
//  _    ___         Michal "Sektor" Malecki <sektor(whirl)kis.p.lodz.pl>
\\ L_ |/ `|  /^\ ,()                         <ethourhs(O)wp.pl>
// \_ |\  \/ \_/ /\ C++ bez cholesterolu: http://www.intercon.pl/~sektor/cbx
"I am allergic to Java because programming in Java reminds me casting spells"

Sektor van Skijlen (ethouris@pl.wp.spamu.lubie.nie.invalid)
napisał(a):

>> a) przelecieć raz tablicę tych liczb tworząc tabliczkę pięciu
>> największych i przeglądając ją prawie 10 milionów razy (w
>> większości przypadków nie całą, przy losowym rozrzucie liczb)

> Moim zdaniem najsensowniejszym sposobem jest zapamiętywać 5
> ostatnich liczb z analizy. Trzymać coś w rodzaju ograniczonej
> kolejki 5 elementów (ograniczonej, tzn. jak się doda nowy element,
> to ostatni w kolejce wylatuje), jak się znajdzie liczbę większą od
> tej na szczycie, to spuszczamy wszystko o jeden, a znalezioną
> liczbę umieszczamy na szczycie. Jako wynik zwracamy liczbę na
> samym dole.

Czyli zgadzasz się z moim pomysłem a)
ok

-- 
Pozdrawiam
Miroo
Teoria względności: "Pracownik jest zbędny w firmie gdy prosi o
podwyżkę, lecz niezastąpiony gdy prosi o urlop" 

"Miroo" <miroo75@REMOVEIT.o2.pl> writes:

> "Piotr Dembiński" (pdemb@gazeta.pl) napisał(a):
>> "Miroo" <miroo75@REMOVEIT.o2.pl> writes:
>>> A.L. (alewando@kapturek62.com) napisał(a):
>>>> Mamy 10 milionow liczb integer w pamieci. Jak jest najszybszy
>>>> sposob zeny znalezc 5 najwieksza?
>> [...]
>>> A jakie jest prawidłowe rozwiązanie?
>> Najpierw trzeba spytać, czy te liczby są posortowane.
>
> Skoro nie było zaznaczone w zadaniu tzn że nie były.

Tia, poza tym nie odpowiada się pytaniem na pytanie.

> Przy posortowanych nie ma w zasadzie  mowy o jakimkolwiek
> zadaniu i "naszybszym sposobie".

Jak nieposortowane, to tworzysz pięcioelementowy kopiec z najmniejszą
na szczycie i porównujesz każdą liczbę z badanej tablicy z liczbą,
która znajduje się na szczycie kopca.  Jak jest większa 
od najmniejszej z kopca, to wyrzucasz z kopca dotychczasową 
najmniejszą i dodajesz do kopca liczbę, która ją wyrzuciła.
Na końcu bierzesz liczbę znajdującą się na szczycie kopca.

Sięgnąłem do mądrej książki i wyszło mi, że, przy założeniu 
najgorszego przypadku, rozwiązanie tego problemu wymaga
10mln operacji porównania dwu liczb całkowitych plus lg5 * 10mln 
operacji porównania potrzebnych na przebudowanie pięcioelementowego
kopca.

-- 
http:// www.piotr.dembiński.prv.pl

Sektor van Skijlen (ethouris@pl.wp.spamu.lubie.nie.invalid)
napisał(a):
> Moim zdaniem najsensowniejszym sposobem jest zapamiętywać 5
> ostatnich liczb z analizy. Trzymać coś w rodzaju ograniczonej
> kolejki 5 elementów (ograniczonej, tzn. jak się doda nowy element,
> to ostatni w kolejce wylatuje), jak się znajdzie liczbę większą od
> tej na szczycie, to spuszczamy wszystko o jeden, a znalezioną
> liczbę umieszczamy na szczycie. Jako wynik zwracamy liczbę na
> samym dole.

Ooops, błąd - nie zauważyłem wcześniej.
Nie można porównywać tylko najwyższej liczby.

-- 
Pozdrawiam
Miroo
Teoria względności: "Pracownik jest zbędny w firmie gdy prosi o
podwyżkę, lecz niezastąpiony gdy prosi o urlop" 

Dnia Wed, 16 Nov 2005 14:57:50 +0100, Miroo skrobie:
> Sektor van Skijlen (ethouris@pl.wp.spamu.lubie.nie.invalid)
> napisał(a):

> >> a) przelecieć raz tablicę tych liczb tworząc tabliczkę pięciu
> >> największych i przeglądając ją prawie 10 milionów razy (w
> >> większości przypadków nie całą, przy losowym rozrzucie liczb)

> > Moim zdaniem najsensowniejszym sposobem jest zapamiętywać 5
> > ostatnich liczb z analizy. Trzymać coś w rodzaju ograniczonej
> > kolejki 5 elementów (ograniczonej, tzn. jak się doda nowy element,
> > to ostatni w kolejce wylatuje), jak się znajdzie liczbę większą od
> > tej na szczycie, to spuszczamy wszystko o jeden, a znalezioną
> > liczbę umieszczamy na szczycie. Jako wynik zwracamy liczbę na
> > samym dole.

> Czyli zgadzasz się z moim pomysłem a)
> ok

Tak, ale zrobiłem dodatkowo babola: liczby w tej kolejce też muszą być
posortowane. Czyli napotkanie liczby większej od tego, co jest na szczycie
powinno dodać do zbiornika, ale musi wylecieć najmniejsza liczba. Na końcu
zwracamy najmniejszą z nich.

-- 
//  _    ___         Michal "Sektor" Malecki <sektor(whirl)kis.p.lodz.pl>
\\ L_ |/ `|  /^\ ,()                         <ethourhs(O)wp.pl>
// \_ |\  \/ \_/ /\ C++ bez cholesterolu: http://www.intercon.pl/~sektor/cbx
"I am allergic to Java because programming in Java reminds me casting spells"

"Piotr Dembiński" (pdemb@gazeta.pl) napisał(a):
>>> Najpierw trzeba spytać, czy te liczby są posortowane.
>> Skoro nie było zaznaczone w zadaniu tzn że nie były.
> Tia, poza tym nie odpowiada się pytaniem na pytanie.

A to to to.. A poza tym "Nie garb się!" :)

>> Przy posortowanych nie ma w zasadzie  mowy o jakimkolwiek
>> zadaniu i "naszybszym sposobie".
> Jak nieposortowane, to tworzysz pięcioelementowy kopiec z
[..]

I to miałem na myśli w moim rozwiązaniu...

> kopca. Sięgnąłem do mądrej książki i wyszło mi, że, przy założeniu
> najgorszego przypadku, rozwiązanie tego problemu wymaga
> 10mln operacji porównania dwu liczb całkowitych plus lg5 * 10mln
> operacji porównania potrzebnych na przebudowanie pięcioelementowego
> kopca.

...ale ty tak ładnie to opisałeś i poparłeś literaturą :)

-- 
Pozdrawiam
Miroo
Teoria względności: "Pracownik jest zbędny w firmie gdy prosi o
podwyżkę, lecz niezastąpiony gdy prosi o urlop" 

"Miroo" <miroo75@REMOVEIT.o2.pl> wrote:

> > Mamy 10 milionow liczb integer w pamieci. Jak jest najszybszy sposob
> > zeny znalezc 5 najwieksza?
>
> Jaki? Pytam z ciekawości.

Zadanie:

Jaka jest _minimalna_ liczba porownan ? Wartosc dokladna poprosze, bez
oszacowan :-)

[Uwaga - dowod jest duzo trudniejszy niz samo rozwiazanie]


mp

Dnia Wed, 16 Nov 2005 15:33:48 +0100, Michal Przybylek skrobie:
> "Miroo" <miroo75@REMOVEIT.o2.pl> wrote:

> > > Mamy 10 milionow liczb integer w pamieci. Jak jest najszybszy sposob
> > > zeny znalezc 5 najwieksza?
> >
> > Jaki? Pytam z ciekawości.

> Zadanie:

> Jaka jest _minimalna_ liczba porownan ? Wartosc dokladna poprosze, bez
> oszacowan :-)

Istnieje taka możliwa sytuacja, że dla danego elementu tablicy zostanie
porównana tylko ze szczytem stosu, a następnie zaakceptowana lub odrzucona.
Jeśli zostanie zaakceptowana, to spycha pozostałe w dół. Nie widzę tu żadnego
innego porównania (poza ewentualnie sprawdzeniem, czy doszliśmy do końca
zbiornika). Ani, szczerze mówiąc, innych możliwych sytuacji.

Poza tym nie miałem racji w poprzednim poście (tak mnie tylko tknęło dla
bezpieczństwa), że trzeba będzie pilnować sortowania. Jeśli liczba dostanie
się na szczyt kolejki, to znaczy, że jest większa od szczytu, więc liczby będą
tak czy siak posortowane.

-- 
//  _    ___         Michal "Sektor" Malecki <sektor(whirl)kis.p.lodz.pl>
\\ L_ |/ `|  /^\ ,()                         <ethourhs(O)wp.pl>
// \_ |\  \/ \_/ /\ C++ bez cholesterolu: http://www.intercon.pl/~sektor/cbx
"I am allergic to Java because programming in Java reminds me casting spells"

Sektor van Skijlen (ethouris@pl.wp.spamu.lubie.nie.invalid)
napisał(a):
> Istnieje taka możliwa sytuacja, że dla danego elementu tablicy
> zostanie porównana tylko ze szczytem stosu, a następnie
> zaakceptowana lub odrzucona. Jeśli zostanie zaakceptowana, to
> spycha pozostałe w dół. Nie widzę tu żadnego innego porównania
> (poza ewentualnie sprawdzeniem, czy doszliśmy do końca zbiornika).
> Ani, szczerze mówiąc, innych możliwych sytuacji. Poza tym nie
> miałem racji w poprzednim poście (tak mnie tylko tknęło dla
> bezpieczństwa), że trzeba będzie pilnować sortowania. Jeśli liczba
> dostanie się na szczyt kolejki, to znaczy, że jest większa od
> szczytu, więc liczby będą tak czy siak posortowane.

Chyba cię wcześniej źle zrozumiałem - czy liczba "na szczycie"
stosu jest największą w tym stosie czy najmniejszą?
Bo jeśli największą to źle, bo "zgubisz" liczby mniejsze niż
ta największa a większe niż któraś z pozostałych.
Jeśli "na szczycie" jest najmniejsza liczba ze stosu to
nie ma z kolei mowy o spychaniu pozostałych ale o wejściu
na jej miejsce (a potem porównywaniu z następnymi liczbami
w kopcu i ewntualnym przesuwaniu, żeby zachować sortowanie).

-- 
Pozdrawiam
Miroo
Teoria względności: "Pracownik jest zbędny w firmie gdy prosi o
podwyżkę, lecz niezastąpiony gdy prosi o urlop" 

Dnia Wed, 16 Nov 2005 16:04:31 +0100, Miroo skrobie:
> Sektor van Skijlen (ethouris@pl.wp.spamu.lubie.nie.invalid)
> napisał(a):
> > Istnieje taka możliwa sytuacja, że dla danego elementu tablicy
> > zostanie porównana tylko ze szczytem stosu, a następnie
> > zaakceptowana lub odrzucona. Jeśli zostanie zaakceptowana, to
> > spycha pozostałe w dół. Nie widzę tu żadnego innego porównania
> > (poza ewentualnie sprawdzeniem, czy doszliśmy do końca zbiornika).
> > Ani, szczerze mówiąc, innych możliwych sytuacji. Poza tym nie
> > miałem racji w poprzednim poście (tak mnie tylko tknęło dla
> > bezpieczństwa), że trzeba będzie pilnować sortowania. Jeśli liczba
> > dostanie się na szczyt kolejki, to znaczy, że jest większa od
> > szczytu, więc liczby będą tak czy siak posortowane.

> Chyba cię wcześniej źle zrozumiałem - czy liczba "na szczycie"
> stosu jest największą w tym stosie czy najmniejszą?
> Bo jeśli największą to źle, bo "zgubisz" liczby mniejsze niż
> ta największa a większe niż któraś z pozostałych.
> Jeśli "na szczycie" jest najmniejsza liczba ze stosu to
> nie ma z kolei mowy o spychaniu pozostałych ale o wejściu
> na jej miejsce (a potem porównywaniu z następnymi liczbami
> w kopcu i ewntualnym przesuwaniu, żeby zachować sortowanie).

Aha, czyli w efekcie mój sposób jest całkiem do chrzanu ;) To oznacza, że
trzeba wrzucać każdą liczbę do kolejki i w ogóle nie porównywać.

A minimalna liczba porównań jest taka, jakiej potrzebuje kolejka do utrzymania
sortowności.

-- 
//  _    ___         Michal "Sektor" Malecki <sektor(whirl)kis.p.lodz.pl>
\\ L_ |/ `|  /^\ ,()                         <ethourhs(O)wp.pl>
// \_ |\  \/ \_/ /\ C++ bez cholesterolu: http://www.intercon.pl/~sektor/cbx
"I am allergic to Java because programming in Java reminds me casting spells"

"Michal Przybylek" <mrp@neostrada.pl> writes:

> "Miroo" <miroo75@REMOVEIT.o2.pl> wrote:
>
>> > Mamy 10 milionow liczb integer w pamieci. Jak jest najszybszy
>> > sposob zeny znalezc 5 najwieksza?
>>
>> Jaki? Pytam z ciekawości.
>
> Zadanie:
>
> Jaka jest _minimalna_ liczba porownan ? 

10 mln minus pięć plus to, co potrzebne by stwierdzić, że pierwsze
pięć liczb w tablicy tworzy potrzebny kopiec.

> Wartosc dokladna poprosze, bez oszacowan :-)

Dokładnie to będzie 10^6 - 5 + 4.

> [Uwaga - dowod jest duzo trudniejszy niz samo rozwiazanie]

Trzeba przynajmniej raz porównać wybraną liczbę z pozostałymi.

-- 
http://www.piotr.dembiński.prv.pl

"Miroo" <miroo75@REMOVEIT.o2.pl> writes:

[...]

> ...ale ty tak ładnie to opisałeś i poparłeś literaturą :)

Bo nie pamiętałem, jakie złożoności czasowe ma kopiec :>

Dnia Wed, 16 Nov 2005 16:39:56 +0100, Piotr Dembiński skrobie:
> > Jaka jest _minimalna_ liczba porownan ? 

> 10 mln minus pięć plus to, co potrzebne by stwierdzić, że pierwsze
> pięć liczb w tablicy tworzy potrzebny kopiec.

I co zrobisz jak już te liczby porównasz?

> > Wartosc dokladna poprosze, bez oszacowan :-)

> Dokładnie to będzie 10^6 - 5 + 4.

> > [Uwaga - dowod jest duzo trudniejszy niz samo rozwiazanie]

> Trzeba przynajmniej raz porównać wybraną liczbę z pozostałymi.

Przypominam, że co do zbioru liczb nie ma żadnych założeń. Również co do tego,
czy liczby się powtarzają.

Zatem jeśli masz w zbiorniku np. { 2 3 5 5 6 10 10 10 10 9 10 7 7 }, to wtedy
kolejka 5 liczb po zakończeniu przetwarzania musi zawierać { 10 10 10 10 10 }.

Czyli najprościej to albo wziąć pierwsze pięć liczb "jak leci", a potem każdą
wsadzać do zbioru, usuwając z niej najmniejszy element. Operacja wsadzania do
zbioru jest jedyną, w której stosuje się jakiekolwiek porównanie. W najlepszym
razie będzie się okazywało, że wsadzany element jest większy od największego,
więc po jednym porównaniu wyląduje na szczycie.

-- 
//  _    ___         Michal "Sektor" Malecki <sektor(whirl)kis.p.lodz.pl>
\\ L_ |/ `|  /^\ ,()                         <ethourhs(O)wp.pl>
// \_ |\  \/ \_/ /\ C++ bez cholesterolu: http://www.intercon.pl/~sektor/cbx
"I am allergic to Java because programming in Java reminds me casting spells"

Sektor van Skijlen (ethouris@pl.wp.spamu.lubie.nie.invalid)
napisał(a):
> najlepszym razie będzie się okazywało, że wsadzany element jest
> większy od największego, więc po jednym porównaniu wyląduje na
> szczycie.

A ja bym powiedział, że w najlepszym razie każdy następny
element jest mniejszy od najmniejszego w kopcu. Wtedy jest
tylko jedno porównanie dla każdej liczby i żadnego przesuwania
w kopcu (nie licząc pierwszych pięciu).

-- 
Pozdrawiam
Miroo
Teoria względności: "Pracownik jest zbędny w firmie gdy prosi o
podwyżkę, lecz niezastąpiony gdy prosi o urlop" 

Dnia Thu, 17 Nov 2005 11:47:59 +0100, Miroo skrobie:
> Sektor van Skijlen (ethouris@pl.wp.spamu.lubie.nie.invalid)
> napisał(a):
> > najlepszym razie będzie się okazywało, że wsadzany element jest
> > większy od największego, więc po jednym porównaniu wyląduje na
> > szczycie.

> A ja bym powiedział, że w najlepszym razie każdy następny
> element jest mniejszy od najmniejszego w kopcu. Wtedy jest
> tylko jedno porównanie dla każdej liczby i żadnego przesuwania
> w kopcu (nie licząc pierwszych pięciu).

Nie rozumiem, dlaczego akurat się upierasz, że najmniejszy.

Oczywiście to zależy od tego, jak jest zbudowany zbiornik realizujący kopiec.
Głównie on tu rzęzi na porównaniach.


-- 
//  _    ___         Michal "Sektor" Malecki <sektor(whirl)kis.p.lodz.pl>
\\ L_ |/ `|  /^\ ,()                         <ethourhs(O)wp.pl>
// \_ |\  \/ \_/ /\ C++ bez cholesterolu: http://www.intercon.pl/~sektor/cbx
"I am allergic to Java because programming in Java reminds me casting spells"

Sektor van Skijlen wrote:
> Dnia Thu, 17 Nov 2005 11:47:59 +0100, Miroo skrobie:
> 
>>Sektor van Skijlen (ethouris@pl.wp.spamu.lubie.nie.invalid)
>>napisał(a):
>>
>>>najlepszym razie będzie się okazywało, że wsadzany element jest
>>>większy od największego, więc po jednym porównaniu wyląduje na
>>>szczycie.
> 
>>A ja bym powiedział, że w najlepszym razie każdy następny
>>element jest mniejszy od najmniejszego w kopcu. Wtedy jest
>>tylko jedno porównanie dla każdej liczby i żadnego przesuwania
>>w kopcu (nie licząc pierwszych pięciu).
> 
> Nie rozumiem, dlaczego akurat się upierasz, że najmniejszy.

Nie najmniejszy, a mniejszy (bądź równy) od najmniejszego w kopcu. 
Algorytm Miroo zaczyna porównania zawsze od najmniejszego elementu 
kopca. Co po zapełnieniu kopca, eliminuje potrzebę jakiejkolwiek jego 
reorganizacji. W Twoim przypadku będzie, to niewiele, ale jednak większa 
praca (przesunięcie, nawet gdy to tylko przewiązanie węzłów) i 
odrzucenie ostatniego elemntu -- stąd zapewne mowa o lepszym razie.


piotr

Piotr Dembiński wrote:

>>>>Mamy 10 milionow liczb integer w pamieci. Jak jest najszybszy
>>>>sposob zeny znalezc 5 najwieksza?
>>
>>Zadanie:
>>
>>Jaka jest _minimalna_ liczba porownan ? 
> 
> Dokładnie to będzie 10^6 - 5 + 4.

Dokładnie, to 10^7 - 1. Zakładam, że literówka. ;)

I może nieco trudniejsze:

Jaka jest maksymalna konieczna liczba porównań ?


piotr

Dnia Thu, 17 Nov 2005 22:47:43 +0100, Piotr Kobzda skrobie:
> Sektor van Skijlen wrote:
> > Dnia Thu, 17 Nov 2005 11:47:59 +0100, Miroo skrobie:
> > 
> >>Sektor van Skijlen (ethouris@pl.wp.spamu.lubie.nie.invalid)
> >>napisał(a):
> >>
> >>>najlepszym razie będzie się okazywało, że wsadzany element jest
> >>>większy od największego, więc po jednym porównaniu wyląduje na
> >>>szczycie.
> > 
> >>A ja bym powiedział, że w najlepszym razie każdy następny
> >>element jest mniejszy od najmniejszego w kopcu. Wtedy jest
> >>tylko jedno porównanie dla każdej liczby i żadnego przesuwania
> >>w kopcu (nie licząc pierwszych pięciu).
> > 
> > Nie rozumiem, dlaczego akurat się upierasz, że najmniejszy.

> Nie najmniejszy, a mniejszy (bądź równy) od najmniejszego w kopcu. 
> Algorytm Miroo zaczyna porównania zawsze od najmniejszego elementu 
> kopca. Co po zapełnieniu kopca, eliminuje potrzebę jakiejkolwiek jego 
> reorganizacji. W Twoim przypadku będzie, to niewiele, ale jednak większa 
> praca (przesunięcie, nawet gdy to tylko przewiązanie węzłów) i 
> odrzucenie ostatniego elemntu -- stąd zapewne mowa o lepszym razie.

Nie rozumiem.

Co to znaczy "po zapełnieniu kopca" i dlaczego eliminuje to potrzebę jego
reorganizacji?

Można oczywiście robić tak, że wsadzamy do kopca wszystkie wartości i robimy
sortowanie częściowe. Ale czy to jest lepsze rozwiązanie to jest już sprawa
dyskusyjna.

-- 
//  _    ___         Michal "Sektor" Malecki <sektor(whirl)kis.p.lodz.pl>
\\ L_ |/ `|  /^\ ,()                         <ethourhs(O)wp.pl>
// \_ |\  \/ \_/ /\ C++ bez cholesterolu: http://www.intercon.pl/~sektor/cbx
"I am allergic to Java because programming in Java reminds me casting spells"

Sektor van Skijlen wrote:

>>Nie najmniejszy, a mniejszy (bądź równy) od najmniejszego w kopcu. 
>>Algorytm Miroo zaczyna porównania zawsze od najmniejszego elementu 
>>kopca. Co po zapełnieniu kopca, eliminuje potrzebę jakiejkolwiek jego 
>>reorganizacji. W Twoim przypadku będzie, to niewiele, ale jednak większa 
>>praca (przesunięcie, nawet gdy to tylko przewiązanie węzłów) i 
>>odrzucenie ostatniego elemntu -- stąd zapewne mowa o lepszym razie.
> 
> 
> Nie rozumiem.

Więc nieco się skup. :)

> 
> Co to znaczy "po zapełnieniu kopca" i dlaczego eliminuje to potrzebę jego
> reorganizacji?

Po zapełnieniu kopca oznacza zbudowanie kopca pięcioelementowego 
(przyjąłem po prostu, że kopiec buduję od zera). I to akurat [czyli 
zapełnienie kopca] potrzeby reorganizacji kopca nie eliminule. Tą 
[potrzebę] eliminuje założenie, że każdy dochodzący element [z tych 10^7 
- 5], jest mniejszy (bądź równy) od najmniejszego w kopcu.

A teraz wykreśl frazy w [...], naprawdę trudniej zrozumieć?

> 
> Można oczywiście robić tak, że wsadzamy do kopca wszystkie wartości i robimy
> sortowanie częściowe. Ale czy to jest lepsze rozwiązanie to jest już sprawa
> dyskusyjna.

A teraz to ja nie rozumiem. Skąd pomysł sortowania wszystkiego?


piotr

>> Można oczywiście robić tak, że wsadzamy do kopca wszystkie wartości i 
>> robimy
>> sortowanie częściowe. Ale czy to jest lepsze rozwiązanie to jest już 
>> sprawa
>> dyskusyjna.
> 
> A teraz to ja nie rozumiem. Skąd pomysł sortowania wszystkiego?

Tfuj, chciałem zapytać, nie o pomysł sortowania wszystkiego, a 
przechowywaia wszystkiego. Mówisz, ze sortujesz częściowo, więc na cóż 
Ci śmieci? No chyba, że masz na mysli to, że szybsze może być 
pozostawienie tego co jest podwiązane głębiej, od odwiązywania zbędnych 
elementów, tak? Wtedy, istotnie, sprawa może być dyskusyjna...


piotr

Dnia Fri, 18 Nov 2005 00:04:59 +0100, Piotr Kobzda skrobie:
> Sektor van Skijlen wrote:

> >>Nie najmniejszy, a mniejszy (bądź równy) od najmniejszego w kopcu. 
> >>Algorytm Miroo zaczyna porównania zawsze od najmniejszego elementu 
> >>kopca. Co po zapełnieniu kopca, eliminuje potrzebę jakiejkolwiek jego 
> >>reorganizacji. W Twoim przypadku będzie, to niewiele, ale jednak większa 
> >>praca (przesunięcie, nawet gdy to tylko przewiązanie węzłów) i 
> >>odrzucenie ostatniego elemntu -- stąd zapewne mowa o lepszym razie.
> > 
> > 
> > Nie rozumiem.

> Więc nieco się skup. :)

> > 
> > Co to znaczy "po zapełnieniu kopca" i dlaczego eliminuje to potrzebę jego
> > reorganizacji?

> Po zapełnieniu kopca oznacza zbudowanie kopca pięcioelementowego 
> (przyjąłem po prostu, że kopiec buduję od zera). I to akurat [czyli 
> zapełnienie kopca] potrzeby reorganizacji kopca nie eliminule. Tą 
> [potrzebę] eliminuje założenie, że każdy dochodzący element [z tych 10^7 
> - 5], jest mniejszy (bądź równy) od najmniejszego w kopcu.

Można to napisać krócej i bez stosowania prywatnych skrótów myślowych.

Po zapełnieniu kopca PIERWSZYMI PIĘCIOMA ELEMENTAMI, w najlepszym razie każdy
następny element będzie mniejszy od najmniejszego z nich, więc te pięć
elementów to już są te największe.

I to się zgadza.

> > Można oczywiście robić tak, że wsadzamy do kopca wszystkie wartości i robimy
> > sortowanie częściowe. Ale czy to jest lepsze rozwiązanie to jest już sprawa
> > dyskusyjna.

> A teraz to ja nie rozumiem. Skąd pomysł sortowania wszystkiego?

No jak gęś z prosięciem dosłownie.

Ja piszę "sortowanie częściowe", a ty na to "skąd pomysł sortowania
wszystkiego".

örnen klantö trofflön tööla...

-- 
//  _    ___         Michal "Sektor" Malecki <sektor(whirl)kis.p.lodz.pl>
\\ L_ |/ `|  /^\ ,()                         <ethourhs(O)wp.pl>
// \_ |\  \/ \_/ /\ C++ bez cholesterolu: http://www.intercon.pl/~sektor/cbx
"I am allergic to Java because programming in Java reminds me casting spells"

Dnia Fri, 18 Nov 2005 00:16:07 +0100, Piotr Kobzda skrobie:
> >> Można oczywiście robić tak, że wsadzamy do kopca wszystkie wartości i 
> >> robimy
> >> sortowanie częściowe. Ale czy to jest lepsze rozwiązanie to jest już 
> >> sprawa
> >> dyskusyjna.
> > 
> > A teraz to ja nie rozumiem. Skąd pomysł sortowania wszystkiego?

> Tfuj, chciałem zapytać, nie o pomysł sortowania wszystkiego, a 
> przechowywaia wszystkiego. Mówisz, ze sortujesz częściowo, więc na cóż 
> Ci śmieci? No chyba, że masz na mysli to, że szybsze może być 
> pozostawienie tego co jest podwiązane głębiej, od odwiązywania zbędnych 
> elementów, tak? Wtedy, istotnie, sprawa może być dyskusyjna...

Jest dyskusyjna, choć podejrzewam, że raczej to szybsze nie będzie.
Sama kwestia przydziału pamięci za każdym razem na nowo może nieźle zarzeźbić
system. Natomiast jeśli stosowalibyśmy alokator specjalizowany i to nawet z
ograniczonym buforem, narzut w tej kwestii będzie praktycznie żaden.

-- 
//  _    ___         Michal "Sektor" Malecki <sektor(whirl)kis.p.lodz.pl>
\\ L_ |/ `|  /^\ ,()                         <ethourhs(O)wp.pl>
// \_ |\  \/ \_/ /\ C++ bez cholesterolu: http://www.intercon.pl/~sektor/cbx
"I am allergic to Java because programming in Java reminds me casting spells"

Piotr Kobzda <pikob@gazeta.pl> writes:

> Piotr Dembiński wrote:
>
>>>>>Mamy 10 milionow liczb integer w pamieci. Jak jest najszybszy
>>>>>sposob zeny znalezc 5 najwieksza?
>>>
>>>Zadanie:
>>>
>>> Jaka jest _minimalna_ liczba porownan ?
>> Dokładnie to będzie 10^6 - 5 + 4.
>
> Dokładnie, to 10^7 - 1. Zakładam, że literówka. ;)
>
> I może nieco trudniejsze:
>
> Jaka jest maksymalna konieczna liczba porównań ?

 5 + 3 * (10^7 - 5)

---      ----------
(1)         (2)
     --------------
         (3)

(1) Liczba porównań potrzebna na zbudowanie kopca z pierwszych pięciu
    elementów tablicy w przypadku pesymistycznym.

(2) Liczba elementów, które pozostały w tablicy po odjęciu pierwszych
    pięciu, z których utworzono kopiec.

(3) W przypadku pesymistycznym każdy z pozostałych elementów tablicy
    trzeba porównać z trzema elementami kopca.