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!newsfeed.fsmpi.rwth-aachen.de!feeder1-2.pro
xad.net!proxad.net!feeder2-2.proxad.net!nx01.iad01.newshosting.com!newshosting.
com!newsfeed.neostrada.pl!unt-exc-01.news.neostrada.pl!unt-spo-a-02.news.neostr
ada.pl!news.neostrada.pl.POSTED!not-for-mail
Content-Type: text/plain; charset=iso-8859-2; format=flowed; delsp=yes
Newsgroups: pl.comp.programming
Subject: Re: zadanie z netu
References: <2...@g...com>
<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>
<a...@n...plus.net>
<kj7b71$mme$1@mx1.internetia.pl>
Date: Sat, 30 Mar 2013 19:33:13 +0100
MIME-Version: 1.0
Content-Transfer-Encoding: Quoted-Printable
From: "Jordan Szubert" <u...@j...us.to>
Organization: HELL inc.
Message-ID: <o...@a...home>
User-Agent: Opera Mail/12.14 (Win32)
Lines: 28
NNTP-Posting-Host: 83.10.198.176
X-Trace: 1364668395 unt-rea-a-02.news.neostrada.pl 1250 83.10.198.176:59143
X-Complaints-To: a...@n...neostrada.pl
Xref: news-archive.icm.edu.pl pl.comp.programming:202401
[ ukryj nagłówki ]
Dnia 30-03-2013 o 19:25:40 Michoo <m...@v...pl> napisał(a):

> On 30.03.2013 18:39, Roman W wrote:
>>
>> Nada sie i pewnie w praktyce zadziala, ale wymaga O(log N) pamieci.
>> Mozna to zrobic w O(1).
>
> Wybierasz pierwszą. W każdym kroku z prawdopodobieństwem P zależącym od
> ilości wczytanych linii wybierasz bieżącą a z (1-P) zostajesz przy
> poprzednim wyborze. Tylko trzeba mieć dobry generator dla takich
> sekwencji i nie nadziać się na zaokrąglenia.

moje prawie wszytkie losowania robi dla zakresu 256, więc o zaokrąglenia
nie trzeba się martwić, i pewnie szybciej działa, robiąc ok. n/255
prostych losowań, a nie n trudniejszych

--
Jordan Szubert