¿La velocidad de las búsquedas de fila / columna de DataSet?

Question

Hace poco tuve que procesar cosas pesadas con datos almacenados en un DataSet. Fue lo suficientemente pesado que terminé usando una herramienta para ayudar a identificar algunos cuellos de botella en mi código. Cuando estaba analizando los cuellos de botella, noté que aunque las búsquedas en DataSet no eran terriblemente lentas (no eran el cuello de botella), era más lenta de lo que esperaba. Siempre asumí que los DataSets usaban algún tipo de implementación de estilo HashTable que haría búsquedas O (1) (o al menos eso es lo que creo que son HashTables). La velocidad de mis búsquedas parecía ser significativamente más lenta que esta.

Me preguntaba si a alguien que sepa algo sobre la implementación de la clase DataSet de .NET le gustaría compartir lo que sabe.

Si hago algo como esto:

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

¿Qué tan rápido sería el tiempo de búsqueda para el método Contains (...) , y para recuperar el valor para almacenar en Object o ? Pensé que sería muy rápido como un HashTable (asumiendo que lo que entiendo sobre HashTables es correcto) pero no lo parece ...

Escribí ese código de memoria, por lo que algunas cosas pueden no ser " sintácticamente correctas " ;.

Answer 1

A través de Reflector , los pasos para DataRow [" ColumnName "] son:

1. Obtenga el DataColumn de ColumnName. Utiliza el objeto DataColumnCollection [" ColumnName "] de la fila. Internamente, DataColumnCollection almacena sus DataColumns en un Hastable. O (1)
2. Obtener el índice de fila de DataRow. El índice se almacena en un miembro interno. O (1)

3. Obtenga el valor de DataColumn en el índice usando DataColumn [índice]. DataColumn almacena sus datos en un miembro System.Data.Common.DataStorage (interno, abstracto):

   devuelve dataColumnInstance._storage.Get (recordIndex);

   Una implementación concreta de ejemplo es System.Data.Common.StringStorage (interno, sellado). StringStorage (y los otros DataStorages concretos que verifiqué) almacenan sus valores en una matriz. Get (recordIndex) simplemente toma el objeto en la matriz de valores en el recordIndex. O (1)

Entonces, en general, usted es O (1), pero eso no significa que el hash y la función de llamada durante la operación sean sin costo. Simplemente significa que no cuesta más a medida que aumenta el número de DataRows o DataColumns.

Es interesante que DataStorage use una matriz para los valores. No puedo imaginar que sea fácil de reconstruir cuando agregas o eliminas filas.

Answer 2

En realidad, es recomendable utilizar un número entero al hacer referencia a la columna, que puede mejorar mucho en términos de rendimiento. Para mantener las cosas manejables, podrías declarar un entero constante. Así que en lugar de lo que hiciste, podrías hacerlo

const int SomeTable_SomeColumn = 0;

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

Answer 3

Me imagino que cualquier búsqueda sería O (n), ya que no creo que usen ningún tipo de tabla hash, pero en realidad usaría más de una matriz para encontrar filas y columnas.

Answer 4

En realidad, creo que los nombres de las columnas se almacenan en un Hashtable. Debe ser O (1) o búsqueda constante para búsquedas sensibles a mayúsculas y minúsculas. Si tuviera que mirar a través de cada uno, entonces, por supuesto, sería O (n).