Lettura di una riga casuale da un file di testo di grandi dimensioni

Question

Ho un file con più di 5000 righe. Voglio trovare il modo più efficiente per scegliere una di queste righe ogni volta che eseguo il mio programma. Inizialmente avevo intenzione di usare il metodo casuale per sceglierne uno (era prima che sapessi che c'erano 5000 linee). Pensavo che potesse essere inefficiente quindi ho pensato di dare un'occhiata alla prima riga, quindi eliminarla dall'alto e aggiungerla in fondo. Ma sembra che devo leggere l'intero file e creare un nuovo file da eliminare dall'alto.

Qual è il modo più efficiente: il metodo casuale o il nuovo metodo di file?

Il programma sarà eseguito ogni 5 minuti e sto usando C# 4.5

Answer 1

presumo che l'obiettivo è quello di scegliere a caso una riga da un file di 5000+ linee.

Prova questo:

1. ottenere il conteggio line utilizzando file.readlines (file) Count().
2. Generare un numero casuale, utilizzando il conteggio delle righe come limite superiore.
3. Eseguire una lettura lenta del file con File.ReadLines (file).
4. Scegliere una linea da questa matrice utilizzando il numero casuale.

MODIFICA: come indicato, fare File.ReadLines (file) .toArray() è piuttosto inefficiente.

Answer 2

In .NET 4. *, è possibile accedere direttamente a una singola riga di un file. Ad esempio, per ottenere la linea X:

string line = File.ReadLines(FileName).Skip(X).First(); 

completa esempio:

var fileName = @"C:\text.txt" 
var file = File.ReadLines(fileName).ToList(); 
int count = file.Count(); 
Random rnd = new Random(); 
int skip = rnd.Next(0, count); 
string line = file.Skip(skip).First(); 
Console.WriteLine(line); 

Answer 3

Ecco una rapida implementazione di @LucasTrzesniewski s metodo proposto nei commenti alla domanda:

// open the file 
using(FileStream stream = File.OpenRead("yourfile.dat")) 
{ 
    // 1. index all offsets that are the beginning of a line 
    List<Long> lineOffsets = new List<Long>(); 
    lineOffsets.Add(stream.Position); //the very first offset is a beginning of a line! 
    int ch; 
    while((ch = stream.ReadByte()) != -1) // "-1" denotes the end of the file 
    { 
     if(ch == '\n') 
      lineOffsets.Add(stream.Position); 
    } 

    // 2. read a random line 
    stream.Seek(0, SeekOrigin.Begin); // go back to the beginning of the file 
    // set the position of the stream to one the previously saved offsets 
    stream.Position = lineOffsets[new Random().Next(lineOffsets.Count)]; 
    // read the whole line from the specified offset 
    using(StreamReader reader = new StreamReader(stream)) 
    { 
     Console.WriteLine(reader.ReadLine()); 
    } 
} 

I don Non ho alcun VS vicino a me al momento, quindi non è stato verificato.

Answer 4

Supponiamo che il file sia così grande che non ci si può permettere di inserirlo nella RAM. Poi, si vorrebbe utilizzare Reservoir Sampling, un algoritmo progettato per gestire la raccolta in modo casuale dalle liste di sconosciuti, lunghezza arbitraria che potrebbero non adattarsi in memoria:

Random r = new Random(); 
int currentLine = 1; 
string pick = null; 
foreach (string line in File.ReadLines(filename)) 
{ 
    if (r.Next(currentLine) == 0) { 
     pick = line; 
    } 
    ++currentLine; 
} 
return pick; 

A un livello elevato, il campionamento serbatoio segue una regola di base: ogni l'ulteriore linea ha una possibilità di 1/N di sostituire tutte le linee precedenti.

Questo algoritmo non è intuitivo. Ad un livello alto, funziona facendo in modo che la linea N abbia una possibilità 1/N di sostituire la linea attualmente selezionata. Quindi, la linea 1 ha una probabilità del 100% di essere selezionata, ma una possibilità del 50% di essere successivamente sostituita dalla linea 2.

Ho trovato la comprensione di questo algoritmo per essere più semplice sotto forma di una prova di correttezza. Quindi, una semplice dimostrazione per induzione:

1) Caso di base: tramite ispezione, l'algoritmo funziona se è presente 1 riga.
2) Se l'algoritmo funziona per le linee N-1, l'elaborazione delle linee N funziona perché:
3) Dopo l'elaborazione delle iterazioni N-1 di un file di linee N, tutte le linee N-1 sono ugualmente probabili (probabilità 1/(N -1)).
4) La successiva iterazione assicura che la linea N ha una probabilità di 1/N (perché è quello assegna esplicitamente l'algoritmo, ed è l'iterazione finale), riducendo la probabilità di tutte le linee precedenti:

1/(N-1) * (1-(1/N)) 
1/(N-1) * (N/N-(1/N)) 
1/(N-1) * (N-1)/N 
(1*(N-1))/(N*(N-1)) 
1/N 

Se si conosce il numero di righe presenti nel file in anticipo, questo algoritmo è più costoso del necessario, poiché legge sempre l'intero file.