В декомпилированных исходниках Cyberpunk 2077, есть алгоритмы работающие со сложностью O(n^3). Потом люди удивляются, а чего игры лагают, даже на мощных ПК

3232

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

1. Первый цикл: пробегаем по массиву actionEffectsOfEffects.
2. Второй цикл: пробегаем по элементам вложенного массива actionEffectsOfEffects[i] (который мы выше назвали actionEffects).
3. Третий цикл: пробегаем по вообще не связанному массиву и сравниваем с actionEffects[j].

Аналогия для людей, далёких от программирования: у тебя колода карт. В ней всего N карт, но они разбиты на несколько мастей (допустим M <= N).

Если мы пробежали по всем картам, какая тут сложность? O(N).

А если карты рассортированы по мастям, и мы сначала проходимся по всем мастям, и внутри каждой масти по всем картам из этой масти (карты уже разложены по M стопочкам). Изменится ли сложность? Станет ли она квадратичной?

Нет, нихуя не станет. Пока M <= N, асимптотическая оценка не меняется вообще никак. Это по-прежнему линейное O(N). И это сложность первых двух циклов. Давай посмотрим на третий.

Теперь каждую карту этой масти потом сравниваем с каждой картой в каком-то списке (например карт, за которые принято бить в морду). Насколько длинный список? А кто его знает. Название appliedEffects намекает, что это может быть что-то очень короткое.

В результате мы получили O(N * ArraySize(AppliedEffects)), где ArraySize(AppliedEffects) скорее всего вообще крошечный.

Мудацкий ли код? Безусловно да, если N велико.
Безусловно нет, если и N маленькое, и ArraySize(AppliedEffects) крошечный.

Свидетелям кубической сложности просьба перечитать код: первые два цикла пробегают не по тем же самым элементам.

72
Ответить

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

10
Ответить

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

4
Ответить

Комментарий недоступен

1
Ответить

Безусловно да, если N велико. Безусловно нет, если и N маленькое, и ArraySize(AppliedEffects) крошечный.Смело предполагается что N всегда будет маленьким.Oh, my sweet summer child.

1
Ответить

Сам же придумал условия, и сам себе все объяснил, умен

Ответить