Forum: PC-Programmierung C++: Design einer performanten Bestenliste?


von Joseph (Gast)


Lesenswert?

Hallo,

ich suche eine Datenstruktur für eine Bestenliste mit möglichst 
schnellem Zugriff/Performance. Eine große Anzahl an Funktionen soll je 
nach Rückgabewert sich in die Bestenliste eintragen sofern sie die 
Bedingungen erfüllt.

Jede Funktion hat eine individuelle ID als int.
Jede Funktion liefert ein Rückgabewert als double.

Die Funktionen werden immer wieder aufgerufen und geben ständig neue 
Rückgabewerte raus.

Die Bestenliste hat eine Maximalgröße an Einträgen, die nicht 
überschritten werden darf (zB 5).

In der Bestenliste sollen evt immer die IDs der Funktionen gespeichert 
sein, welche aktuell den die höchsten double Rückgabewert liefern sowie 
ein mindest-double Wert erfüllen.

Wenn noch Platz in der Bestenliste ist, werden einfach Einträge gemacht 
bis die Maximalgröße an Einträgen erreicht ist sofern der mindest-double 
Wert erfüllt wird.

Wenn die Bestenliste voll ist, soll immer geprüft werden, ob ein 
folgender Funktionsaufruf nicht ein höheren/besseren double-Wert liefert 
als der aktuell kleinste in der Bestenliste. Wenn das so ist, soll der 
aktuell kleinste Wert gelöscht werden und der neue Wert der Funktion und 
dessen ID hinzugefügt werden. Eine bessere Funktion kann also eine 
schlechtere Verdrängen.

Eine Funktion kann sich aber auch selbst wieder aus der Liste austragen 
wenn bei einem neuen Aufruf ein mindest-double Wert nicht erreicht wird.

