[C++] 50 random elementen uit unordered_map

[Olaf van der Spek]

Ik heb een unordered_map met meer dan 50 elementen en wil daar willekeurig 50 elementen uithalen. Hoe doe ik dit het beste?
Performance is belangrijk, de grootte van de containers ligt tussen de 0 en 10000 elementen en het trucje moet tot 10000x per seconde herhaalt worden.

Momenteel kopieër ik de elementen naar een vector en haal daar dan 50 elementen uit maar dat is niet echt efficient.

Oh ja, in sommige gevallen wordt de input container nog gefilterd, dus dan doen niet alle elementen mee.

Ik zou 50 random indexes in een vector kunnen stoppen, die sorteren en dan de originele unordered_map uitlezen maar weet niet of dat veel beter is en of het nog beter kan.

C++:

std::vector<std::array<char, 6>> candidates;
candidates.reserve(peers.size());
// populate candidates from unordered_map
size_t c = 50;
std::string d;
d.reserve(300);
if (candidates.size() > c)
{
    while (c--)
    {
        int i = rand() % candidates.size();
        d.append(candidates[i].begin(), candidates[i].end());
        candidates[i] = candidates.back();
        candidates.pop_back();
    }
}
else
{
    for (auto& i : candidates)
        d.append(i.begin(), i.end());
}
return d;

Het type van de elementen is std::array<char, 6> om het wat makkelijker te maken.
Het is een IP adres / port combi.

[ Voor 5% gewijzigd door Olaf van der Spek op 06-03-2015 12:03 ]

[PrisonerOfPain]

offtopic:
Waarom sla je een IP adres als een std::array<char, 6> op ipv een u32?

Wat is het volledige type van peers?

Also, wellicht is het sneller om std::advance(peers.begin(), rand() % peers.size()) te gebruiken ipv element te kopiëren.

[MSalters]

Je alternatief is inderdaad beter: genereeer 50 random unieke indices, loop door de map heen en selecteer de 50 overeenkomende elementen.

Om die 50 unieke indices te generen is het waarschijnlijk handig om er 50 random te genereren, te sorteren, en dan met unique te filteren. Je hebt er dan mogelijk 1 of 2 te kort, dus die moet je niuew genereren, met lower_bound in je sorted array opzoeken (het zou weer een dubbele kunnen zijn) en zoniet inserten achter die lower_bound (dit houdt de array sorted)

Vervolgens kun je met die 50 sorted indices door je map lopen en de elementen eruit kopieren.

[Olaf van der Spek]

PrisonerOfPain schreef op vrijdag 06 maart 2015 @ 12:41:

offtopic:
Waarom sla je een IP adres als een std::array<char, 6> op ipv een u32?

Port past dan niet en het IP adres is big endian, dus niet echt een u32.

Wat is het volledige type van peers?

C++:

struct t_peer
{
        long long downloaded;
        long long uploaded;
        time_t mtime = 0;
        int uid;
        short port;
        bool left;
        std::array<char, 20> peer_id;
};

typedef boost::unordered_map<peer_key_c, t_peer> t_peers;

https://code.google.com/p...runk/xbt/Tracker/server.h

Also, wellicht is het sneller om std::advance(peers.begin(), rand() % peers.size()) te gebruiken ipv element te kopiëren.

Zo werkt advance niet. std::next werkt zo wel.
Voor een peer zou dat werken maar voor meerdere wordt het lastig.

[ Voor 5% gewijzigd door Olaf van der Spek op 06-03-2015 14:01 ]

[Olaf van der Spek]

MSalters schreef op vrijdag 06 maart 2015 @ 13:42:
Om die 50 unieke indices te generen is het waarschijnlijk handig om er 50 random te genereren, te sorteren, en dan met unique te filteren. Je hebt er dan mogelijk 1 of 2 te kort, dus die moet je niuew genereren, met lower_bound in je sorted array opzoeken (het zou weer een dubbele kunnen zijn) en zoniet inserten achter die lower_bound (dit houdt de array sorted)

Als je toevallig 1000 van de 1001 elementen moet hebben zou dit nog wel eens langzaam kunnen zijn.

Is het niet beter de tweede keer % (size - 1) te nemen, de derde keer % (size - 2), enz?
Dan sorteren en bij elk element de positie optellen.
Dit voorkomt volgens mij ook dubbele.

[Soultaker]

