Ich bereite mich auf ein Telefoninterview vor. Ich bin im Internet auf diese Fragen gestoßen. Kann mir jemand eine gute Antwort auf diese Fragen geben?
Angenommen, ich gebe Ihnen eine Textdatei und möchte Sie bitten, ein Programm zu schreiben, das eine zufällige Zeile aus der Datei zurückgibt (alle Zeilen müssen die gleiche Wahrscheinlichkeit haben, zurückgegeben zu werden)
Wie Teil 1, nur dass diesmal die gesamte Textdatei nicht in den Hauptspeicher passt
Wie Teil 2, nur dass Sie jetzt einen Stream anstelle einer Datei haben.
Bitte helfen Sie.
Ok ... @ Alle, ich hatte wirklich ein paar Ideen in meinem Pfefferminz, bevor ich das frage ... Als ich den unerbittlichen Angriff meiner Kollegen sehe, poste ich meine Antworten. Bitte zögern Sie nicht, sie auch anzugreifen ...
1: Zählen Sie die Anzahl von '\ n' in der Datei. Erzeugen Sie eine Zufallszahl zwischen 1 und der Zahl und geben Sie die Zeile nach der Zahl 1 '\ n' zurück.
2: Bringe die Datei Teil für Teil in den Hauptspeicher und folge der obigen Prozedur.
3: Ich habe keine Ahnung davon und würde mich über etwaige Eingaben freuen.
Es ist wundervoll, dass ihr euch wirklich inspiriert, weiterzumachen .....
Liest alle Zeilen in ein Array ein und gibt eine zufällige Zeile im Bereich 1 und die Anzahl der Zeilen zurück.
Am einfachsten: Zählen Sie die Zeilen, wählen Sie zufällig eine Zeilennummer, gehen Sie die Datei ein zweites Mal durch und geben Sie sie zurück.
Sie müssen sich nur an eine Zeile erinnern. Jede neue Zeile hat eine Wahrscheinlichkeit von 1 / N (N wird gelesen).
Pseudocode:
%Vor%Algorithmus Nummer 3 könnte auch für 1 und 2 verwendet werden.
Sie können dies tun, ohne alle Zeilen im Speicher lesen zu müssen, was gut für große Dateien funktioniert. Pseudocode:
%Vor% Beweis : Zunächst möchten wir darauf hinweisen, dass wir immer die erste Zeile in ret speichern. Wenn die Datei eine Zeile hat, werden Sie sie auswählen, und Sie sind fertig.
Bei zweizeiliger Datei speichert ret die erste Zeile zu 100% und die zweite Zeile wird in ret 50% der Zeit während der zweiten Iteration der Schleife gespeichert. Daher wird für jede Zeile eine Wahrscheinlichkeit von 0,5 ausgewählt.
Nehmen wir nun an, dass diese Methode für Dateien mit ≤ N -Zeilen funktioniert. Um zu beweisen, dass dies für N+1 funktioniert, gibt es in der (N+1) -ten Iteration der Schleife eine Wahrscheinlichkeit von 1/(N+1) , dass die letzte Zeile ausgewählt wird ( random(0, N+1) < 1 hat diese Wahrscheinlichkeit). Somit hat die letzte Zeile 1/(N+1) Wahrscheinlichkeit, ausgewählt zu werden. Die Wahrscheinlichkeit, dass alle anderen Zeilen ausgewählt werden, ist immer noch gleich, nennen wir das x . Dann N*x + 1/(N+1) == 1 , was bedeutet, dass x = 1/(N+1) .
Beweis durch Induktion ist abgeschlossen.
Bearbeiten : Ups, die dritte Methode der ersten Antwort wurde vor der Antwort nicht angezeigt. Dennoch werde ich diesen Beitrag hier behalten, wenn nur für den Beweis, und die Möglichkeit für andere Leute, es zu korrigieren, wenn es irgendwelche Fehler darin gibt.
Zu 1: Lösung zu 2 verwenden
Zu 2: Sie möchten die gesamte Datei mit einem RandomAccessFile-Zugriff scannen, um die Anzahl der Zeilen zu zählen und (möglicherweise) die Dateizeiger für jeden Zeilenanfang zwischenzuspeichern. Dann könnten Sie eine zufällig auswählen (ich gehe davon aus, dass es bei dieser Frage nicht darum geht, Zufallszahlen zu generieren) und zu diesem Startpunkt zurückkehren, die Zeile lesen und zurückgeben. Wenn Sie es schnell wollen, stellen Sie sicher, dass Sie die Lesevorgänge puffern (raf ist sonst langsam).
Zu 3: Wenn der Stream nicht in den Speicher passt (dh Sie können das Ganze nicht zwischenspeichern) und Sie wissen nicht, wie viele Zeilen im Stream sind, ohne den gesamten Stream zu lesen (vorausgesetzt, Sie bekommen nur gelesen) einmal) dann kann ich keine Lösung sehen. Ich warte auch auf Antworten ...