50 Mio Datensätze Zuordnung, Abfragen, Performance

[Helmut]

Für eine Facharbeit stehe ich vor folgendem Zuordnung (s) problem

Als Beispiel will ich die bekannte App Quizduell anführen.

Dort kommen bei jedem Spieldurchgang 4 Fragen, diese wiederholen sich im laufe des Spielen nicht mehr, und bei weiteren Spielen auch nicht mehr.

Nehmen wir einmal an es sind 10.000 Fragen hinterlegt und es gibt 500.000 Spieler. wie werden, bzw. können die Fragen abgespeichert werden, so das sie nicht mehr wieder vorkommen.

Beipsiel User 100:

Das einfachste wäre, eine simple Tabelle in der die USER ID und die Frage hinterlegt ist, nur wenn wir 500.000 User haben und im Schnitt jeder 100 Fragen schon zugeteilt bekommen hat, wären das schon 50 Mio Einträge.

User - Fragen 100 - 12 100 - 321 100 - 32 100 - 432 u.s.w.

Der zweite Lösungsansatz wäre, zu jedem User eine Textfeld abzuspeichern, in dem die einzelnen Fragen per Komma getrennt sind, und dann wieder ausgelesen werden.

User - Fragen 100 - 12,321,32,432

Was für Lösungen kommen den noch in Frage, die die Performance einer MYSQL Datenbank nicht in die Knie zwingt.

Es wäre toll wenn der ein oder andere seine Ideen, Gedanken mit mir teilt.

Danke

Helmut

[Google weiß alles]

Das einfachste wäre, eine simple Tabelle in der die USER ID und die Frage hinterlegt ist, nur wenn wir 500.000 User haben und im Schnitt jeder 100 Fragen schon zugeteilt bekommen hat, wären das schon 50 Mio Einträge.

Du kannst, wenn Du Bedenken hast, die Tabelle anhand der User-ID partitionieren,

[1unitedpower]

Was für Lösungen kommen den noch in Frage, die die Performance einer MYSQL Datenbank nicht in die Knie zwingt.

Nimm die erste Variante, dann gibst du dem DBMS die Chance selber eine Index-Struktur aufzustellen, um die Tabelle effizient zu verwalten. Bei einem ausbalancierten Baum als Indexstruktur hast du zum Beispiel eine obere Laufzeitschranke von O(log(n)), wobei n der Anzahl der Datensätze entspricht. Das bedeutet für dein Beispiel, dass der Server log2(50.000.000) ~= 26 Vergleiche auf der Index-Struktur ausführen müsste, um zu erfahren wo der gesuchte Datensatz zu finden ist. Und wenn es statt 50.000.000 nun 5.000.000.000 Einträge sind? Rechne es ruhig mal aus.

Es gibt eine goldene Regel beim DB-Design: Arbeite mit dem DBMS und nicht dagegen.

[Rolf b]

Ein DB Server verwendet keinen binären Baum, sondern einen B-Tree oder eine Variante davon. Jeder Knoten im Baum enthält so viele Einträge, dass man damit eine Index-Page füllen kann (die Pagesize zu bestimmen ist je nach Engine eine Optimierungsaufgabe für SQL-Server, File-System oder DB-Admin). Ein Indexeintrag auf Blatt-Ebene enthält die Indexfeld-Daten plus eine Referenz auf die Daten-Page; Indexeinträge auf Knotenebene die Indexfeld-Daten des ersten Eintrags der untergeordneten Page sowie eine Referenz auf diese Page. Bei angenommenen 2K Pagesize und 16 Byte pro Eintrag sind das 128 Einträge, d.h. eine Suche auf 50.000.000 Rows muss maximal $$\log_{128}{50000000} \approx 3,65$$ Zugriffe machen. In den meisten Fällen also 4, und bei 5.000.000.000 Rows kommt nur eine weitere Ebene hinzu.