Is de unordered_map vast of variabel? Met andere woorden: pak je 10,000 keer 50 elementen uit dezelfde verzameling, of is die verzameling ook steeds verschillend?

[Olaf van der Spek]

Het is code van een BitTorrent tracker. Elke torrent heeft zo'n peers map, die map wordt elke keer geupdate.
Het aantal torrents is tot 1m, het totaal aantal peers tot zo'n 10m.

[ Voor 27% gewijzigd door Olaf van der Spek op 06-03-2015 14:17 ]

[Soultaker]

Aha, dan maakt het ook niet uit of het helemaal uniform random is, of wel?

[Olaf van der Spek]

Nee, het hoeft niet perfect uniform random te zijn. Dan was rand() sowieso niet zo'n beste keuze.

Is dit geen 'bekend' probleem met een standaard oplossing eigenlijk?

[ Voor 31% gewijzigd door Olaf van der Spek op 06-03-2015 14:28 ]

[PrisonerOfPain]

Olaf van der Spek schreef op vrijdag 06 maart 2015 @ 14:00:
[...]

Port past dan niet en het IP adres is big endian, dus niet echt een u32.

Port sla je dan ook meestal apart op, verder is voor de endian conversion std::htonl.

https://code.google.com/p...runk/xbt/Tracker/server.h

Ik was vooral eigenlijk benieuwed of je de keys ergens anders nog in een list opsloeg maar blijkbaar niet. Wat je overigens ook nog zou kunnen overwegen is ipv een std::unordered_map<key, value> een std::vector<key> en std::vector<value> te gebruiken.

Zo werkt advance niet. std::next werkt zo wel.
Voor een peer zou dat werken maar voor meerdere wordt het lastig.

std::advance en std::next zijn vrijwel gelijk, maar je hebt gelijk, std::next is voor forward iterators die je van unordered_map terug krijgt.

[Olaf van der Spek]

PrisonerOfPain schreef op vrijdag 06 maart 2015 @ 14:28:
Ik was vooral eigenlijk benieuwed of je de keys ergens anders nog in een list opsloeg maar blijkbaar niet. Wat je overigens ook nog zou kunnen overwegen is ipv een std::unordered_map<key, value> een std::vector<key> en std::vector<value> te gebruiken.

En dan? Een soort flat_map lijkt me dat, maar insert en delete zijn dan duurder.

std::advance en std::next zijn vrijwel gelijk, maar je hebt gelijk, std::next is voor forward iterators die je van unordered_map terug krijgt.

De iterator category is niet relevant.

[PrisonerOfPain]

Olaf van der Spek schreef op vrijdag 06 maart 2015 @ 14:32:
[...]

En dan? Een soort flat_map lijkt me dat, maar insert en delete zijn dan duurder.

Delete doe je dan niet met erase, maar met swap-with-last + pop_back, en insert word push_back. Kortom constant time / constant time amortized respectievelijk.

[Soultaker]

Okee, stel dat je je peers in een std::set hebt zitten. Dan kun je een vector van iterators bouwen, en daarin kun je efficient samplen op deze manier:

C++:

for (int i = 0; i < samples; ++i) {
  swap(peers[i], peers[i + rand()%(total - i)]);
}
// peers[0..samples) bevat nu `samples` random samples.

Het lastige deel is het bijhouden van de vector als je peers toevoegt of verwijdert. Toevoegen is makkelijk: je kunt een element toevoegen aan de set en de corresponderende iterator aan het eind van de vector pushen. Verwijderen is ook makkelijk: je kunt het element uit de set verwijderen en de corresponderende iterator swappen met de laatste in de vector. Om dit efficiënt te doen, moet je set niet alleen peers bevatten, maar ook een index in de vector met iterators (het wordt dan dus een set<pair<size_t, Peer>> ofzo).

Gevolg is wel dat je bij elke swap (dus ook bij de swaps die je doet om te samplen!) de indices in de set moet updaten.

Dit is onder de aanname dat iterators in een std::set niet geïnvalideerd worden door wijzigingen in de set. Ik weet uit m'n hoofd niet of dat ook voor std::unordered_set geldt.

edit:
Mogelijk heeft PoP hetzelfde idee als ik. (Ik heb niet alle details gelezen.)

