.net - 使用.net 3.5框架快速排序

Question

在我正在编写的科学应用程序(vb.net)中，我使用存储在树结构中的大量对象集合。每个对象都公开一个 LastAccessed 属性(日期时间)，该属性存储算法上次访问节点的时间。

我需要找到一种快速方法来查找结构中 N 个最少访问的对象。

我正在使用这样的算法(伪代码)

dim Olist as new list (of myobject)
....
array.sort(Olist,address of compareByDataReverse)
for index=0 to N-1
   dosomething(Olist.item(index))
end

我确信有更好的方法来做到这一点，因为列表通常很大(包含超过 10^6 个对象)。

谢谢
PIL 路易吉

Answer 1

您提到您使用树结构，但您向我们展示了一个列表。如果您使用列表，您确实可以对其进行排序 (O(l log(l))，然后在 O(1) 中获取最后 n 个元素。或者只是迭代它并在 (O(l)) 中获取最后 n 个元素。

但是您可以使用 TreeView 。您没有提到您的树是如何实现的。您可以使用 LastAccessed 日期作为键创建二叉搜索树。搜索前 N 个元素也可以非常快地完成。

或者，您可以保留一个索引。只需创建一个以 LastAccessed 日期为键的 TreeView 。在原始列表中插入或删除项目也会更新您的索引。然后，您可以根据项目的日期快速检索项目的链接。以较慢的插入/删除为代价。