Ода лени

Хакер дает советы, раскрывает секреты и делится своими мыслями по поводу программирования.

Модератор: Хакер

Хакер
Телепат
Телепат
Аватара пользователя
 
Сообщения: 16473
Зарегистрирован: 13.11.2005 (Вс) 2:43
Откуда: Казахстан, Петропавловск

Ода лени

Сообщение Хакер » 31.03.2010 (Ср) 2:45

Есть два утверждения:
  • Плохие, постоянно виснущие программы создаются программистами благодаря лени.
  • Хорошие, быстро работающие программы создаются программистами благодаря лени.
Они оба верны.

— Почему так, и в чём разница?
— Всё просто. Разница в том, на что программисты распространяют лень.

У первых лень распространяется на самих себя — программистам лень делать лишние (по их мнению) действия. Как результат: плохие, постоянно виснущие программы. У вторых лень распространяется на их программу — она не делает лишних действий и, как результат, работает быстро, не зависает.

Вот и всё разница.

— Что имеется в виду под «ленивой программой», «ленивым кодом»?
— Имеется в виду код, следующий старым как мир принципам «Бритва Оккама», KISS и не выполняющий любых лишних действий для решения задачи, если задачу можно решить без их выполнения.

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

(И если вы не имеете представления о классах сложности и букве «О», советую вам его сформировать)

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

вычисление Математическая формула: \sum_{i=1}^n i!

  • Ленивый программист беспокоится о количестве мыслей, которые его голове предстоит обдумать. Поэтому он не будет думать о количестве действий, которые его программе предстоит совершить, и будет решать задачу «в лоб»: напишет функцию, считающую факториал от аргумента, и функцию, считающую сумму элементов последовательности. В итоге (с учётом свёртки двух функций в одну) он получит следующее:
    Код: Выделить всё
    For i = 1 To n
        fac = 1
        For j = 1 To i
            fac = fac * j     
        Next j
        sum = sum + fac
    Next i

    Ленивого программиста не волнует, что 20-ой итерации придётся заново перемножить 20 чисел, результат перемножения 19-и из которых уже был получен одну итерацию назад, и что он ровно в 20 раз меньше, чем результат перемножения текущих двадцати. Его не волнует, что вместо совершения бессмысленных умножений, уже ранее неоднократно проводившихся, достаточно умножить последнее произведение на 20. Его волнует другое: «Как бы сделать задание, затратив меньше своего времени и своих сил» (как будто они кроме него самого кого-то интересуют...).
  • Не ленивый программист не пожаелет времени (1,5 секунды), чтобы проанализировать процесс и понять, что Математическая формула: n! в Математическая формула: n раз больше, чем Математическая формула: (n-1)!.
    В его коде не будет двойного цикла и лишних умножений:
    Код: Выделить всё
    sum = 1
    fac = 1
    For i = 2 To n
        fac = fac * i
        sum = sum + fac
    Next i

  • Думающий программист не остановится и увидит в вышеобозначенном свойстве следующее: множитель Математическая формула: i присутствует во всех слагаемых начиная с i-того. Это означает, что для для каждого Математическая формула: i \in \[1; n] можно взять Математическая формула: n - i + 1 слагаемых справа, заключить их в скобки и вынести множитель Математическая формула: i за скобки. Каждая такая группировка с выносом будет давать выражение Математическая формула: i(1 + (i+1)(1 + ...)). При этом, так как в слагаемом каждый каждый множитель присутствует лишь один раз, а выносу подверглись все множители со значением от 1 до n, от n-го слагаемого после выноса всех сомножителей останется лишь единица.
    Для примера, при Математическая формула: n = 4:
    Математическая формула: \sum_{i=1}^4 i!= 1 + 1 \cdot 2 + 1 \cdot 2 \cdot 3 + 1 \cdot 2 \cdot 3 \cdot 4 = 1(1 + 2(1 +  3(1 + 4(1))))
    Можно для наглядности привести это выражений в RPN:
    Код: Выделить всё
    [0] 1 + 4 * 1 + 3 * 1 + 2 * 1 + 1 *

    Отсюда хорошо видно, что для вычисления этого выражения стековой машине потребуется лишь один дополнительный фрейм стека. Это видно из того, что операторы и операнды строго чередуются. Фактически, это означает, что для вычисления данного выражения, хоть оно и имеет Математическая формула: n-1 вложенных неатомарных подвыражений, нам хватит цикла с одной переменной, кроме переменной самого цикла. Ленивый, если и дойдёт до этого места, поленится подумать, и будет вычислять выражение рекурсией...

    Таким образом, у думающего программиста код будет такой же, как и у не ленящегося, но без одной лишней переменной:
    Код: Выделить всё
    sum = 1
    For i = n To 2 Step -1
        sum = sum * i + 1
    Next i


    А сишники смогут поразить вас ещё и компактностью: for(sum = 1, i = n; i > 1; (sum *= i--)++);
    Полученный вариант является тем самым минимумом: в нём выполняется минимально возможное число операций и используется минимальное число переменных. Дальше оптимизировать упрощать уже некуда выкидывать лишний хлам невозможно, потому что его не осталось.

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