edit2:
Je kunt niet simpelweg een set<pair<size_t,Peer>> gebruiken want dan is de index onderdeel van de key waarop elementen vergeleken worden. Je moet dan dus een custom comparator schrijven die alleen naar de Peer kijkt, en niet naar z'n index. Immers is het de bedoeling dat de index aangepast kan worden zonder dat structuur van de set in de war gegooid wordt.

[ Voor 31% gewijzigd door Soultaker op 06-03-2015 15:27 ]

[.oisyn]

PrisonerOfPain schreef op vrijdag 06 maart 2015 @ 14:28:
std::advance en std::next zijn vrijwel gelijk, maar je hebt gelijk, std::next is voor forward iterators die je van unordered_map terug krijgt.

std::advance verwacht een reference naar een iterator die hij aanpast. std::next geeft de nieuwe iterator als return-waarde

Soultaker schreef op vrijdag 06 maart 2015 @ 14:37:
Dit is onder de aanname dat iterators in een std::set niet geïnvalideerd worden door wijzigingen in de set. Ik weet uit m'n hoofd niet of dat ook voor std::unordered_set geldt.

Ja dat is zo

[ Voor 28% gewijzigd door .oisyn op 06-03-2015 14:50 ]

[PrisonerOfPain]

Soultaker schreef op vrijdag 06 maart 2015 @ 14:37:
edit:
Mogelijk heeft PoP hetzelfde idee als ik. (Ik heb niet alle details gelezen.)

Mijn idee is vij eenvoudig ipv een unordered_set gebruik je dit:

C++:

std::vector<peer_key_c> Keys;
std::vector<peer_value_whatever> Values;

// random selectie, doe wat je wil, gewoon een random index genereren is nu vrij eenvoudig
uint idx = rand() % Keys.size();
const auto &k = Keys[idx];
const auto &v = Values[idx];

// insert
Keys.push_back(k);
Value.push_back(v);

assert(Keys.size() == Values.size());

// delete-by-idx
if(Keys.size() > 1)
{
    std::swap(Keys[idx], Keys.back());
    std::swap(Values[idx], Values.back());
}

Keys.pop_back();
Value.pop_back();

assert(Keys.size() == Value.size());

[.oisyn]

Hoe ga je dan een key opzoeken? Linear search?

[Olaf van der Spek]

PrisonerOfPain schreef op vrijdag 06 maart 2015 @ 14:50:
// random selectie, doe wat je wil, gewoon een random index genereren is nu vrij eenvoudig
uint idx = rand() % Keys.size();
const auto &k = Keys[idx];
const auto &v = Values[idx];

Eén random sample was al vrij eenvoudig.

Soultaker schreef op vrijdag 06 maart 2015 @ 14:37:
edit2:
Je kunt niet simpelweg een set<pair<size_t,Peer>> gebruiken want dan is de index onderdeel van de key waarop elementen vergeleken worden. Je moet dan dus een custom comparator schrijven die alleen naar de Peer kijkt, en niet naar z'n index. Immers is het de bedoeling dat de index aangepast kan worden zonder dat structuur van de set in de war gegooid wordt.

Set elementen zijn const. En peers is een map..

[ Voor 43% gewijzigd door Olaf van der Spek op 06-03-2015 15:31 ]

[Soultaker]

Waarop is je map gekeyt dan? (Daar gaat het uiteindelijk om.)

M'n hele verhaal gaat trouwens ook op voor std::map.

[Olaf van der Spek]

Een map wordt gebruikt zodat een peer snel te vinden is (zonder linear search).
Ik begrijp je verhaal, maar is je oplossing beter dan die van MSalters?

Er is nog een complicatie: soms moet maar een deel van de elementen worden gesampled.

[MSalters]

Olaf van der Spek schreef op vrijdag 06 maart 2015 @ 14:07:
[...]

Als je toevallig 1000 van de 1001 elementen moet hebben zou dit nog wel eens langzaam kunnen zijn.

Is het niet beter de tweede keer % (size - 1) te nemen, de derde keer % (size - 2), enz?
Dan sorteren en bij elk element de positie optellen.
Dit voorkomt volgens mij ook dubbele.

Nee. Als je een significante fractie nodig hebt, dan gebruik je weer een ander algoritme. Genereer de verzameling van indices 0..1000, roep `std::shuffle( )` op die verzameling, en neem de eerste N indices.

(En voor N > 500 gebruik je natuurlijk de inverse methode - 1000 van 1001 doe je door het ene element te picken wat je niet gebruikt.)

