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

Тема в разделе "Свободное общение", создана пользователем European, 5 апр 2007.

  1. European

    Регистрация:
    4 сен 2006
    Сообщения:
    2.580
    Симпатии:
    0
    Значит задачка такова: имеется некоторое событие, атрибутами которого являются время события и текстовое описание.
    На вход программы поступает неупорядоченное множество событий размерностью N. Необходимо, пробежавшись по множеству событий, найти M наиболее поздних событий. M на несколько порядков меньше N.
    Ну и стандартное требование: минимальная вычислительная сложность с минимальными затратами памяти.

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

    grigsoft Well-Known Member

    Регистрация:
    15 ноя 2005
    Сообщения:
    735
    Симпатии:
    0
    Наверняка есть, но на вскидку -
    А - массив указателей с результатом, он сортируется по дате при вставке.
    Dm - текущая самая _поздняя_ дата элемента в А.
    Код (Text):
    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)).
     
  3. European

    Регистрация:
    4 сен 2006
    Сообщения:
    2.580
    Симпатии:
    0
    <!--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) использовать для максимизации эффективности вставки, удаления и сортировки, хотя с сортировкой все более-менее понятно
     
  4. grigsoft

    grigsoft Well-Known Member

    Регистрация:
    15 ноя 2005
    Сообщения:
    735
    Симпатии:
    0
    Я же пересортировывать не предлагаю. Вставка в отсортированный массив - ln(M).
    Я STL не использую, но тут разницы никакой - вектор вполне пойдет, насколько я понимаю. Вставка потребует смещения массива, но если там указатели - то нестрашно. Можно подумать, как сделать на списке с возможностью поиска, но сходу ничего не приходит умного в голову.
    Если М больше 10-50, то я бы добавил дополнительную проверку на быструю замену последнего значения.
     
  5. European

    Регистрация:
    4 сен 2006
    Сообщения:
    2.580
    Симпатии:
    0
    Для: grigsoft
    Спасибо и на этом :ph34r:
     
Загрузка...
Похожие Темы - Задачка на эффективный
  1. Hehabr
    Ответов:
    1
    Просмотров:
    482
  2. Gepard26
    Ответов:
    0
    Просмотров:
    1.113
  3. lisica198808
    Ответов:
    0
    Просмотров:
    1.018
  4. student55
    Ответов:
    1
    Просмотров:
    1.711
  5. vbs
    Ответов:
    21
    Просмотров:
    7.503

Поделиться этой страницей