Dies ist im Wesentlichen eine eingeschränktere Version von diese Frage .
Angenommen, wir haben eine sehr große Textdatei mit einer großen Anzahl von Zeilen.
Wir müssen eine zufällige Zeile aus der Datei mit einer einheitlichen Wahrscheinlichkeit auswählen, aber es gibt Einschränkungen:
Mein erster Gedanke ist, einen lstat() Aufruf zu verwenden, um die gesamte Dateigröße in Bytes zu erhalten. fseek() kann dann verwendet werden, um direkt auf einen zufälligen Byte-Offset zuzugreifen und etwas wie O (1) Zugriff in einen zufälligen Teil der Datei zu bekommen.
Das Problem ist, dass wir dann nicht so etwas wie den nächsten Zeilenumbruch lesen und ihn als Tag bezeichnen können, denn das würde eine Verteilung erzeugen, die auf lange Zeilen ausgerichtet ist.
Mein erster Gedanke, dieses Problem zu lösen, besteht darin, bis zu den ersten "n" Zeilenumbrüchen zu lesen (wenn nötig, zurück zum Anfang der Datei) und dann aus dieser kleineren Menge eine Zeile mit einheitlicher Wahrscheinlichkeit auszuwählen. Es kann davon ausgegangen werden, dass der Inhalt der Datei zufällig angeordnet ist, so dass diese Unterstichprobe in Bezug auf die Länge einheitlich sein sollte, und da ihr Startpunkt einheitlich aus allen möglichen Punkten ausgewählt wurde, sollte sie eine einheitliche Wahl aus der Datei darstellen ganze. In pseudo-C sieht unser Algorithmus also so aus:
%Vor%Das scheint keine besonders elegante Lösung zu sein, und ich bin nicht ganz sicher, dass es einheitlich sein wird, also frage ich mich, ob es einen besseren Weg dafür gibt. Irgendwelche Gedanken?
EDIT: Bei weiterer Überlegung bin ich mir jetzt ziemlich sicher, dass meine Methode nicht einheitlich ist, da der Startpunkt eher in längeren Wörtern liegt und somit nicht einheitlich ist. Tricky!
Wählen Sie ein zufälliges Zeichen aus der Datei (über rand and seek wie Sie notiert haben). Nun, anstatt die dazugehörige Zeilenschaltung zu finden, würde ich den folgenden Algorithmus anwenden, da dies so ist, wie Sie es angemerkt haben:
%Vor%Ich kann nicht sehen, wie das alles außer einer gleichmäßigen Verteilung von Linien geben konnte. Die Effizienz hängt von der durchschnittlichen Länge einer Linie ab. Wenn Ihre Datei relativ kurze Zeilen hat, könnte dies praktikabel sein. Wenn jedoch die Datei selbst vom Betriebssystem nicht vorgeladen werden kann, müssen Sie möglicherweise einen hohen Preis für die Suche nach physischen Datenträgern bezahlen.
Lösung gefunden, die überraschend gut funktioniert. Hier für mich und andere dokumentieren.
Dieser Beispielcode führt in der Praxis etwa 80.000 Zeichen pro Sekunde aus, mit einer mittleren Zeilenlänge, die mit der der Datei übereinstimmt, mit 4 signifikanten Ziffern bei den meisten Läufen. Im Gegensatz dazu bekomme ich ungefähr 250 Züge pro Sekunde mit der Methode aus dem Querverweisende Frage .
Im Wesentlichen wird ein zufälliger Platz in der Datei abgetastet und dann wieder verworfen und mit der Wahrscheinlichkeit umgekehrt proportional zur Zeilenlänge gezeichnet. Dies hebt die Voreingenommenheit für längere Wörter auf. Im Durchschnitt erstellt die Methode eine Anzahl von Draws, die der durchschnittlichen Zeilenlänge in der Datei entspricht, bevor sie akzeptiert wird.
Einige bemerkenswerte Nachteile:
Dateien mit längeren Zeilenlängen benötigen in der rdraw-Funktion eine größere Konstante als 50, was in der Praxis für viel längere Suchzeiten bedeutet, wenn die Zeilenlängen eine hohe Varianz aufweisen. Zum Beispiel habe ich es auf BUFSIZ für eine Datei eingestellt, die ich getestet habe, mit verringerter Ziehgeschwindigkeit auf ungefähr 10000 Ziehungen pro Sekunde. Immer noch viel schneller als das Zählen von Zeilen in der Datei.
%Vor%Wenn sich die Datei erst am Ende ändert (es werden mehr Zeilen hinzugefügt), können Sie einen Algorithmus mit einheitlicher Wahrscheinlichkeit erstellen:
Vorbereitung: Erstellen Sie eine Indexdatei, die den Offset für jede n: te Zeile enthält. Verwenden Sie ein Format mit fester Breite, damit die Position verwendet werden kann, um zu bestimmen, welcher Datensatz Sie haben.
Öffnen Sie die Indexdatei und lesen Sie den letzten Datensatz. Verwenden Sie ftell , um die Datensatznummer zu bestimmen.
Öffnen Sie die große Datei und fseek für den in Schritt 1 erhaltenen Offset.
Lesen Sie die große Datei bis zum Ende und zählen Sie die Anzahl der Zeilenumbrüche. Sie haben jetzt die Gesamtzahl der Zeilen in der großen Datei.
Generieren Sie eine Zufallszahl bis zur Anzahl der in Schritt 3 erhaltenen Zeilen.
fseek und lesen Sie den entsprechenden Datensatz in der Indexdatei.
fseek auf den entsprechenden Offset in der großen Datei. Überspringen Sie den Rest der Zeilenumbrüche.
Lies die Zeile!
Beispiel
Nehmen wir an, wir haben n = 100 gewählt und die große Datei enthält 367 Zeilen.
Indexdatei:
%Vor%Die Indexdatei hat 4 Datensätze, also enthält die große Datei mindestens 300 Datensätze (100 * (4-1)). Letzter Offset ist 16303.
Öffnen Sie die große Datei und fseek bis 16303.
Zählen Sie die verbleibende Anzahl von Zeilen (67).
Generata eine Zufallszahl im Bereich [0-366]. Nehmen wir an, wir haben 112.
112/100 = 1 mit 12 als Rest. Lesen Sie den Index-Datei-Datensatz mit Offset 1. Wir erhalten das Ergebnis 4753.
fseek bis 4753 in der großen Datei und dann 11 (12-1) Zeilen überspringen.
Lesen Sie die 12. Zeile.
Voila!
Bearbeiten:
Ich habe gesehen, wie sich der Kommentar zur Zieldatei geändert hat. Wenn sich die Zieldatei nur selten ändert, kann dies immer noch ein praktikabler Ansatz sein. Sie müssen vor dem Wechseln der Zieldatei eine neue Indexdatei erstellen. Möglicherweise möchten Sie auch die Indexdatei aktualisieren, wenn die Zieldatei um mehr als n rows gewachsen ist.
Tags und Links c random random-access