DataSet行/列查找的速度？

Question

最近,我不得不对存储在DataSet中的数据做一些非常重要的处理.它足够重,我最终使用工具来帮助识别代码中的一些瓶颈.当我分析瓶颈时,我注意到尽管DataSet查找速度并不是非常慢(它们不是瓶颈),但它比我预期的要慢.我总是假设DataSet使用某种HashTable样式实现,这将使查找O(1)(或者至少是我认为的HashTables).我的查找速度似乎明显慢于此.

我想知道是否有人知道.NET的DataSet类的实现,他们会分享他们所知道的内容.

如果我做这样的事情:

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

查找时间对于该Contains(...)方法的速度有多快,以及检索要存储的值的时间有多快Object o？我会认为它像HashTable一样非常快(假设我对HashTables的理解是正确的)但它似乎不是......

我从内存中编写了这段代码,所以有些东西可能不是"语法正确".

Answer 1

通过Reflector， DataRow["ColumnName"] 的步骤是：

1. 从 ColumnName 获取 DataColumn。使用行的 DataColumnCollection["ColumnName"]。在内部，DataColumnCollection 将其 DataColumn 存储在 Hastable 中。复杂度(1)
2. 获取 DataRow 的行索引。索引存储在内部成员中。复杂度(1)

3. 使用 DataColumn[index] 获取索引处 DataColumn 的值。DataColumn 将其数据存储在 System.Data.Common.DataStorage （内部、抽象）成员中：

   返回 dataColumnInstance._storage.Get(recordIndex);

   具体实现示例是 System.Data.Common.StringStorage（内部、密封）。StringStorage（以及我检查的其他具体 DataStorage）将它们的值存储在数组中。Get(recordIndex) 只是获取值数组中 recordIndex 处的对象。复杂度(1)

所以总的来说，你的时间复杂度是 O(1)，但这并不意味着操作期间的散列和函数调用是没有成本的。这只是意味着随着 DataRows 或 DataColumns 数量的增加，成本不会增加。

有趣的是，DataStorage 使用数组来存储值。无法想象当您添加或删除行时重建会很容易。