开发者

fast sorting using .net 3.5 framework

In a scientific application I'm writi开发者_运维知识库ng (vb.net) I use a huge collection of object stored in a tree structure. Every object exposes a LastAccessed property (datetime) that stores the last time the node was accessed by the algorithm.

I need to find a fast way to find the N least accessed objects in the structure.

I'm using an algorithm like this (pseudo-code)

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

I'm sure there is a better way to do that because the list is normally huge ( consisting of more than 10^6 objects).

Thanks

Pierluigi


You mention that you use a tree structure yet you show us a list. If you use a list you can indeed sort it (O(l log(l)) and then take the last n elements in O(1). Or just iterate it and get your last n elements in (O(l)).

You however work with a tree view. You didn't mention how your tree is implemented. You can create a binary search tree with as key your LastAccessed date. Searching for your first N elements can then also be done very fast.

Alternatively you could keep an index. Just create a tree view with as key the LastAccessed date. Inserting or removing an item in your original list should also update your index. You can then quickly retrieve a link to your items based on their date. At the cost of slower inserts/removals.


in best case your code will perform with O(nlogn). You should begin with dim Olist as new list (of myobject) then take a LinkedList and go over your collection and add values to your list keeping it sorted. This will be O(n*m)


If you use Selection sort then after N iterations first N elements will be in sorted order.

NOTE:But I am not sure if this solves your problem completely.

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