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

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

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

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

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

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

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

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

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

А вообще что-то мы(я ) воротим не то... сейчас придут maxim1000 и podval, и докажут что все гениальное в простом.

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

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

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

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

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

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

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

Цитата

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

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

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

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

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

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

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

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

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

LSD

Цитата

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

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

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

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

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

Цитата

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

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

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

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

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

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