Скорость поиска строк/столбцов DataSet?

Question

Недавно мне пришлось выполнить очень тяжелую работу по обработке данных, хранящихся в DataSet.Он был настолько тяжелым, что мне пришлось использовать инструмент, помогающий выявить некоторые узкие места в моем коде.Анализируя узкие места, я заметил, что хотя поиск в DataSet был не очень медленным (узким местом не были они), он оказался медленнее, чем я ожидал.Я всегда предполагал, что DataSets использует какую-то реализацию стиля HashTable, которая будет выполнять поиск O (1) (или, по крайней мере, я думаю, что это то, чем являются HashTables).Скорость моего поиска, казалось, была значительно медленнее.

Мне было интересно, захочет ли кто-нибудь, кто знает что-нибудь о реализации класса DataSet в .NET, поделиться своими знаниями.

Если я сделаю что-то вроде этого:

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

Насколько быстрым будет время поиска Contains(...) метод и для получения значения для хранения в Object o?Я бы подумал, что это будет очень быстро, как HashTable (при условии, что то, что я понимаю о HashTables, правильно), но это не так...

Я написал этот код по памяти, поэтому некоторые вещи могут быть «синтаксически правильными».

Answer 1

С помощью Отражатель шаги для DataRow["ColumnName"]:

1. Получите DataColumn из ColumnName.Использует DataColumnCollection["ColumnName"] строки.Внутри DataColumnCollection хранит свои DataColumns в Hastable.О(1)
2. Получите индекс строки DataRow.Индекс хранится во внутреннем элементе.О(1)

3. Получите значение DataColumn по индексу, используя DataColumn[index].DataColumn хранит свои данные в элементе System.Data.Common.DataStorage (внутреннем, абстрактном):

   вернуть dataColumnInstance._storage.Get(recordIndex);

   Пример конкретной реализации — System.Data.Common.StringStorage (внутренний, запечатанный).StringStorage (и другие проверенные мной конкретные хранилища данных) хранят свои значения в массиве.Get(recordIndex) просто захватывает объект из массива значений по адресу RecordIndex.О(1)

Итак, в целом вы O (1), но это не означает, что хеширование и вызов функций во время операции не требуют затрат.Это просто означает, что это не будет стоить больше по мере увеличения количества DataRows или DataColumns.

Интересно, что DataStorage использует массив для значений.Не могу себе представить, что это легко перестроить, когда вы добавляете или удаляете строки.

Answer 2

На самом деле при ссылке на столбец рекомендуется использовать целое число, что может значительно улучшить производительность.Чтобы сохранить управляемость, вы можете объявить постоянное целое число.Поэтому вместо того, что вы сделали, вы могли бы сделать

const int SomeTable_SomeColumn = 0;

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

Answer 3

Я предполагаю, что любой поиск будет O (n), поскольку я не думаю, что они будут использовать какой-либо тип хеш-таблицы, но на самом деле будут использовать больше массива для поиска строк и столбцов.

Answer 4

На самом деле, я считаю, что имена столбцов хранятся в хеш-таблице.Должен быть O(1) или постоянный поиск для поиска с учетом регистра.Если бы ему пришлось просмотреть каждый из них, то, конечно, это было бы O(n).