Grund für den B-Tree ist, dass die Daten von der Festplatte sowieso Page-weise angeliefert werden und ein Plattenzugriff VIEL Zeit braucht. Ist eine Page geladen, kann der Server darin binär den richtigen Eintrag suchen, das ist eine in-memory Operation, wahrscheinlich sogar im Datencache der CPU, und die dafür benötigte Zeit ist im Vergleich zur I/O Zeit komplett vernachlässigbar.

Bei einem Clustering-Index sieht es etwas anders aus, da stecken die Daten in den Indexblättern drin und man bekommt typischerweise einen Indexlevel mehr. Was aber im vorliegenden Fall egal ist; es sei denn, man braucht außer Spieler-ID und Frage-ID noch weitere Daten für die Spieler-Frage Relation.

Beim Schreiben wird's dann aufwändiger: sobald eine Page voll wird muss sie geteilt werden, überfüllt das die Parent-Page im Index, teilt sie sich auch, etc, ggf. bis zum Index-Root. Die geteilten Seiten liegen auf der Platte nicht mehr beieinander, was zu mehr Kopfbewegungen beim Lesen führt, d.h. viele INSERTS machen eine DB mit der Zeit immer langsamer (weshalb man schließlich einen Reorg braucht). Zugegeben, es heißt von MySQL InnoDB, dass es eine schleichende Fragmentierung gut bekämpft. Aber auch ein automatischer Defragmentierer kostet Leistung.

Rolf

[TS]

Hallo und guten Tag,

Nimm die erste Variante, dann gibst du dem DBMS die Chance selber eine Index-Struktur aufzustellen, um die Tabelle effizient zu verwalten. Bei einem ausbalancierten Baum als Indexstruktur hast du zum Beispiel eine obere Laufzeitschranke von O(log(n)), wobei n der Anzahl der Datensätze entspricht. Das bedeutet für dein Beispiel, dass der Server log2(50.000.000) ~= 26 Vergleiche auf der Index-Struktur ausführen müsste, um zu erfahren wo der gesuchte Datensatz zu finden ist. Und wenn es statt 50.000.000 nun 5.000.000.000 Einträge sind? Rechne es ruhig mal aus.

Das Problem ist nicht das Lesen, sondern das Neuschreiben des Index. Und das kann leider nicht verzögert stattfinden, da schon der nächste Besucher den Index wieder benötigt.

Die Idee mit der Partionierung finde ich daher ganz smart.

Alternativ kann man auch für jeden Teilnehmer eine separate "Frage-schon-gehabt"-Tabelle führen. Aber wenn ich das richtig verstanden habe, darf die Frage überhaupt nicht mehr vorkommen, wenn sie schon einmal ausgelobt war. Dann geht das leider auch nicht.

Es gibt eine goldene Regel beim DB-Design: Arbeite mit dem DBMS und nicht dagegen.

Genau, deshalb würde man einen Index auch nicht bei jeder Veränderung sofort zurückschreiben lassen, wenn es die Aufgabenstellung zulässt. Das ist hier aber leider nicht möglich.

Grüße
TS

[Rolf b]

Es sind nicht 500.000 User, sondern lt. Google Play 10.000.000 bis 50.000.000. Und das ist nur Android, mit iOS und Windows Phone kommen sicher noch etliche Milliönchen dazu. Nehmen wir einfach mal 50 Mio User an. Die sind natürlich nicht alle aktiv, aber es werden auch etliche hochaktive Spieler dabei sein.

Wenn Du Dir eine Tabelle vorstellst, wo pro gespielter Kombination Frage/User ein Eintrag steht, dann hast du im Worstcase 500 Milliarden Rows. Ich weiß nicht was die durchschnittliche Anzahl gespielter Fragen pro User ist. Nehmen wir mal 200 an? Also durchschnittlich 200 Rows pro Spieler. Jede Row enthält 32 Bit für die Userid und 16 Bit für die Frage-ID, das sind 6 Bytes pro Row oder 1200 Bytes pro Spieler (wovon 800 Bytes für das hundertfache Speichern seiner User-ID draufgehen). Die Tabelle belegt mit 10 Milliarden Rows 60GB Nettospeicher, es kommt noch Verwaltungsspeicher pro Row und der Index hinzu. Vermutlich brutto 100GB-120GB.

