🚀 go-pugleaf

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"