[Soultaker]

Olaf van der Spek schreef op vrijdag 06 maart 2015 @ 16:03:
Een map wordt gebruikt zodat een peer snel te vinden is (zonder linear search).
Ik begrijp je verhaal, maar is je oplossing beter dan die van MSalters?

Het is me ten eerste niet duidelijk hoe in MSalters' voorstel de 50 elementen uit de map gevist worden, en ten tweede leek de methode om 50 indices te genereren me niet heel efficiënt (ook vanwege de situatie die jij noemde: als je totaal dicht bij vijftig zit, duurt het lang voor je 50 unieke elementen gegenereerd hebt).

Mijn oplossing doet strikt N swaps om N elementen te vinden. Ik zie eigenlijk niet hoe het beter kan.

Er is nog een complicatie: soms moet maar een deel van de elementen worden gesampled.

Hoe is dat een complicatie?

[ Voor 17% gewijzigd door Soultaker op 06-03-2015 18:15 ]

[Caelorum]

.oisyn schreef op vrijdag 06 maart 2015 @ 14:51:
Hoe ga je dan een key opzoeken? Linear search?

Is dat zo'n groot probleem? als je data een goede layout heeft en het dan alsnog traag is kan je vrij eenvoudig wat extra threads pakken en het op meerdere cores gooien.

[Orphix]

Geïndexeerde toegang is niet mogelijk voor unordered_map (het is een forward iterator), dus je hebt alleen sequentiele toegang. Oftewel, als bij toeval de 'eerste', 'middelste' en 'laatste' elementen worden gekozen dan moet je hoe dan ook door de gehele set gaan (=worst case). Daarnaast zijn de elementen van een unordered_map niet opgeslagen in een aaneengesloten datablok zoals bij een vector dus sequentieel benaderen zal minder efficient zijn dan bij een vector. Wat de performance precies is, is afhankelijk van de hashtable implementatie en dit zal je echt moeten benchmarken.

Om de keys te kopieëren naar een vector zal ook eerst de gehele set moeten worden ingelezen, én je moet ook nog eens voor alle keys geheugen alloceren en een kopie maken, dus dat is tenminste net zo (in)efficient.

Omdat de unordered_map ook nog eens bij elke aanroep gewijzigd kan zijn biedt het daarnaast weinig voordelen om tussendoor testresultaten of state te cachen. Tenzij er een soort 'dirty flag' wordt bijgehouden dat aangeeft of er een mutatie is geweest.

Dan, de cijfers:
sizeof(t_peer) = 48 bytes
sizeof(peer_key_c) = 8 bytes

Bij 10.000 elementen telt dit op tot 480.000 + 80.000 = 560.000 bytes (560 kB). Dit past op moderne CPU's in de L2/L3 cache dus om hier op een cache-friendly manier een paar keer per seconde overheen te itereren zou vrij rap kunnen gaan. Maar nogmaals, dit is afhankelijk van de cache vriendelijkheid van de hashtable implementatie en dit zal je moeten benchmarken.

Maar.. als dit 10.000x per seconde gebeurt (!) dan beginnen de cijfers flink toe te nemen en heb je flink wat bandbreedte nodig. 560kB * 10.000 = 5600 mB/s = 5.6 gB/s. Dat is al een flink gedeelte van de maximale bandbreedte van bv een i5 core als je data uit main memory moet komen. En die theoretische cijfers zijn gebaseerd op perfecte throughput.

En dan is je cpu dus vrijwel continu bezig om enkel random peers te selecteren. Ik ben daarom wel benieuwd naar de reden dat dit zo frequent (10.000/s) moet gebeuren?

Om in te gaan op de oorspronlijke vraag, mijn suggestie zou zijn om van te voren 50 indices te generen en in een vector opslaan. Random als je unorderd_map relatief groot is, of via std::shuffle als je unordered_map relatief klein is, zoals MSalters opmerkte. De indices in de vector sorteren op aflopende volgorde. Vervolgens over de unordered_map itereren, een tellertje bijhouden, en als je tellertje gelijk is aan de laatste index uit je random populatie (back()) dan kopieer je dat element naar een vector (push_back). Vervolgens een pop_back() op je vector met gekozen indices, zodat je op zoek kan gaan naar het volgende element.

