Velocidade de DataSet pesquisas de linha / coluna?

Question

Recentemente eu tinha que fazer alguma coisa pesada muito processamento com dados armazenados em um DataSet. Foi o suficiente pesado que acabei usando uma ferramenta para ajudar a identificar alguns gargalos no meu código. Quando eu estava analisando os gargalos, notei que, embora pesquisas de conjunto de dados não foram terrivelmente lento (que não eram o gargalo), foi mais lento do que eu esperava. Eu sempre assumiu que DataSets usado algum tipo de implementação estilo HashTable que faria pesquisas de O (1) (ou pelo menos isso é o que eu penso Hashtables são). A velocidade das minhas pesquisas parecia ser significativamente mais lento do que isso.

Eu queria saber se alguém que sabe alguma coisa sobre a implementação da classe DataSet do .NET se importaria de compartilhar o que sabem.

Se eu fizer algo como isto:

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

Como rápido que o tempo de pesquisa ser para o método Contains(...), e para recuperar o valor a loja em Object o? Eu teria pensado que ser muito rápido como um HashTable (supondo que eu entendo sobre Hashtables está correta), mas não parece que isso ...

Eu escrevi que o código da memória assim que algumas coisas podem não ser "sintaticamente correto".

Answer 1

refletor os passos para DataRow [ "ColumnName"] são:

1. Obter o DataColumn de ColumnName. Usa DataColumnCollection do row [ "ColumnName"]. Internamente, DataColumnCollection armazena seus DataColumns em um Hastable. O (1)
2. Obter índice de linha do DataRow. O Índice é armazenado em um membro interno. O (1)

3. Obter o valor da DataColumn no índice usando DataColumn [índice]. DataColumn armazena seus dados em um (abstract interna), membro System.Data.Common.DataStorage:

   retornar dataColumnInstance._storage.Get (recordIndex);

   Uma implementação concreta amostra é System.Data.Common.StringStorage (interno, selado). StringStorage (e os outros DataStorages concretas que verifiquei) armazenar seus valores em uma matriz. Obter (recordIndex) simplesmente agarra o objecto na matriz valor no recordIndex. O (1)

Portanto, em geral você está O (1), mas isso não significa que o hashing e função de chamada durante a operação é sem custo. Significa apenas que não custa mais do que o número de DataRows ou DataColumns aumenta.

Interessante que DataStorage usa uma matriz de valores. Não posso imaginar que é fácil de reconstruir quando você adicionar ou linhas remover.

Answer 2

Na verdade, é aconselhável o uso inteiro ao fazer referência a coluna, o que pode melhorar muito em termos de desempenho. Para manter as coisas gerenciável, você poderia declarar constante inteira. Então, ao invés do que você fez, você poderia fazer

const int SomeTable_SomeColumn = 0;

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

Answer 3

Eu imagino que quaisquer pesquisas seria O (n), como eu não acho que eles iriam usar qualquer tipo de hashtable, mas seria realmente usar mais de uma matriz para encontrar linhas e colunas.

Answer 4

Na verdade, eu acredito que as colunas nomes são armazenados em uma tabela de hash. Deve ser O (1) ou de pesquisa constante para pesquisas de caso-sensível. Se ele tinha que olhar através de cada, então é claro que seria O (n).