В анализе сложности алгоритмов оператор += это одна операция или две?
Добрый день всем. Наткнулся в интернете на картиночку с анализом сложности алгоритма подсчета сложных процентов.
Собственно сабж в заголовка: почему человек посчитал, что оператор += имеет стоимость 1, когда по сути эти две операции? Это ошибка, или действительно так считают?
Это одна операция, посчитано правильно. При подсчете числа операций (FLOPS), во внимание принимают только арифметические операции.
При выводе O-оценки алгоритма (это другое), изучают вид функции, которая выражает зависимость между параметрами алгоритма (например, числом сортируемых элементов для сортировки) и потребляемыми ресурсами (количеством итераций цикла, требуемым размером массива для промежуточных данных и т.п.)
DollyPapper, А у автора вашего алгоритма - какая-то своя логика, отличная от общепринятой. Он зачем-то считает все подряд операции, вместе с присваиваниями. А инкремент считает за одну операцию.
Практического смысла в этом довольно мало, потому что такой подсчет имеет хоть какой-то смысл при анализе ассемблерного кода, но никак не в рамках высокоуровневого языка - мало ли, во что это дело соптимизируется в итоге.
Ипатьев, давайте так - вы сначала гулите, что вам непонятно, а потом выдаете эпитеты вроде вшего "чушь" и подобной лексики. В данном случае, я для вас погуглю: FLOPS
Ипатьев, Армянское Радио, операции я думаю тут считаются абстрактные типа машина сделала работу, (а + для машины это одна операция ассемблерного ADD, MUL, DIV, и т.д.), но тогда ИМХО и присваивание нужно считать за операцию (работу), потому что MOV тоже как бы операция и время занимает. В общем действительно хрень какая-то.
используемая для измерения производительности компьютеров, показывающая, сколько операций с плавающей запятой в секунду выполняет данная вычислительная система
и данный алгоритм? Что в итоге считать за операции, а что нет? Математические операции мы считаем, а операцию присваивания нет?
DollyPapper, Логика такая - при дефолтных настройках большинство трансляторов-компиляторов транслируют арифметические действия "как написано" - не применяют математических правил (иначе говоря, не расставляют и не перествляют скобки в выражениях) для того, чтобы сократить число таких операций.
Таким образом, арифметические операции в итоге процессор выполнить обязан. И кроме того, они обычно на порядок дольше по числу тактов, чем операции присваивания между регистрами.
Относительно применимости FLOPS как метрики производительности - все сильно зависит от того, что мы хотим этой метрикой сравнивать. Если речь идет о выполнении стандартного теста LAPACK, который состоит из популярных для вычислительной математики операций - мы можем довольно достоверно понять, какой из двух компьютеров быстрее, измерив, сколько гиганских матриц каждый из них перемножает в секунду.
Армянское Радио, есть только проблема что если уж мы начинаем считать такты процессора, то в таком случае нелогично считать деление и сложение одинаковыми по сложности операциями.
Lynn «Кофеман», если почитать рецензированные научные работы, в них часто операции делят на два-три класса - считают сложение/вычитание отдельно от умножения/деления, и даже выносят деление в отдельный класс. Ну и пишут - "наш алгоритм умножения матриц специального вида требует X операций типа "сложение" и Y операций типа "умножение".
Армянское Радио, вот именно. А автор оригинальной картинки смешал в кучу сложение, умножение, деление и присваивание. Т.е. FLOPS у него и рядом не стоял
В том то и вопрос, сколько операций я проделал? Я не особо помню, что на уровне маш. команд происходит в этом случае.
Мы берем в регистр значение из памяти, прибавляем к нему значение и кладем обратно в память или мы делаем INC. Понятно, что тут всё зависит от архитектуры, компилятора, версии компилятора, счастливого случая и фазы луны, но в общем случае как я понимаю: мат. операции мы в любом случае будем выполнять, а вот присваивания может и не быть, по этому не имеет смысла её считать.
Зависит от архитектуры. А x86_64, вероятно, я подождал несколько тактов до синхронизации с памятью, за один раз, если мне повезло (или за два, если не повезло), загрузил оба операнда в кэш процессора, затем за две операции (или за одну, если повезло), раскидал операнды по регистрам, потом сложил, потом снова подождал синхронизации с RAM и выгрузил результат. В итоге, если мне не повезло и не было попаданий в кеш, я скорее всего прождал как минимум два периода тактовой частоты памяти, а то и больше.
если не повезло, то вместо кешей всех уровней попал чисто на память и это становится очень долго :)
в алгоритмах много чего не учитывается, в том числе и аппаратные потребности.
сложность алгоритма это "философский вопрос" а не прикладной.