Je worst-case is dat je dan eenmalig over alle elementen gaat. Het is iets gunstiger als je grootste index kleiner is dan het aantal peers. Je hoeft dan immers de peers na de laatste index niet meer uit te lezen.

[MSalters]

Soultaker schreef op vrijdag 06 maart 2015 @ 18:13:
[...]
Het is me ten eerste niet duidelijk hoe in MSalters' voorstel de 50 elementen uit de map gevist worden

Ik doe de lineaire access van de unordered_set nadat ik de indices heb bepaald. Dus voor indices [5,9,10] zijn dat calls naar std::advance(5), std::advance(4) en std::advance(1).

Caelorum schreef op vrijdag 06 maart 2015 @ 19:32:
[...]

Is dat zo'n groot probleem? als je data een goede layout heeft en het dan alsnog traag is kan je vrij eenvoudig wat extra threads pakken en het op meerdere cores gooien.

De layout is hier een gegeven, een unordered_set (hashtable). Die kun je niet in O(1) partitioneren. Dat compliceert het opdelen in threads. Twee threads kan wel, je kunt van beide einden beginnen.

[ Voor 37% gewijzigd door MSalters op 07-03-2015 12:30 ]

[MSalters]

Orphix schreef op zaterdag 07 maart 2015 @ 11:49:
Het is iets gunstiger als je grootste index kleiner is dan het aantal peers. Je hoeft dan immers de peers na de laatste index niet meer uit te lezen.

Micro-optimalisatie. Met N=50 scheelt dat naar verwachting ~2%.

Maar gezien de berekeningen komt de vraag naar boven of die unordered_set wel de juiste keuze is. Het lijkt er op dat een vector een betere keuze was geweest. Keyed access is trager maar sampling is veel sneller.

[Soultaker]

MSalters schreef op zaterdag 07 maart 2015 @ 12:28:
Ik doe de lineaire access van de unordered_set nadat ik de indices heb bepaald. Dus voor indices [5,9,10] zijn dat calls naar std::advance(5), std::advance(4) en std::advance(1).

Juist, maar dan moet je gemiddeld toch alsnog de hele map door? Met 50 samples uit 10,000 elementen is dat niet bijster efficiënt; dan kun je nog beter direct een residue sampling methode toepassen (dus zonder eerst de indices te genereren).

Orphix schreef op zaterdag 07 maart 2015 @ 11:49:
Om in te gaan op de oorspronlijke vraag, mijn suggestie zou zijn om van te voren 50 indices te generen en in een vector opslaan. [..]
Je worst-case is dat je dan eenmalig over alle elementen gaat.

Dit is toch precies wat MSalters ook voorstelde?

Volgens mij stellen jullie allebei algoritmen met complexiteit O(totaal aantal peers) voor, terwijl mijn voorstel O(aantal samples) was. Met aantal samples << aantal peers lijkt mijn voorstel me dus strikt beter, tenzij je relatief zeldzaam samplet (in dat geval maakt het niet veel uit hoe je samplet, en moet je gewoon de efficiëntste datastructuur voor je set van peers gebruiken).

[ Voor 5% gewijzigd door Soultaker op 07-03-2015 13:34 ]

[Orphix]

MSalters schreef op zaterdag 07 maart 2015 @ 12:34:
[...]
Micro-optimalisatie. Met N=50 scheelt dat naar verwachting ~2%.

Zal inderdaad weinig schelen. Al is een early-return wel logisch om te doen.

Soultaker schreef op zaterdag 07 maart 2015 @ 13:31:
Dit is toch precies wat MSalters ook voorstelde?

Klopt. Heb het iets anders verwoord maar komt op hetzelfde neer (had ik misschien beter kunnen vermelden).

Volgens mij stellen jullie allebei algoritmen met complexiteit O(totaal aantal peers) voor, terwijl mijn voorstel O(aantal samples) was. Met aantal samples << aantal peers lijkt mijn voorstel me dus strikt beter, tenzij je relatief zeldzaam samplet (in dat geval maakt het niet veel uit hoe je samplet, en moet je gewoon de efficiëntste datastructuur voor je set van peers gebruiken).

Dit zou opgaan als peers een vector zou zijn. Maar in dit geval gaat het om een unordered_map. Je kunt deze map niet benaderen via een index, enkel via de key. Vandaar ook 'unordered'. En het key-type is hier geen integer, maar peer_key_c. In jouw voorbeeld zou je eerst alle key's moeten inlezen, vervolgens daar 50 uit selecteren en dán pas de unordered_map benaderen via de gekozen keys. En dat is ook de benadering van TS.