Das ist sicherlich handhabbar. Aber bei bei Vielspielern wird es zum Problem, bei jedem Spiel die für sie relevanten Rows zu laden. Hat der Spieler schon 5000 Fragen gespielt, muss man für ihn 5000 Rows laden. Bei Verwendung eines Cluster-Index stehen die zwar beisammen, aber dafür hast Du den Aufwand des Clusterns. Des weiteren sind 2/3 des zu lesenden Volumens (db-intern) keine Fragenummer, sondern die Usernummer. Für Wenigspieler mag das eine sinnvolle Lösung sein, bei Vielspielern würde ich das nicht tun.

Die gespielten Fragen als langen String zu speichern, wo die Fragenummern durch Komma getrennt sind, ist Platzverschwendung. Eine Frage belegt dann typischerweise 6 Bytes. Zumindest sollte man da die Fragenummern base-64 in 3 Bytes codieren, das speichert bis $$2^{18}$$ Fragen pro Triplet, auf die Kommas verzichten und einfach alle gespielten Triplets hintereinanderhängen. Dann muss man keine Kommas parsen, und eine base-64 decodierung ist auch nicht langsamer als das Parsen eines int-Wertes. Der Durchschnittsspieler belegt dann ca 600 Bytes, aber das kann die DB nicht so optimal speichern weil es ein varchar oder varbinary String ist, die brauchen Reserven. Und ein Vielspieler mit 2000 gespielten Fragen belegt 6K.

Ich würde es anders realisieren. Ich würde bei 10000 Fragen einen Bitvektor der Länge 10000 anlegen. Der belegt 1250 Bytes und kann z.B. in einer BLOB Spalte abgelegt werden. Sowas hab ich mit PHP noch nicht verarbeitet, würde aber vermuten, dass es geht (mysqli_stmt::bind_param Datentyp 'b' und pack/unpack). Aber es gibt ja auch eine Welt jenseits von PHP und ich würde eine solche Komponente vermutlich eher mit einer Sprache realisieren, die maschinennahe Operationen besser abbildet.

Jedes Bit im Vektor entspricht dann einer Frage. Freie Fragen zu finden hängt dann von der Implementierung ab. In PHP macht man erstmal mit $vec = unpack("I4") aus dem Blob ein Array aus 32-bit Integers (jajaja, geht bei 1250 Byte nicht auf) und sucht dann einen Eintrag, der nicht -1 ist (0xffffffff). Und darin dann ein ungesetztes Bit. Ist in PHP etwas frickelig, aber sicherlich möglich. Aber wie gesagt, es gibt dafür elegantere Sprachen. C++, Java, C#, irgendwas mit hinreichend low-level Funktionalität.

Wenn der Fragenkatalog erweitert wird, erweitere ich z.B. den Bitvektor. Ein BLOB kann bis 65535 Bytes lang werden. Man muss sich hier aber genau anschauen, wie die aktuell verwendete DB und DB-Engine BLOBs speichert, um zu wissen, ob man bei mehr Fragen eher den BLOB verlängert oder ob man mehrere kleine BLOBs verwendet. Man muss auch die Packet-Size des DBMS beachten. Das sind ein paar technische Details, die bei der Programmierung zu beachten sind. Eventuell merkt man dann, dass BLOBs nicht effizient sind, und verwendet statt dessen eine base64-codierung in VARCHAR-Feldern. Das sind aber alles Fragen, die sich darum drehen, wie man die Bitmap in die DB bringt, sie ändern nichts an der Grundidee, eine Bitmap für die verwendeten Fragen zu nutzen. Die Bitmap wird erst dann unpraktisch, wenn der Fragenkatalog soweit anwächst, dass die Bitmaps nicht mehr effizient verarbeitet werden können. Wann diese Grenze erreicht ist, hängt von der Hardware ab, die ich zu bezahlen bereit bin :)

