Почему вложенные циклы считаются плохой практикой?

33

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

Я не очень понимаю, почему? Это потому, что это влияет на читабельность кода? Или это что-то более "техническое"?

DSF
источник
4
Если я правильно помню свой курс CS3, то это потому, что он часто приводит к экспоненциальному времени, что означает, что если вы получите большой набор данных, ваше приложение станет непригодным для использования.
Трэвис Пессетто
21
Одна вещь, которую вы должны узнать о лекторах CS, это то, что не все, что они говорят, применимы на 100% в реальном мире. Я бы не рекомендовал циклы, вложенные более чем в несколько глубин, но если вам нужно обработать m x n элементов, чтобы решить вашу проблему, вы будете делать это много итераций.
Blrfl
8
@TravisPessetto На самом деле это все еще полиномиальная сложность - O (n ^ k), где k - число вложенных, а не экспоненциальных O (k ^ n), где k - константа.
m3th0dman
1
@ m3th0dman Спасибо, что поправили меня. Мой учитель не был лучшим в этом предмете. Он рассматривал O (n ^ 2) и O (k ^ n) как то же самое.
Трэвис Пессетто
2
По мнению некоторых людей, вложенные циклы увеличивают цикломатическую сложность (см. Здесь ), что снижает удобство сопровождения программы.
Марко

Ответы:

62

Вложенные циклы хороши, если они описывают правильный алгоритм.

Вложенные циклы имеют соображения производительности (см. Ответ @ Travis-Pesetto), но иногда это совершенно правильный алгоритм, например, когда вам нужно получить доступ к каждому значению в матрице.

Маркировка циклов в Java позволяет преждевременно разорвать несколько вложенных циклов, когда другие способы сделать это будут громоздкими. Например, некоторые игры могут иметь такой код:

Player chosen_one = null;
...
outer: // this is a label
for (Player player : party.getPlayers()) {
  for (Cell cell : player.getVisibleMapCells()) {
    for (Item artefact : cell.getItemsOnTheFloor())
      if (artefact == HOLY_GRAIL) {
        chosen_one = player;
        break outer; // everyone stop looking, we found it
      }
  }
}

Хотя код, подобный приведенному выше, иногда может быть оптимальным способом выражения определенного алгоритма, обычно лучше разбить этот код на более мелкие функции и, вероятно, использовать returnвместо него break. Так что breakс этикеткой - слабый кодовый запах ; обратите особое внимание, когда вы видите это.

9000
источник
2
Так же, как в качестве примечания, используйте алгоритм, который должен получить доступ к каждому фрагменту матрицы. Тем не менее, GPU специализируется на том, чтобы справляться с этим экономически эффективным образом.
Трэвис Пессетто
Да, GPU делает это массивно-параллельным способом; вопрос был об одном потоке казни, я полагаю.
9000
2
Одна из причин, по которой ярлыки вызывают подозрение, заключается в том, что часто есть альтернатива. В этом случае вы можете вернуться вместо.
jgmjgm
22

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

Например, если у вас есть 100 элементов в списке A и 100 элементов в списке B, и вы знаете, что для каждого элемента в списке A есть один элемент в списке B, который соответствует ему (с определением «match», оставлено намеренно неясным здесь), и вы хотите создать список пар, простой способ сделать это так:

for each item X in list A:
  for each item Y in list B:
    if X matches Y then
      add (X, Y) to results
      break

Если в каждом списке 100 элементов, это займет в среднем 100 * 100/2 (5000) matchesопераций. С большим количеством элементов или если соотношение 1: 1 не гарантировано, оно становится еще дороже.

С другой стороны, есть гораздо более быстрый способ выполнить такую ​​операцию:

sort list A
sort list B (according to the same sort order)
I = 0
J = 0
repeat
  X = A[I]
  Y = B[J]
  if X matches Y then
    add (X, Y) to results
    increment I
    increment J
  else if X < Y then
    increment I
  else increment J
until either index reaches the end of its list

Если вы делаете это таким образом, то вместо того, matchesчтобы основывать количество операций length(A) * length(B), теперь оно основано length(A) + length(B), что означает, что ваш код будет работать намного быстрее.

Мейсон Уилер
источник
10
С оговоркой, что установка сортировки занимает нетривиальное количество времени, O(n log n)дважды, если используется быстрая сортировка.
Роберт Харви
@RobertHarvey: Конечно. Но это все же намного меньше, чем O(n^2)для немигающих значений N.
Мейсон Уилер
10
Вторая версия алгоритма, как правило, неверна. Во-первых, предполагается, что X и Y сравнимы через <оператор, который, как правило, не может быть получен из matchesоператора. Во-вторых, даже если X и Y являются числовыми, 2-й алгоритм все равно может давать неправильные результаты, например, когда X matches Yесть X + Y == 100.
Паша
9
@ user958624: Очевидно, это очень общий обзор общего алгоритма. Как и оператор «совпадения», «<» должно быть определено так, чтобы оно было правильным в контексте сравниваемых данных. Если это сделано правильно, результаты будут правильными.
Мейсон Уилер
PHP сделал что-то подобное с их уникальным массивом и / или противоположностью этому. Вместо этого люди просто использовали бы массивы PHP, основанные на хэше, и это было бы намного быстрее.
jgmjgm
11

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

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

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

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

