losowa linia w pliku

Question

To pytanie zostało mi udzielone podczas wywiadu. Wywiad jest już dawno za nami, ale ja wciąż myśli o hte problemu i jego podsłuch mnie:

Masz język, który zawiera następujące narzędzia: a rand() funkcji, while i for pętli if oświadczeń, oraz sposobu readline() (podobne do Pythona readline()). Biorąc pod uwagę te narzędzia, napisz algorytm, który zwraca losową linię w pliku. Nie znasz rozmiaru pliku, a pętlę można przewinąć tylko raz.

Answer 1

nie wiem pożądaną odpowiedź, ale moje rozwiązaniem byłoby następujące:

chosen_line = "" 
lines = 0 

while (current_line = readline()): 
    if (rand(0, lines) == 0): 
     chosen_line = current_line 

    lines++ 

return chosen_line 

Edit: dobre wyjaśnienie dlaczego to działa został opublikowany w this comment.

Answer 2

Jedną z metod, zapewniając jednolitą dystrybucję:

(1) odczytać pliku wiersz po wierszu w szeregu (i podobne, np pytona list)

(2) Za pomocą rand() aby wybrać liczba od 0 do największego indeksu w tablicy.

Innym, nie gwarantuje równomierny rozkład:

przeczytać każdy wiersz. Przy każdym czytaniu również wywołaj rand(). Jeśli przekroczysz próg, zwróć linię.

Answer 3

Mimo że jest podobny do trzeciej opcji Marcela, implementacja Luc zawsze zwraca pierwszą linię, parsując cały plik.

Powinno być coś takiego:

chosen_line = "" 
treshold = 90 
max = 100 

while chosen_line == "": 
    current_line = readline() 
    if (rand(0, max) > treshold): 
     chosen_line = current_line 

print chosen_line 

Można również powrócić current_line w przypadku linia nie została wybrana i przeczytać cały plik.