fast sorting using .net 3.5 framework

Question

Hello everybody

In a scientific application I'm writing (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

Answer 1

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)

Answer 2

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.

Answer 3

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.