Was ist der beste Weg, um eine zufällige Zeile in einer Textdatei mit C zurückzugeben?

Question

Was ist der beste Weg, um eine zufällige Zeile in einer Textdatei mit C zurückzugeben? Es muss die Standard-I/O-Bibliothek verwendet werden ( <stdio.h> ), weil es für Nintendo DS Homebrew ist.

Klarstellungen:

• Die Verwendung einer Kopfzeile in der Datei, um die Anzahl der Zeilen zu speichern, funktioniert nicht für das, was ich tun möchte.
• Ich möchte, dass es so zufällig wie möglich ist (am besten ist es, wenn jede Zeile die gleiche Wahrscheinlichkeit hat, ausgewählt zu werden wie jede andere Zeile).
• Die Datei wird während der Ausführung des Programms nicht geändert. (Es ist der DS, also kein Multi-Tasking.)

Answer 1

Sie müssen lediglich eine nicht skalierte Zufallszahl pro Zeile erzeugen und dabei den Höchstwert für alle von Ihnen erzeugten Zufallszahlen beibehalten. Jedes Mal, wenn Sie den Maximalwert aktualisieren, überschreiben Sie die ausgewählte Zeile mit der aktuellen Zeile.

Am Ende erhalten Sie die Zeile mit der höchsten Zahl, die rand() ausgespuckt hat, was bei allen Ihren Zeilen gleich wahrscheinlich sein sollte.

Answer 2

Nur eine kurze Anmerkung zu Mark Ransom Der DS hat keine FPU, so dass die Fließkommadivision in Software emuliert wird und sehr langsam ist. Sie wollen vermeiden, typecasting/Promotion zu float oder double um jeden Preis, wenn Geschwindigkeit ein Anliegen ist.

Hier ist ein anderer Weg, um einen Integer-Überlauf zu vermeiden, der ohne Fließkomma-Mathematik auskommt:

if(rand() <= RAND_MAX / count)

Die Wahrscheinlichkeiten können aufgrund der Integer-Division etwas verzerrt sein, aber auf einem DS sollte das Ganze sicherlich viel schneller laufen.

Answer 3

Verwenden Sie eine Kombination aus Adams Ansatz des zufälligen Versatzes in die Datei und Marks Wahrscheinlichkeitsansatz. Mit Adams Methode können Sie zufällig einen Abschnitt der Datei finden. Dann verwenden Sie Marks Ansatz, um zu vermeiden, dass die größeren Zeichenketten bevorzugt werden. Marks Algorithmus wird die ersten paar Zeichenfolgen bevorzugen, egal wo er beginnt,