Inu*_*a G 8 c# tree dictionary
我正在开发一个自定义持久键值类型数据结构,以与SqlLite和Berkley DB进行比较.无论如何,在我编写实现之前,我想找到用于此目的的最佳数据结构.我看着一对夫妇:
我希望我选择的数据结构的性能数字与.net字典相当.
我使用了一个简单的测试循环,对插入进行了500k次迭代,并使用秒表测量插入和键查找:
我注意到了
插入时间:比.net字典慢7%.
查找时间:比.net字典慢1000%.这比使用sqllite的查找速度还要慢!我尝试在打开编译器优化的情况下执行测试,但仍然得到了类似的结果.
我意识到我正在比较Hashtables和树等,但我难以理解所有数据结构之间的性能差异.
任何人都有任何想法
两个想法：
您应该确保您的测试中没有无意中包含 JIT 时间 - 这可能会给结果增加相当多的时间。您应该在同一次执行中执行两次运行并放弃第一次运行。
您应该确保您没有在调试器下运行 - 这可能会极大地影响性能结果。
除此之外，您看到的任何性能差异很可能是哈希表和树之间性能差异的结果。树结构的查找平均性能通常为 O(n*log(n))。平衡树可以将其减少到 O(lon(n))。同时，当避免哈希冲突时，哈希表的查找时间可以接近 O(1)。
我还认为 .NET Dictionary 类是高度优化的，因为它是 .NET 中许多不同事物的基础数据结构。此外，通用 Dictionary<> 可能能够避免装箱，因此您可能会看到一些性能差异。
| 归档时间： |
|
| 查看次数： |
933 次 |
| 最近记录： |