В стек 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 разбираться с результатами.

Dimitry SibiryakovЯ смотрю автора ещё никто не спросил какого типа данные у него в очереди... И почему бы не считать этот min/max при необходимости, а не на лету?..
Я оговаривался - целочисленные.авторm_Sla ворочал запятую, а уменя все целочисленное. Необходимость такая есть. Надо просто принять это :)

Anatoly MoskovskyТут бы еще узнать зачем оно вообще надо :)Да все очень просто. Нужно продемонстрировать, что существующая методика и инструментарий для сбора, оценки м анализа параметров процесса устарели и нужно вложиться в нормальную разработку. И уж если я на коленке смог собрать более эффективную и, главное, работающую модель, то наверное следует нанять профессионалов и сделать все красиво :)

maytonУ меня почему-то в голове крутиться аналогия с расчётом
"скользящего среднего" если считать FIFO - статистической
выборкой.Не удивительно, что крутится :)авторна каждом тике еще считаются (но все тривиально):
- приращение очереди: (Chg = New - Old);
- сумма значений очереди: (Sum = Sum + Chg);
- скользящее среднее: (Avg = Sum / Siz);
- диапазон минмакс: (Dnx = Max - Min)

Dimitry Sibiryakov"Я" бывают разные. (с) Кролик.

Целочисленные значения имеют разрядность от 1 до 64 бит минимум. Какие у тебя? До
разрядности в 8 бит будет эффективным уже предложенный способ счётчиков.
Мои целочисленные - VBA-шный тип long:
F1Long (long integer) variables are stored as signed 32-bit (4-byte) numbers ranging in value from -2,147,483,648 to 2,147,483,647

Dimitry Sibiryakov,

* Ну, раз ты так считаешь...
это VBA так считает. Чем-то мои лонги не понравились...

* кто и с какой частотой использует эти min/max значения?
С частотой поступления тиков все это предварительно считаемое добро участвует в последующей математике системы принятия решения. Также, параллельно с сырыми данными, пишется статистика. Для истории и для оффлайн анализа как наблюдаемых процессов, так и поведения самой системы наблюдения за ними

У меня был один простой вопрос - уважаемые спецы по Си, как вам видится мой алгоритм и получу ли я ожидаемую (в пределах +- трамвайная остановка) скорострельность.

Спасибо всем явно или косвено подтвердивших работоспособность алгоритма и особенно тем, кто не поленился и смоделировал. Vladimir Baskakov , m_Sla - снкс. Спасибо остальным за высказанные идеи и ориентиры на будущее.

Осталось два простых вопроса. Их, к сожалению, залистали:

- как передать в длл массив значений разом вместо нескольких параметров , и

- как получить из нее так же массив значений, вместо нескольких вызовов .

Dimitry Sibiryakov,
* Гораздо интереснее мнение того, кто эти данные присылает
Уточни, плз, что имеется ввиду?

Если только это:
* Конкретнее - диапазон генерируемых значений.
то датчиками генрируется абстракщина, понятия не имею. А на выходе из API - лонги любого знака. Порядок величин - 10^5, не более. За исключением моего собственного сквозного таймштемпа, который я проставляю с точностью 100 мксек. Так что у него порядок до 10^9.

авторТо есть принятие решения осуществляется на каждое поступление новых данных, 500 раз в секунду?Я оценил сарказм. Позволь и мне?

Не поверишь - именно так. 500 раз в секунду и даже с большей частотой оператор сидит ровно на заднице и не подпрыгивает к пультам, а принимает, и принимает и снова принимает решение сидеть так же ровно и дальше . И лишь несколько раз в день он отрывает тохес от стула потому что загорается большая красная лампочка. Сказать почему она загорается? В частности потому, что 500 раз в секунду считается (среди прочего) минмакс.

maytonЯ сильно сомневаюсь [...] Ну вот ... в таком вот аспекте. n'est-ce pas?
mayton , c'est tout. В смысле - pourquoi cure l'accordeon? ;)

Ну зачем же так серьезно о метафоре, тем более анонсированной как сарказм в ответ на сарказм :)

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

Смысл этой метафоры совсем даже философский - бездействие так же суть следствие принятия решения, как и действие. Если кто знаком с уставами или кодексом, то знает, что бездействие часто наказывается даже сильнее. Типа:
"... если боевое дежурство приведо к последствиям, во избежание которых оно назначено..." - ну и далее кирдык по тексту :)

