2013-10-16 7 views
5

Ho un dictionary<string, int[]> che ho bisogno di archiviare e recuperare nel modo più efficiente possibile dal disco.Il modo più efficiente per archiviare/recuperare un dizionario in C#?

La lunghezza della chiave (stringa) varia in genere da 1 a 60 caratteri (unicode) ma potrebbe superare tale lunghezza (questo è tuttavia marginale e questi valori potrebbero essere scartati). Gli interi nell'array saranno compresi nell'intervallo da 1 a 100 milioni. (In genere, da 1 a 5 M)

La mia prima idea era quella di utilizzare un formato delimitato:

key [tab] int,int,int,int,... 
key2 [tab] int,int,int,int,... 
... 

e per caricare il dizionario come segue:

string[] Lines = File.ReadAllLines(sIndexName).ToArray(); 
string[] keyValues = new string[2]; 
List<string> lstInts = new List<string>(); 
// Skip the header line of the index file. 
for (int i = 1; i < Lines.Length; i++) 
{ 
    lstInts.Clear(); 
    keyValues = Lines[i].Split('\t'); 
    if (keyValues[1].Contains(',')) 
    { 
     lstInts.AddRange(keyValues[1].Split(',')); 
    } 
    else 
    { 
     lstInts.Add(keyValues[1]); 
    } 
    int[] iInts = lstInts.Select(x => int.Parse(x)).ToArray(); 
    Array.Sort(iInts); 
    dic.Add(keyValues[0], iInts);    
} 

Funziona, ma andare oltre il requisiti di dimensioni potenziali, è ovvio che questo metodo non verrà mai scalato abbastanza bene.

Esiste una soluzione off-the-shelf per questo problema o è necessario rielaborare completamente l'algoritmo?


Edit: Sono un po 'imbarazzato ad ammetterlo, ma non sapevo dizionari potevano solo essere serializzati in binario. Ho dato un test ed è praticamente quello di cui avevo bisogno.

Ecco il codice (suggerimenti di benvenuto)

public static void saveToFile(Dictionary<string, List<int>> dic) 
{ 
    using (FileStream fs = new FileStream(_PATH_TO_BIN, FileMode.OpenOrCreate)) 
    { 
     BinaryFormatter bf = new BinaryFormatter(); 
     bf.Serialize(fs, dic); 
    } 
} 

public static Dictionary<string, List<int>> loadBinFile() 
{ 
    FileStream fs = null; 
    try 
    { 
     fs = new FileStream(_PATH_TO_BIN, FileMode.Open); 
     BinaryFormatter bf = new BinaryFormatter(); 
     return (Dictionary<string, List<int>>)bf.Deserialize(fs); 
    } 
    catch 
    { 
     return null; 
    } 
} 

con un dizionario di 100k voci con una serie di 4k interi ciascuno, la serializzazione richiede 14 secondi e deserializzazione 10 secondi e il file risultante è 1,6 GB.

@Patryk: Si prega di convertire il commento in una risposta in modo che possa contrassegnarlo come approvato.

+1

Per "efficientemente" si intende "efficiente in termini di dimensioni"? – Stefan

+0

@Stefan - la dimensione/velocità sembra non essere un problema poiché OP lo memorizza in un file di testo ... Ma in effetti è necessario sapere quale tipo di "scala è sufficiente" prima di poter rispondere. –

+1

Poche note a margine; piuttosto che avere la tua lista fuori dal giro e svuotarla costantemente, basta definire la lista all'interno del ciclo. La divisione di una stringa senza delimitatori restituisce semplicemente un array di dimensione uno con quel valore, quindi non è necessario controllare se la stringa contiene ',', basta dividerlo ogni volta e aggiungere tutti i valori all'elenco, anche se "tutto" è solo uno. Hai bisogno di ordinare l'array? Se stai ricreando una struttura esistente, perché non sono già ordinati? – Servy

risposta

0

Il Dictionary<TKey, TValue> è contrassegnato come [Serializable] (e implementa ISerializable) che can be seen here.

Ciò significa che è possibile utilizzare ad es. BinaryFormatter per eseguire la serializzazione binaria e la deserializzazione da e verso uno stream. Dì, FileStream. :)

1

Suppongo che vogliate ridurre l'ingombro della memoria durante il caricamento. In questo momento stai caricando tutto in memoria in un array, quindi copi tutto in un dizionario. Fino a quando l'array originale non sarà più fuori campo e verrà raccolta la garbage, ci sarà un periodo di tempo con circa 2 volte l'utilizzo della memoria necessario. Se è un file molto grande, potrebbe essere molto ... se è solo pochi megabyte non è un grosso problema.

Se si vuole fare questo in modo più efficiente si può leggere i dati da un flusso in questo modo:

string fileName = @"C:\..."; 
var dict = new Dictionary<string, int[]>(); 

using (var fs = new FileStream(fileName, FileMode.Open)) 
using (var reader = new StreamReader(fs)) 
{ 
    string line; 
    while ((line = reader.ReadLine()) != null) 
    { 
     var values = line.Split(','); 
     dict.Add(values[0], values.Skip(1).Select(x => Convert.ToInt32(x)).ToArray()); 
    }  
} 

oppure è possibile utilizzare la scorciatoia Jim suggerito:

string fileName = @"C:\..."; 
var dict = new Dictionary<string, int[]>(); 

foreach (string line in File.ReadLines(fileName)) 
{ 
    var values = line.Split(','); 
    dict.Add(values[0], values.Skip(1).Select(x => Convert.ToInt32(x)).ToArray()); 
} 

Questo rende un po 'stretto presunzioni sul formato del file. In particolare, ogni riga è nel formato key,int1,int2,int3,int4,... e che la chiave non contiene una virgola. Ogni riga deve anche terminare con un carattere Environment.NewLine.

Anche se vale la pena notare che è necessario considerare il fatto che mentre il codice corrente non è molto efficiente, non è il collo di bottiglia principale. La velocità di lettura del file è solitamente il collo di bottiglia più grande. Se si è in realtà si verificano problemi di prestazioni con il codice che molto probabilmente ha a che fare semplicemente con la lettura dal file in modo sincrono. Qualsiasi I/O di file dovrebbe essere eseguito in modo asincrono in un'applicazione con un'interfaccia utente.

+1

+1. Si noti che è possibile sostituire molto di quel codice con 'foreach (riga di stringa in File.ReadLines (fileName))' –