Auf diese Weise ist das pro User zu ladende Datenvolumen nicht sonderlich groß und der Aufwand zum Durchsuchen ist begrenzt. Der Nachteil ist, dass man für Wenigspieler genausoviel Platz braucht wie für Vielspieler. Bei 1250 Bytes für 10000 Fragen sind es 62GB an BLOB-Volumen. Das entspricht der relationalen Durchschnittsangabe vom Anfang - aber dafür ist es gleichzeitig die Obergrenze des belegten Volumens. Weiterer Nachteil ist, dass es keine einfache Query gibt, um festzustellen, welche Fragen wie oft gespielt wurden. Dafür muss man dann alle Blobs einmal Laden und decodieren. Um festzustellen, ob das akzeptabel ist, muss man alle Anforderungen an die DB sammeln (nicht nur aus Sicht der Spieler, sondern auch aus Sicht des Herstellers).

Rolf

[1unitedpower]

Hi @Rolf b,

+1 für die Ausführlichkeit deiner Argumentation, auch wenn ich deine Position nicht in allen Aspekten teile.

Ich finde die Konstruktion deines worst cases, der dich zu einer Annahme von 120GB Speicherbedarf führt, zu pessimistisch. Wenn man mit 50.000.000 Nutzern kalkuliert, sind die 120GB Speicherbedarf völlig vernachlässigbar, denn dann ist horizontale Skalierung kein Engpass.

Unter solchen Umständen sind auch Power-User mit mehr als 5.000 gespielten Fragen keine herausfordende Extremsituation. Das anfallende Datenvolumen auf dem Endgerät des Nutzers zu laden, wäre natürlich unzumutbar, allerdings wäre das auch nicht notwendig: Der Nutzer muss nur mit einigen wenigen ungestellten Fragen versorgt werden; die Ressourcen zum Ermitteln selbiger können schon serverseitig investiert werden. Und nochmal: Wenn wir mit 50.000.000 Nutzern rechnen, sind Power-User kein stressriges Szenario für die eingesetzte Infrastruktur.

In solchen Fällen ist horizontale Skalierung extrem günstig und maßgeblich beschränkt durch das Laufzeitverhalten der involvierten Algorithmen. Wenn man dort investiert, erzielt man Gewinne für die Performance, die jene auf horizontaler Ebene, um Größenordnungen übertreffen dürften.

[Rolf b]

Hallo 1up :)

ich meinte auch nicht die Übertragung vom Gameserver zum Handy, dorthin schickt man natürlich nur die Fragen. Es ging mir um die Interaktion zwischen Gameserver und SQL Server.

Natürlich ist es kein Thema, 5000 Rows von einem SQL Server zu laden, wenn man allein auf der Welt ist. Aber wenn das eine Million Leute parallel tun, sieht die Sache schon anders aus. Dann braucht der SQL Server einen fetten Cache oder kommt recht schnell ins Schwimmen. Natürlich kann ich die Datenbank partitionieren und den SQL Server clustern (den Cluster brauche ich eh für Ausfallsicherheit) und damit das Problem durch Hardware erschlagen.

Das Problem, wie man am effizientesten prüft ob eine Frage schon gespielt wurde, kann man dann natürlich auch unterschiedlich lösen. Bei der von mit genannten Bitmap-Methode hat man deterministischen Aufwand und eine klar definierte Datenmenge.

Bei Verwendung einer Spielernummer-Fragenummer Relation kann ich einen Monte-Carlo Algorithmus probieren, d.h. drei Fragen zufällig bestimmen und per

SELECT frageId FROM SpielerFrage 
WHERE spielerID = :spielerID AND frageId IN (:frage1, :frage2, :frage3)

