Gewichtetes Zufallsergebnis aus einer SQLite-Tabelle

Aus einer SQLite-Tabelle soll mit einem einfachen SELECT-Query ein gewichtetes Zufallsergebnis, also eine zufällig ausgewählte Zeile selektiert werden. Die in der Tabelle vorhandenen Zeilen sollen aber nicht mit der gleichen Wahrscheinlichkeit auftreten, sondern nach einem zeilenspezifischen Integer-Wert gewichtet werden.

In der Tabelle Event liegen folgende Spalten vor:

id | bezeichnung | gewichtung

Eine Zeile mit gewichtung = 2 soll also doppelt so häufig selektiert werden wie eine Zeile mit gewichtung = 1.

Eine (pseudo-)zufällig ausgewählte, dabei aber nach gewichtung gewichtete Zeile erhält man nun, unter Zuhilfenahme der kumulierten Gewichtung, durch folgende Abfrage:

SELECT
  t.id, t.bezeichnung, t.gewichtung
FROM
  Event t
INNER JOIN
(
  SELECT t.id, SUM(tt.gewichtung) AS cum_weight
  FROM Event t
  INNER JOIN Event tt ON tt.id <= t.id
  GROUP BY t.id
) tc ON tc.id = t.id
,( SELECT ABS(RANDOM() % SUM(gewichtung)) AS rnd FROM Event)
WHERE
  rnd >= (cum_weight - gewichtung)
  AND rnd < cum_weight
ORDER BY
  t.id ASC;

 

Echte Zufallszahlen mit Qt/C++

In einer Qt/C++-Application habe ich zum Erstellen von Zufallszahlen die eingebaute qrand()-Methode verwendet. Dazu hatte ich einmal beim Programmstart den Seed über die qsrand()-Methode initialisiert:

QTime time = QTime::currentTime();
qsrand((uint)time.msec());

Nach kurzer Zeit ist mir aufgefallen, dass die so generierten Zufallszahlen nur scheinbar zufällig sind. Ein großes Problem war insbesondere, dass alle Zahlen, die in der gleichen Millisekunde generiert wurden, gleich waren. Das war in meiner Anwendung häufig der Fall, weil ich zum Teil in einer Schleife (nahezu) gleichzeitig sehr viele Zufallszahlen generieren musste.

Schließlich bin ich beim C++-Standardheader <random> gelandet, der eine ganze Reihe unterschiedlicher Zufallsgeneratoren zur Verfügung stellt. Unter anderem steht mit dem Generator random_device ein Non-deterministic true random number generator bereit, den ich in meiner Applikation wie folgt implementiert habe:

std::random_device generator;
std::uniform_int_distribution<int> distribution(low, high);
int result = distribution(generator);
return result;

Ein schneller Test hat ergeben, dass die so generierten Zufallszahlen tatsächlich nicht nur bei jedem Programmstart unterschiedlich sind, sondern sich auch bei der Massengenerierung in einer Schleife immer unterscheiden.

Eine gute Quelle für die Möglichkeiten des <random>-Headers habe ich hier gefunden:

http://www.cplusplus.com/reference/random/

Ideale Spielplan-Berechnung mit Kantenfärbung

Das Problem

Für ein privates Projekt bin ich auf die Herausforderung gestoßen, aus einer gegebenen Liste von Mannschaften einen Spielplan zu erstellen. Das klingt zunächst extrem trivial, hat sich aber schnell als durchaus spannend herausgestellt.

Die Liste der Mannschaften liegt als Liste von Vereins-IDs vor. Das kann ja eigentlich nicht so kompliziert sein – man bestimmt einfach über eine simple verschachtelte for-Schleife alle Kombinationsmöglichkeiten der Listeneinträge und hat das Problem gelöst. Interessant wurde es erst, als ich mir die so generierten Paare genauer angeschaut habe. Dabei waren mehrere Randbedingungen verletzt, die ich implizit vorausgesetzt hatte.

Die Randbedingungen

A. Eine Mannschaft soll an jedem Spieltag nur höchstens einmal spielen.

