В стек FIFO, реализованный в массиве с плавающим пойнтером*, поступают данные. Среди прочих вычислений необходимо иметь доступ к мин-макс значениям, находящимся в данный момент в стеке.

Как это эффективно реализовать? Есть ли нативная сишная ф-ция вычисления мин-макс массива?

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

Быстродействие крайне критично. Из-за этого и обратился к C++

*
не знаю, как обозвать - постоянно хранится указатель на индекс, в который произошла последняя запись. Т.е. новым значением перезаписывается самое старое - FO. Без смещения всего стека по массиву.

** C++ почти не знаю. Допиливаю чужую заготовку.

Сорри. Я не настоящий сварщик :)

В предлагаемой нотации - очередь. FIFO. Или LILO. Как удобнее. Пулеметная лента. Не магазин. Стек, прдн, очередь, выдавливается. Т.е. всегда заполнен(а) полностью.

m_Sla,
m_SlaДве переменные max и min, определяются перед помещением значений в FIFO.
При выталкивании значений проверяем на max(min). Если вытолкнули max(min), то перебором находим новое max(min). Схоже с тем, что я предложил выше. Только хранятся сами значения, а не указатели. А т.к. в стеке м.б. несколько величин, равных граничным, то в моем варианте можно оптимизироваться под хранение указателя на наиболее актуальную максимальную величину, перебирая стек с последнего вошедшего. Тогда не придется перебирать при выходе каждой величины, равной граничным. На длинных стеках может возникнуть существенная экономия.

Vladimir Baskakov ,

* как много операций вставки - удаления - запроса минимакса будет?
- непрерывно поступают данные с неких датчиков со скоростью до 500 отсчетов секунду в пределе, стандартно - 5-10 в сек. Каждое входящее надо проверять на минмакс и фиксировать, если оно таково.

* Какова длина очереди
- три-четыре самостоятельных очереди с максимальной длиной до 10 тыс. Из расчета, чтобы охватить хотя бы 3-4 минуты в экстремуме (0.2 мсек Х 10'000 pcs)

* Рискну предположить, что этот участок не станет узким местом системы.
- Ну, за всю систему, конечно, не самое-самое. А на этапе обработки сырых данных - самое узкое. Из сложной статистики, вычисляемой на каждом тике еще считаются (но все тривиально):
- приращение очереди: (Chg = New - Old);
- сумма значений очереди: (Sum = Sum + Chg);
- скользящее среднее: (Avg = Sum / Siz);
- диапазон минмакс: (Dnx = Max - Min)

Так что, все упирается в минмакс...

На книжку обязательно взгляну. Снкс.

Anatoly Moskovsky,
Спасиюо. Чуть позже отвечу. Надо отлучиться.

underCAnatoly Moskovsky,
Спасиюо. Чуть позже отвечу. Надо отлучиться.Отлучился, млин, сходил за хлебушком :) Полсоюза за это время проехал.
Прошу прощения за пропажу топикстартера.

Спасиюо за высказанные соображения и примеры. С позволения присутствующих - возьму еще таймаут. В понедельник-вторник вернемся к обсуждению, ОК?

Ну вот. У меня есть первые результаты и замеры. Я реализовал вот такой алгоритм в модели на VBA, которую предполагаю переносить в сишную длл:

У меня этот цикл выполняется для очередей длиной:
(все округлено-усреднено на глаз, но замеры ведутся с точностью до 1 мксек)

Vladimir Baskakov
* на джаве - милион тупых минимаксов - секунд 30 на глаз

m_Sla
* double data[10000] на моем компьютере выполняется за 0,00002 сек

Спасибо за цифры. На джаве - это, конечно, ни в какие ворота :) А вот 2 мксек на 1000 записей - меня это более чем устраивает. Под VBA производительность получается на два порядка ниже. И то, с учетом, что m_Sla ворочал запятую, а уменя все целочисленное. Но это только модель. Потом все портируется на С и будет летать :) Важно алгоритм оценить.

Теоретически, можно еще ускориться за счет линейной записи кода - уйти от второго for (это я чисто для экономии строчек кода и понимания так записал).

