Re: zadanie z netu - Grupy dyskusyjne w eGospodarka.pl

eGospodarka.pl › Grupy › pl.comp.programming › zadanie z netu › Re: zadanie z netu

Path: news-archive.icm.edu.pl!agh.edu.pl!news.agh.edu.pl!news.cyf-kr.edu.pl!news.nask
.pl!news.nask.org.pl!news.unit0.net!border1.nntp.ams2.giganews.com!border3.nntp
.ams.giganews.com!Xl.tags.giganews.com!border1.nntp.ams.giganews.com!nntp.gigan
ews.com!local2.nntp.ams.giganews.com!nntp.brightview.co.uk!news.brightview.co.u
k.POSTED!not-for-mail
NNTP-Posting-Date: Sat, 30 Mar 2013 12:39:33 -0500
From: Roman W <b...@g...pl>
Newsgroups: pl.comp.programming
Subject: Re: zadanie z netu
Date: Sat, 30 Mar 2013 17:39:31 +0000
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
In-Reply-To: <o...@a...home>
References: <2...@g...com>
<0...@g...com>
<kj047e$kbo$1@node1.news.atman.pl> <kj1535$k5f$1@mx1.internetia.pl>
<kj1o8h$mg9$1@node2.news.atman.pl> <kj2av2$go4$1@mx1.internetia.pl>
<kj2hof$gmf$1@node2.news.atman.pl>
<8...@g...com>
<1...@g...com>
<c...@g...com>
<9...@g...com>
<7...@g...com>
<0...@g...com>
<7...@g...com>
<a...@n...plus.net>
<5...@g...com>
<a...@n...plus.net>
<0...@g...com>
<a...@n...plus.net>
<o...@a...home>
Message-ID: <a...@n...plus.net>
User-Agent: Groundhog Newsreader for Android
Lines: 28
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-CUeLXK50gWBJu8IANwvMjrCDwUqnYLsjcTa+YZQuLQcV8kAPw2vrBmdxxCwum4Goi/DOEHDN
EQj43LJ!xL63D3/e0WqQtF94EA7xgowGZxynC30P5zncdBqfq5pU8wyzXgb+eHjXVwCVYwt6bTgj
vJaTpg9j!ODerm6ibO2R3YPw4Fg==
X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly
X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly
X-Postfilter: 1.3.40
X-Original-Bytes: 2786
Xref: news-archive.icm.edu.pl pl.comp.programming:202399
[ ukryj nagłówki ]
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