Качественият начин да се пишат програми

Записах един курс.
Системно програмиране на C за Линукс.
Принципно страхотен курс, но преподавателят понякога се…увлича.
Основен проблем на некадърните програмисти е, че програмите им са бъгави, защото не могат да вържат десет реда код смислено.
Основен проблем на кадърните програмисти е, че се опитват твърде силно да оптимизират нещата, при което често програмите им стават дори по-зле от тези на новаците.
Мисля, че успях да преодолея този проблем.


Всичко започна от…

Този код:

#define PRNT(i) { \
    l = fmt_uint(num_buf, i); \
    num_buf[l++] = '\n'; \
    buffer_put(&output, num_buf, l); }

Някой да се сеща какво прави това? Точно така, печата едно единствено число на екрана.
ЕЙ! Няма ли си в C функция, която прави точно това? И е по… как да се изразя… НеКаращаМеДаСиИзповръщамЧервата? Има, макар и да е съвсем малко по-бавна. Но според преподавателя, трябва да се оптимизира абсолютно навсякъде. На всяка цена.
Това работи, ако програмата ти е дълга общо 100 реда и цял живот ще я пишеш само и единствено ти. Естествено, никоя реална програма не е такава. Повечето са дълги десетки хиляди редове. Някои стигат до милиони. Тогава става сложно, оплетено, неразбираемо и невъзможно за работа.
Стана ми интересно. Хайде да видим колко време се спестява по този начин, а?

Задачата:

Проект Ойлер 237:
Нека T(n) е броят възможни пътища, по които може да се обиколи дъска с размери $4 * n$, като:

  • Се тръгва от горния ляв ъгъл
  • Стига се до долния ляв ъгъл
  • Всеки ход е нагоре, надолу, наляво или надясно
  • Всяко поле се посещава точно веднъж

Т(10) = 2329

p_237.gif

Колко е Т(1000000000000) по модул 1000000001?

За да илюстрирам твърденията си, ще използвам това, което всеки истински geek знае и обича. Аниме.

Нормален човек:

naruto_clown.jpg

Ъъъъ Какво?
Боли ме главата. Оххх.

Начинаещ програмист с две години опит:

naruto_shippuden.jpg

Известно още като аз в 12 клас. Това беше една задача от американската система за тренировки USACO, там ограничението беше само 10000.
О, това не е толкова трудно!

В дванадесети клас написах това на чисто C. Работеше бързо. Не беше прекалено грозно. Беше си вярно. Йей.

Сега го показвам на Питон, защото на това го написах вчера :)

По-кадърен програмист, четири години опит:

NarutoSageMode.jpg

Добре, това работеше за 10000 стъпки. Извършва $N * C$ операции, където N е броят колони, които трябва да се обходят, а C е някаква константа(по-малка от сто, ама не съм гледал точно колко). При милион операции на секунда, това влиза отвсякъде в лимита за време. Обаааче… Тук не говорим за 10000, вече не сме малки деца. Тук е 1000000000000. А да видим сега дали годините обучение са си стрували. Момент на медитация…
ДА!
Окей, цялата работа е следната:
Дефинираме си функция F, която(да кажем по горния алгоритъм) намира по колко начина може да се стигне от позиция start, до позиция finish, минавайки през N колони междувременно. Ако N < 10, примерно(или < 2, същата работа), ползваме горния алгоритъм. Иначе - не е ли F(start, end, n) просто сума на всички F(start, mid, n/2)*F(mid,end, n - n/2)?

F(start, end, n) = sum(F(start, mid, n/2)*F(mid,end, n - n/2)) за всяко възможно състояние mid.