А касательно мувингов (скользящих средних) - это ведь отдельная песня. Инструмент хороший, но... Там столько "но"... короче, его уметь надо готовить. С ними, в частности и сравнивается минмакс. Тут нюанс в том, что если мы говорим о процессах физического, природного характера, т.е. о процессах, обладающих определенной инерцией (ну, типа нагрев заготовки, разгон торможение э-двигателя), то мувинги и их комбинации справляются на ура. Если же наблюдаемые процессы безынерционны и, более того, склонны мгновенно менять знак (вектор) на противоположный, то мувинги будут совсем даже во вред. И вот отслеживание этой точки перелома есть одна из основных задач данной, простите, задачи :) На передний план выходит фильтрация шума (естественных смен знака).

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

Dimitry SibiryakovunderCдатчиками генрируется абстракщина, понятия не имею.А ты поинтересуйся. Потому что если диапазон значений невелик и разброс - тоже, то быстрейшим способом получить экстремумы будет массив счётчиков значений. Как тебе уже сказали.Может в этом и есть сермяжная правда. Но ведь таким образом ты меня подталкиваешь к написанию собственного API, а это не есть гуд. Сырые данные с датчиков... гальванические развязки, калибровки, шумы... Ты это все серьезно?

Dimitry SibiryakovunderCЯ оценил сарказм. Позволь и мне?Не позволю. Потому что это не был сарказм. Я знаю что такое ИИ и системы принятия решений.
Если их алгоритмы должны работать в реальном времени, на каждую порцию данных, тогда - да, min/max надо считать при занесении данных в буфер. Если они работают реже чтобы не дёргать зазря исполнительные цепи из-за кратковременных выбросов - нет смысла мучить сборщика данных.
* Не позволю.
Ну, я ужЕ, сорри :)

* Я знаю что такое [...]
Ну, я про себя так не скажу. А вот очередной притчей поделюсь. Про восходящие(!) стадии становления философа:

- Я знаю, что я знаю.
- Я знаю, что мало знаю.
- Я знаю, что ничего не знаю (это уже на смертном одре).

Так вот. Ты рассматриваешь кратенько, абрисно(!) описанную мной систему лишь в удобном для твоего знания и понимания разрезе. Оговорюсь о таком, к примеру, нюансе - есть один чуткий и нежный датчик. Так вот если в его отсчетах среди минмаксов начнут преобладать минимумы с явной периодичностью, а период будет иметь тенденцию уменьшаться, то готовь его к замене, он наелся. Если же он, начинает давать хаотичные выбросы в макс, то надо проверить его эл.цепь или же правильность установки. И таких примеров полно. Ты мне дашь гарантию, что заниженная частота опросов его минмаксов не стушует картину его тенденции к выходу? Или вообще не снивелирует ее? Йенг даешь на пятаки?

Я не могу понять, почему нельзя просто принять на веру мое "надо"? Даже если это просто мой каприз. Даже, если это просто дурость. Помогите разобраться с этим гребаным Си, и не учите меня жить ;)

Я ведь говорил уже - да часть информации избыточна и мои требования к системе тоже. Но это ведь только стадия если не разработки, но все еще обкатки. Пока есть запас прочности (а замеры мужиков выше это подтверждают) - надо делать в самой простой модели, соответствующей моему низкому скиллу в Си . Вот когда заработает и станет это узким местом - вот тогда и вернемся к вопросу.

m_Sla, спасибо за код, но я в некоторых непонятках.

1. Если я правильно понимаю, то структуры в C++, это как пользовательские типы в VBA. Но это ведь имеет смысл, если участвуют данные разных типов, а у меня ведь все лонги.

2. Ну, пусть структура. Но я в этом коде не увидел, ни как передать ее в длл из VBA, ни как выплюнуть результаты вычислений обратно. Это же пример лишь как ворочать ее внутри длл.

Повторюсь (уточню). В длл я должен передать вновь поступившие показания нескольких датчиков. Они (по твоему коду) будут сохранены в массивах data (у тебя он один, но можно добавить ему измерение). Сейчас я передаю их параметрами, а хотелось бы - массивом. Или типом, т.к. из VBA, чтобы он был проинтерпретирован внутри как структура.

Из длл я должен получить минмаксы по каждому из датчиков. Массивом ли, струтурой ли (преобразованной как-то обратно в тип), но не цепочкой обращений за мин, за макс, за чем-то там еще.

Правильно я понимаю, что невозможно передать из VBA в сишную длл параметр по ссылке? Чтобы в VBA этот параметр отразил модифицированное внутри длл его значение.