Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Поиск максимального значения в очереди

Автор: LSD 2.11.2004, 23:24

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

Единственный вариант который я смог придумть это:

заводим некую хэш таблицу, в которой ключом является значение из очереди, а значением, то сколько раз оно там встречается
при добавлении нового значения, если оно уже есть, то просто увеличиваем счетчик, если такого значения там нет то добавляем его туда
при удалении элемента соответсвенно уменьшаем счетчик, если он становится равен нулю то удаляем элемент

Затем из данной хэш таблицы получаем максимальное и минимальное значение.

Еще есть один вариант, связанный с тем, что очередть переодически просматривается и в эти моменты можно провести поиск максимума и минимума обычным способом. Проблема в том, что значения максимума и минимума нужны до того как будет произведен просмотр очереди, и частота просмотров не совпадает с частотой добавления данных (она меньше, иногда просмотр вообще не производится длительное время).

Автор: 3,14 3.11.2004, 11:25

В общем случае придумать ничего лучше прохода по очереди не получится. Оптимизация возможно только для специфических задач, например, очередей большого размера, удаление в к-ых практически не происходит.

Автор: Sardar 3.11.2004, 13:06

Если известны все значения(принадлежат к, в фиксированному пределах разумного пречиляемому множеству), допустим их N, то можно сделать массив с длинной N, по некоторому признаку вычисляем индекс, в ячейках счетчик. С ограничениями, но за то самый быстрый/простой вариант.

Если значения это строки(бесконечное множество значений), то можно сделать B+ дерево(или что то подобное), и держать ссылки на первый и последний лист, тогда операции: min, max имеют константную скорость(первый/последний лист), добавление логарифмическую + балансировка дерева.

Хешь таблица с красно-чёрным деревом в ковше, название говорит само за себя, реализация посложнее, но скорость при этом "самая-самая".

А вообще что-то мы(я

) воротим не то... сейчас придут maxim1000 и podval, и докажут что все гениальное в простом.

Автор: Akina 3.11.2004, 13:34

В общем если параллельно с очередью хранить ее копию в отсортиренном массиве

тада пожалуй можно и ускорить поиск...

Автор: Mad 3.11.2004, 13:43

LSD
При добавлении нового элемента, проверять его значение с текущим максимумом и минимумом.
При удалении мфксимального или минимального элемента, пробегатся по по очереди в поисках новых.

Автор: podval 3.11.2004, 18:32

При обновлении очереди надо смотреть на выкидываемый элемент: если он равен текущему максимуму/минимуму, то после выкидыша запускать поиск максимума/минимума заново.
Если нет, то смотреть на входящий: превосходит ли он текущий максимум (меньше ли он текущего минимума). Если да, то присвоить это значение максимуму(минимуму).

Автор: 3,14 3.11.2004, 18:59

Цитата(podval @ 3.11.2004, 18:32)

А смысл? Чем это лучше простого однократного прохода при поиске?

Автор: podval 3.11.2004, 20:20

3,14
Тем, что не каждый раз поиск нужен. Вместо просмотра очереди просто сравнили и попрыгали дальше.
Тем более так устроены условия задачи:

Цитата

частота просмотров не совпадает с частотой добавления данных (она меньше, иногда просмотр вообще не производится длительное время).

Автор: LSD 3.11.2004, 21:17

Цитата(Sardar @ 3.11.2004, 13:06)

Если известны все значения(принадлежат к, в фиксированному пределах разумного пречиляемому множеству)

Множество конечное, но ОЧЕНЬ большое: восмибайтовое целое.

Цитата(Akina @ 3.11.2004, 13:34)

В общем если параллельно с очередью хранить ее копию в отсортиренном массиве тада пожалуй можно и ускорить поиск...

Время сортировки массива сопоставимо с временем его просмотра, вот только если использовать список.

Mad, podval
Как я понял ваши предложения, они по сути одинаковы, наверно так и попробую сделать.

Спасибо всем отвечавшим

Автор: Akina 4.11.2004, 09:45

LSD

Цитата

Время сортировки массива сопоставимо с временем его просмотра

Но выполняется она ОДИН РАЗ, при формировании очереди, т.е. при старте программы. А если она начинает работать с пустой очередью - то вообще не выполняется. Просто потом массив поддерживается в сортированном состоянии при вставке-удалении, вот и все... ну есссно это будет не массив, а фактически файл индекса...

Автор: LSD 4.11.2004, 20:02

Цитата(Akina @ 4.11.2004, 09:45)

Вставка элемента в массив задача тоже весьма трудоемкая, а списки довольно медленная штука.

Автор: Sardar 4.11.2004, 21:54

Цитата

Вставка элемента в массив задача тоже весьма трудоемкая, а списки довольно медленная штука.

Теоритически деревья будут самыми оптимальными по быстроте. Но узлы раскиданны по памяти, возможно процессором почти не будет использоватся кеш. Впрочем с современным железом, наверное, это уже не актуально.

Автор: LSD 6.11.2004, 00:23

В общем я надеялся, что есть некий простой способ, которого я не заметил, но похоже что нет.
Задача состоит в отображении диаграммы некого процесса. Я предполагаю делать так: есть две переменные которые хранят максимум и минимум очереди. Они будут обновляться следующим образом:

когда происходит просмотр списка, туда записываюся реальный максимум и минимум
при добавлении новых элементов в очередь, если надо, значения корректируются
при удалении ничего не происходит

таким образом диаграмма, будет не совсем соответсвовать по максимуму и минимуму, всего один цикл перерисовки максимум.

Автор: Sardar 6.11.2004, 00:46

А почему так страшно пробежатся по очереди? Мониторим входные элементы, обновляем минимум. Мониторим выходные элементы, если минимум/максимум выпал, то пробегаемся по очереди. Для минимумов/максимумов держим отдельную очередь в N елементов, при изменении максимумов/минимумов обновлям эту буферную очередь, если она опустеет то пробегаесмся по очерди с данными. Как видим чем больше буферная очередь, тем реже ты будешь бегать по очереди с данными.