Нахождение числа элементарных операций алгоритма

Всем доброго времени суток!
Я не до конца понимаю, таким ли образом производят оценку алгоритма, но всё же я хотел бы произвести расчёт потребной производительности "железа" (ПК, спец. микросхемы или других аналогов) для того, чтобы исполнение среднего количества операций в некоем алгоритме укладывалось в конкретный предел времени вычислений.
Вероятно, я переборщил с конструкциями в предыдущем абзаце (), поэтому опишу иначе: существует некий алгоритм "переменной длины" (с парой рекурсивных функций, глубина рекурсии которых не может быть вычислена заранее никаким образом), то есть, с переменным числом элементарных операций; я хочу определить, видимо, частоту ядра вычислительного устройства, с которой оно должно работать, для того, чтобы уложить выполнение всех элементарных операций алгоритма в, например, пять секунд.
В общем, я хотел бы, чтобы кто-нибудь подсказал мне, как вообще считается количество элементарных операций алгоритма, если посчитать их "ручками" не представляется возможным (или это займёт месяц), и нужно ли оно мне, если есть какие-то другие методы оценки потребной производительности вычислительного устройства.
Буду весьма признателен за любую помощь и информацию!

0

Sindbad_M, для ускорения многих алгоритмов циклы наоборот разворачиваются - а вы предлагаете добавить накладных расходов... Я понял бы еще предвычисление значений x-1 x+1 y-1 y+1 -- и их подстановку в функции, но думаю, компилятор и так это проделает.

0

Ромуальд_7, что в вашем алгоритме соответствует вызову функции решения системы нелинейных уравнений?

Добавлено через 6 минут

Сообщение от vantfiles а вы предлагаете добавить

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

Сообщение от vantfiles В нем каждая точка тестируется до 8 раз. В "построчном" варианте - один раз.

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

2

Сообщение от Sindbad_M не каждая же.

каждая. каждый рекурсивный вызов порождает восемь проверок.

Сообщение от Sindbad_M Это же и есть построчный поиск

Вовсе нет.

1

Сообщение от vantfiles Но в данном случае это как проделать?

Я имею ввиду не замену рекурсии циклом, а замену циклом восьми (почти) одинаковых строчек. Цикл по всем соседям клетки. Для того чтобы отделить логику определения соседних клеток от собственно алгоритма заливки.

Сообщение от vantfiles цвет точки с номером пять проверяется из каждой из остальных точек - отсюда и восемь проверок.

1. На сложность алгоритма это не влияет.
2. Количество проверок зависит от цвета окружающих точек. Восемь проверок будет только для точки, все соседи которой ненулевые.

Сообщение от vantfiles Этой избыточности можно избежать - алгоритм я приводил.

Дайте ссылку, пожалуйста.

1

Сообщение от Sindbad_M Такая замена не изменяет временной сложности алгоритма. Также как и разворачивание цикла.

А зачем тогда его сворачивать? Чтобы сложнее было прочесть?

1

Сообщение от vantfiles каждая. каждый рекурсивный вызов порождает восемь проверок.

Не каждая. Соседи нулевой клетки не проверяются.

1

Shamil1, придется поискать, но разумеется.

0

Сообщение от vantfiles А зачем тогда его сворачивать?

Я писал:

Сообщение от Shamil1 Для того чтобы отделить логику определения соседних клеток от собственно алгоритма заливки.

1

Алгоритм выделения областей в двумерном массиве

Вот этот пост, ссылка на обзор алгоритмов и рекомендуемый мной, как опробованный мной когда-то давно на практике.

2

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

Добавлено через 10 минут

Сообщение от vantfiles ссылка на обзор алгоритмов и рекомендуемый мной, как опробованный мной когда-то давно на практике

На первый взгляд в линейном алгоритме по ссылке сравнений не меньше, чем простом алгоритме. Всё отличие - в глубине рекурсии.

1

Сообщение от Sindbad_M На самом деле, не надо смешивать два разных вопроса:

А так я и не смешиваю (более подробно - чуть ниже).

Сообщение от Sindbad_M А разве Матлаб это не есть С/С++ ?

