Velocità delle ricerche di righe / colonne DataSet?

Question

Recentemente ho dovuto fare delle cose pesanti molto elaborate con i dati memorizzati in un DataSet. Era abbastanza pesante che ho finito per usare uno strumento per aiutare a identificare alcuni colli di bottiglia nel mio codice. Quando stavo analizzando i colli di bottiglia, ho notato che sebbene le ricerche di DataSet non fossero tremendamente lente (non erano il collo di bottiglia), era più lento di quanto mi aspettassi. Ho sempre pensato che i DataSet usassero una sorta di implementazione di stile HashTable che avrebbe reso le ricerche O (1) (o almeno questo è quello che penso siano HashTables). La velocità delle mie ricerche sembrava essere significativamente più lenta di questa.

Mi chiedevo se qualcuno che fosse a conoscenza dell'implementazione della classe DataSet di .NET avrebbe voluto condividere ciò che sapeva.

Se faccio una cosa del genere:

DataTable dt = new DataTable();
if(dt.Columns.Contains("SomeColumn"))
{
    object o = dt.Rows[0]["SomeColumn"];
}

Quanto sarebbe veloce il tempo di ricerca per il metodo Contains (...) e per recuperare il valore da archiviare in Object o ? Avrei pensato che fosse molto veloce come una HashTable (supponendo che ciò che ho capito su HashTables sia corretto) ma non sembra ...

Ho scritto quel codice dalla memoria, quindi alcune cose potrebbero non essere "sintatticamente corrette".

Answer 1

Tramite Reflector i passaggi per DataRow [" ColumnName "] sono:

1. Ottieni DataColumn da ColumnName. Utilizza DataColumnCollection della riga [" ColumnName "]. Internamente, DataColumnCollection memorizza i suoi DataColumns in un Hastable. O (1)
2. Ottieni l'indice di riga del DataRow. L'indice è memorizzato in un membro interno. O (1)

3. Ottieni il valore di DataColumn nell'indice utilizzando DataColumn [indice]. DataColumn archivia i suoi dati in un membro System.Data.Common.DataStorage (interno, astratto):

   return dataColumnInstance._storage.Get (recordIndex);

   Un'implementazione concreta di esempio è System.Data.Common.StringStorage (interno, sigillato). StringStorage (e gli altri DataStorage concreti che ho controllato) memorizzano i loro valori in un array. Get (recordIndex) prende semplicemente l'oggetto nella matrice di valori in recordIndex. O (1)

Quindi nel complesso sei O (1) ma ciò non significa che l'hash e la chiamata di funzione durante l'operazione siano gratuiti. Significa solo che non costa di più all'aumentare del numero di DataRows o DataColumns.

Interessante che DataStorage utilizzi un array per i valori. Non riesco a immaginare che sia facile ricostruire quando aggiungi o rimuovi righe.

Answer 2

In realtà è consigliabile usare numeri interi quando si fa riferimento alla colonna, il che può migliorare molto in termini di prestazioni. Per mantenere le cose gestibili, potresti dichiarare un numero intero costante. Quindi, invece di quello che hai fatto, potresti fare

const int SomeTable_SomeColumn = 0;

DataTable dt = new DataTable();
if(dt.Columns.Contains(SomeTable_SomeColumn))
{
    object o = dt.Rows[0][SomeTable_SomeColumn];
}

Answer 3

Immagino che qualsiasi ricerca sarebbe O (n), poiché non penso che utilizzerebbero alcun tipo di hashtable, ma in realtà utilizzerebbero più di un array per trovare righe e colonne.

Answer 4

In realtà, credo che i nomi delle colonne siano memorizzati in un Hashtable. Dovrebbe essere O (1) o una ricerca costante per le ricerche con distinzione tra maiuscole e minuscole. Se dovesse guardare attraverso ciascuno, ovviamente sarebbe O (n).