6

最近，我不得不对存储在 DataSet 中的数据进行一些非常繁重的处理。它足够重，以至于我最终使用了一个工具来帮助识别我的代码中的一些瓶颈。当我分析瓶颈时，我注意到虽然 DataSet 查找并不是很慢（它们不是瓶颈），但它比我预期的要慢。我一直认为 DataSets 使用了某种 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 的理解是正确的），但它看起来不像......

我从内存中编写了该代码，因此有些事情可能不是“语法正确”。

4

4 回答 4

3

实际上，在引用列时建议使用整数，这样可以大大提高性能。为了使事情易于管理，您可以声明常量整数。所以你可以做而不是你所做的

const int SomeTable_SomeColumn = 0;

DataTable dt = new DataTable();
if(dt.Columns.Contains(SomeTable_SomeColumn))
{
    object o = dt.Rows[0][SomeTable_SomeColumn];
}
于 2008-09-28T05:56:09.747 回答
2

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

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

  3. 使用 DataColumn[index] 在索引处获取 DataColumn 的值。DataColumn 将其数据存储在 System.Data.Common.DataStorage (internal, abstract) 成员中：

    返回 dataColumnInstance._storage.Get(recordIndex);

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

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

有趣的是，DataStorage 使用数组作为值。无法想象添加或删除行时重建起来很容易。

于 2008-10-29T18:28:58.057 回答
0

我想任何查找都是 O(n)，因为我认为它们不会使用任何类型的哈希表，但实际上会使用更多的数组来查找行和列。

于 2008-09-28T01:01:16.587 回答
0

实际上，我相信列名存储在哈希表中。对于区分大小写的查找，应该是 O(1) 或常量查找。如果它必须逐个查看，那当然是 O(n)。

于 2008-09-28T01:09:32.107 回答