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

Вопрос был про задачу «симметричная ли матрица?»: надо проверить, симметрична ли заданная квадратная матрица. В ней есть достаточно простое решение примерно следующего вида:

z = True
for i in range(n):
    for j in range(i+1, n):
        if a[i][j] != a[j][i]:
            z = False
if z:
    print('yes')
else:
    print('no')

В том числе, именно решения такого вида приведены в разделе «хорошие решения» на алгопроге.

Тем не менее, может возникнуть идея написать такой код:

ans = True
for i in range(n):
    for j in range(i+1, n):
        if a[i][j] != a[j][i]:
            ans = False
            break
    if not ans:
        break
if ans:
    print('yes')
else:
    print('no')

Действительно, зачем дальше итерироваться, если мы уже нашли несимметричность в матрице?

И такие решения я засчитываю, причем засчитываю без каких-либо замечаний-комментариев, но в «хороших решениях» таких решений нет.

Дело в следующем. Эти дополнительные break’и не влияют на сложность алгоритма, и даже не влияет на время работы в худшем случае (точнее, в худшем случае время работы даже самую малость увеличивается: худший случай тут — симметричная матрица, надо все равно все циклы прогнать до конца, но лишняя проверка чуть-чуть, но увеличит время работы). При этом они немного усложняют код (хотя, конечно, не особо сильно).

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

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

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

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

Надо еще отметить вот что. В реальной жизни у вас будет не целая программа, как тут, а скорее всего функция, принимающая в качестве параметра матрицу, и возвращающая bool. Тогда вы внутри функции в if’е просто сразу напишете return False, и это будет эквивалентно двум break’ам, но без всяких плясок с break. То есть необходимость этого лишнего if’а с break обусловлена чисто спецификой данной задачи (что вы не выделяете функцию проверки матрицы на симметричность), в реальной жизни вы такой код все равно писать не будете.

В общем, да, я понимаю логику написания такого if’а, но на мой взгляд это очень незначительное улучшение программы, и не факт, что оно оправдывает усложнение программы из-за лишнего if с break. Усложнение, конечно, незначительное, но и улучшение тоже незначительное. И в конце концов, это все-таки уровень 1Б, большинство людей, решающих эти задачи, только-только освоили if’ы и циклы, и для них дополнительный if реально может быть усложнением.

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

Для сравнения, в этой задаче есть еще одна оптимизация — внутренний цикл можно начинать от i+1, а не от 0 (как и написано выше). Вот эта оптимизация реально ускоряет программу в два раза даже в худшем случае, плюс она намного проще, чем дополнительный if, ну и даже в реальном коде она будет полезна. Ну и такие решения есть и в «хороших решениях».

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

Для примера — в соседней задаче «Состязания-2» на время работы очень сильно влияет то, в каком порядке вы будете перебирать элементы, по строкам или по столбцам, т.е. напишете вы for i in range(n): for j in range(m):, или наоборот — for j in range(m): for i in range(n): (при условии, что i у вас номер строки — номер спортсмена, а j — номер стобца — номер попытки). Программа в обоих случаях будет корректной, но во втором случае вы будете работать с элементами массива не в том порядке, в котором они лежат в памяти, и потому процессорный кеш будет неэффективен и программа сильно замедлится. Не знаю, можно ли этот эффект наблюдать на питоне, но на C++ при больших размерах это точно будет заметно. Но эти особенности тоже за пределами моего курса.

Мой курс по алгоритмическому программированию (и подготовке к олимпиадам) для школьников, студентов и всех желающих — algoprog.ru