.net - 令人惊讶的性能差异 : List. Contains、SortedList.ContainsKey、DataRowCollection.Contains、Data Table.Select、DataTable.FindBy

Question

最初我想询问查询数据表中特殊行的最快方法。

我测试了 5 种不同方法的性能，结果令人惊讶(对我来说)。

背景: 我在 MS Sql-Server 2005 数据库中创建了一个 View 。该 View 当前的总行数为 6318 行。因为我必须经常检查给定的 id 是否存在于该 View 中，所以我想知道什么是最有效的方法。我在强类型数据集中创建了一个 DataAdapter，它返回所有行并填充数据表。 我的第一个方法是创建一个共享通用列表(Int32)，并在应用程序启动时用 View 中的 ID 填充它。然后使用List.Contains检查当前 ID 是否在此列表中。因为所有行都是不同的，我想知道使用 SortedList 及其 ContainsKey 是否不是更快-方法。 然后我还检查了直接访问数据表的性能 Select-Method ，它是自动生成的(当列定义为主键时)FindBy-method最后但并非最不重要的一点是 DatarowCollection.Contains -方法。 所以我有 5 种方法来检查我的 ID 是否在该 View (或映射列表/排序列表)中。

我用System.Diagnostics.StopWatch测量了他们的表现并得到了一些有趣的结果。我认为 SortedList.ContainsKey 一定比 List.Contains 更快，因为它们是不同的且已排序，但事实恰恰相反。 但最令我惊讶的是 DataRowCollection.Contains-Method(我首先忘记的)是迄今为止最快的。它甚至比 dataTable.FindBy 方法快 50 倍。

1. 是什么导致了这些差异？
2. 我是否忘记了更好的方法？
3. 我的测量方法是否正确(我认为我最好应该循环它们并获取该值)？
4. 这些值是否可转移或取决于数据表/集合的大小？
5. 在我的更新(1000000 次迭代)之后，ContainsKey 是最快的。这是因为我总是检查相同的 id 还是一般情况？是否有某种没有字典键值对开销的 SortedList？

结果 [1000000 次迭代*]

• 时间跨度 1 = SortedList.ContainsKey = Ø 0.65634 [238.1095] 毫秒
• 时间跨度 2 = List.Contains = Ø 0.06802 [57045.37955] 毫秒
• 时间跨度 3 = DataTable.FindByIdData (自动生成的方法)= Ø 0.31580 [1542.62345] ms
• 时间跨度 4 = DataTable.Select = Ø 0.27790 [26029.39635] 毫秒

• 时间跨度 5 = DataRowCollection.Contains = Ø 0.00638 [1202.79735] 毫秒

  1.)
  Timespan 1: 0,6913 ms
  Timespan 2: 0,1053 ms
  Timespan 3: 0,3279 ms
  Timespan 4: 0,1002 ms
  Timespan 5: 0,0056 ms
  
  2.)
  Timespan 1: 0,6405 ms
  Timespan 2: 0,0588 ms
  Timespan 3: 0,3112 ms
  Timespan 4: 0,3872 ms
  Timespan 5: 0,0067 ms
  
  3.)
  Timespan 1: 0,6502 ms
  Timespan 2: 0,0588 ms
  Timespan 3: 0,3092 ms
  Timespan 4: 0,1268 ms
  Timespan 5: 0,007 ms
  
  4.)
  Timespan 1: 0,6504 ms
  Timespan 2: 0,0586 ms
  Timespan 3: 0,3092 ms
  Timespan 4: 0,3893 ms
  Timespan 5: 0,0063 ms
  
  5.)
  Timespan 1: 0,6493 ms
  Timespan 2: 0,0586 ms
  Timespan 3: 0,3215 ms
  Timespan 4: 0,386 ms
  Timespan 5: 0,0063 ms
  
  
  
  Timespan 1: 0,6913 0,6405 0,6502 0,6504 0,6493 = Ø 0,65634
  Timespan 2: 0,1053 0,0588 0,0588 0,0586 0,0586 = Ø 0,06802
  Timespan 3: 0,3279 0,3112 0,3092 0,3092 0,3215 = Ø 0,31580
  Timespan 4: 0,1002 0,3872 0,1268 0,3893 0,3860 = Ø 0,27790
  Timespan 5: 0,0056 0,0067 0,0070 0,0063 0,0063 = Ø 0,00638
  

为了完整起见，VB.Net 源部分:

Dim applies As Boolean
Dim clock As New System.Diagnostics.Stopwatch

clock.Start()
For i As Int32 = 1 To 1000000
    applies = sortedListAC17NextClaims.ContainsKey(myClaim.idData)
Next
clock.Stop()
Dim timeSpan1 As String = "Timespan 1: " & clock.Elapsed.TotalMilliseconds.ToString & " ms"

clock.Reset()
clock.Start()
For i As Int32 = 1 To 1000000
    applies = listAC17NextClaims.Contains(myClaim.idData)
Next
clock.Stop()
Dim timeSpan2 As String = "Timespan 2: " & clock.Elapsed.TotalMilliseconds.ToString & " ms"

clock.Reset()
clock.Start()
For i As Int32 = 1 To 1000000
    applies = Not MyDS.AC17NextClaims.FindByIdData(myClaim.idData) Is Nothing
Next
clock.Stop()
Dim timeSpan3 As String = "Timespan 3: " & clock.Elapsed.TotalMilliseconds.ToString & " ms"

clock.Reset()
clock.Start()
For i As Int32 = 1 To 1000000
    applies = MyDS.AC17NextClaims.Select("idData=" & myClaim.idData).Length > 0
Next
clock.Stop()
Dim timeSpan4 As String = "Timespan 4: " & clock.Elapsed.TotalMilliseconds.ToString & " ms"

clock.Reset()
clock.Start()
For i As Int32 = 1 To 1000000
    applies = MyDS.AC17NextClaims.Rows.Contains(myClaim.idData)
Next
clock.Stop()
Dim timeSpan5 As String = "Timespan 5: " & clock.Elapsed.TotalMilliseconds.ToString & " ms"

• 更新: 我已经改变了我的结果和上面的来源。方括号中是 1000000 次迭代的值。现在结果完全不同了。现在最快的方法肯定是SortedList的ContainsKey。

• 更新 2: 我忘记了使用 List.BinarySearch 的替代方案。 这对我来说似乎是最快的:

  clock.Start()
  For i As Int32 = 1 To 1000000
      applies = listAC17NextClaims.BinarySearch(myClaim.idData) > -1
  Next
  clock.Stop()
  

  只需要 219.1805 毫秒即可执行 1000000 次迭代，因此是最快的，没有 SortedList-KeyValue-Pair 的开销。 我可以使用它而无需对列表进行排序，因为 DataAdapter 使用 Order By 子句填充数据表。

Answer 1

为什么不使用具有 HashTable 的集合作为底层数据结构( Dictionary<TKey, TValue> 或 HashSet<T> )？ HashTables应该提供O(1)如果键中没有冲突(正如您所说)，则查找时间并且不需要“排序”的开销。

编辑:如果您只想存储 key ，则应该使用 HashSet<T>它在 .NET 3.5 及更高版本中可用。

From MSDN在排序列表上:

Operations on a SortedList object tend to be slower than operations on a Hashtable object because of the sorting.

要以 .NET 2.0 为目标，您可以自行推出或使用预构建的，例如 Wintellect's Power Collections (您也可以轻松地使用源代码)。