Можно еще попытаться ускориться за счет уточнения - кто, мин или макс все-таки вышел, и проверять дальше только на него. vromanov , об этом шла речь в 14191192 ?vromanovЕще одна оптимизация. При обычном поиске мин/макс в массиве делается два сравнения на элемент. Можно делать так, берем два значения из массива. сравниваем их между собой, а потом максимальный сравниваем с макс и меньший с мин. Итого получается 1.5 сравнения на элемент. Ускорение на 25%
И там же 14191192 :
Бъем очередь на сегменты. например, на 100
* 2) на каждом сегменте храним время старта и стопа, считаем мин, макс, среднее.
Непонятно, зачем хранить время (хоть оно у меня хранится).

* 3) при добавлении/удалении значения пересчитываем только значения в блоке.
Недостаточно. После удаления текущего минимакса, ближайший может оказаться в другом блоке.


Anatoly Moskovsky
Спасибо за примеры кода. Но я, к сожалению, совершенно поверхностно знаю язык - лишь в рамках той длл, которую мне придется модифицировать. Поэтому я просто не могу по достоинству оценить предложенное. И хотелось бы остаться в рамках того, что я смогу потянуть самостоятельно без погружения в маны.

Интересны приведенные оценки сложности алгоритма O(log(n)). Что можно почитать на эту тему? Если не очень заумное :)


Vladimir Baskakov 14191364
* Какая структура данных - что кроме замеренного числа записывается?
Фактически очередь - это двумерный массив, т.к. значений (полей), одновременно в нее передающихся - несколько, плюс таймстемп на каждую запись, который я проставляю самостоятельно. Очередей таких - несколько разных длин. Т.е. элементы самой короткой очереди дублируются в более длинной. Кстати, в этом направлении тоже, думаю, есть место для оптимизации. Но мне пока надо в самом простом, но эффективном варианте.

* Может сделать конвеер. Приемник данных заполняет блоки в памяти, второй паралельно работающий процесс скидывает полностью заполненные блоки в файлы, а уже третий, фоновый - все обрабатывает?
Это было бы шикарно. Но я не потяну самостоятельно. Да и еще такой аспект - все сейчас обрабатыывается в Access через подключенный API в COM-модели. Поэтому синхронная обработа навязана. Можно было бы говорить о буфере, но по ТЗ указано мириться с потерянными тиками в пользу самых свежих. Т.е. выбор сделан в пользу актуальности, за счет целостности, полноты данных
.

Vladimir Baskakov ,

* и у меня на джаве 10 К записей, а не 1 К.
Вот, что было написано выше: "милион тупых минимаксов - секунд 30 на глаз" . Пусть 20. Итого, на 1'000 циклов:

Что уж так за яву расстраиваться :) Странно было бы от нее большего ожидать.

* В Ваши ворота пролазит с запасом. у Вас же 1000 замеров в секунду?
Пролазит. Ну и что? Пролазит-то лишь среднебольничная температура...

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

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

* И ВБА - уж тормозит так тормозит.
Ну, надо уметь его готовить :) А цифры выше я привел.

* Ну посмотрите шутки ради - сколько времени оно туда льется. Через COM.
Да не надо шуток. Смотрю постоянно :)
БД - десятка полтора целочисленных полей и три дабла, строковых нет. В онлайне пишется меньше чем за 1 мск (0.001 сек) запись (это включая сопутствующие статистические вычисления) и еще полно мест для оптимизации. Последовательное чтение (имитация онлайна, тоже с вычислениями) - до 80'000 записей в сек. Access на удивление шустер.

Пишется до 1.5 млн записей в сутки (обычно 700-800 тыс). Это в среднем чуть больше 10 записей в сек. В среднем!

mayton ,
это мне сейчас не потянуть. Надо учиться. На заметку возьму, как и предложения Anatoly Moskovsky про уникальные значения и Vladimir Baskakov про конвейер. Конечно, вместо того, чтобы из API выплевывать в VBA, оттуда в сишную длл, а потом обратно, лучше на си написать шлюз (бридж) к API со всей математикой, а аксу оставить исключтельно БД-шный функционал.

В плане портирования предложенного алгоритма на C++ возникает следующий вопрос - как передать из VBA в сишную длл массив значений ?

Сейчас я передаю в нее несколько параметров.
Вот у меня вызов инициализации очереди:


Вот передача новых значений к пересчету:


Я, конечно, могу увеличить число передаваемых параметров, но может лучше массивом.

А еще более важно массивом же из нее получить результаты вычислений . Сейчас для получения одного из результатов вычислений я вызываю ее функцию с определенным параметром. И так несколько раз. Слава богу, они не все нужны одновременно. Но гораздо интереснее получить все махом за один вызов и уже в VBA разбираться с результатами.