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

Lesen Sie jede Zeile und entscheiden Sie anhand einer Zufallszahl, ob Sie die Zeile behalten oder ignorieren wollen. Für die erste Zeile wollen Sie eine Quote von 1:1, für die zweite eine Quote von 1:2 usw.

count = 0;
while (fgets(line, length, stream) != NULL)
{
    count++;
    if ((rand() * count) / RAND_MAX == 0)
        strcpy(keptline, line);
}

Ich habe nicht überprüft, ob dies die richtigen Zufallseigenschaften hat, aber auf den ersten Blick scheint es richtig zu sein.

---

Es wurde darauf hingewiesen, dass ein Integer-Überlauf bei der Art und Weise, wie der Vergleich kodiert ist, schnell zu einem Problem werden würde, und ich war unabhängig davon selbst zu demselben Schluss gekommen. Es gibt wahrscheinlich viele Möglichkeiten, dies zu beheben, aber dies ist die erste, die mir einfällt:

if ((rand() / (float)RAND_MAX) <= (1.0 / count))

Answer 2

Die Antwort von Mark ist fast richtig, bis auf zwei Punkte:

1. Wenn eine Zeile länger ist als length - 1 Zeichen (einschließlich des Zeilenumbruchs), dann wird die while Schleife wird inkrementiert count mindestens zweimal für dieselbe Zeile: einmal für die erste length - 1 Zeichen, ein weiteres für das nächste length - 1 Zeichen, etc.
2. Die Berechnung der rand() * count kann einen Integer-Überlauf verursachen.

Um das erste Problem zu lösen, können Sie fgets in einen Papierkorb, bis er zurückkehrt NULL (was auf einen E/A-Fehler oder EOF ohne gelesene Daten hinweist) oder der Papierkorbpuffer enthält einen Zeilenumbruch:

count = 0;
while (fgets(line, length, stream) != NULL)
{
    char *p = strchr(line, '\n');
    if (p != NULL) {
        assert(*p == '\n');
        *p = '\0'; // trim the newline
    }
    else { // haven't reached EOL yet. Read & discard the rest of the line.
#define TRASH_LENGTH 1024
        char trash[TRASH_LENGTH];
        while((p = fgets(trash, TRASH_LENGTH, stream)) != NULL) {
            if ((p = strchr(trash, '\n')) != NULL) // reached EOL
                break;
        }
    }
    assert(strchr(line, '\n') == NULL); // `line` does not contain a newline
    count++;
    // ...

Das zweite Problem kann mit dem Vorschlag von @tvanfosson gelöst werden, wenn keine Fließkommaarithmetik verfügbar ist:

int one_chance_in(size_t n)
{
    if (rand() % n == 0) // `rand` returns an integer in [0, `RAND_MAX`]
        return 1;
    else
        return 0;
}

Aber beachten Sie, dass rand() % n ist keine einheitliche, diskrete Zufallsvariable auch wenn rand() wird als eins angenommen, weil die Wahrscheinlichkeit, dass rand() % n == 0 kann so viel wie 1/ RAND_MAX höher als die gewünschte Wahrscheinlichkeit 1/ n . Auf meinem Rechner, RAND_MAX ist 2147483647, also beträgt die Differenz 4,66 × 10 -10 , aber der C-Standard verlangt nur, dass RAND_MAX mindestens 32767 betragen (3,05 × 10 -5 Unterschied).

Für alle, die sich (wie ich) fragen, warum dieses Schema funktioniert, könnte es hilfreich sein, die Berechnung der Wahrscheinlichkeit durchzugehen, dass die erste Zeile in keptline wenn es m Linien und verallgemeinern: Bei der ersten Iteration der Schleife ist die Wahrscheinlichkeit, dass die erste Zeile nach keptline ist 1/1. Bei der zweiten Iteration der Schleife ist die Wahrscheinlichkeit, dass die zweite Zeile nicht Überschreiben der ersten Zeile ist 1/2. Bei der dritten Iteration ist die Wahrscheinlichkeit, dass die dritte Zeile nicht die erste Zeile zu überschreiben, beträgt 2/3. Die Wahrscheinlichkeit, dass die letzte Zeile die erste Zeile nicht überschreibt, ist also ( m - 1)/ m . Somit bleibt die Wahrscheinlichkeit, dass die erste Zeile in keptline nach Iteration über alle Zeilen ist:

1/1 × 1/2 × 2/3 × 3/4 × ... × ( m - 2)/( m - 1) × ( m - 1)/ m \= 1/ m

Die Wahrscheinlichkeit, dass die zweite Zeile bleibt in keptline ist:

1/2 × 2/3 × 3/4 × ... × ( m - 2)/( m - 1) × ( m - 1)/ m \= 1/ m

Die Wahrscheinlichkeit, dass die dritte Zeile bleibt in keptline ist:

1/3 × 3/4 × ... × ( m - 2)/( m - 1) × ( m - 1)/ m \= 1/ m

Etc. Sie sind alle 1/ m .

Answer 3

Diese Methode ist gut, weil:

i) Sie können weiterhin zufällige Zeilen ohne große Kosten erzeugen

