Article View: pl.comp.lang.c
Article #309379losowy element z QMap lub std:set
From: M.M.
Date: Fri, 11 Aug 2017 14:29
Date: Fri, 11 Aug 2017 14:29
33 lines
2274 bytes
2274 bytes
Szukam efektywnej metody wybierania losowego elementu z takich struktur jak w tytule: 1) QMap 2) std::set Obie struktury mają to do siebie, że są zaimplementowane jako drzewa poszukiwań binarnych. Drzewka te maja mechanizm wyważania, zdaje się że są to drzewa czerwono czarne. Zatem struktury z bosta: boost::container::flat_set nie mogę użyć, bo wstawianie (o ile się nie mylę) jest w czasie O(N). W QT ze struktury QMap próbowałem wybierać losowy element mniej/więcej w taki sposób: map.constBegin() + random() % map.size(); W std tak: i = set.cbegin(); std::advanced( i , random() % set.size() ); Obie metody w są koszmarnie wolne, zdaje się, że iterują po drzewku, czyli czas działania jest liniowy względem numeru elementu i jeszcze trochę zależy od głębokości drzewka. Jak można to zrobić efektywniej? Trzeba zakodzić swoje drzewo czerwono czarne? Jakbym zakodził swoje, to bym miał od razu na kiedyś statystyki pozycyjne... Pozdrawiam
Technical Details
Message-ID:
<3daf52db-2ca9-43fb-9ac4-fb0a5e010681@googlegroups.com>Path:
mbox-mo1.pugleaf.net!news-archive.icm.edu.pl!agh.edu.pl!news.agh.edu.pl!newsfeed2.atman.pl!newsfeed.atman.pl!goblin2!goblin.stu.neva.ru!weretis.net!feeder6.news.weretis.net!feeder.usenetexpress.com!feeder-in1.iad1.usenetexpress.com!border1.nntp.dca1.giganews.com!nntp.giganews.com!s6no263681qtc.1!news-out.google.com!i9ni180qte.0!nntp.google.com!s6no263678qtc.1!postnews.google.com!glegroupsg2000goo.googlegroups.com!not-for-mailShow Full Headers
Complete Article Headers
X-Received: by 10.129.56.66 with SMTP id f63mr9353902ywa.96.1502461777100; Fri, 11 Aug 2017 07:29:37 -0700 (PDT) X-Received: by 10.31.191.67 with SMTP id p64mr82006vkf.4.1502461777063; Fri, 11 Aug 2017 07:29:37 -0700 (PDT) Path: mbox-mo1.pugleaf.net!news-archive.icm.edu.pl!agh.edu.pl!news.agh.edu.pl!newsfeed2.atman.pl!newsfeed.atman.pl!goblin2!goblin.stu.neva.ru!weretis.net!feeder6.news.weretis.net!feeder.usenetexpress.com!feeder-in1.iad1.usenetexpress.com!border1.nntp.dca1.giganews.com!nntp.giganews.com!s6no263681qtc.1!news-out.google.com!i9ni180qte.0!nntp.google.com!s6no263678qtc.1!postnews.google.com!glegroupsg2000goo.googlegroups.com!not-for-mail Newsgroups: pl.comp.lang.c Date: Fri, 11 Aug 2017 07:29:36 -0700 (PDT) Complaints-To: groups-abuse@google.com Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=159.205.39.242; posting-account=xjvq9QoAAAATMPC2X3btlHd_LkaJo_rj NNTP-Posting-Host: 159.205.39.242 User-Agent: G2/1.0 MIME-Version: 1.0 Message-ID: <3daf52db-2ca9-43fb-9ac4-fb0a5e010681@googlegroups.com> Subject: losowy element z QMap lub std:set From: "M.M." <mmarszik@gmail.com> Injection-Date: Fri, 11 Aug 2017 14:29:37 +0000 Lines: 41 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit