В анализе сложности алгоритмов оператор += это одна операция или две?

Question

[DollyPapper]

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

Собственно сабж в заголовка: почему человек посчитал, что оператор += имеет стоимость 1, когда по сути эти две операции? Это ошибка, или действительно так считают?

Comments

[Lynn «Кофеман»]

В нормальном анализе такой фигнёй не страдают. Потому что сложность O(n), а константы не имеют значения.

[DollyPapper]

Lynn «Кофеман», то что сложность O(n) вопроса не возникает это и так понятно, вопрос был именно почему += посчитали за одну операцию.

[Ипатьев]

Надо спрашивать у автора картинки

[Alexandroppolus]

оператор += имеет стоимость О(1) операций

[DollyPapper]

Alexandroppolus, вопрос в их количестве,а не сложности, т.е. один это оператор или два.

Answer 1

[Армянское Радио]

Это одна операция, посчитано правильно. При подсчете числа операций (FLOPS), во внимание принимают только арифметические операции.

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

Comments

[DollyPapper]

Тогда во второй строке тоже одна операция и оператор присваивания в расчет не должен браться, однако судя по картинке это не так. В чем логика?

[Ипатьев]

И в четвёртой тогда должно быть 2 а не 3

[Армянское Радио]

DollyPapper, А у автора вашего алгоритма - какая-то своя логика, отличная от общепринятой. Он зачем-то считает все подряд операции, вместе с присваиваниями. А инкремент считает за одну операцию.

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

[Ипатьев]

вообще какая-то чушь.
я, конечно, академиев не кончал, но что это за оценка сложности, где + и / имеют одинаковый вес?

[Армянское Радио]

Ипатьев, давайте так - вы сначала гулите, что вам непонятно, а потом выдаете эпитеты вроде вшего "чушь" и подобной лексики. В данном случае, я для вас погуглю: FLOPS

[DollyPapper]

Ипатьев, Армянское Радио, операции я думаю тут считаются абстрактные типа машина сделала работу, (а + для машины это одна операция ассемблерного ADD, MUL, DIV, и т.д.), но тогда ИМХО и присваивание нужно считать за операцию (работу), потому что MOV тоже как бы операция и время занимает. В общем действительно хрень какая-то.

[Ипатьев]

Спасибо, что любезно нашли подтверждение моим словам:

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

[Ипатьев]

Плюс мне кажется, что FLOPS - это всё-таки не "анализ сложности", что бы это не значило, а измерение производительности.

[Ипатьев]

В общем, дело ясное, что дело тёмное

[DollyPapper]

Армянское Радио, а можете пояснить, при чем тут

используемая для измерения производительности компьютеров, показывающая, сколько операций с плавающей запятой в секунду выполняет данная вычислительная система

и данный алгоритм? Что в итоге считать за операции, а что нет? Математические операции мы считаем, а операцию присваивания нет?

[Армянское Радио]

DollyPapper, Логика такая - при дефолтных настройках большинство трансляторов-компиляторов транслируют арифметические действия "как написано" - не применяют математических правил (иначе говоря, не расставляют и не перествляют скобки в выражениях) для того, чтобы сократить число таких операций.

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

Относительно применимости FLOPS как метрики производительности - все сильно зависит от того, что мы хотим этой метрикой сравнивать. Если речь идет о выполнении стандартного теста LAPACK, который состоит из популярных для вычислительной математики операций - мы можем довольно достоверно понять, какой из двух компьютеров быстрее, измерив, сколько гиганских матриц каждый из них перемножает в секунду.

[Lynn «Кофеман»]

Армянское Радио, есть только проблема что если уж мы начинаем считать такты процессора, то в таком случае нелогично считать деление и сложение одинаковыми по сложности операциями.

[Армянское Радио]

Lynn «Кофеман», если почитать рецензированные научные работы, в них часто операции делят на два-три класса - считают сложение/вычитание отдельно от умножения/деления, и даже выносят деление в отдельный класс. Ну и пишут - "наш алгоритм умножения матриц специального вида требует X операций типа "сложение" и Y операций типа "умножение".

[Lynn «Кофеман»]

Армянское Радио, вот именно. А автор оригинальной картинки смешал в кучу сложение, умножение, деление и присваивание. Т.е. FLOPS у него и рядом не стоял

Answer 2

[Владимир Куц]

Ну смотрите... - в ячейке по адресу №000001 хранится число 1.
Вы эту ячейку увеличили на 1 - теперь в ячейке хранится 2

Сколько операций вы проделали?

Comments

[DollyPapper]

В том то и вопрос, сколько операций я проделал? Я не особо помню, что на уровне маш. команд происходит в этом случае.
Мы берем в регистр значение из памяти, прибавляем к нему значение и кладем обратно в память или мы делаем INC. Понятно, что тут всё зависит от архитектуры, компилятора, версии компилятора, счастливого случая и фазы луны, но в общем случае как я понимаю: мат. операции мы в любом случае будем выполнять, а вот присваивания может и не быть, по этому не имеет смысла её считать.

[Армянское Радио]

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

[pfg21]

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