Zufall und Priorität

Computer: Software & Programmierung Programmierung allgemein
#1

Hallo liebe Gemeinde,

ich steh vor einem kleinen Problem und frage mich, wie man dieses „schön“ lösen könnte.

Ich habe eine Liste von Datensätzen (wären auch in einer DB) und soll nun von dieser List „zufällige“ Herauspicken. Diese Datensätze haben auch eine Prio zwischen 1 und 5. 1 = Hoch und 5=Niedrig, welche ich auch in den „Zufall“ einfließen lassen möchte. Sprich, dass die Wahrscheinlichkeit einem Datensatz mit Prio 1 5x höher ist als einen mit Prio 5. Eventuell würde ich auch gerne eine kalkulierten Faktor „Nutzbarkeit“ berücksichtigen, welche so zwischen 1 und 10 liegen wird.

Die einzige Lösung, was mir nun auf die schnelle einfällt wäre, eine Liste/Array/ mit allen Datensätzen anzulegen, in welcher Datensätze mit hoher Prio x-mal so oft vorkommen wie niedrige. Aber wenn ich von 500 Datensätzen oder gar mehr ausgehe, kommt schon eine ganz schön lange liste zusammen und es würde viele solcher Zufallsdatensätze benötigt, dann wäre Speicher/Zeitverbrauch recht hoch :frowning:

Hat vielleicht jemand einen besseren Vorschlag?

Danke und LG Matthias

#2

Hallo!

Die einzige Lösung, was mir nun auf die schnelle einfällt
wäre, eine Liste/Array/ mit allen Datensätzen anzulegen, in
welcher Datensätze mit hoher Prio x-mal so oft vorkommen wie
niedrige.

Genauso würd ich es auch machen. Das ergibt leicht verständlichen und „schönen“ Quellcode. Das hat für mich immer erstmal Priorität.

Aber wenn ich von 500 Datensätzen oder gar mehr
ausgehe, kommt schon eine ganz schön lange liste zusammen und
es würde viele solcher Zufallsdatensätze benötigt, dann wäre
Speicher/Zeitverbrauch recht hoch :frowning:

Selbst bei 100.000 Elementen im Array würd ich mir da keine Sorgen machen. Du musst ja einen Datensatz nicht x-mal vorhalten, sondern nur einmal. Und im Array sind eben nur 5 Verweise auf den einen Datensatz. Diese Verweise sind entweder Referenzen/Zeiger auf Datensatzobjekte, die Du erzeugt hast, oder es sind direkt die IDs der Datenbank.

Jan

#3

Hallo Matthias,

ich würde die Datensätze nach Priorität sortieren, die Priorität ‚würfeln‘ und einen zufälligen Datensatz mit der ‚gewürfelten‘ Priorität anzeigen.

Um beim ‚Würfeln‘ die höchste Priorität am häufigsten zu bekommen würde ich eine zahl zwischen 3 und 403 wählen und den Ganzzahligen Teil des natürlichen Logarithmus dieser Zahl von 6 abziehen. Dann kommt die 1 am häufigsten, die 5 am seltensten.

Gruß, Rainer

#4

Du brauchst doch nur für die Datensätze eine Prioritäts-Zuteilung (1-5),
dann für den ‚gefundenen‘ Datensatz außerdem nochmal 'ne Zufallsverteilung (-10, oder ebenfalls 1-5) ?
Meinem Gefühl nach geht das mit ‚ner Unterschleife oder Unterbedingung, oder nich‘?
Also,
code: Wenn: einer von Fünf, dann nochmal einer von Fünf bzw 10.
Bzw: wenn einer von Fünf -> Priorität = nochmal (per rnd) einer von Fünf.
(?)
Bzw: Wer soll denn bestimmen, welche Priorität ‚Deine‘ Datensätze haben?
Entscheidest Du das vorher und programmierst es entsprechend oder soll das Programm das zufällig machen?

#5

Bei dieser Lösung wäre die Wahrscheinlichkeit, eine Prio 1 zu bekomme 5x höher als eine Prio 5, das ist schon richtig aber es gibt bei weitem weniger Datensätze mit Prio 1 als z.b. prio 3(der größteil). Daher würde das Verhältnis der Datenmenge dabei nicht berücksichtigt :frowning:

[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]

#6

Bzw: Wer soll denn bestimmen, welche Priorität ‚Deine‘
Datensätze haben?
Entscheidest Du das vorher und programmierst es entsprechend
oder soll das Programm das zufällig machen?

