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

发布于 2024-09-12 11:22:26 字数 5442 浏览 6 评论 0 原文

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

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

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

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

是什么造成了这些差异？
我忘记了更好的方法吗？
我的测量方法是否正确（我认为我最好应该循环它们并取该值）？
这些值是否可传输或取决于数据表/集合的大小？
在我的更新（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
Timespan 4 = DataTable.Select = Ø 0.27790 [26029.39635] ms
Timespan 5 = DataRowCollection.Contains = Ø 0.00638 [1202.79735] 毫秒
<前><代码>1。）时间跨度 1：0.6913 毫秒时间跨度 2：0,1053 毫秒时间跨度 3：0.3279 毫秒时间跨度 4：0,1002 毫秒时间跨度 5：0,0056 毫秒 2.) 时间跨度 1：0.6405 毫秒时间跨度 2：0.0588 毫秒时间跨度 3：0.3112 毫秒时间跨度 4：0.3872 毫秒时间跨度 5：0,0067 毫秒 3.) 时间跨度 1：0.6502 毫秒时间跨度 2：0.0588 毫秒时间跨度 3：0,3092 毫秒时间跨度 4：0.1268 毫秒时间跨度 5：0,007 毫秒 4.) 时间跨度 1：0.6504 毫秒时间跨度 2：0.0586 毫秒时间跨度 3：0,3092 毫秒时间跨度 4：0.3893 毫秒时间跨度 5：0,0063 毫秒 5.) 时间跨度 1：0.6493 毫秒时间跨度 2：0.0586 毫秒时间跨度 3：0.3215 毫秒时间跨度 4：0,386 毫秒时间跨度 5：0,0063 毫秒时间跨度 1：0,6913 0,6405 0,6502 0,6504 0,6493 = Ø 0,65634 时间跨度 2：0,1053 0,0588 0,0588 0,0586 0,0586 = Ø 0,06802 时间跨度 3：0,3279 0,3112 0,3092 0,3092 0,3215 = Ø 0,31580 时间跨度 4：0,1002 0,3872 0,1268 0,3893 0,3860 = Ø 0,27790 时间跨度 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()
对于 i 作为 Int32 = 1 到 1000000
    适用 = listAC17NextClaims.BinarySearch(myClaim.idData) > -1
下一个
时钟.Stop()
```
只需要 219.1805 毫秒即可执行 1000000 次迭代，因此是最快的，没有 SortedList-KeyValue-Pair 的开销。我可以使用它而无需对列表进行排序，因为 DataAdapter 使用 Order By 子句填充数据表。

原文

Originally i wanted to ask for the fastest way to query a Datatable for a special row.

I have tested 5 different methods for their performance with a surprising(for me) result.

Background:
I have created a View in a MS Sql-Server 2005 Database. This view has current a total count of 6318 rows. Because i must check very often if a given id exists in this view, i wondered what is the most efficient way to do. I created a DataAdapter in a strongly typed dataset which returns all rows and fills a Datatable.
My first approach was to create a shared generic List(of Int32) and fill it with the ID's from the view once on Application start. Then use List.Contains to check if the current ID is in this List. Because all rows are distinct i wondered if its not faster to use a SortedList and its ContainsKey-metod.
Then i checked also the performance of direct access to the Datable with its Select-Method, its automatically generated(when column is defined as primary-key) FindBy-method and last but not least the DatarowCollection.Contains-Method.
So i have 5 Methods to check if my ID is in that View(or mapped List/SortedList).

I measured their performance with the System.Diagnostics.StopWatch and got some interesting results. I thought the SortedList.ContainsKey must be faster than the List.Contains because they're distinct and sorted but the opposite is true.
But the most surprising for me was that the DataRowCollection.Contains-Method(that i first had forgotten) is by far the fastest. It is even 50 times faster than the dataTable.FindBy-method.

What caused these differences?
Have i forgotten a better way?
Is my measurement method correct(i think i better should loop them and take that values)?
Are the values transferrable or dependent on the size of the Datatable/Collection?
After my update(1000000 iterations) ContainsKey is the fastest. Is this because i always check for the same id or in general? Is there some kind of SortedList without the overhead of a Dictionary's KeyValue-Pair?

Results [for 1000000 iterations*]

Timespan 1 = SortedList.ContainsKey = Ø 0.65634 [238.1095] ms
Timespan 2 = List.Contains = Ø 0.06802 [57045.37955] ms
Timespan 3 = DataTable.FindByIdData(auto-generated method) = Ø 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

And for the sake of completeness part of the VB.Net source:

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"

UPDATE:
I have changed my results and the source above. In squared brackets are the values for 1000000 iterations. Now the result is completely different. The fastest method now is definitely is the ContainsKey of the SortedList.
UPDATE 2:
I forgot the alternative to use List.BinarySearch.
This seems to be fastest for me:
```
clock.Start()
For i As Int32 = 1 To 1000000
    applies = listAC17NextClaims.BinarySearch(myClaim.idData) > -1
Next
clock.Stop()
```
needs only 219.1805 ms to perform 1000000 iterations and hence is the fastest without the overhead of a SortedList-KeyValue-Pair.
I can use it without to sort the list because the DataAdapter filled the datatable with an Order By clause.

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

享受孤独 2024-09-19 11:22:26

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

编辑：如果您只想存储密钥，则应该使用HashSet 在 .NET 3.5 及更高版本中可用。

来自 MSDN 上的 SortedList：

对 SortedList 对象的操作往往
比在 a 上的操作慢
哈希表对象因为
排序。

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

回复收藏 0 原文

只为守护你 2024-09-19 11:22:26

在我看来，你并没有提供足够的工作来在这里获得有用的时间。您所有的时间都是亚毫秒级的，并且几乎肯定只是噪音 - 缓存、jit-ing、抢占等。

让您的集合足够大，需要几秒钟才能运行，或者至少在一个时间内运行每个测试足够多的次数。紧密循环需要几秒钟。

回复收藏 0 原文

甜心小果奶 2024-09-19 11:22:26

如前所述，您的代码仅运行该操作一次。通常的策略是多次运行代码（例如，进行 3 次搜索）以获得更大的数字（因此，如果 3 次搜索需要 0.9 秒，则可以说一次搜索需要 0.3 秒）。然后循环几次以允许您计算平均值（如果您愿意，可以包括标准差，以过滤掉疯狂的结果），然后最重要的是，运行一次而不注意记录时间，以便任何 JITing被执行。

另外，在不附加调试器的情况下以发布模式运行代码。