В декомпилированных исходниках Cyberpunk 2077, есть алгоритмы работающие со сложностью O(n^3). Потом люди удивляются, а чего игры лагают, даже на мощных ПК
В декомпилированных исходниках Cyberpunk 2077, есть алгоритмы работающие со сложностью O(n^3). Потом люди удивляются, а чего игры лагают, даже на мощных ПК
Непонятно какой язык, но код вполне читабельный, так что давай посчитаем на пальцах.
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) крошечный.
Свидетелям кубической сложности просьба перечитать код: первые два цикла пробегают не по тем же самым элементам.
Свифт там, согласен, вполне нормальный читаемый код который приемлемо будет в большинстве случаев, никакого o(n^3) там даже близко нету, тс херню какуюто высрал даже не разобравшись.
всё кайфово расписал, и всё скорее всего действительно так. никто не будет убиваться по ассоциативным массивам в случаях на таких крошечных данных и лишняя оптимизация в лучшем случае приведёт к тому, что код не читаем будет (а значит и трудно поддерживаемым, а на проектах в активной разработке уж лучше будет тупо написано, чем "умно").
Комментарий недоступен
Безусловно да, если N велико. Безусловно нет, если и N маленькое, и ArraySize(AppliedEffects) крошечный.Смело предполагается что N всегда будет маленьким.Oh, my sweet summer child.
Сам же придумал условия, и сам себе все объяснил, умен