Про алгоритмический сахар, или почему я требую писать все вручную
На алгопроге на начальных уровнях есть ряд задач, которые легко решаются стандартными функциями из стандартной библиотеки почти любого языка программирования — например, Максимум в массиве или Перевести символ в верхний регистр. Тем не менее, я всегда в этих задачах требую от учеников реализовать нужные действия вручную — в первом случае через цикл по массиву, во втором — работой с кодами символов. Недавно я доформализовал ответ на вопрос, почему я это требую.
Когда мы говорим, например, про массивы, есть очень небольшое количество простейших стандартных операций для работы с ними — это в первую очередь создание нового массива и доступ к элементу массива по индексу; если мы говорим про динамические массивы (а в современных языках программирования в первую очередь про них и имеет смысл говорить), то еще получение длины массива, добавление элемента в конец массива и удаление последнего элемента. И, пожалуй, все.
Этих операций мало, они простые и понятные, но уже с их помощью с массивом можно делать что угодно.
При этом, вдобавок к ним, современные языки программирования обычно предоставляют ряд более
удобных операций — то же вычисление максимума в массиве, или например переворот массива,
или питоновские срезы. Эти операции кажутся удобными, и кажется зачем уметь вычислять максимум
через обход массива, если можно просто написать max(a)?
Но проблема в том, что какие бы удобные операции не предоставлял бы вам язык программирования,
найдется момент, когда выразить нужные вам действия через них станет сложно.
Найти максимум в массиве? Да, max(a). Найти номер такого элемента? Ну ок, a.index(max(a)).
(Но вы уже бегаете по массива два раза.)
А если вам нужны все такие индексы? Это уже несколько сложнее. Можно,
конечно, что-нибудь придумать с там filter или map, но уже как-то мутновато получается.
А если массив у вас двумерный? Если вы попробуете
решить задачу с двумерным массивом с помощью таких «удобных» функций, а не просто проходом
по массиву вручную, то скорее всего решение у вас получится уже сложнее.
В итоге вы или в принципе не сможете решить сложные задачи с помощью «удобных» операций, или решение получится чересчур сложным и непонятным.
Вторая тут проблема в том, что далеко не каждый язык предоставляет такие удобные функции. В некоторых языках подобных функций вообще нет (привет Free Pascal’ю), в некоторых есть, но использование их настолько неудобно и чревато ошибками, что проще написать вручную (привет C++). Базовые же функции — доступ к элементу по индексу в первую очередь — вам предоставляет любой язык, который вообще имеет понятие массивов.
Третья проблема в том, что эти удобные функции могут дать вам ложное ощущение всесилия, ощущение эдакой «серебряной пули», которая позволяет решить все проблемы. Вы можете думать: у меня не получается решить эту задачу — может быть, это потому, что я не знаю каких-нибудь удобных функций? Может надо применить срезы, или что-то еще продвинутое? Но ничего подобного: эти удобные функции вам не дают абсолютно ничего нового. У них есть свои преимущества — их быстрее писать, код получается понятнее, в их терминах иногда удобнее думать, — но они нисколько не расширяют ваши возможности в плане того, какие задачи в принципе можно решить.
И наоборот, использование удобных функций может дать вам ложное ощущение крутости. Вам может казаться, что в любом решении их надо использовать, и что если вы написали решение, напихав туда много вызовов таких функций, то это будет лучшее и крутейшее решение. Но очень часто оказывается, что это совсем не так. Очень часто оказывается, что решение, написанное вручную через циклы и другие базовые конструкции, понятнее, проще, а зачастую еще и намного быстрее.
Вот поэтому я считаю, что в первую очередь стоит учиться писать все нужные алгоритмы только с использованием элементарных операций. Впоследствии вы узнаете все дополнительные функции, сможете с ними писать ваши программы намного проще, но — и это очень важно — вы будете понимать, что в любой сложной ситуации у вас всегда остается гарантированно работающее решение — закатать рукава и написать код через простейшие операции. Вот это понимание, что у вас всегда есть запасной вариант, что вы всегда можете сами закатать рукава и сделать всю нужную работу вручную — это, на мой взгляд, одно из важнейших умений программиста.
…При этом на тот же вопрос — зачем надо уметь писать максимум вручную — довольно популярен немного другой ответ: прежде чем использовать стандартную функцию максимума, надо понять, как она работает.
Но на мой взгляд, такое объяснение весьма спорно,
потому что задать вопрос «как оно работает» можно про любой код вообще, и не только про код.
Вы написали код через max? А как оно работает? Вы написали код через цикл с
доступом к каждому элементу массива? А как оно работает? Грубо говоря, понимаете ли вы,
как это работает на ассемблерном уровне? Про ассемблер, конечно, вопрос тот же — а понимаете ли вы,
как он работает? Знаете ли вы, как устроен процессор, какие там логические элементы,
почему этот ассемблерный код работает именно так, как вы думаете? А как работают логические
элементы? А как работает транзистор и p-n переход? А как по транзистору распределена
волновая функция электрона? И так далее, вопросы можно задавать до бесконечности.
Конечно, профессиональному программисту безусловно нужно иметь некоторые знания вглубь.
Конечно, надо понимать, что массив в памяти хранится подряд, и что адрес i-го элемента
массива можно легко вычислить. Безусловно, полезно иметь общее представления об ассемблере
и том, как работает процессор. Но для начального обучения ничего этого, на мой взгляд,
совершенно не нужно.
Что надо — это иметь конкретный набор инструментов, гарантированно позволяющий решить любую задачу, которая у вас может появиться. Так вот, чтобы написать любой алгоритм, использующий массивы, вполне достаточно указанных выше элементарных операций на массивах. Это вообще весьма похоже на понятие тьюринг-полноты: тьюринг-полный язык программирования — это язык, на котором можно реализовать абсолютно любой алгоритм (в том смысле, который в эту фразу вкладывает наука). Аналогично можно говорить про тьюринг-полный набор операций и т.д. То, про что я пишу тут, это не совсем тьюринг-полнота, но идеи весьма близкие.
С другой стороны, если мы попробуем обходиться только высокоуровневыми операциями с массивами, то далеко не каждый алгоритм получится реализовать, или по крайней мере получится заметно сложнее. И это и есть то, про что я писал выше. Смысл не в том, что «надо понимать, как это устроено», а в том, что надо знать и понимать именно те операции, с помощью которых вы сделаете всё, что захотите, надо знать набор операций, который в каком-то смысле является тьюринг-полным.
(Это все, конечно, про элементарные операции, а не про серьезные алгоритмы. Когда мы говорим про серьезные алгоритмы — сортировку, например, или там какие-нибудь сбалансированные деревья поиска — там понимание «почему это работает» становится очень важным, а про а-ля-тьюринг-полноту говорить уже не приходится.)
Есть такое понятие — синтаксический сахар.
Это дополнения в синтаксис языка, служащие чисто для упрощения написания кода программы,
не привносящие никакого нового смысла в программу. Типичный пример — отрицательные индексы
массивов в питоне. Запись a[-2] во всех смыслах (ну не совсем, на самом деле)
эквивалентна записи a[len(a)-2]
— смысл тот же, работать будет так же. Это никакая не оптимизация, никакой не новый
способ доступа к элементам массива, это придумано чисто для того, чтобы код программы был проще.
Аналогично C++-шный range-based-for (for (const auto& x: container)) — это просто
сокращение для более традиционного цикла с итераторами и begin/end.
(Правда, вот в википедии и в других местах как пример синтаксического сахара приводят
конструкцию a[i] в языке C, как замену записи *(a+i). Мне это кажется плохим примером, т.к. запись a[i]
— это не просто арифметика указателей, а введение целой новой концепции — массива.
А то можно дойти до того, что циклы и if‘ы объявить синтаксическим сахаром, т.к. есть goto.)
Синтаксический сахар упрощает написание программ, но одним сахаром вы не обойдетесь, иногда придется все-таки применять не-сахарные конструкции; сахар имеет, конечно, ряд проблем, очень сходных с теми, про которые я писал выше. Поэтому, конечно, хорошо, если вы знаете и умеете использовать синтаксический сахар, но все-таки он вторичен и в первую очередь надо знать и уметь использовать основные конструкции.
Соответственно, на мой взгяд также имеет смысл говорить про алгоритмический сахар —
это стандартные функции, которые упрощают выполнение часто встречающихся операций.
Ту же функцию max для массива, или, возвращаясь к примерам в начале текста,
функцию str.upper() вряд ли кто назовет синтаксическим сахаром, но и то и другое
— ярко выраженный алгоритмический сахар.
И да, я не везде, конечно, запрещаю использовать такой алгоритмический сахар. Когда ученики уже освоились с базовыми операциями, я только рад, когда они используют продвинутые функции — если такое использование, конечно, к месту.
И да, конечно, тут надо много оговорок — в реальной жизни всё вообще сложнее и уж точно не такое черно-белое, как, может быть, кажется по тексту выше; всегда есть и промежуточные конструкции, которые то ли алгоритмический сахар, а то ли базовые операции. И, конечно, эти самые «базовые операции» можно выбирать по-разному, и т.д.
Мой курс по алгоритмическому программированию (и подготовке к олимпиадам) для школьников, студентов и всех желающих — algoprog.ru