Ами да, така е. Не се доказва прекалено трудно. Трудното е да се сетиш. Сложността на този алгоритъм е логаритмична $F = O(log N))$. В момента няма значение точно какво е логаритъм, важното е, че това забързва МНОГО. Първата програма за 1 квадрилион2 ще изпълни около един квадрилион операции. Даже мобе би около сто квадрилиона операции. Ще отнеме минимум няколко месеца да привърши успешно.
Втората?
Няма и петдесет хиляди.
Това е втора техника, наречена Разделяй и владей. От задача с размер N само за една стъпка направих две задачи с размер $\cfrac{N}{2}$. От тях четири с размер $\cfrac{N}{4}$ и така нататък. Обединявайки Разделяй и Владей с Динамично оптимиране, се получават завидни резултати. Това вече ще работи за по-малко от секунда, дори на наистина слаби компютри. Дори и да е написано наистина некадърно.

Програмист с обсесивно-компулсивно разстройство

Kyubi.jpg

Какво е очевидното в горната програма? Адски лесна е за четене(стига, разбира се, да прекарваш дните си в четене на код. Предполагам за някой зарзаватчия би била също толкова тъмна Индия, колкото и коя да е друга).
Кратка е, и кажи-речи 1:1 превежда моето обяснение с думи в програмен код.

Но има още нещо. Нещо, което досега не съм обяснил:

@memoize

Това се нарича декоратор. Това е елемент от метапрограмирането.
Това е програма, която пише програми.
Повечето програмисти не стигат до това ниво, никога.
С което не искам да се надувам. За да станеш наистина велик, в коя да е област от живота - от градинарство, до хирургия - се изисква да вложиш поне десет хиляди часа от живота си в усъвършенстване на умения. Аз съм извървял досега около половината от този път. Може да го докарам и до 7000 часа, но - серзионо - всички знаем, че през повечето време просто играх игрички, така че не се брои. Даже може по-малко от 5000 да се окажат…
Фактът, че повечето програмисти така и не стигат до метапрограмиране е защото повечето всъщност въобще не се и стараят. За много хора това е "лесна работа, в която не трябва да носиш тежки предмети, получаваш добри пари". Е, може би. Не тези хора, обаче, създават Интернет. Не е нужно да си най-най-великият въобще. Но със сигурност трябва да заспиваш върху клавиатурата, ако искаш да постигнеш нещо. Като следствие - повече от половината хора са под средното ниво. Да, знам, оксиморон. Пак е вярно :)

Та, декоратори. Там е цялата работа, че в програмирането има адски много повторение.
Ествено, че всеки път мога да го пиша наново. Но все пак.
Имаш два избора:

  1. Пишеш един и същи код до припадък. Ежедневието ти се превръща в рутина. Ставаш скучен, сух и тъп.
  2. Пишеш програми, които да вършат работата вместо теб. Играеш на канадска борба с мечки. Жените те замерят с бикините си.

Та, този декоратор, @memoize(Мемоизация е още едно име за Динамично оптимиране. Р-то се изпуска нарочно) върши цялата работа вместо мен. През живота си съм решил стотици такива задачи. И всичките са точно едни и същи.

Ако нещо си го изчислявал преди, не го изчислявай пак.
Просто запомни някъде сметнатата стойност и направо връщай нея.

Това е всичко. Това е правилото. Има ли смисъл да го пиша двеста пъти отначало?
Не, няма. Затова, измежду дъвчейки стомана и ловко избягвайки бикини на път към ФМИ, си написах следното нещо:

def memoize(fun):
    '''
    Мемоизира функция.
    Този декоратор собственоръчно решава 1/3 от всички състезателни задачи въобще.
    '''
    memoized = {}
    def memo(*args, **kwargs):
        key = "%s %s" % (args, kwargs)
        if not memoized.has_key(key):
            memoized[key] = fun(*args, **kwargs)
        return memoized[key]
    return memo

Резултатът е по-горе. Без тази функция както първата, така и втората програми щяха да работят за по няколко хилядолетия. С нея, става за няколко секунди.

Нещо повече

С тази функция, тези има-няма десет реда се решават ВСИЧКИ подобни задачи.
От кеширане на уеб-страница, през запомняне на последните заявки в база от данни, през кеширане в програма за гледане на картинки, през сравнение на два документа и проверка за грешки в офис програма - всичко.
Ето това е разликата между човек, който учи за програмист и човек, който просто удря по клавиатурата.

