Wie heißt diese Datenstruktur
Geizhals » Forum » Programmierung » Wie heißt diese Datenstruktur (19 Beiträge, 698 Mal gelesen) Top-100 | Fresh-100
Du bist nicht angemeldet. [ Login/Registrieren ]
Wie heißt diese Datenstruktur
22.08.2012, 13:28:03
Ein Array, eine list oder was auch immer die folgendes kann/macht:

Es gibt maximal x Integer Elemente, die Struktur wird gefüttert mit Integerwerten zwischen 0 und x-1. Größere und kleinere Werte kommen nicht vor.
Die neueste Zahl kommt immer "oben" drauf.
Falls die hinzuzufügende Zahl y schon vorkommt:
Die Zahl y kommt wie immer ganz oben auf die Struktur, auf der alten Position wird y entfernt, aber alle Zahlen unter/hinter/nach y sollen aufrücken.

Beispiel:
Die Zahlen, 5, 20, 2, 21, 22 werden nacheinander, beginnend mit 5 an die Struktur geschickt:
Die Reihenfolge wie folgt:
5, 20, 2, 21, 22.
Jetzt geben wir nochmal 21 dazu, die Reihenfolge ist dann wie folgt:
21, 5, 20, 2, 22

Auf gut Deutsch: Eine Liste von Zahlen, in der jede Zahl nur einmal existieren darf, wobei bereits vorhandene Zahlen an den Anfang der Liste gestellt werden, die alte Position dieser Zahl gelöscht wird und der Rest aufrückt.

Ich könnte mir das wahrscheinlich selber basteln würde es aber wahrscheinlich nur äußerst unperformant hinbekommen.
Jede Zahl in eine Instanz der Speicherklasse ala Binärbaum?
Dann könnte ich am leichtesten aufrücken.

Das Ziel ist, dass ich herausfinden möchte ob man bei möglichst perfekten Zufallszahlen zwischen 0 und x durch das Erwarten der am längsten nicht aufgetretenen Zahlen die Wahrscheinlichkeit des Auftretens jeder einzelnen Zahl zwischen 0 und x berechnen kann.

Man könnte ja sagen:
"Jeder Griff in den Random Topf holt eine komplett zufällige Zahl hervor!"
oder
"Dass 100 mal hintereinander dieselbe Zahl y auftritt bei einer Auswahl aus 10^1000 Zahlen muss genauso wahrscheinlich sein wie jede andere definierte Folge derselben Größe aus demselben Arsenal!"
aber ich bin trotzdem misstrauisch.


Antworten PM Übersicht Chronologisch
 
Melden nicht möglich
 

Dieses Forum ist eine frei zugängliche Diskussionsplattform.
Der Betreiber übernimmt keine Verantwortung für den Inhalt der Beiträge und behält sich das Recht vor, Beiträge mit rechtswidrigem oder anstößigem Inhalt zu löschen.
Datenschutzerklärung