C++: Design einer performanten Bestenliste?

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.

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.

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.

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:
> 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.