Struttura del file del disco per una lista di stringhe di grandi dimensioni con letture veloci per indice

0

Ho una lunga lista di stringhe. Ogni stringa ha una lunghezza diversa, proprio come una frase nel testo. La lunghezza media è inferiore a 255 caratteri. Per favore, proponi la struttura dei file su disco per abilitare il prelievo rapido di una frase casuale. Ciò significa che ho bisogno di veloce: * leggi il conteggio totale * leggi la stringa N-esima. Non ci sono requisiti di tempo di scrittura. È meglio se la struttura sarebbe semplice e lo spreco di spazio su disco è minimo.

Vengo con il seguente formato:

<N, number of strings>
<S1, fixed size first chunk of string 1,
    right padded with zeroes if size of chunk is less than size of string>
...
<SN, string N chunk, ends with index of next string N chunk,
    if string N dont fits in single chunk>
<SN+1, string N additional chunk 1>
<SN+2, string N additional chunk 2>

Pezzi aggiuntivi della stessa stringa che posso mettere insieme per ridurre al minimo la ricerca e la lettura. In questo modo seleziono ogni stringa con uguale probabilità e la leggo con un minimo di 1 ricerca e 1 lettura e al massimo 2 ricerche e 2 letture. Posso scegliere una lunghezza di stringa media come dimensione di un blocco.

    
posta Dmitry Teslenko 25.04.2017 - 11:53
fonte

2 risposte

1

Questo mi sembra un compito a casa, ma cercherò di dare la mia risposta migliore qui.

L'archiviazione per cercare / cercare qualsiasi valore nel disco è un problema risolto. I DBMS fanno tutto il tempo, e l'unica cosa che il DBMS fa meglio della maggior parte dei programmi è I / O.

Detto questo, prendi la stessa struttura che usano per memorizzare gli indici B Trees o Alberi B + .

Se sei veramente interessato a qualcosa di veloce per le query e hai ottime capacità di hash, potresti creare una sorta di tabella basata su hash indice.

    
risposta data 25.04.2017 - 14:41
fonte
0

Questo processo può solo essere veloce se hai fissato record di lunghezza, permettendoti di saltare il file su un particolare record in base al suo valore di indice (e alla lunghezza del record).

Domanda: Perché questo deve essere in un file singolo ?

  • Memorizza ogni frase in un file separato, numerato, in una singola directory.
  • Salva il numero di file in un altro file "count".
  • Leggi il file count.
  • Genera il numero casuale in base al conteggio.
  • Leggi il file appropriato.
risposta data 25.04.2017 - 12:48
fonte

Leggi altre domande sui tag