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
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.
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.
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.
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
In welcher Zeiteinheit passieren "millionenfache Zugriffe"? Sekunde oder Tag? Schreibend oder lesende Zugriffe?
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...
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.
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.
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.
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.
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.
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
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.
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.
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.
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 ;-)
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.
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.
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
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.
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.
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
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.