[Soultaker]

Bij mijn voorstel ga ik er vanuit dat je een vector met iterators bijhoudt naast de unordered_map met peers. Daardoor kun je efficient samplen uit de vector, zonder dat je daarbij de hele map uit hoeft te lezen. Operaties op de map (en de vector) worden wel iets kostbaarder doordat je tegelijkertijd de vector (en de map) moet updaten. Vandaar mijn opmerking dat dit vooral handig is als je relatief veel samplet.

[MSalters]

Soultaker schreef op zaterdag 07 maart 2015 @ 13:31:
[...]
Juist, maar dan moet je gemiddeld toch alsnog de hele map door? Met 50 samples uit 10,000 elementen is dat niet bijster efficiënt; dan kun je nog beter direct een residue sampling methode toepassen (dus zonder eerst de indices te genereren).

Het is onvermijdelijk dat je de hele map doorloopt, want je hebt geen random access tot het midden van de map. Met mijn methode doe je die iteratie nadat je de indices hebt bepaald, dus nog steeds eenmalig. Het voordeel is dat je niet alle elementen hoeft te kopieren.

[Soultaker]

MSalters schreef op zondag 08 maart 2015 @ 13:13:
Het is onvermijdelijk dat je de hele map doorloopt, want je hebt geen random access tot het midden van de map.

Als je een vector met iterators bijhoudt, heb je juist wél toegang tot midden in de map. Ik geloof dat we een beetje langs elkaar heen praten momenteel Misschien kan ik met een code-voorbeeld verduidelijken wat ik bedoel.

edit:

C++:

#include <algorithm>
#include <unordered_map>
#include <vector>
#include <utility>
#include "assert.h"

template<class Key, class Value>
class IndexedMap
{
public:
    typedef std::pair<size_t,Value> value_t;
    typedef std::unordered_map<Key, value_t> map_t;
    typedef std::pair<Key,Value> sample_t;
    typedef std::vector<sample_t> samples_t;

    void Add(const Key& key, const Value& value) {
        assert(map_.find(key) == map_.end());
        auto it = map_.insert({key, {0, value}}).first;
        it->second.first = index_.size();
        index_.push_back(it);
    }

    void Remove(const Key& key) {
        auto it = map_.find(key);
        assert(it != map_.end());
        Swap(it->second.first, index_.size() - 1);
        map_.erase(it);
        index_.pop_back();
    }

    Value Find(const Key& key) {
        auto it = map_.find(key);
        assert(it != map_.end());
        return it->second.second;
    }

    size_t Size() const { return index_.size(); }

    samples_t Sample(size_t n) {
        const size_t total = Size();
        assert(n <= total);
        samples_t samples;
        samples.reserve(n);
        for (size_t i = 0; i < n; ++i) {
            Swap(i, i + rand()%(total - i));
            samples.push_back({index_[i]->first, index_[i]->second.second});
        }
        return samples;
    }

private:
    void Swap(size_t i, size_t j) {
        if (i == j) return;
        std::swap(index_[i], index_[j]);
        std::swap(index_[i]->second.first, index_[j]->second.first);
    }

    std::vector<typename map_t::iterator> index_;
    map_t map_;
};

//
//  Test code follows.
//
 
#include <string>
#include <iostream>

int main() {
    IndexedMap<int,std::string> map;
    map.Add(7, "seven");
    map.Add(42, "the answer");
    map.Add(-5, "negative 5");
    map.Add(1337, "leet");
    map.Add(666, "beast");
    for (int n = 0; n < 10; ++n) {
        std::cout << "Three random samples:\n";a
        for (auto sample : map.Sample(3)) {
            std::cout << '\t' << sample.first << ':' << sample.second << '\n';
        }
    }
    map.Remove(42);
    map.Add(100, "hundred");
    map.Remove(666);
    std::cout << "\nRemoved 42 and 666. Added 100.\n\n";
    for (int n = 0; n < 10; ++n) {
        std::cout << "Three random samples:\n";
        for (auto sample : map.Sample(3)) {
            std::cout << '\t' << sample.first << ':' << sample.second << '\n';
        }
    }
}