feststellen, ob eine Frage schon mal gestellt wurde. Mit einem Index auf (spielerID,frageID) ist das vermutlich eine schnelle Abfrage. Aber - wenn die Spieler viele Rows hat, wird sie eher nicht mehr auf eine Indexpage passen und daher doch zusätzlichen Leseaufwand im SQL Server auslösen. Bei Kollision würfele ich die kollidierenden Fragen neu aus und wiederhole die Query. Das klappt alles ganz gut, wenn die Quote bisher gespielter Fragen klein ist, aber das wird schnell schlechter (bei 10000 Fragen und 100 gespielten Fragen ist die Doublettenchance 3%, bei 1000 gespielten Fragen schon 27%, bei 2000 sind es 49% und bei 3000 sind es 66%. Sowas kann man natürlich per stored procedure rein im SQL Server abfackeln, ohne den Gameserver damit aufzuhalten, oder man kann gleich mehrere Fragen pro Kategorie erwürfeln und versuchen, die Query so geschickt zu gestalten dass sie pro Kategorie die erste ungestellte Frage zurückgibt.

Habe ich 3 ungestellte Fragen, muss ich sie in die Tabelle inserten. Jetzt wird es langsamer, weil ich einen ständigen Strom von INSERTs habe und daher regelmäßig unter Lese-Last die Knoten im Indexbaum spalten muss. Das ist bei meinem Bitmap-Vorschlag nicht der Fall, hier wird der Index im Wesentlichen nur gelesen, gespielte Fragen gelangen als Update in die entsprechende Row.

Aber letztlich hilft wohl nur eine Probeimplementierung und Lasttest :)

Rolf

[TS]

Hallo und guten Tag,

Das ist sicherlich handhabbar. Aber bei bei Vielspielern wird es zum Problem, bei jedem Spiel die für sie relevanten Rows zu laden. Hat der Spieler schon 5000 Fragen gespielt, muss man für ihn 5000 Rows laden. Bei Verwendung eines Cluster-Index stehen die zwar beisammen, aber dafür hast Du den Aufwand des Clusterns. Des weiteren sind 2/3 des zu lesenden Volumens (db-intern) keine Fragenummer, sondern die Usernummer. Für Wenigspieler mag das eine sinnvolle Lösung sein, bei Vielspielern würde ich das nicht tun.

Um sich den Aufwand mit einer Neuindexierung zu ersparen, wird man das Problem anders lösen!

Für die Fragen baut man sich eine direkt gestreute Tabelle mit einem Feld "Spiel-Status[1]". Für den User baut man sich jeweils eine Tabelle, welche Fragen er schon gespielt hat. Beginnt ein User ein neues Spiel, wählt man für Ihn ein Kontingent an Fragen aus, das auch sofort im Spiel-Status als "im Spiel" gekennzeichnet wird. Da kein Index neu geschrieben werden muss, geht das relativ schnell.

Für andere Spieler sind diese Fragen dann solange gesperrt oder - wenn der User sie tatsächlich alle spielt - bleiben sie es auch. Sie werden dann nach und nach nur im Status-Feld auf "gespielt" umgestellt. Wenn der Benuter abbricht, werden die nicht gespielten Fragen "zurückgegeben". Das bedeutet, der Status wird auf frei zurückgesetzt.

Um keinen nicht balancierten Index zu erzeugen für die Status-Felder, kann man dann von Zeit zu Zeit die gepielten Fragen aus der Tabelle entfernen (wenn Zeit dafür ist).

Wenn die Fragen bereits in gemischter Form in der Tabelle vorliegen, braucht man sie nur von vorne streng sequentiell ab einem Aufsetzpunkt durchzuackern, bis man jeweils ein Kontingent für einen User zusammengetragen hat. Da hierbei nur zum Auffinden des Aufsetzpunktes ein Indexzugriff benötigt wird, vermindern sich die Indexzugriffe um den Faktor der Anzahjl der Fragen pro Spiel.

Nach diesem Schema baue ich Dir das ohne Datenbanksystem (habe ich 1991 schon mal...).