Естествено, за специфични ситуации може да се наложи промяна на това-онова. Горният код може още да бъде оптимизиран. Което ме води до:

Програмистът, за който мама те предупреди като беше малка

kyubi-6.png

Ето тук вече идва моментът за оптимизация. Чак тук можем да използваме ученията на преподавателя по Системно Програмиране.

Code Profiler

Ако си като мен, това е нещо, което ще промени начина по който мислиш за писането на код.
Code Profiler е програма, която ти казва точно къде и с колко се бави програмата ти.
Съществува такъв инструмент за кажи-речи всеки език, създаден от хората.
Ето как е реализиран на Python:

#!/usr/bin/python
# -*- coding:UTF-8 -*-
import cProfile
import sys
'''
Програмата профилира даден модул.
В контекста на тази папка, програмата профилира задачи :)
'''
cProfile.run('import %s' % sys.argv[1])

Внимание: Това е най-важната част от статията.

Извиквам го с:

profiler.py p237

И връща:

         120253 function calls (44411 primitive calls) in 0.272 CPU seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.272    0.272 <string>:1(<module>)
        1    0.000    0.000    0.272    0.272 p237.py:3(<module>)
   3241/1    0.007    0.000    0.271    0.271 p237.py:43(p237)
      161    0.000    0.000    0.001    0.000 p237.py:57(<genexpr>)
  25200/8    0.058    0.000    0.271    0.034 p237.py:58(<genexpr>)
        1    0.000    0.000    0.000    0.000 utils.py:170(memoize)
  44213/1    0.177    0.000    0.271    0.271 utils.py:176(memo)
        1    0.000    0.000    0.000    0.000 utils.py:2(<module>)
        1    0.000    0.000    0.000    0.000 utils.py:91(Fraction)
       16    0.000    0.000    0.000    0.000 {method 'append' of 'list' objects}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
    44213    0.017    0.000    0.017    0.000 {method 'has_key' of 'dict' objects}
        2    0.000    0.000    0.000    0.000 {method 'keys' of 'dict' objects}
   3199/1    0.012    0.000    0.271    0.271 {sum}
        2    0.000    0.000    0.000    0.000 {time.time}

ncalls е колко пъти е извикана някоя функция.
tottime е колко време общо е работила функцията.
Другите не ни интересуват сега.
Какво е най-важното тук?
Програмата работи за 0.3 секунди. Не е зле.

         120253 function calls (44411 primitive calls) in 0.272 CPU seconds
   3241/1    0.007    0.000    0.271    0.271 p237.py:43(p237)
  25200/8    0.058    0.000    0.271    0.034 p237.py:58(<genexpr>)
  44213/1    0.177    0.000    0.271    0.271 utils.py:176(memo)
    44213    0.017    0.000    0.017    0.000 {method 'has_key' of 'dict' objects}
   3199/1    0.012    0.000    0.271    0.271 {sum}

Ето това са най-бавните места. Вижда се, че memo(от декоратора @memoize) е десет пъти по-бавна от останалата част на програмата. Тоест, ако ще да оптимизираме всичко друго до край, няма да се получи по-голямо подобрение от 10%. Окей, не е чак десет пъти. Но със сигурност е от по-висок порядък.

Нещо повече, функцията за печатане на числа - print?
Нея въобще я няма.
Преподавателят ми си губи времето, защото колкото и да подобрява точно кода за печатане на число, програмата му няма да се забърза с повече от една десетохилядна от секундата.

Аз обаче… Аз ще оптимизирам там, където има значение. В bottleneck-а. Всеки истински майстор трябва да се старае да прави точно това. Иначе си губи времето.
За следващата част се изискват по-задълбочени познания на езика:

def memoize(fun):
    '''
    Мемоизира функция.
    Този декоратор собственоръчно решава 1/3 от всички състезателни задачи въобще.
    '''
    memoized = {}
    def memo(*args, **kwargs):
        if not kwargs:
            key = args
        else:
            key = (args,str(kwargs))
        if not memoized.has_key(key):
            memoized[key] = fun(*args, **kwargs)
        return memoized[key]
    return memo