Die Datensätze haben alle eine Priorität. Ist ein Feld bei der Datenerfassung und wird daher vom Erfasser vergeben.

#7

Hallo Matthias,

die Frage ist, wie die Daten organisiert sind. Falls alle Daten in einem Array abgelegt sind, würd sich dieser Weg anbieten:

Berechne gewichtete Anzahl aller Objekte: +1 für prio 1 Objekt,…, +5 für prio 5 Objekt. Nennen wir die Summe G.

Ziehe eine gleichverteilte Zufallszahl z aus 0,…,G-1;

Laufe über den Array und ziehe von z die prio der einzellnen objekte ab. Sobald der Wert kleiner gleich 0 ist, ist das zufällig ausgewählte Element gefunden.

Hat natürlich linare Rechenzeit. Schneller gehts so:

Wenn man pro Priorität einen eigenen Array verwendet, kann man zuerst aus z die Prio ausrechnen (wieder die gewichteten Anzahlen berücksichtigen) und dann den Index des zufälligen Objekts ausrechnen und direkt drauf zugreifen.

Grüße
Thorsten

#8

Hallo,

Bei dieser Lösung wäre die Wahrscheinlichkeit, eine Prio 1 zu
bekomme 5x höher als eine Prio 5, das ist schon richtig aber
es gibt bei weitem weniger Datensätze mit Prio 1 als z.b. prio
3(der größteil). Daher würde das Verhältnis der Datenmenge
dabei nicht berücksichtigt :frowning:

ja, das hatte ich für gewollt gehalten.
Wenn Du sowohl die Anzahl der Datensätze als auch die Priorität gewichten willst, mußt Du die jeweilige Anzahl ermitteln und das in der Gewichtung berücksichtigen.
Statt Logarithmus sind auch Potenzen noch zur Gewichtung geeignet, Du musst nur dafür sorgen, daß Du als Ergebnis der gewichteten Auswertung eine Zahl zwischen 1 und 5 bekommst und einen Datensatz entsprechend der gewichteten Auswertung bekommst.
Wie stark welches Kriterium die Gewichtung beeinflussen soll, kannst Du einstellen, wie Du es wünschst. Das hängt von Vorgaben oder Geschmack ab, kann man mit dem passenden Algorithmus recht fein einstellen.

Gruß, Rainer

#9

Hallo,
ja, das hatte ich für gewollt gehalten.
Wenn Du sowohl die Anzahl der Datensätze als auch die
Priorität gewichten willst, mußt Du die jeweilige Anzahl
ermitteln und das in der Gewichtung berücksichtigen.
Statt Logarithmus sind auch Potenzen noch zur Gewichtung
geeignet, Du musst nur dafür sorgen, daß Du als Ergebnis der
gewichteten Auswertung eine Zahl zwischen 1 und 5 bekommst und
einen Datensatz entsprechend der gewichteten Auswertung
bekommst.
Wie stark welches Kriterium die Gewichtung beeinflussen soll,
kannst Du einstellen, wie Du es wünschst. Das hängt von
Vorgaben oder Geschmack ab, kann man mit dem passenden
Algorithmus recht fein einstellen.

Gruß, Rainer

Hallo,

also ich hab mir eure Vorschläge zu Herzen genommen und das nun mal so gelöst:
Ich hole mir eine Liste von allen brauchbaren Datensätze. Errechen für jeden Datensatz eine Gewichtung, die sich aus dem Statistikwert 1-10 und dem Prioritätswert 1-5 (5 für Prio 1 und 4 für Prio 2 etc.) hoch 2 errechnet. Die Liste wird dann nach Gewichtung sortiert, damit das dann vielleicht ein bisschen schneller geht. Dann wird eine Zufallszahl zwischen 2^2 und 15^2 genommen und mittels eines simplen „Divide and Conquer“ Algorithmus der Datensatz mit der gleichen oder nächst höheren Gewichtung herausgesucht. Wenn der verwendetet Datensatz aus der Liste herausgenommen wird, sollten alle weitern „Zufalllssuchen“ recht flott gehen.

Ich werde mal in nächster Zeit am Testsystem beobachten wie das nun mit Speicher und Performance aussieht.

Ich danke euch schon mal ganz viel für eure Antworten, habt mir schon recht viel weitergeholfen :smile:

LG Matthias