Мораль: лень очень важна в создании качественного ПО. Главное, чтобы она поселилась в логике работы ПО, а не в логике его создателя.

P.S. Настоящие мастера практически никогда не занимаются оптимизацией своего кода: они просто не задумываясь пишут изначально оптимальный код.

Уточнение
Описанные примеры и рекоммендации не актуальны для языков, которые «исповедуют» функциональную (а не императивную) парадигму. Там даже такое явление, как ленивые вычисления имеется, поэтому думать о том, не выполняются ли лишние действия программисту не нужно, так же как и думать, какие вообще действия выполняются — специфика парадигмы.
—We separate their smiling faces from the rest of their body, Captain.
—That's right! We decapitate them.

FaKk2
El rebelde gurú
El rebelde gurú
Аватара пользователя
 
Сообщения: 2031
Зарегистрирован: 09.03.2003 (Вс) 22:10
Откуда: Los Angeles

Re: Ода лени

Сообщение FaKk2 » 31.03.2010 (Ср) 3:26

И что, часто приходиться, сумму факториалов считать?

Нет, это я в шутку конечно-же. Мысль изложена верно, только... я бы сказал что в больших проектах быстродействие зачастую упирается в архитектуру, а её так, за полторы секунды не поменяешь.
Для получения ответа надо продемонстрировать качества, позволяющие стать компетентным — внимательность, вдумчивость, наблюдательность, желание активно участвовать в выработке решения.

Хакер
Телепат
Телепат
Аватара пользователя
 
Сообщения: 16473
Зарегистрирован: 13.11.2005 (Вс) 2:43
Откуда: Казахстан, Петропавловск

Re: Ода лени

Сообщение Хакер » 31.03.2010 (Ср) 3:31

Кстати, в тему не лишним будет процитировать сообщения из одного легендарного топика:


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

Я сел и неделю писал прогу на VB с разными наворотами вроде возможности приостановки вычисления (типа Hibernate) и последующего продолжения; упаковки восьми булевских переменных в один байт; всяческой оптимизацией и т.п.
За 20 часов (три ночи) эта прога сосчитала мне значения до 250.

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

Я пошёл к преподу выяснять, как быть - получается, уже для 1000 потребуется месяц вычислений, а то и больше. И он мне показал свою прогу на JS для решения этой же задачи. Мои результаты до 250 она получает за несколько минут, за 20 часов - примерно до 400, а за пару суток - до 600. Естественно, у него там более хитроумный алгоритм, выгода от которого в тысячи раз превышает разницу в быстродействии языков.
—We separate their smiling faces from the rest of their body, Captain.
—That's right! We decapitate them.

Денис
Доктор VB наук
Доктор VB наук
Аватара пользователя
 
Сообщения: 2734
Зарегистрирован: 07.11.2006 (Вт) 13:55
Откуда: Ейск, Краснодарский край

Re: Ода лени

Сообщение Денис » 31.03.2010 (Ср) 8:36

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

FaKk2
El rebelde gurú
El rebelde gurú
Аватара пользователя
 
Сообщения: 2031
Зарегистрирован: 09.03.2003 (Вс) 22:10
Откуда: Los Angeles

Re: Ода лени

Сообщение FaKk2 » 31.03.2010 (Ср) 8:48

Денис писал(а):Программисты старой школы еще помнят, что главное, это алгоритм, а не архитектура.


Гы, ну-ну.
Для получения ответа надо продемонстрировать качества, позволяющие стать компетентным — внимательность, вдумчивость, наблюдательность, желание активно участвовать в выработке решения.

Debugger
Продвинутый гуру
Продвинутый гуру
Аватара пользователя
 
Сообщения: 1667
Зарегистрирован: 17.06.2006 (Сб) 15:11

Re: Ода лени

Сообщение Debugger » 31.03.2010 (Ср) 8:59

Хочу быть думающим программистом!

Хакер
Телепат
Телепат
Аватара пользователя
 
Сообщения: 16473
Зарегистрирован: 13.11.2005 (Вс) 2:43
Откуда: Казахстан, Петропавловск

Re: Ода лени

Сообщение Хакер » 01.04.2010 (Чт) 16:44

Fakk2 накаркал: конкретно сейчас пришлось считать сумму факториалов от 1 до n.
—We separate their smiling faces from the rest of their body, Captain.
—That's right! We decapitate them.


Вернуться в МануAll

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 2

    TopList  
cron