[1] Man kann auch direkt die Usernummer einsetzen, 0 == "ungespielt".

Ich hoffe, Ihr konntet mir folgen.

Grüße
TS

[TS]

Hallo und guten Tag,

Wenn die Fragen bereits in gemischter Form in der Tabelle vorliegen, braucht man sie nur von vorne streng sequentiell ab einem Aufsetzpunkt durchzuackern, bis man jeweils ein Kontingent für einen User zusammengetragen hat. Da hierbei nur zum Auffinden des Aufsetzpunktes ein Indexzugriff benötigt wird, vermindern sich die Indexzugriffe um den Faktor der Anzahjl der Fragen pro Spiel. Und wenn man tatsächlich eine Ramdom-Access-Datei gebaut hat, benötigt man gar keinen Index. Fragenummer * Blockgröße -> Zugriffspunkt.

Schneller kann es keine Datenbank! Manchmal ist back to the Roots einfach das bessere Konzept.

Grüße
TS

[Rolf b]

Direkt gestreut? Was ist das, eine Mischung aus Direktzugriff und Hashing? Du wirst wohl eher eine Datei mit direktem Zugriff meinen (d.h. die Speicherposition wird eineindeutig und kollisionsfrei aus den Dateninhalten bestimmt, bei Hashing kann es Kollisionen geben).

Aber warum brauchst Du überhaupt eine Fragentabelle? Wenn User A gegen User B spielt und gleichzeitig irgendwo anders der User C gegen User D, spricht doch nichts dagegen, wenn beide die gleiche Frage bekommen. Der Fragengenerator muss ein paar Fragen auswürfeln und dann für A UND B (bzw. für C UND D) prüfen, ob ihnen diese Fragen neu sind. Um das zu prüfen, brauche ich keine übergreifende Fragentabelle, nur die gespielten Fragen pro User.

Allerdings haben wir ja mittlerweile auch gelernt, dass sich die Fragen in der App wiederholen und das Thema vom App-Hersteller gar nicht angegangen wurde. Die haben sich diese Riesen-DB lieber gespart :) Insofern ist unser Gespräch rein akademisch, aber das macht ja auch Spaß...

