Что такое «мягкое» реальное время?

Разве при этом блокируются все потоки, как в питоне?

А разве все сборщики мусора блокирующие как в питоне? И это никак не влияет на детерминированность. Освобождение дерева в плюсах точно также вносит недетерминированность как и его освобождение сборщиком мусора. У гц есть недетерминированность, которой нет в плюсах, но она заключается в другом, а люди этого просто не понимают.

алгоритмы со сложностью O(1). То есть алгоритмы независящие от количества обрабатываемых элементов

С одной стороны, сложность O(1) не гарантирует, что алгоритм не зависит от количества элементов. Она гарантирует, что время работы алгоритма никогда не превысит некую константу.

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

Если сделать допущение, что каждая операция в алгоритме выполняется константное время и сделать переход «реальное время» -> «шаг алгоритма», то задача сводится к исследованию сложности алгоритма. Так как константа N - это О(1), то алгоритмы реального времени - это алгоритмы со сложностью O(1). То есть алгоритмы независящие от количества обрабатываемых элементов.

Ну я вижу вы поднялись на одну ступеньку к пониманию процессов. Но нужно еще на одну подняться. Открою вам страшную тайну, только вы (тссссс!) никому-никому не говорите! Обещаете? Так вот, сложность алгоритма это только лишь одна сторона и она не определяющая. Бывает, когда алгоритм O(N^2) лучше и более «рилтаймовее»(с), чем алгоритм O(logN). Жизнь слишком сложная штука, чтобы делить ее на черное и белое

Мне нравится этот человек.

Все правильно говорит.

Бывает, когда алгоритм O(N^2) лучше и более «рилтаймовее»(с), чем алгоритм O(logN).

И тут начинают умничать про значения-экстремумы функции на отрезке, про константы перед О-большими и о-малыми.

Еще раз повторю свои слова

задача сводится к исследованию сложности алгоритма

при определеных условиях.

Придрался, чтобы придраться?

Для тебя поправлюсь:

«То есть алгоритмы, сложность которых в О-нотации не зависит от количества обрабатываемых элементов.»

С другой стороны, если ограничить количество элементов

Еще один с экстремумами на отрезке.

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

Придрался, чтобы придраться?

Твой пост, в том виде, в каком он был написан, мог ввести в заблуждение других читателей. Ты расставил акценты так, будто «рилтаймовость» алгоритма зависит исключительно от того, O(1) это алгоритм, или нет.

системы с заранее известным (малым) количестом

Не обязательно малым.

ибо сборка мусора и прочие «радости слабых» исключающие детерминированное поведение

как уже достали эти мифы. Насколько детерминированным будет в С++ освобождение дерева? Вот вышел у нас из скоупа shared_ptr на корень дерева. Какие гарантии нам дает С++, что время освобождения, скажем, не превысит N микросекунд? Радость сильных, блин. shared_ptr в С++ это тоже автоматическая сборка мусора и она имеет все те же недостатки что и трассирующий сборщик мусора плюс свои особенности. Не нужно рассказывать сказки. Ничто не мешает выделить всю необходимую память перед началом работы и потом вообще ее не выделять и сборщик даже не запустится (хотя это от языка конечно зависит)

Сказки в ваших головах ;)

В условиях жесткого реального времени C++ почти всегда тоже идет в лес, во всяческими STL, boost и т.д.

Собственно, суть в в том, чтобы вместе с кодом (в идеальном случае) получить доказательство, что в при любых данных соответствующих условиям, и либом исходном (но корректном) состоянии некий кусок кода отработает не более чем за N тактов CPU.

Соответственно, вольности типа new/malloc, std::sort и т.п., как правило запрещаются «законодательно». В том числе, почти всегда специально используются более медленные алгоритмы, но с более стабильным/гарантированным результатом.

Ты расставил акценты так, будто «рилтаймовость» алгоритма зависит исключительно от того, O(1) это алгоритм, или нет.

Хочешь, «глупость» скажу: любая «конечная» функция на отрезке принадлежит O(1). Так что любой вычислимый детерминированный алгоритм для начальных данных с заранее известными свойствами имеет сложность O(1).

Поэтому в реале выходит так, что реалтайм системы имеют заранее определенный набор управляемых элементов. И разработчик занимается подгонкой константы для О(1).

В условиях жесткого реального времени C++ почти всегда тоже идет в лес, во всяческими STL, boost и т.д.

Вот в этом и дело, что не только:

Python, Java, C# и т.п. не подходят для задач реального времени, ибо сборка мусора и прочие «радости слабых» исключающие детерминированное поведение. Т.е. их можно использовать в сопутствующих задачах, но не в самом пути выполнения realtime.

Да и Си тогда в том числе.

А точнее: идёт не язык, а код написанный без соответствующих ограничений, использующий любой рантайм без ограничений. Т.к. и сборщик мусора может быть реального времени.

любой вычислимый детерминированный алгоритм для начальных данных с заранее известными свойствами имеет сложность O(1)