Steve314
источник
1
Очень часто вы можете просто сгладить вложенный цикл, и это все равно занимает столько же времени. принять от 0 до ширины, от 0 до высоты; Вместо этого вы можете просто указать ширину от 0 до высоты.
jgmjgm
@jgmjgm - да, есть риск усложнить код внутри цикла. Сглаживание может иногда это упростить, но чаще вы, по крайней мере, добавляете сложность восстановления индексов, которые вам действительно нужны. Один из приемов для этого - использование типа индекса, который учитывает вложение всех циклов в логику для увеличения специального составного индекса - вы вряд ли сделаете это только для одного цикла, но, возможно, у вас есть несколько циклов со схожими структурами или, возможно, Вы можете написать более гибкую универсальную версию. Затраты на использование этого типа (если таковые имеются) могут стоить этого для ясности.
Steve314
Я не предлагаю делать это как хорошую вещь, но как просто удивительно просто превратить две петли в одну, но это никак не повлияет на сложность времени.
jgmjgm
7

Учитывая случай многих вложенных циклов, вы получите полиномиальное время. Например, учитывая этот псевдокод:

set i equal to 1
while i is not equal to 100
  increment i
  set j equal to 1
  while j is not equal to i
    increment j
  end
 end

Это будет считаться O (n ^ 2) время, которое будет график, похожий на: введите описание изображения здесь

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

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

Трэвис Пессетто
источник
10
Вы можете захотеть повторно выбрать свой график: это экспоненциальная кривая, а не квадратичная, а также рекурсия не делает вещи O (n log n) из O (n ^ 2)
трещотка урод
5
Для рекурсии у меня есть два слова «стек» и «переполнение»
Mateusz
10
Ваше утверждение о том, что рекурсия может уменьшить операцию O (n ^ 2) до O (n log n), в значительной степени неточно. Тот же алгоритм, реализованный рекурсивно по сравнению с итеративным, должен иметь ту же сложность, что и время. Кроме того, рекурсия часто может быть медленнее (в зависимости от языковой реализации), поскольку каждый рекурсивный вызов требует создания нового фрейма стека, а итерация требует только ветвления / сравнения. Вызовы функций обычно дешевы, но они не бесплатны.
dckrooney
2
@TravisPessetto Я видел 3 переполнения стека за последние 6 месяцев при разработке приложений на C # из-за рекурсии или циклических ссылок на объекты. Что смешного в этом то, что он рухнет, а ты не знаешь, что поразило тебя. Когда вы видите вложенные циклы, вы знаете, что может случиться что-то плохое, и исключение из-за неправильного индекса для чего-то легко увидеть.
Матеуш
2
@Mateusz также, языки как Java позволяют вам поймать ошибку переполнения стека. Это с трассировкой стека должно позволить вам увидеть, что произошло. У меня нет большого опыта, но я видел единственную ошибку переполнения стека в PHP, в котором была ошибка, приводившая к бесконечной рекурсии, и PHP исчерпал 512 МБ памяти, которая была ему выделена. Рекурсия должна иметь конечное завершающее значение, которое не подходит для бесконечных циклов. Как и все в CS, есть время и место для всего.
Трэвис Пессетто
0

Вождение 30-тонного грузовика вместо небольшого легкового автомобиля - плохая практика. За исключением случаев, когда вам нужно перевезти 20 или 30 тонн груза.

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

Однако кто-то жаловался на маркировку петель. Ответ на этот вопрос: если вам нужно задать вопрос, не используйте маркировку. Если вы знаете достаточно, чтобы решить сами, то вы решаете сами.

gnasher729
источник
Если вы знаете достаточно, чтобы решить сами, вы знаете достаточно, чтобы не использовать помеченные петли. :-)
user949300
Нет. Когда вас научили достаточно, вас научили не использовать помеченное использование. Когда вы знаете достаточно, вы выходите за пределы догмы и делаете то, что правильно.
gnasher729
1
Проблема с лейблом в том, что он редко нужен, и многие люди используют его на ранних этапах, чтобы обойти ошибки управления потоком. Вроде как, как люди ставят выход повсюду, когда они неправильно управляют потоком. Функции также делают его в значительной степени избыточным.
jgmjgm
-1

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

Статьи, к которым вас привели, вероятно, во имя краткости или из-за психологического процесса, известного как сгорание, пропускающего специфику.

Быть сожженным - это когда вы испытываете негативный опыт чего-либо с вовлеченным существом, тогда вы избегаете этого. Например, я могу резать овощи острым ножом и резать себя. Я мог бы тогда сказать, что острые ножи плохи, не используйте их для нарезки овощей, чтобы попытаться сделать так, чтобы этот плохой опыт не повторился. Это, очевидно, очень непрактично. На самом деле вам просто нужно быть осторожным. Если вы говорите кому-то еще, чтобы нарезать овощи, то у вас это ощущается еще сильнее. Если бы я велел детям нарезать овощи, я бы очень чувствовал, что им не следует пользоваться острым ножом, особенно если я не могу пристально следить за ними.

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