Разликата е съвсем минимална. Кодът продължава да е четим. Но нека да проверим(в съкратен вариант):
         120253 function calls (44411 primitive calls) in 0.140 CPU seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
  25200/8    0.048    0.000    0.138    0.017 p237.py:58(<genexpr>)
  44213/1    0.057    0.000    0.138    0.138 utils.py:176(memo)
    44213    0.015    0.000    0.015    0.000 {method 'has_key' of 'dict' objects}
   3199/1    0.011    0.000    0.138    0.138 {sum}

А? А? Бавната част се забърза тройно, а цялата програма - двойно. Съвсем малко по-добре от една десетохилядна от секундата, мисля аз?

Гуру

Kyubi-9.jpg

Има ниво, което още не съм достигнал.
Казват, че който го достигне, губи интерес от живота, защото вече няма какво да научи в него. Е, предполагам че такива хора прекарват дните си скачайки от разни високи места, вместо забили нос в някой учебник. Аз това бих правил във всеки случай. Но чак след като стигна дотам. Ако се откажеш преди това, ти си просто поредният провален загубеняк и няма да заслужаваш почивката си. Но не е важно да победиш, де - важно е участието, нали? Ахам, да бе.
Та, най-високото ниво е:
Да напишеш всички горни неща. Но така, че да работят не за Python. Питон ти дава твърде много улеснения. Не, трябва да го направиш на C. На Асемблер, на Лисп. Трябва да работи не за 0.1 секунди, а за 0.01 секунди. Чак тогава ще бъде наистина значимо постижение, чак тогава всички ще могат да се ползват от работата ти.
Някой ден.

Ето така, според мен, трябва да се пишат програми.

Точно в този ред, точно по този план:

  1. Обмисли проблема
  2. Пробвай с най-тъпото нещо, което работи. Ако те устройва(не е прекалено бавно, не харчи твърде много памет), остави го така. Ако ли не - продължавай.
  3. Измисли качествен алгоритъм.
  4. Оптимизирай логиката на аглоритъма.
  5. Използвай оптимизационни техники(например кеширане/разделяй и владей).
  6. Профилирай кода си, потърси места, които са бавни.
  7. Пренапиши ги така, че да са по-бързи.
  8. Ако въобще е възможно, напиши ги на по-бърз език и просто викай готовите функции в твоя. Тоест, не пренаписвай всичко на Асемблер - само частта, която е много бавна.

По-голямата част от времето на великите програмисти е прекарана в опити да се озаптят. Да не прекаляват с голямата сила, която притежават.
Линукс е свободна операционна система. Целият интернет се крепи на Линукс. По моя преценка, по-малко от десет процента от всички сървъри са на каквато и да е друга система. Линукс се базира на Юникс. Ето философията на Юникс:

Правило 1: Не можеш предварително да кажеш къде програмата ти ще се бави най-много. Забавянията се появяват на изненадващи места, така че не пипай нищо преди да си профилирал програмата и да си сигурен какво трябва да се направи.

Правило 2: Измервай: Не оптимизирай за скорост докато не си измерил. Дори тогава не го прави, освен ако някоя част от програмата не е в пъти по-бавна от останалите.

Правило 3: Сложните алгоритми са бавни, когато N е малко. N почти винаги е малко. Сложните алгоритми имат големи константи. Докато не си сигурен, че N често ще бъде голямо, не използвай сложни алгоритми(Дори и N да стане голямо, първо приложи Правило 2).

Правило 4: Сложните алгоритми имат повече бъгове от простите, а и са много по-трудни за написване. Използвай прости алгоритми, както и прости структури от данни.

Правило 5: Данните доминират. Ако си избрал правилната стурктура от данни и си организирал нещата правилно, алгоритмите почти винаги ще са очевидни. Структурите от данни, а не алгоритмите, са централни за програмирането.

Правило 6: Няма правило 6.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License