Да-да, поинт в том, что не нужно бездумно выносить свойство «объем»=N за скобки и затем мастурбировать на f из выражения O(f(N)). В реальности почти никогда не бывает, чтобы N было по-настоящему неограниченным (в частности, чтобы N не было ограничено вследствие ограниченного объема памяти у компьютера, вследствие ограниченного срока эксплуатации системы, и тд и тп); да и по-настоящему большие N также относительно редки. В конечном итоге важна не столько форма кривой на графике f, сколько вся совокупность констант (одной из констант будет максимум f), потому что система реального времени должна со своей реакцией уложиться в константное время.

уложиться в константное время

Точнее, в заранее зафиксированное время.

Так что любой вычислимый детерминированный алгоритм для начальных данных с заранее известными свойствами имеет сложность O(1).

Неправильно. Линейный поиск в массиве размером n - O(n). Двоичный поиск в отсортированном массиве O(log(n)). Это я уже знаю.

У тебя здесь n заранее не известно. Назови вместо n конкретное число.

Ты вообще понимаешь что такое O большое? Чтобы найти элемент в массиве нужно последовательно просмотреть все элементы, так что время поиска - линейная функция от числа элементов.

То есть, ты согласился с O(1).

В реальности почти никогда не бывает, чтобы N было по-настоящему неограниченным

«В реальности» если к системе реального времени подключишь еще один элемент, то он перестает быть системой реального времени (СРВ), или вообще престанет быть системой. И эту ограниченность «экплуатируют» во весь рост.

Ты вообще понимаешь что такое O большое?

Да, понимаю. Не умничай, просто назови, чему в твоих данных равно n. Напечатай сюда конкретное число, а потом мы обсудим что в результате произошло с твоим O-большим.

А O(1) - отсутствие зависимости от числа элементов. Пример - вставка в начало списка, операция не зависит от числа элементов в списке.

А я бы не сел в аппарат, софт для которого писал ТС.

Я хоть учусь и пытаюсь разобраться, а половина ответивших тут уже работают с кашей в голове.

праально, топчи их в пол

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

То есть, ты согласился с O(1).

То есть, я не вижу проблемы в том, чтобы использовать в системе реального времени алгоритмы, сложность которых зависит от N (и в частности, "алгоритмы поиска"). Кроме того, считаю абсолютно неадекватной привычку некоторых «специалистов» судить о пригодности того или иного алгоритма исходя исключительно из асимптотической сложности (той, которая пишется внутри O-большого). Почему я так считаю - подробно разжевано выше по топику. В итоге, считаем, что мы с тобой пришли к полному взаимопониманию? ;)

А зачем использовать CPython?

Потому что эталонная реализация стандарта. Можно и PyPy использовать, что и делают, те кому надо.

А конкретно micropython использовать вне своей ниши - сомнительная радость, ибо реализация стандартной библиотеки не полностью совместима и сильно урезана, а по языковым средствам отставание в 3-5 минорных версий. Ну, и где-то читал, что какие-то оптимизации в силу специфики сделаны хаками.

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

Поэтому для СРВ нормально, если увидишь пузырьковую сортировку для 8 элементов. :)

Я хоть учусь и пытаюсь разобраться

Пытаешься? Давай, расскажи нам о смысле выражения «g(N)=O(f(N))» при условии, что N ограничено сверху неким наперёд заданным N1. Можешь ты в матан хоть на пол-шишечки, или в голове вместо мозгов резонирует желеобразная масса?

Поэтому для СРВ нормально, если увидишь пузырьковую сортировку для 8 элементов. :)

Собственно, это не только для СРВ характерно - выбирать алгоритм с учетом размера и характера данных. В серьезных библиотеках это делают (переключаются налету между несколькими принципиально разными алгоритмами, имеющими разные константы и асимптотики) чтобы выжать максимум производительности, а в прикладном коде это делают (по возможности реализуют алгоритм попроще) чтобы обеспечить хорошие readability, maintainability, time-to-market, повысить качество тестирования.

Хотел посмотреть, из какой анимы юзерпик. И нашел в tineye Filename: x-men-magneto.jpg (550 x 543, 125.8 KB)

Вот как анима влияет на американские комиксы

Воспламенение любителя баззвордов

«Реальное время» это обман чтобы набрать классы.

fixed

Да хоть бы и так. Люди любят баззворды. «Реальное время», «гибридное ядро», «большие данные», «эджайл», «скрам», «высокая доступность» и т.д.

его используют в программах для интернет-вещей

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

Просто сложился стереотип, что системы реального времени это что-то сверхбыстрое.

Анон дело говорит, всем слушать анона.

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

Ай отлично объяснил, ай молодца.

реальное время --- длительность опереции апрорна известна, жетстко задана

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

Это если свосем коротко

Мягкий реалтайм - видеостриминг и игрушки, т.е. когда если за определенное время фрейм не успевает отрисоваться, то это не фатально, но неприятно.

Жестский реалтайм - микроконтроллеры на атомных станциях, и системы автопилотов, когда выход за определенную временную границу означает что всё, приехали в кювет.

Для систем жестко реального времени обычно используются достаточно низкоуровневые языки, но не всегда. Обычно это Си, или что-либо подобно низкоровневое, типа фортрана. Некоторые вариации Java или Lisp - подходят, впрочем тоже.

C++ например для этого категорически не подходит, от слова вообще. Как и питон.

Для софт-реалтайма подходит вообще практически че угодно при современных уровнях развития железа, от CL до C#. Ну кроме скриптовых говноязыков типа питона, естественно.