Как многие ответы здесь указывают на то, что вложенный цикл for является показателем характеристик производительности вашей программы, которые могут экспоненциально ухудшаться с каждым вложением. То есть O (n), O (n ^ 2), O (n ^ 3) и т. Д., Которые содержат O (n ^ глубина), где глубина представляет, сколько циклов вы вложили. По мере роста вашего вложения необходимое время растет в геометрической прогрессии. Проблема в том, что это не уверенность в том, что ваша временная или пространственная сложность такова, что (довольно часто a * b * c, но не все гнездовые циклы могут выполняться все время), и это не уверенность, что вы будете есть проблемы с производительностью, даже если это так.

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

Вложенные циклы могут разрастаться, то есть они могут оказаться вложенными очень глубоко. Если я пройду через каждый континент, затем через каждую страну, затем через каждый город, затем через каждый магазин, затем через каждую полку, затем через каждый продукт, если это будет банка бобов через каждый боб, и измерить его размер, чтобы получить среднее значение, затем вы Я вижу, что это будет очень глубоко. У вас будет пирамида и много пустого пространства подальше от левого края. Вы можете даже уйти со страницы.

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

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

Существует естественная тенденция к тому, что люди привыкли. Если вы программируете что-то самым простым способом, вероятность того, что вам не понадобится вложение, является самой высокой, вероятность того, что вам нужен один уровень, уменьшается на порядок, а вероятность другого уровня снова падает. Частота падает и, по сути, означает, что чем глубже вложение, тем менее обученные человеческие чувства должны его предвидеть.

С этим связано то, что в любой сложной конструкции, которую можно рассматривать как вложенный цикл, всегда следует спрашивать, является ли самое простое из возможных решений, поскольку существует вероятность пропущенного решения, требующего меньшего количества циклов. Ирония заключается в том, что вложенное решение часто является самым простым способом создания чего-то, что работает с минимальными затратами усилий, сложности и когнитивной нагрузки. Часто бывает естественным гнездо для петель. Если вы рассмотрите, например, один из ответов выше, где гораздо более быстрый способ, чем вложенный цикл for, также гораздо сложнее и состоит из значительно большего количества кода.

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

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

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

Ответ на ваш вопрос заключается в том, что это и то и другое, но ни одна из проблем не является абсолютной. Они либо полностью субъективны, либо только контекстуально объективны. К сожалению, иногда полностью субъективное или, вернее, мнение занимает прецедент и доминирует.

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

Другое эмпирическое правило заключается в том, что вы всегда должны проверять количество элементов и спрашивать себя, будет ли этот цикл проблемой. В моем предыдущем примере я прошел через города. Для тестирования я могу пройти только десять городов, но какое максимальное количество городов ожидать в реальном мире? Тогда я мог бы умножить это на континенты. Эмпирическое правило всегда учитывать циклы, особенно те, которые повторяют динамическое (переменное) количество раз, что это может перевести вниз.

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

jgmjgm
источник
Пример острого <-> тупого ножа не велик, поскольку тупые ножи обычно более опасны для резки. И О (п) -> О (п ^ 2) -> О (п ^ 3) не экспоненциальному в n, это геометрический или многочленом .
Caleth
То, что унылые ножи хуже, это немного городской миф. На практике это варьируется и обычно характерно для случая, когда тупые ножи являются особенно неподходящими, обычно требующими большого усилия и большого проскальзывания. Хотя вы правы, здесь есть скрытое, но неотъемлемое ограничение: вы можете резать только мягкие овощи. Я бы посчитал n ^ глубину экспоненциальной, но вы правы, что эти примеры сами по себе не являются.
jgmjgm
@jgmjgm: n ^ глубина полиномиальная, глубина ^ n экспоненциальная. Это не совсем вопрос интерпретации.
Роэль Шровен
х ^ у отличается от у ^ х? Ошибка, которую вы сделали, заключается в том, что вы никогда не читали ответ. Вы выбрали экспоненциальную, а затем - уравнения, которые сами по себе не являются экспоненциальными. Если вы прочтете, вы увидите, что я сказал, что оно увеличивается экспоненциально для каждого уровня вложенности, и если вы сами это проверяете, время для (a = 0; a <n; a ++); для (b = 0; b <n б ++), для (с = 0; с <п, C ++); добавляя или удаляя циклы, вы увидите, что это действительно экспоненциально. Вы найдете, что один цикл выполняет при n ^ 1, два - при n ^ 2, а три - при n ^ 3. Вы не понимаете, вложенные: D. Гемоетрические подмножества экспоненциальные.
jgmjgm
Я думаю, это доказывает, что люди действительно борются с вложенными конструкциями.
jgmjgm