IndexedMap combineert een unordered_map met een vector die als index fungeert. Map-operaties (zoals Add, Remove, Find) blijven O(1). Maar je kunt de elementen ook op positie benaderen via de index-vector, zodat je elementen kunt samplen in O(|samples|) tijd in plaats van O(total).

[ Voor 76% gewijzigd door Soultaker op 08-03-2015 14:36 ]

[.oisyn]

Caelorum schreef op vrijdag 06 maart 2015 @ 19:32:
[...]

Is dat zo'n groot probleem? als je data een goede layout heeft en het dan alsnog traag is kan je vrij eenvoudig wat extra threads pakken en het op meerdere cores gooien.

Is dat altijd hoe jij en optimalisatieprobleem tacklet? Gewoon meerdere threads ertegenaan gooien, ipv te kijken naar algoritmische complexiteit?

[Caelorum]

Als het eenvoudig en snel te doen is, ja ^^ pas als ook dat problemen oplevert kink ik verder.

[Orphix]

Soultaker schreef op zondag 08 maart 2015 @ 13:47:
Als je een vector met iterators bijhoudt, heb je juist wél toegang tot midden in de map.

Maar in dit specifieke geval is de map niet stabiel en dus kan (mag) je niet de iterators cachen. In een extreem geval zou de map bij de eerste sampling 10.000 peers kunnen bevatten, en bij de volgende sampling bijvoorbeeld 100 peers. Of 10.000 andere peers. En aangezien je niet weet wat er is gewijzigd moet je de map elke keer opnieuw lezen.

[Soultaker]

Orphix schreef op maandag 09 maart 2015 @ 09:08:
Maar in dit specifieke geval is de map niet stabiel en dus kan (mag) je niet de iterators cachen. In een extreem geval zou de map bij de eerste sampling 10.000 peers kunnen bevatten, en bij de volgende sampling bijvoorbeeld 100 peers. Of 10.000 andere peers. En aangezien je niet weet wat er is gewijzigd moet je de map elke keer opnieuw lezen.

Ik update de vector tegelijk met de map. Heb je m'n code überhaupt bekeken?

Zo nee, ga dat alsjeblieft eerst even doen. Zo ja, wijs maar aan wat er niet aan klopt. Voor de duidelijkheid: ik claim updates in O(1) en sampling O(|sample|).

[ Voor 12% gewijzigd door Soultaker op 09-03-2015 09:51 ]

[.oisyn]

Caelorum schreef op zondag 08 maart 2015 @ 20:49:
Als het eenvoudig en snel te doen is, ja ^^ pas als ook dat problemen oplevert kink ik verder.

Algoritmische complexiteit optimaliseren door simpelweg het gebruik van een andere container kost veel minder tijd en levert exponentieel meer op bij grote N

[Olaf van der Spek]

Soultaker schreef op vrijdag 06 maart 2015 @ 18:13:
Hoe is dat een complicatie?

Er zijn twee (of drie) soorten peers: seeders (hebben alle data) en leechers. Alleen leechers samplen kan door of seeders en leechers helemaal gescheiden te houden of door een tweede vector met iterators of pointers bij te houden.

[Olaf van der Spek]

Orphix schreef op zaterdag 07 maart 2015 @ 11:49:
Dan, de cijfers:
sizeof(peer_key_c) = 8 bytes

4 bytes

En dan is je cpu dus vrijwel continu bezig om enkel random peers te selecteren. Ik ben daarom wel benieuwd naar de reden dat dit zo frequent (10.000/s) moet gebeuren?

Het gaat om een BitTorrent tracker (server). Als er 15m peers zijn die elk 2x per uur een announce (request) doen, heb je dus ongeveer 8300 requests/s gemiddeld. Niet elke torrent heeft 10k peers, dus vaak is de input wel wat kleiner.

[Caelorum]

.oisyn schreef op maandag 09 maart 2015 @ 12:50:
[...]
Algoritmische complexiteit optimaliseren door simpelweg het gebruik van een andere container kost veel minder tijd en levert exponentieel meer op bij grote N

Hij had het toch al over een andere container (std::vector)?
Zolang duurt het toch niet om een std::vector af te lopen? Als het goed is zit het toch al aan 1 stuk in het geheugen.

[Soultaker]

Olaf van der Spek schreef op maandag 09 maart 2015 @ 13:14:
Er zijn twee (of drie) soorten peers: seeders (hebben alle data) en leechers. Alleen leechers samplen kan door of seeders en leechers helemaal gescheiden te houden of door een tweede vector met iterators of pointers bij te houden.

