我的数据结构知识已经很陈旧了,说实话这从来不是我最擅长的领域。
现在我们要开发一个类似于队列的组件,具有以下要求:
- 必须能够排队、出队并通过关键字查找特定项。
- 每个项都将是一个由另一个类作为关键字的结构或类,具有 5 个不同的属性,类别类似。假设类似于:MasterCategoryId、ChildCategoryId、TimeId、PriorityId、GroupId。
- 它必须是一个排序集合。
- 通常情况下,该集合将包含从 5k 到 10k 个对象,但为了考虑最坏情况,我们正测试当前原型以容纳大约一百万个对象。
- 目前它不支持多线程。
- 大约有 90 或 95% 的项目(队列)将在创建组件时发生,但组件被用作树,也就是说,我们将从集合中出队最后一个项目,对其进行计算,然后将其结果报告给其父级,该父级可能已经存在于集合中,也可能不存在。如果不存在,则用于查找父级的队列方法将必须插入该项。
- 由于该组件类似于处理队列,因此在出队所有内容后,集合将为空。
我想这总结了一下。所以,显然一个单一的列表或有序列表是不可行的,因为每次我们向集合中添加或删除对象时都会对其进行排序,而在包含一百万个对象的单个集合中执行此操作很慢。
我们过去测试了几种方法,例如链表,它们在排队方面证明很快,但在查找项目方面很慢(因为我们确实有这种情况)。
现在我们想到了一种结构,类似于
SortedDictionary<int, SortedDictionary<int, SortedDictionary<int, SortedDictionary<int, SortedDictionary<int, ..
你明白了。这种分组级别的处理方式是一种较为理想的方法,每个集合大小相对较小(每个字典约为300个项目)。
因此,对于第一层级别,我们将使用SortedDictionary,其键是每个主要类别的ID,而值将是一个SortedDictionary,其键是子类别的ID...以此类推。
目前,我们已经测试了100、1,000、10,000、100,000和1,000,000项。
对于较小的范围,最高可达100k,解决方案速度非常快。即使对于最多达到300k的情况,它也可以在不到一秒的时间内进行排队/出队/查找,这实际上已经超出了我们将要处理的80-90%的场景。
当处理一百万时,速度会变慢,排队整个过程需要大约3-4秒钟,排队全部完成需要长达10秒的时间。
所以,我的问题是:
1. 是否有更适合我们特定情况的集合或方法? 2. 我以前从未在集合中处理此数量的项目。这些时间对于如此高的数字是否合理?我之所以问是因为我读过一些人的推文,他们在像MSMQ或NserviceBus这样的东西上进行了200k次/秒的操作(我知道这与此无关,只是想了解和比较我的结果)。 3. 我在原型中使用的对象只是模拟类,仅有组合对象键和单个属性。当我使用真实类时,我的结果会受到影响吗?我猜想不会,因为框架所要做的就是添加对该对象的引用,但我只是想确认一下,因为像我说的那样,数据结构从来都不是我的强项。 4. 如果我想要为这个多线程准备,我需要考虑哪些问题?
谢谢。