быстрая сортировка с использованием .net 3.5 framework

Question

В научном приложении, которое я пишу (vb.net), я использую огромную коллекцию объектов, хранящихся в древовидной структуре.Каждый объект предоставляет свойство LastAccessed (datetime), в котором хранится последний раз, когда алгоритм получил доступ к узлу.

Мне нужно найти быстрый способ найти 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).объекты).

СпасибоПьерлуиджи

Answer 1

Вы упоминаете, что используете древовидную структуру, но покажете нам список. Если вы используете список, вы действительно можете его отсортировать (O (l log (l)), а затем взять последние n элементов в O (1). Или просто выполнить итерацию и получить последние n элементов в (O (l)).

Однако вы работаете с деревом. Вы не упомянули, как реализовано ваше дерево. Вы можете создать бинарное дерево поиска, указав в качестве ключа дату вашего последнего обращения. Поиск первых N элементов также может быть выполнен очень быстро.

В качестве альтернативы вы можете сохранить индекс. Просто создайте древовидное представление с ключом даты последнего доступа. Вставка или удаление элемента в исходном списке также должно обновить ваш индекс. Затем вы можете быстро получить ссылку на ваши товары на основе их даты. За счет более медленных вставок / удалений.

Answer 2

Если вы используете Выбор сортировки , то после N итераций первые N элементов будут отсортированы в порядке

ПРИМЕЧАНИЕ: Но я не уверен, что это решит вашу проблему полностью.

Answer 3

в лучшем случае ваш код будет работать с O (nlogn). Вы должны начать с dim Olist as new list (of myobject), затем взять LinkedList, просмотреть свою коллекцию и добавить значения в свой список, сохраняя его отсортированным. Это будет O (n * m)