Aha, dat bedoel je met "een deel van". Ik dacht dat je een variabel aantal bedoelde.

Je kunt prima alle peers in één map houden en losse vectors creëeren voor elke subset waar je uit wil kunnen samplen. Dat gaat er vanuit dat het aantal subsets redelijk beperkt is, anders wordt de overhead van het bijhouden van al die vectors misschien te groot.

[.oisyn]

Caelorum schreef op maandag 09 maart 2015 @ 13:31:
[...]

Hij had het toch al over een andere container (std::vector)?
Zolang duurt het toch niet om een std::vector af te lopen? Als het goed is zit het toch al aan 1 stuk in het geheugen.

Ik hoef toch niet het verschil uit te leggen tussen O(n) van een lookup in een vector en O(1) van een lookup in een hash table?

[Orphix]

Soultaker schreef op maandag 09 maart 2015 @ 09:48:
[...]

Ik update de vector tegelijk met de map. Heb je m'n code überhaupt bekeken?

Zo nee, ga dat alsjeblieft eerst even doen. Zo ja, wijs maar aan wat er niet aan klopt. Voor de duidelijkheid: ik claim updates in O(1) en sampling O(|sample|).

In jouw code introduceer je een custom container. Dat is inderdaad een oplossing als de mogelijkheid bestaat om de huidige container (unordered_map) aan te passen, inclusief alle code waarbij de huidige unordered_map wordt aangeroepen. Maar dat is een luxe waar ik vanuit ging dat dit niet zondermeer mogelijk was, zoals ik de probleemstelling van TS las. Dat de huidige unordered_map geen ideale container is, is inmiddels wel duidelijk

Olaf van der Spek schreef op maandag 09 maart 2015 @ 13:19:
4 bytes

Ok, ging voor de worst-case er vanuit dat PEERS_KEY ge-defined was. Maar dit scheelt weer iets

[Soultaker]

Orphix schreef op maandag 09 maart 2015 @ 14:17:
In jouw code introduceer je een custom container. Dat is inderdaad een oplossing als de mogelijkheid bestaat om de huidige container (unordered_map) aan te passen, inclusief alle code waarbij de huidige unordered_map wordt aangeroepen. Maar dat is een luxe waar ik vanuit ging dat dit niet zondermeer mogelijk was, zoals ik de probleemstelling van TS las. Dat de huidige unordered_map geen ideale container is, is inmiddels wel duidelijk

Okee, dat is een geldige interpretatie van de TS, maar aangezien efficient samplen met alleen een map niet mogelijk is, en Olaf de eigenaar van de hele xbt-codebase is (en dus prima een andere datastructuur kan introduceren als dat nodig is), dan lijkt het me een goed idee om de datastructuur uit te breiden.

Het lijkt me een geval van een XY-probleem, waarbij X="een set peers bijhouden zodat ik peers kan vinden a.d.h.v. een key, en er een random sample uit kan nemen", en Y="efficient random samplen uit een std::unordered_map". Olaf wil X, en vraagt om Y.

(Overigens heeft Olaf al allerlei relevante context-informatie gegeven; het zijn vooral anderen in dit topic die hardnekkig aan Y vasthouden.)

[Olaf van der Spek]

Soultaker schreef op zondag 08 maart 2015 @ 13:47:

C++:

    Value Find(const Key& key) {
        auto it = map_.find(key);
        assert(it != map_.end());
        return it->second.second;
    }

Dat is meer At/Get dan Find.
Is dit echt een XY-geval? Veel problemen kun je (ook) op een hoger niveau oplossen maar dat is iets anders dan een XY-probleem toch?

[ Voor 18% gewijzigd door Olaf van der Spek op 11-03-2015 13:56 ]

[Soultaker]

De code is vooral een illustratie van het principe.

Veel problemen kun je (ook) op een hoger niveau oplossen maar dat is iets anders dan een XY-probleem toch?

Daar heb je gelijk in. In dit geval hangt het er vanaf wat jij wil: als je een methode zoekt om efficiënt te samplen en je bent bereid de gebruikte datastructuren te wijzigen, dan was je oorspronkelijke vraagstelling wellicht wat te beperkt. Als je de datastructuren wil houden zoals ze zijn, dan heb ik ten onrechte de vraagstelling naar een hoger niveau vertaald.