Für den User halte ich den Ansatz mit einer Tabelle pro User für nicht so gut, weil man dann eine Direktzugriffsdatei pro User braucht und dann das Problem bekommt, 50.000.000 Dateien für die App zu managen (ist vielleicht kein Prob für Unix, für Windows wär's eins). Also, wenn man es schon ohne DB machen will, dann lieber eine Riesendatei (bzw. über Nummernkreise der Usernummer in mehrere Riesendateien partitionieren) und da einen zusammenhängenden Bereich pro User reservieren, in dem sich die Map der gespielten Fragen findet. Als einfache Lösung ein Byte pro Frage, als etwas kniffligere Lösung ein Bit pro Frage (siehe meinen Bitmap-Vorschlag von oben). Kleines Problem ist, dass gelöschte User Löcher in der Datei hinterlassen, dafür bräuchte man entweder eine Logik, die freiwerdende Usernummern wiederverwendet oder man schaltet eine Indirektion ein und verwendet zum Positionieren in der Direktzugriffsdatei Blocknummern, die man beim Registrieren dem User zuordnet.

Ob sich das dann performancemäßig lohnt, oder ob man die User-Fragen-Map doch wieder als Spalte in der User-Tabelle aufnimmt - wer weiß...

Rolf

[TS]

Hallo und guten Tag,

Direkt gestreut? Was ist das, eine Mischung aus Direktzugriff und Hashing?

Das ist ein Fachbegriff der Informatik um ca. 1970, also von den ersten Bandanlagen bis hin zum IBM XT mit 10MB-Festplatte. Der scheint so alt und etabliert zu sein (in meinen Fachbüchern steht er drin), dass sogar Google ihn nicht kennt. Die Amis nannten das wohl "Random Access File", was es aber nicht genau trifft. Google ist ja auch erst ca. 35 Jahre später erfunden worden!

Du wirst wohl eher eine Datei mit direktem Zugriff meinen (d.h. die Speicherposition wird eineindeutig und kollisionsfrei aus den Dateninhalten bestimmt, bei Hashing kann es Kollisionen geben).

Mit Dateninhalten hat die Position nichts zu tun, sondern nur mit der (festen) Blockgröße des Datensatzes. Ob da etwas drinsteht, oder die Datenfelder leer sind, ist unerheblich. Aber jeder Datensatz hat eine feste Größe und damit auch einen festen Aufsetzpunkt in der Datenspeicherung. Ob die Felder darin auch eine feste Größe haben, oder sich die Gesamtgröße des Datensatzes teilen, ist dann die nächste Entwicklungsstufe.

Aber warum brauchst Du überhaupt eine Fragentabelle? Wenn User A gegen User B spielt und gleichzeitig irgendwo anders der User C gegen User D, spricht doch nichts dagegen, wenn beide die gleiche Frage bekommen.

Die Aufgabenstellung stammt nicht von mir. Wenn es Bedingung ist, dass jede Frage nur genau einmal gespielt werden darf, reicht die direkt gestreute Datei dafür aus. Wenn dann auch noch Historie für die User, für das Spiel usw. geschrieben werden soll, benötigt man ggf. weitere Dateien.

Der Fragengenerator muss ein paar Fragen auswürfeln und dann für A UND B (bzw. für C UND D) prüfen, ob ihnen diese Fragen neu sind. Um das zu prüfen, brauche ich keine übergreifende Fragentabelle, nur die gespielten Fragen pro User.

Wenn die Fragen öfter gespielt werden dürfen, reicht das aus. Wenn jede Frage nur einmal gespielt werden darf, benötigt man auch eine Eigenschaftentabelle für die Fragen. Eine einwertige Eigenschaft kann man dann selbstverständlich direkt in der Fragentabelle mit unterbringen. Für mehrwertige Eigenschaften benötogt man ggf. zusätzliche Tabellen.

Allerdings haben wir ja mittlerweile auch gelernt, dass sich die Fragen in der App wiederholen

Das ist aber so in der ursprünglichen Aufgabenstellung noch nicht geändert worden.

Grüße
TS

[Rolf b]

Direkt gestreut? Was ist das, eine Mischung aus Direktzugriff und Hashing?

Das ist ein Fachbegriff der Informatik um ca. 1970. Der scheint so alt und etabliert zu sein (in meinen Fachbüchern steht er drin), dass sogar Google ihn nicht kennt. Die Amis nannten das wohl "Random Access File", was es aber nicht genau trifft.

Ist ok. Ich habe nicht wirklich nachgedacht. "Direkt" hat verschiedene Varianten und "Gestreut" ist eine davon. "Random Access" passt zu "Direkt". Den alten IBM Begriff (aus der *AM Abkürzungsgruppe) für Direktzugriff mit Hashing finde ich heutzutage auch nicht mehr, und meine "schlauen" Bücher von damals (ich habe '85 angefangen) sind schon längst zu Klopapier oder Zeitung geworden.

Mit kam der Begriff nur erst mal in sich widersprüchlich vor.

Rolf

[TS]

Hallo und guten Morgen,

Direkt gestreut? Was ist das, eine Mischung aus Direktzugriff und Hashing?

Das ist ein Fachbegriff der Informatik um ca. 1970. Der scheint so alt und etabliert zu sein (in meinen Fachbüchern steht er drin), dass sogar Google ihn nicht kennt. Die Amis nannten das wohl "Random Access File", was es aber nicht genau trifft.

Ich habe jetzt nochmal geschaut, wie der Begriff klassifiziert wurde:

Direkt gestreute Struktur:
Eine Speicheranordnung auf einem Datenträger, die es über einen ordinalen Suchbegriff (Index) gestattet, den Startpunkt der gesuchten Teilstruktur direkt zu adressieren.

Der Begriff der Ordinalität gehört also wohl zwingend dazu. Die ist bei "Fragennummer" ja eindeutig gegeben. Und wenn es Frage Nummer 90184 nicht gibt, bleibt der Speicherblock eben leer, aber er exisiert auf dem Datenträger.

Grüße
TS

[Regina Schlauklug]

Dort kommen bei jedem Spieldurchgang 4 Fragen, diese wiederholen sich im laufe des Spielen nicht mehr, und bei weiteren Spielen auch nicht mehr.

Ich weiß das war nur ein Beispiel, der Vollständigkeit wegen aber eine Korrektur dazu: Bei Quizduell kann die gleiche Frage in späteren Spielen wieder kommen. Das weiß ich aus eigener Erfahrung.

[Der Martin]

Hallo,

Bei Quizduell kann die gleiche Frage in späteren Spielen wieder kommen. Das weiß ich aus eigener Erfahrung.

sicher, dass es die gleiche Frage war und nicht bloß eine sehr ähnliche? - Zumindest hat der Moderator Jörg Pilawa in einer Sendung vor ein paar Tagen mal erklärt, man habe für jede Kategorie einen großen Vorrat an Fragen, und wenn eine Frage einmal gespielt wurde, sei sie raus aus dem Pool.

Was mir allerdings hin und wieder auffällt: Anscheinend werden Fragen zwischen verschiedenen Quizsendungen herumgereicht. Es kommt öfters vor, dass eine Frage erst beim Quizduell auftaucht, und kurze Zeit später fast wörtlich identisch z.B. bei Wer wird Millionär oder Gefragt, Gejagt. Oder auch andersrum. Da ich allgemein ein Fan solcher Quizshows bin und sie häufig anschaue (zumindest wenn ich sowieso zuhause bin), kriege ich das manchmal mit.

So long,
 Martin

[Rolf b]

Haben "Quizduell im Ersten" und die "Quizduell-App" den gleichen Fragenpool? Das, was Pilawa sagt, muss nicht für die fernsehunabhängige App gelten.

[Der Martin]

Hallo,

Haben "Quizduell im Ersten" und die "Quizduell-App" den gleichen Fragenpool?

da bin ich nicht sicher. Vermutlich nicht. Sicher ist das nur für die Spieler, die live während der Sendung mitspielen. Die kriegen genau dieselben Fragen wie die Kandidaten.

Das, was Pilawa sagt, muss nicht für die fernsehunabhängige App gelten.

Stimmt, an die hatte ich nicht gedacht.

So long,
 Martin

[Auge]

Hallo

Bei Quizduell kann die gleiche Frage in späteren Spielen wieder kommen. Das weiß ich aus eigener Erfahrung.

sicher, dass es die gleiche Frage war und nicht bloß eine sehr ähnliche?

Ja. Die Fragen kommen, wenn man regelmäßig spielt, -zigfach wieder.

Tschö, Auge

[Der Martin]

Hi,

Bei Quizduell kann die gleiche Frage in späteren Spielen wieder kommen. Das weiß ich aus eigener Erfahrung.

sicher, dass es die gleiche Frage war und nicht bloß eine sehr ähnliche?

Ja. Die Fragen kommen, wenn man regelmäßig spielt, -zigfach wieder.

du sprichst auch von der App, die unabhängig von der Sendung läuft? Denn ich bezog mich nur auf die Fernsehsendung; die App hatte ich gar nicht auf dem Radar.

So long,
 Martin

[Auge]

Hallo

Bei Quizduell kann die gleiche Frage in späteren Spielen wieder kommen. Das weiß ich aus eigener Erfahrung.

sicher, dass es die gleiche Frage war und nicht bloß eine sehr ähnliche?

Ja. Die Fragen kommen, wenn man regelmäßig spielt, -zigfach wieder.

du sprichst auch von der App, die unabhängig von der Sendung läuft?

Genau die.

Tschö, Auge