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