И да и нет. .m-язык это интерпретируемый язык, который, как мы знаем, во всём хуже компилируемого. Ощутимо проявляется это, прежде всего, в его графической составляющей - пусть matlab и утверждает, что использует OpenGL (кстати говоря, какой? Не указано), на деле же поворот трёхмерной поверхности (всего на 90'000 узловых точек сетки) вызывает какие-то невероятные сложности, от которых "всё тормозит"; на Си, как мы знаем, с лёгкостью можно провернуть и не такое.

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

Вот теперь можно вернуться к началу и продолжить: мой код на матлабе я МАКСИМАЛЬНО оптимизировал до состояния "из песни слов не выкинешь". Алгоритм является максимально эффективным с точки зрения матлаба, но даст ли исполнение на компилируемом языке ощутимый прирост? Можно ли из C++ "выбить" решение системы нелинейных уравнений не за матлабовские 3-5 секунд, а за 0.5-1? Чисто теоретический вопрос, чтобы знать, стоит ли игра свеч.

Добавлено через 13 минут
vantfiles, Shamil1,
К сожалению, я предполагал, что приведение этого примера введёт Вас в заблуждение.

Сообщение от Shamil1 Можно.

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

Сообщение от Shamil1 Максимальная глубина рекурсии - количество клеток в одной "связанной" области.

А вот это не совсем так, кстати говоря. На какой-то клетке алгоритм может начать уходить в одну сторону, "пожирая" соседние клетки, и прийти к точке, вернуться назад от которой будет невозможно; тогда рекурсия будет "подниматься" до той глубины, где будет возможно продолжение поиска. Таким образом, частой является ситуация, когда, например, алгоритм несколько раз доходит до глубины "15", после чего возвращается к глубине "1" и возобновляет поиск по другому направлению до глубины "20"; как итог - точек не менее 35, а максимальная глубина - 20. В качестве примера такой области я вижу крест.

Сообщение от vantfiles Это самый простой и самый неоптимальный алгоритм.

В масштабе мой глобальной задачи, которая выполняется около одной минуты, эти несчастные "неоптимальные" 4 миллисекунды в её составе, всплывающие от трёх до пяти раз - фигня

Добавлено через 14 минут

Сообщение от Sindbad_M Ромуальд_7, что в вашем алгоритме соответствует вызову функции решения системы нелинейных уравнений?

Я не до конца понял Ваш вопрос. Если Вас интересует метод вызова на языке матлаба, то вот:
Сама система выглядит так (вставлю ссылку на свой же вопрос в другом разделе) - Аппаратное обеспечение алгоритма

По сути, вся проблема в том, что матлаб не даёт регулировать точность решения по методу Solve. Он оооочень долго что-то там делает, а потом выводит результат, порой, с точностью до тридцатого знака. На мои вопросы, вроде: "а чем тебе не нравится третий знак после запятой?" - он не отвечает. Возможно, стоило бы своими ручками составить алгоритм решения этой системы (благо, методов к этому времени скопилось дофигища), но глобальной задачей было изобретение универсального, стабильного алгоритма, работающего от любого входа, не имеющего обработчика исключений (за ненадобностью). Я создал такой алгоритм, однако возможности матлаба меня, в какой-то степени, не устраивают.
P.S. Ещё в матлабе есть метод fSolve, который работает очень быстро, однако главным ограничением использования которого является вывод только одного решения из всех возможных (ближайшего к начальному приближению). С ним ещё больше заморочек, поэтому он мне не нравится.

0

Сообщение от Ромуальд_7 точек не менее 35, а максимальная глубина - 20

Максимальная глубина - это не сколько получилось в неком конкретном случае, а максимум того, что может получиться. Для 35 точек можно подобрать область таким образом, чтобы глубина рекурсии стала 35 (выстроить их в линию). Значит, максимальная глубина - 35, даже если в каком-то случае глубина будет 15.

1

Shamil1, а, понял Вас - рассматривается худший случай; спасибо!

0

Сообщение от Ромуальд_7 .m-язык это интерпретируемый язык, который, как мы знаем, во всём хуже компилируемого

MATLAB Coder не пробовали?

0

Сообщение от vantfiles MATLAB Coder не пробовали?

Ох, как же с ним всё грустно... С одной стороны, matlab Help почти для каждой функции указывает синтаксис, который "матлаб умеет, но не умеет кодер", а также синтаксис, который "умеет и матлаб и кодер", а с другой, даже если сделать ровно так, как говорит "MHelp" (там прямо жирными буквами написано: "ТАКАЯ ЗАПИСЬ ПОДДЕРЖИВАЕТСЯ КОДЕРОМ ПРИ ПЕРЕВОДЕ"), кодер в самом начале скажет "неа, не буду", и на этом всё и закончится, хотя казалось бы.
Кроме того, многие из интересующих меня функций просто не могут быть переведены на Си, что весьма удручает.
В общем, как я уже говорил, всё грустно..

0

Сообщение от Ромуальд_7 Возможно, стоило бы своими ручками составить алгоритм решения этой системы (благо, методов к этому времени скопилось дофигища)

Так при портировании на компилируемый язык программирования, решение системы все равно придется составить самостоятельно. На мой взгляд, если вы можете написать эффективный алгоритм решения системы, стоит написать его прямо на языке Матлаба. Если алгоритм решения будет быстрым, то и в интерпретируемом Матлабе он выполнится быстро.

0

Sindbad_M, вообще говоря, Вы правы, конечно же, и, боюсь, что ждёт меня именно это занятие.

0