ii) Sie müssen die Datei insgesamt nur 1 Mal lesen + jeweils 1 Zeile pro gewünschter Zufallszeile. Der Überschuss an gelesenen Daten ist nur so groß wie die Datei selbst.

iii) Es gibt jeder Zeile eine faire Chance, unabhängig von ihrer Position in der Datei.

iv) Es gibt jeder Zeile eine faire Chance, egal wie lang sie in der Datei ist.

Die Anregung:

Ich würde einen 2-Pass-Algorithmus vorschlagen. Eigentlich ist es ein 1-Durchgang + N Zeilen. Dabei ist N die Anzahl der zufälligen Zeilen, die Sie wünschen.

Im ersten Durchgang berechnen Sie die Anzahl der Zeilen und die Anfangspositionen der einzelnen Zeilen.

Dann nehmen Sie eine Zufallszahl zwischen 0 und der Anzahl der Zeilen minus 1. Mit dieser Zufallszahl, die Ihr Zeilenindex ist, ermitteln Sie die Startposition für diesen Zeilenindex. Suchen Sie an dieser Position.

Sie müssen dann nur noch einmal lesen und kennen die genaue Größe. (bis zum Startindex der nächsten Zeile)

Wie man die Anzahl der Zeilen und den Index jeder Zeile speichert:

Um die Anzahl der Zeilen zu speichern, können Sie natürlich einfach einen int verwenden.

Wenn Sie einen Vektor verwenden können, können Sie jeden Zeilenindex zum Vektor hinzufügen. Wenn nicht, können Sie einfach ein Array von Ints mit der maximalen Anzahl von Zeilen erstellen, die Sie denken, dass es sein wird. Dann indexieren Sie in dieses Array.

Andere Antworten:

In einer anderen Antwort wurde erwähnt, dass Sie eine Zufallszahl zwischen 1 und der Größe der Datei wählen und dann den nächstgelegenen Zeilenumbruch verwenden können. Aber das wird nicht funktionieren. Es könnte z. B. eine Zeile sehr lang sein und die anderen nicht so lang. In diesem Fall hätten Sie eine ungleichmäßige Verteilung.

Answer 4

1. Ermittelt die Länge der Datei.
2. Wählen Sie eine zufällige Position in der Datei.
3. Suchen Sie diese Position auf.
4. Iterieren Sie vorwärts, bis Sie ein Zeilenumbruchszeichen finden.
5. Wenn Sie kein Zeilenumbruchszeichen finden, gehen Sie zurück zum Anfang.
6. Verwenden Sie gets(), um die Zeile zu lesen.

Answer 5

Ich habe eine alternative Lösung. Da es sich bei der Plattform um den DS handelt, sollten Sie wahrscheinlich nicht versuchen, die Datei im Speicher zu halten. Damit wird die Datei zweimal gelesen. Einmal, um die Zeilen zu zählen und das 2. Mal, um die gewünschte Zeile zu finden. Es läuft langsamer als die anderen bisher vorgeschlagenen Lösungen, aber es verbraucht kaum Speicher. Ich habe es sogar für Sie in C geschrieben (die Fehlerbehandlung habe ich weggelassen):

main(int argc, char **argv)
{
    FILE *f;
    int nLines = 0;
    char line[1024];
    int randLine;
    int i;

    srand(time(0));
    f = fopen(argv[1], "r");

/* 1st pass - count the lines. */
    while(!feof(f))
    {
        fgets(line, 1024, f);
        nLines++;
    }

    randLine = rand() % nLines;
    printf("Chose %d of %d lines\n", randLine, nLines);

/* 2nd pass - find the line we want. */
    fseek(f, 0, SEEK_SET);
    for(i = 0; !feof(f) && i <= randLine; i++)
        fgets(line, 1024, f);

    printf("%s", line);
}

UPDATE: Ups, ich hätte die Antwort von Brian R. Bondy lesen sollen, bevor ich das hier gepostet habe, aber ich war irgendwie besessen vom Schreiben des Codes und habe es nicht bemerkt. Dies ist fast das Gleiche, außer dass es die Zeilenpositionen nicht in einem Array speichert. Man kann es so oder so machen, je nachdem, wie groß die Datei ist und ob die Geschwindigkeit wichtiger ist als der Speicherbedarf.