Die Datenstruktur muss also etwa folgende Dinge erfüllen:
- veränderbare Größe.
- enthält pro Eintrag evt sowas wie ein pair aus double und int.
- schneller Zugriff auf kleinsten enthaltenen double Wert und dessen 
zugehöriger ID(int).
- schnelles Löschen und hinzufügen von pair wenn neues pair höheren 
doublewert hat.
- schneller Zugriff per ID(int) damit Funktion prüfen kann ob ggf 
Eintrag gelöscht wird.
- Aktualisieren von double wenn gleiche Funktion einen besseren double 
liefert (Zugriff per ID(int).
- performant, da millionenfache Aufrufe.

Für die Sache dachte ich zuerst an eine std::multimap<double, int> so 
ist der Zugriff auf den aktuell kleinsten Eintrag per map.begin()->first 
sehr einfach. ABER double als Key zu nutzen ist ziemlich übel daher wäre 
es umgekehrt eigentlich besser std::map<int, double> da die IDs immer 
unterschiedlich sind und so save einem double-Wert zugeordnet sind. ABER 
dann ist natürlich die map nicht mehr nach double geordnet und man muss 
sich durch die map iterieren und den kleinsten enthaltenen Wert suchen 
was performancemäßig übel ist.

Ansonsten hatte ich noch an std::pair also ein 
std::set<std::pair<double, int>> gedacht. Die Sache wird dann auch nach 
double geordnet und ein .begin->first funktioniert gut. Aber was da noch 
nicht klappt, ist die ID(int) als Key anzusprechen. Wenn zB eine 
Funktion den mindest-double Wert NICHT mehr erfüllt müsste sie 
eigentlich gucken, ob ihre ID in der Liste aktiv ist und sich dann dort 
löschen. Aber dieser Zugriff (Eintrag finden) am besten wieder ohne 
langsames iterieren. Vielleicht gibt es sowas wie eine performante 
set/map mit zwei Keys?... Oder etwas mit Sortierung nach double Größe 
aber Zugriff nach int(key)...?

Vielleicht sind die Ansätze auch zu kompliziert gedacht und es geht auf 
andere Weise noch viel besser? Augenmerk ist (auch wenn es oft nicht 
gern gelesen wird) zu 100% auf Performance da die Funktionsaufrufe 
millionenfach hintereinander auftreten und jetzt schon ohne die 
Bestenliste eine ordentliche Wartezeit besteht.

Würde mich feuen wenn jmd eine Idee hat wie man eine performante 
Bestenliste am besten gestaltet.

Grüße

von MaWin (Gast)


Lesenswert?

Bei nur 5 (also binärer suche mit 3 vergleichen), und so kleinen 
Einträgen: statisches Array, sortiert nach double, mit umkopieren der 
Einträge. Das geht schneller als verkette Listen oder hash-Tabellen 
umzuorganisieren und ist sehr cache-lokal.
Die Abfrage ob überhaupt relevant geht durch 1 Vergleich an fixer 
Speicherposition, die Suche nach der Einfügestelle kostet 2 weitere 
Vergleiche, eventuelles Verschieben im Mittel (2 Einträge moven) nur 24 
bytes anfassen, und niemals malloc/new oder ähnlichen Blödsinn, nie 
Fehlerüberprüfung ob Pointer gültig, und hinspeichern ist simpelst, nur 
die 12 byte hinspeichern, keinerlei Verwaltungsvariablen (z.B. Anzahl 
der Einträge) mitführen.

von Joseph (Gast)


Lesenswert?

Interessant, daran hatte ich noch gar nicht gedacht.
Wäre ein Array bei max 100 Einträgen auch noch besser als verkette 
Listen oder hash-Tabellen?

Die 5 waren ein Beispiel, minimal 1, im Durchschnitt sind es vielleicht 
etwa 5-20, maximal aber höchstens 100 niemals mehr, eher immer weniger.

Wäre sowas als Basis gut?:

struct paar
{
   double;
   int;
};
std::array<paar,10> bestenliste;


Man bräuchte dann evt noch ein bool im struct um zu kennzeichnen ob der 
Eintrag aktiv ist da das Array immer statisch voll ist.

von mh (Gast)


Lesenswert?

Joseph schrieb:
> Interessant, daran hatte ich noch gar nicht gedacht.
> Wäre ein Array bei max 100 Einträgen auch noch besser als verkette
> Listen oder hash-Tabellen?

Wahrscheinlich ist auch bei 100 Einträgen ein Array besser. Das normale 
Vorgehen bei so einem Problem ist:
1. Die lesbarste (und damit wahrscheinlich einfachste) Lösung, die dir 
einfällt, implementieren.
2. Testen, ob die Lösung schnell genug ist.

von Oliver S. (oliverso)


Lesenswert?

Was soll den schnell sein? Der Zugriff auf die einzelnen Elemente, das 
Einfügen eines neuen Elements, oder beides?

Und was bedeutet „schnell“? Ein std::unordered_multimap<double, int> 
erfüllt die Anforderungen nicht?

Oliver

: Bearbeitet durch User
von Carl D. (jcw2)


Lesenswert?

In welcher Zeiteinheit passieren "millionenfache Zugriffe"?
Sekunde oder Tag?

Schreibend oder lesende Zugriffe?

von Joseph (Gast)


Lesenswert?

Oliver S. schrieb:
> Was soll den schnell sein? Der Zugriff auf die einzelnen Elemente, das
> Einfügen eines neuen Elements, oder beides?
Schon beides.
- Funktionswert(double) soll mit dem kleinstem Wert der Bestenliste 
verglichen werden, wenn größer dann ersetzen inklusiv der ID.
- Funktions-ID(int) sucht nach selbiger in Bestenliste, wenn double 
größer dann aktualisiere, wenn kleiner dann aktualisiere auch (wobei 
dann die Frage wäre ob ein anderer nicht größer war aber zu seinem 
Aufruf eben nicht), und deaktiviere/lösche wenn mindest-double Wert 
nicht erfüllt.

> Und was bedeutet „schnell“?
Naja so schnell wie möglich, daher mache ich mir ja die Gedanken gleich 
im Vorfeld was Sinnvolles zu machen um eben die "langsamen" Ansätze 
zumindest schon im Vorfeld zu vermeiden.

> Ein std::unordered_multimap<double, int> erfüllt die Anforderungen nicht?
Das wäre unsortiert dann müsste man gleich bei zwei Dingen iterieren 1. 
Den kleinsten double Wert suchen. 2. Die ID(int) finden.


Ich versuch zunächst mal was mit std::vector (Bestenlistengröße ist erst 
zur Laufzeit bekannt). Führt natürlich schon dazu, dass ein Zugriff auf 
die ID(int) immer über eine Iteration geht und auch das finden des 
kleinsten Wertes genauso über Iteration geht.
Evt hält man den Vector immer sortiert 
(https://stackoverflow.com/questions/15048466/inserting-element-to-a-sorted-vector-and-keeping-elements-sorted/15048651) 
dann braucht man zumindest die iteration um den kleinsten Wert zu finden 
nicht.
Ansonsten habe ich noch boost::container::flat_set gefunden soll auch 
interessant sein.
Also ihr sehr ich bin noch schwer am Suchen, halte mich jetzt aber 
erstmal an den vector, zwar viel iterieren aber zumindest cache-lokal...

von Joseph (Gast)


Lesenswert?

Carl D. schrieb:
> In welcher Zeiteinheit passieren "millionenfache Zugriffe"?
> Sekunde oder Tag?

Das passiert am Stück in Rahmen einer Simulation, dort werden viele 
Millionen Daten durchgeschleift. Ein Durchlauf kann je nach Simulation 
von Minuten bis Tage dauern, daher ist mir das Thema Performance nicht 
ganz unwichtig.

> Schreibend oder lesende Zugriffe?

beides, wie oben beschrieben vergleichen lesen schreiben einfügen 
löschen.

von MaWin (Gast)


Lesenswert?

Joseph schrieb:
> Wäre ein Array bei max 100 Einträgen auch noch besser als verkette
> Listen oder hash-Tabellen

Nein. Ich schätze bei 10 den turn around.

Zumindest das umkopieren erspart man sich mit einem indizierten Array, 
aber den Index als Array müsste man immer noch verschieben, zumindest 1 
byte pro Eintrag. Ab 50 dürfte das aufwändiger sein als Verkettung.

von MaWin (Gast)


Lesenswert?

Oliver S. schrieb:
> Was soll den schnell sein?

Na ja, die Erkennung daß ein Eintrag nicht zu den Top 5 gehört wird 
99.99% aller Ergebnisse ganz schnell machen.
Danach dürfte es fast egal sein wie lange die Behandlung eines 
wirklichen Top 5 dauert.

von Joseph (Gast)


Lesenswert?

Ok dann hat der vector doch sein Limit.

Dann eher doch sowas?
std::set<std::pair<double, int>>
um int zu finden muss allerdings auch wieder iteriert werden.

Gibt es denn kein Container mit Key-Zugriff int aber der nach dem 
assozierenden Wert double sortiert ist? Also Sortierung double, Zugriff 
int.

von Carl D. (jcw2)


Lesenswert?

MaWin schrieb:
> Joseph schrieb:
>> Wäre ein Array bei max 100 Einträgen auch noch besser als verkette
>> Listen oder hash-Tabellen
>
> Nein. Ich schätze bei 10 den turn around.
>
> Zumindest das umkopieren erspart man sich mit einem indizierten Array,
> aber den Index als Array müsste man immer noch verschieben, zumindest 1
> byte pro Eintrag. Ab 50 dürfte das aufwändiger sein als Verkettung.

Es gab mal einen CppCon-Vortrag zu dieser Frage, mit dem Ergebnis, daß 
auf aktueller PC-HW die Liste nie schneller wird, weil potentiell jedes 
"next" einen Cachemiss hervorruft, beim Vector/Array die HW per Prefetch 
dafür sorgt, daß die Daten im Cache stehen. Selbiges ist übrigens auch 
die Grundlage für die Datenbank eines deutschen DAX-Konzerns.
Wichtigste Aussage aus mehreren Vorträgen zu Performance: nie 
vermuten/"sicher wissen", sondern immer messen. Falls es überhaupt 
notwendig ist, also die Millionen Reads/Inserts/Deletes auch tatsächlich 
jede Minute durchgeführt sein müssen.
Für die Top109-Liste eines Spiels nimmt man std::array<T,100> und die 
std-Algorithmen.

von Oliver S. (oliverso)


Lesenswert?

Joseph schrieb:
> Gibt es denn kein Container mit Key-Zugriff int aber der nach dem
> assozierenden Wert double sortiert ist? Also Sortierung double, Zugriff
> int.

Warum Zugriff int? Willst du gezielt auf den siebt-höchsten Wert 
zugreifen, oder wissen, welchen Rang die Funktion mit ID 17 hat? Und das 
millionenfach pro was auch immer für eine Zeiteinheit?

Oliver

von cppbert3 (Gast)


Lesenswert?

Ich kann mir irgendwie nicht vorstellen das deine Bestenlistenverwaltung 
so viel Zeit frisst im Vergleich zur Funktions Evaluierung, die Liste 
koennte ja nur 0,05% der gesamtzeit aus machen, dann kannst da nichts 
verbessern

Wie Benchmarks du? Ohne konkrete Prüfung ist das recht sinnfrei weil du 
nach Bauchgefühl optimieren

Kannst du mehr Code zeigen von deinen Funktionen und wie du diese immer 
wieder evaluierst, was gehen fuer parameter ein, wie komplex sind die 
Funktionen usw.

von M.K. B. (mkbit)


Lesenswert?

Dieser Vortrag behandelt das Thema.
https://m.youtube.com/watch?v=YQs6IC-vgmo

Theoretisch spart eine Liste gegenüber einem Array das Umkopieren, aber 
dafür ist die Suche beim Einfügen langsamer.
Den Unterschied auf der CPU macht dann der Cache aus. Das Array liegt 
nacheinander in einer Cacheline während es bei der Liste laufend 
Cachemisses gibt. Evtl. kann die CPU auch mit Vectorbefehlen kopieren.

Ich würde das Problem so angehen.
Ein Objekt mit den Funktionen zur Manipulation der Bestenliste anlegen. 
Dann einen Unittest mit Tests zur Verifikation der korrekten Funktion 
und Performancemessungen für das geplant Anwendungsszenario schreiben.

Mein erster Ansatz wäre dann mit einem std::array oder std::vector und 
den Algorithmen aus der STL.

von M.K. B. (mkbit)


Lesenswert?

cppbert3 schrieb:
> Wie Benchmarks du? Ohne konkrete Prüfung ist das recht sinnfrei weil du
> nach Bauchgefühl optimieren
>
> Kannst du mehr Code zeigen von deinen Funktionen und wie du diese immer
> wieder evaluierst, was gehen fuer parameter ein, wie komplex sind die
> Funktionen usw.

Wenn es schon eine Implementierung gibt, dann würde ich mit einem 
Profiler die kritischen Stellen ermitteln und dann den entsprechenden 
Code hier Posten.

von Carl D. (jcw2)


Lesenswert?

M.K. B. schrieb:
> cppbert3 schrieb:
>> Wie Benchmarks du? Ohne konkrete Prüfung ist das recht sinnfrei weil du
>> nach Bauchgefühl optimieren
>>
>> Kannst du mehr Code zeigen von deinen Funktionen und wie du diese immer
>> wieder evaluierst, was gehen fuer parameter ein, wie komplex sind die
>> Funktionen usw.
>
> Wenn es schon eine Implementierung gibt, dann würde ich mit einem
> Profiler die kritischen Stellen ermitteln und dann den entsprechenden
> Code hier Posten.

Der TO sucht eher noch nach der theoretisch schnellsten Lösung.
Da gibt es keine Meßwerte ;-)

von Joseph (Gast)


Lesenswert?

Oliver S. schrieb:
> Joseph schrieb:

> Warum Zugriff int? Willst du gezielt auf den siebt-höchsten Wert
> zugreifen, oder wissen, welchen Rang die Funktion mit ID 17 hat? Und das
> millionenfach pro was auch immer für eine Zeiteinheit?

Zugriff int weil eine Funktion die eigene ID(int) in der Bestenliste 
suchen muss und falls gefunden den dort im pair vorhandenen doublewert 
mit dem neuen vergleichen muss.

Wenn eine Funktion aufgerufen wird erzeugt sie den double Wert. Jede 
Funktion hat eine individuelle ID(int) zusammen also immer ein pair und 
muss dann gucken ob sie in der bestenliste vertreten ist:

Wenn Funktion in Bestenliste vertreten:
- Wenn der mindest-double Wert nicht erfüllt ist: muss sie ihren 
pair-Eintrag in der Liste deaktivieren/löschen.
- Wenn der mindest-double Wert erfüllt ist: muss sie ihren pair-Eintrag 
in der Liste aktualisieren (alter double durch neuen ersetzen).

Wenn Funktion in Bestenliste NICHT vertreten:
- Wenn der neue double-Wert größer ist als der im pair-Eintrag kleinste 
double-Wert in der Bestenliste dann: lösche pair-Eintrag mit dem 
kleinsten double Wert und fügen neues pair mit größerem double-Wert 
hinzu.
- Wenn der neue double-Wert NICHT größer ist als der im pair-Eintrag 
kleinste double-Wert in der Bestenliste dann: hat sich die Funktion 
nicht qualifiziert einen Platz in der Bestenliste zu bekommen. Tue 
nichts.

Im Grunde sollen einfach nur die aktuell besten x Funktionen in der 
Bestenliste vertreten sein. Daher muss bei jedem neuen double-Wert einer 
Funktion geschaut werden ob nicht die qualifikation für die Bestenliste 
besteht.

von B. S. (bestucki)


Lesenswert?

Joseph schrieb:
> Man bräuchte dann evt noch ein bool im struct um zu kennzeichnen ob der
> Eintrag aktiv ist da das Array immer statisch voll ist.

Ist nicht nötig, man definiert einfach eine ungültige ID (z.B. 0), die 
keine Funktion haben darf. Steht als ID eine 0, gilt der Eintrag als 
leer.

M.K. B. schrieb:
> Den Unterschied auf der CPU macht dann der Cache aus. Das Array liegt
> nacheinander in einer Cacheline während es bei der Liste laufend
> Cachemisses gibt.

Dieses Problem kann man mit einem eigenen Allokator, der seinen Speicher 
als Array hält und mit Clustern arbeitet, umgehen. Mit placement new hat 
man seine Knoten auch relativ zügig erstellt. Die Herausforderung in 
diesem Vorgehen besteht darin, möglichst schnell einen freien 
Speicherplatz zu finden.

Joseph schrieb:
> Eine große Anzahl an Funktionen

Wie viele Funktionen sind das und muss nur das Eintragen oder auch das 
Auswerten schnell sein? Evt. könnte man sich Performance gegen Speicher 
erkaufen, sprich, für jede Funktion erstellt du einen Eintrag in deiner 
Bestenliste und wertest am Schluss einmalig aus, welche Funktion nun die 
Beste ist.

Grundsätzlich gilt aber: Welche Variante am schnellsten ist, erfährst du 
nur mit einem Benchmark und dieser gilt auch nur für diese Plattform, 
auf der der Test durchgeführt wurde. Es wäre nicht das erste Mal, dass 
sich eine lineare Suche als die performanteste Variante ergeben würde.

von leo (Gast)


Lesenswert?

Joseph schrieb:
> Jede Funktion hat eine individuelle ID als int.

Du kannst auch checken, ob die kuenstliche? ID nicht durch die Funktion 
selber (also die Adresse derselben) ersetzbar ist.

Sonst wuerde ich zuerst mal bauen und messen, zumal du ja auch noch 
nicht die Groesse der Bestenliste weisst.

leo

von Joseph (Gast)


Lesenswert?

M.K. B. schrieb:
> Ich würde das Problem so angehen.
> Ein Objekt mit den Funktionen zur Manipulation der Bestenliste anlegen.
> Dann einen Unittest mit Tests zur Verifikation der korrekten Funktion
> und Performancemessungen für das geplant Anwendungsszenario schreiben.
>
> Mein erster Ansatz wäre dann mit einem std::array oder std::vector und
> den Algorithmen aus der STL.

Genau so werd ich jetzt mal angehen.
Danke schon mal für die Antworten.

von nfet (Gast)


Lesenswert?

Hier mal mein Ergebnis mit einem sehr naiven Ansatz (gcc 7.4., AMD Ryzen 
5 2600):
1
#include<iostream>
2
#include<array>
3
#include<algorithm>
4
#include<random>
5
6
struct Entry {
7
    int id;
8
    double value;
9
};
10
11
template<size_t SIZE>
12
class Bestenliste {
13
public:
14
    Bestenliste(double minimum) : MINIMUM(minimum) {list.fill(DEFAULT_ENTRY);}
15
    void Insert(Entry entry) {
16
        auto pos = std::find_if(list.begin(), list.end(), [entry](auto e){return e.id == entry.id;});
17
        if (pos != list.end()) {
18
            Remove(pos);
19
        }
20
        if (entry.value > list.back().value) {
21
            list.back() = entry;
22
            Sort();
23
        }
24
    }
25
    void Print() {
26
        for (auto entry : list) {
27
            std::cout << entry.id << "; " << entry.value << std::endl;
28
        }
29
    }
30
private:
31
    const double MINIMUM;
32
    const Entry DEFAULT_ENTRY {-1, MINIMUM};
33
    using List = std::array<Entry, SIZE>;
34
    List list;
35
    void Remove(typename List::iterator& pos) {
36
        *pos = DEFAULT_ENTRY;
37
        Sort();
38
    }
39
    void Sort() {
40
        std::sort(list.begin(), list.end(), [](auto first, auto second){return first.value > second.value;});
41
    }
42
};
43
44
template<class T>
45
class UniformDistributionGenerator {
46
public:
47
    UniformDistributionGenerator(typename T::result_type min, typename T::result_type max) : gen(rd()), dis(min, max) {}
48
    auto Get() {
49
        return dis(gen);
50
    }
51
private:
52
    std::random_device rd;
53
    std::mt19937 gen;
54
    T dis;
55
};
56
57
int main() {
58
    UniformDistributionGenerator<std::uniform_int_distribution<int> > RandomId(1, 1000);
59
    UniformDistributionGenerator<std::uniform_real_distribution<double> > RandomValue(1, 1000);
60
    Bestenliste<10> bestenliste(500);
61
    for (int i = 0; i < 1e9; ++i) {
62
        bestenliste.Insert(Entry{RandomId.Get(), RandomValue.Get()});
63
    }
64
    bestenliste.Print();
65
}
1
> g++ -O3 bestenliste.cpp
2
> time ./a.out
3
637; 997.887
4
563; 996.8
5
635; 995.251
6
680; 994.238
7
817; 993.802
8
261; 993.321
9
270; 993.07
10
311; 992.759
11
830; 991.653
12
3; 990.283
13
14
real    0m26.407s
15
user    0m26.344s
16
sys     0m0.000s

Der Aufruf von RandomId.Get() und RandomValue.Get() dauert dabei 
übrigens alleine bereits ca. 20s.
Macht im Mittel eine Zeit von 6.4s/1e9 = 6.4ns pro Insert.
Bei einer Größe der Liste von 100 sind wir übrigens schon bei 5m13.595s, 
das macht dann schon 293ns pro Insert.

Zusammenfassend, deine Bestenliste zu optimieren lohnt erst ab wirklich 
vielen Zugriffen.

von Oliver S. (oliverso)


Lesenswert?

Joseph schrieb:
> Wenn eine Funktion aufgerufen wird erzeugt sie den double Wert.
> ...
> Wenn Funktion in Bestenliste vertreten:
...
> Wenn Funktion in Bestenliste NICHT vertreten:
> ...
> - Wenn der neue double-Wert NICHT größer ist als der im pair-Eintrag

Ein std::vector mit der Größe entsprechend der Anzahl der Funktions-IDs. 
Funktions-ID ist Index in den Vector. Werte sind double oder "nicht 
vertreten" (als Enum, oder std::numeric_limits<double>::min() ).

Da kann dann jede Funktion nach Größenprüfung ihren Wert eintragen, oder 
sich austragen. Wenn du willst, kannst du dir noch das jeweils aktuell 
größte und kleinste Paar merken. Schneller geht das eintragen vermutlich 
nicht, da gar nichts sortiert wird.

Unklar ist noch, warum du die Tabelle dann auch "schnell" auswerten 
musst, und wie. Bei dem Ansatz ist die Liste nicht sortiert, das muß 
dann vor der Auswertung passieren, falls überhaupt erforderlich.

Oliver

: Bearbeitet durch User
Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.