令人惊讶的性能差异:List.Constains,SortedList.ContainsKey,DataRowCollection.Contains,DataTable.Select,DataTable.FindBy

Question

最初我想问一个查询Datatable特殊行的最快方法.

我已经为他们的表现测试了5种不同的方法,结果令人惊讶(对我而言).

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

我使用System.Diagnostics.StopWatch测量了它们的性能并获得了一些有趣的结果.我认为SortedList.ContainsKey必须比List.Contains更快,因为它们是不同的和排序的,但反之亦然.但对我来说最令人惊讶的是DataRowCollection.Contains-Method(我第一次忘记了)是迄今为止最快的.它甚至比dataTable.FindBy方法快50倍.

1. 是什么造成了这些差异
2. 我忘记了更好的方法吗？
3. 我的测量方法是否正确(我认为我应该更好地循环它们并采用这些值)？
4. 值是可转移的还是取决于Datatable/Collection的大小？
5. 更新后(1000000次迭代)ContainsKey是最快的.这是因为我总是检查相同的ID或一般吗？是否有某种SortedList没有Dictionary的KeyValue-Pair的开销？

结果 [1000000次迭代*]

• Timespan 1 = SortedList.ContainsKey =Ø0.665634[ 238.1095 ] ms
• Timespan 2 = List.Contains =Ø0.06802[ 57045.37955 ] ms
• Timespan 3 = DataTable.FindByIdData(自动生成方法)=Ø0.31580[ 1542.62345 ] ms
• Timespan 4 = DataTable.Select =Ø0.27790[ 26029.39635 ] ms

• Timespan 5 = DataRowCollection.Contains =Ø0.00638[ 1202.79735 ] ms

  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 ms来执行1000000次迭代,因此在没有SortedList-KeyValue-Pair的开销的情况下最快.我可以使用它而不对列表进行排序,因为DataAdapter使用Order By子句填充数据表.

Answer 1

这并不在我看来,你提供近乎足够的工作,在这里得到有用的时机.你的所有时间都是亚毫秒级,并且几乎肯定只是噪音 - 缓存,JIT-ING,优先购买权等.

使您的集合足够大,可以花费几秒钟来运行,或者至少在紧密循环中运行每次测试足够的时间来花费几秒钟.

Answer 2

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

编辑:如果你只需要存储密钥,你应该使用的HashSet <T>这是在.NET 3.5及更高版本.

来自 SortedList上的MSDN:

由于排序,SortedList对象上的操作往往比Hashtable对象上的操作慢.

要定位.NET 2.0,您可以自己动手或使用Wintellect的Power Collections等预先构建的版本(您也可以轻松地使用源代码).