Article View: pl.comp.lang.c
Article #309380Re: losowy element z QMap lub std:set
From: Wojciech Muła
Date: Sat, 12 Aug 2017 08:41
Date: Sat, 12 Aug 2017 08:41
37 lines
2705 bytes
2705 bytes
On Friday, August 11, 2017 at 4:29:38 PM UTC+2, M.M. wrote: > 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... Wepnij własny alokator do std::map, niech on sobie trzyma liniową strukturę danych. I wtedy random robisz na tej strukturze. w.
Technical Details
Message-ID:
<928d2ead-1810-493c-b73d-e84c3b3775f9@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!peer01.am4!peer.am4.highwinds-media.com!peer01.iad!feed-me.highwinds-media.com!news.highwinds-media.com!w51no586835qtc.0!news-out.google.com!i9ni321qte.0!nntp.google.com!s6no588400qtc.1!postnews.google.com!glegroupsg2000goo.googlegroups.com!not-for-mailReferences:
<3daf52db-2ca9-43fb-9ac4-fb0a5e010681@googlegroups.com>Show Full Headers
Complete Article Headers
X-Received: by 10.176.78.236 with SMTP id x44mr11338465uah.22.1502527270683; Sat, 12 Aug 2017 01:41:10 -0700 (PDT) X-Received: by 10.31.154.20 with SMTP id c20mr111827vke.5.1502527270630; Sat, 12 Aug 2017 01:41:10 -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!peer01.am4!peer.am4.highwinds-media.com!peer01.iad!feed-me.highwinds-media.com!news.highwinds-media.com!w51no586835qtc.0!news-out.google.com!i9ni321qte.0!nntp.google.com!s6no588400qtc.1!postnews.google.com!glegroupsg2000goo.googlegroups.com!not-for-mail Newsgroups: pl.comp.lang.c Date: Sat, 12 Aug 2017 01:41:10 -0700 (PDT) In-Reply-To: <3daf52db-2ca9-43fb-9ac4-fb0a5e010681@googlegroups.com> Complaints-To: groups-abuse@google.com Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=37.47.133.127; posting-account=VFwkXwoAAADdT4-lLKRZrMYkTjizGoyn NNTP-Posting-Host: 37.47.133.127 References: <3daf52db-2ca9-43fb-9ac4-fb0a5e010681@googlegroups.com> User-Agent: G2/1.0 MIME-Version: 1.0 Message-ID: <928d2ead-1810-493c-b73d-e84c3b3775f9@googlegroups.com> Subject: Re: losowy element z QMap lub std:set From: Wojciech Muła <wojciech_mula@poczta.onet.pl> Injection-Date: Sat, 12 Aug 2017 08:41:10 +0000 X-Received-Body-CRC: 1814231790 X-Received-Bytes: 2782 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit