Задачка на эффективный поиск

04.09.2006
2 566
3
#1
Значит задачка такова: имеется некоторое событие, атрибутами которого являются время события и текстовое описание.
На вход программы поступает неупорядоченное множество событий размерностью N. Необходимо, пробежавшись по множеству событий, найти M наиболее поздних событий. M на несколько порядков меньше N.
Ну и стандартное требование: минимальная вычислительная сложность с минимальными затратами памяти.

Какие мысли имеются, господа? Может есть стандартный алгоритм решения?
 

grigsoft

Well-known member
15.11.2005
735
0
#2
Наверняка есть, но на вскидку -
А - массив указателей с результатом, он сортируется по дате при вставке.
Dm - текущая самая _поздняя_ дата элемента в А.
Код:
for each K:
if (K.date<Dm || A.size<M)
{
A.SortInsert(&K); 
if (A.size > M)
A.DeleteLast();
Dm = A[last].date;
}
Где-то так. Будет О(N*ln(M)).
 
04.09.2006
2 566
3
#3
<!--QuoteBegin-grigsoft+5:04:2007, 11:30 -->
<span class="vbquote">(grigsoft @ 5:04:2007, 11:30 )</span><!--QuoteEBegin-->Будет О(N*ln(M)).
[snapback]61390" rel="nofollow" target="_blank[/snapback]​
[/quote]
Одна сортировка M*ln(M). Итого O(N*M*ln(M))

Общий алгоритм то понятен, но вот какие структуры данных (контейнеры STL) использовать для максимизации эффективности вставки, удаления и сортировки, хотя с сортировкой все более-менее понятно
 

grigsoft

Well-known member
15.11.2005
735
0
#4
Я же пересортировывать не предлагаю. Вставка в отсортированный массив - ln(M).
Я STL не использую, но тут разницы никакой - вектор вполне пойдет, насколько я понимаю. Вставка потребует смещения массива, но если там указатели - то нестрашно. Можно подумать, как сделать на списке с возможностью поиска, но сходу ничего не приходит умного в голову.
Если М больше 10-50, то я бы добавил дополнительную проверку на быструю замену последнего значения.