Die einfache verschachtelte for-Schleife führt durch die beiden Laufvariablen zwangsläufig dazu, dass an jedem Spieltag entweder die Heimmannschaft oder die Gastmannschaft mehrere Spiele zu absolvieren hat. Das ist in der praktischen Anwendung nicht sinnvoll, keine Mannschaft kann mehr als ein Spiel an einem Spieltag spielen. Es ist daher zwingend notwendig, die Paarungen passend über alle Spieltage zu verteilen.

B. Nach möglichst wenigen Spieltagen soll jede Mannschaft gegen jede andere Mannschaft gespielt haben.

Diese Bedingung erfüllt auch die einfache Schleife (wenn auch in einer unbrauchbaren Reihenfolge). Am Ende der Saison soll jede denkbare Paarung zweimal stattgefunden haben. Dabei soll die Saison so kurz wie möglich gehalten werden, d.h. die Anzahl der Spieltage soll nicht größer sein als unbedingt notwendig um alle anderen Bedingungen zu erfüllen. Daraus ergibt sich, dass etwa bei 18 Mannschaften nur 2×17 Spieltage generiert werden sollen.

C. Heim- und Auswärtsspiele sollen sich idealerweise abwechseln.

Jede Mannschaft soll im Verlauf der Saison gleich viele Heim- und Auswärtsspiele haben. Dabei sollen sich Heim- und Auswärtsspiele abwechseln, so dass auf ein Heimspiel immer ein Auswärtsspiel folgt. Dieses Problem ist nicht ideal lösbar.

Die Lösung

Nach einer anregenden Diskussion mit zwei Kollegen stand schnell fest, dass die Berechnung eines solchen „idealen“ Spielplans nicht so trivial ist wie zunächst gedacht.

Nachdem eine Kollegin mich mit den Stichworten „Graph“ und „Kantenfärbung“ in die richtige Richtung geschubst hatte, konnte ich die mathematischen Hintergründe und die Lösung für das Problem auf einer Seite der RWTH Aachen finden. Dort wird das „Spielplan-Problem“ mithilfe eines Kantenfärbungs-Algorithmus gelöst.

In der Linkliste dieses Artikels war außerdem eine Implementierung dieses Algorithmus in PHP von Andy Theiler zu finden. Andy Theiler hat seine Implementierung dankenswerterweise unter eine freie BSD-Lizenz gestellt, so dass ich seinen Code für meine Bedürfnisse anpassen und nach C++/Qt portieren konnte.

Diese angepasste Portierung stelle ich unter gleicher Lizenz bei Github zur Verfügung.

Website-Relaunch

Nachdem der letzte Relaunch meiner Website nun schon wieder 4 Jahre her ist, war es Zeit für eine Neugestaltung.

Technisch hat sich in dieser Zeit viel getan. Die neue Seite wird nun mit einem modernen WebCMS betrieben und sieht dank Responsive Design auch auf unterschiedlichen Endgeräten gleichermaßen gut aus. Auch das Aussehen insgesamt habe ich heller und lesefreundlicher gestaltet, die Inhalte neu geordnet und klarer gefasst und neue Texte geschrieben.

Bei dieser Gelegenheit habe ich auch die Möglichkeit integriert, Blogeinträge zu verfassen, sodass ich hier in Zukunft regelmäßig zu den unterschiedlichsten IT-Themen bloggen kann.

Über Feedback, Hinweise und Fragen zur neuen Website freue ich mich natürlich sehr.

Herzlich Willkommen auf meiner Website

Hier blogge ich regelmäßig über verschiedene IT-Themen, die mir bei meiner täglichen Arbeit begegnen und die mich beschäftigen. In der Regel werden Sie hier also Artikel zu C++ mit Qt, JavaScript, HTML und/oder CSS und ähnlichen Themen finden.

Ich freue mich dabei natürlich über Kommentare, Fragen und rege Beteiligung.

Daneben finden Sie hier Informationen zu meiner selbstständigen Arbeit in den Bereichen Softwareentwicklung und Netzwerkbetreuung.