Книги: Золотой билет. P, NP и границы возможного

Золотой билет. P, NP и границы возможного
Лэнс Фортноу.
Золотой билет. P, NP и границы возможного.
Лаборатория знаний, 2016.
Популярная изложением книга на тему проблемы перебора (она же P=NP). Сначала автор написал статью и выпустил в ACM, оказалось настолько круто, что из статьи выросла книга в 200+ страниц с множеством картинок, от чего стало ещё лучше.
Нафига вам это читать? Чтобы знать текущий порог эффективности решения алгоритмических задач на уровне человеческой цивилизации, ну и не ляпнуть заказчику “я сделаю это за два дня”, не распознав NP-полную задачу, которая считаться будет миллиард лет.
Написано очень просто, очень доступно и без единой формулы. Можно давать скучающим школьникам на каникулы. Также годится забывшим основы программистам для беглого чтения в метро.
PS. Не, ну я уверен, что чувака, который действительно решит NP-полную, либо в подвалы законопатят, либо удавят. Но мир он разрушит точно.

Когда проект считать большим

Все попытки выразить “большевизну” проекта через абсолютные пороги считаю уязвимым в реальном мире. Предлагаю другую систему отсчёта.
Большим проект становится тогда, когда перестаёт быть контролируемым. Вот и всё. Такое бывает с первой же строки кода, бывает через год, бывает через десять.

Признаки потери контроля следующие…
Во-первых, уже нет человека, который знает о проекте всё. Экспертиза расползается по множеству людей. Чревато потерей экспертизы, т.к. Ваня знает про модуль X, часть знаний передал Пете, потом уволился, Петю бросили на модуль Y, Игорь срочно фиксил модуль X безо всяких знаний о нём и т.д.
Во-вторых, уже есть участки, на которые отсутствует документация и/или тесты. Фактически это означает отсутствие хоть сколь актуальной спецификации. Впрочем, если говорить строго, то отставание спецификации от актуальности является тем же отсутствием.
В-третьих, уже есть участки, поведение которых вы не можете предсказать [без дополнительной проверки] при изменении других участков. Вот это довольно тонкий момент, частью следующий из первых двух. О нём отдельно ниже.
Это три кита потери контроля. Нет экспертизы. Нет спецификации. Нет детальной картины системы.

Подтема этого эссе — Python на больших проектах в production’е. В текущий рабочий период могу плотно наблюдать Python на сервисе в 100K+ LoC. И могу с достаточной [для меня] степенью достоверности оценивать стоимость обеспечения хоть какого SLA такого сервиса. Так вот, если у вас нет батальона разработчиков и целой жизни на каждую задачу, не делайте современные большие сервисы на чём-либо, что не C++ или Java.
Да, вы можете взять другой язык. Но обязательно наступите на грабли разного рода — от поиска специалистов на рынке труда (сейчас даже на одного толкового питониста по три толковых джависта, что уж говорить про Go / Rust / Swift) до выстрела в рантайме на пустом месте в рандомное время (которое стопудово будет новогодней ночью, например, по закону подлости).
Да, вероятно, у вас даже получится что-то годное сделать и жить с ним (Facebook и PHP тому примером). Вероятность, правда, 1:100, а задачи могут превратиться в “как сделать интерпретатор лучше” (и снова Facebook), при этом пацаны на C++ и Java со многими вашими проблемами даже не столкнутся.
Но лучше не бросать мины по ходу движения.

Так вот, языки типа Python / JavaScript способствуют потере контроля.
Вы меняете строчку кода. Собираете пакет. Катите. Взрыв через неделю. Почему? Потому, что у вас 100K+ LoC, не каждая строка покрыта тестами (напомню, нет батальона разработчиков), а синтаксически всё норм.
При загрузке модуля интерпретатор и не вякнет о том, что дёргается функция с несуществующей сигнатурой. Не вякнет о том, что в рантайме у объекта трогается отсутствующий member. Уж тем более не в силах вякать в ситуациях, когда активно используется reflection и около него. Вообще потрясающе редко вякает, надо сказать. Что можно понять, т.к. в том же рантайме этот member может появиться. Или измениться. Или морфировать в нужный тип. Вообще всё произойти может.
Потому отхватить эффект бабочки в любой момент проще простого. И таким макаром вы теряете предсказуемость проекта довольно быстро. Если нужен абсолютный психологический барьер, то пусть 100K LoC.
А прохладные советы быть внимательнее, на всё писать тесты и вообще писать правильно я как слышал, так и сам выдавать могу (и даю, кстати). Дайте мне десять senior разработчиков, год кропотливого написания кода и полноту власти устроить фашизм, сделаю сервис и процесс тютелькой в абзацы учебников. А если ещё и бюджет дополнительный дадут на закупку и доработку нужного инфраструктурного софта, так вообще. Только вот реальный мир выглядит ни фига не так.

Сюда же можно добавить потерю самодокументируемости кода. Хоть кол мне на голове разбейте, но никакой самодокументируемости у Python / JavaScript нет. Чтобы она появилась, надо писать на малом подмножестве, которое не использует всякую весёлую динамику, но тогда смысл был выбирать не C++ / Java? А если использовать, то фиг вы всегда угадаете, откуда и с какими параметрами вызывается та или иная функция. Ладно я с розовыми глазами по ночам, но у меня IDE цепочки вызовов раскрутить не могут иногда, потому приходится занятно извращаться, выясняя, откуда и какой вызов прилетает (как и линтеры, кстати, часто ошибаются, потому тоже фиг надежды на).
И если в тяжёлых случаях с C++ / Java вам поможет глубокое качественное и количественное знание языка (чтобы разобрать особо мудрёные небоскрёбы generics hell, например), то в Python / JavaScript не поможет.

Уф. Чё в итоге из этого сумбура, набитого на перекурах? Язык здорово влияет на субъективный размер проекта. Выбрал Java? Получи “большой проект” после 300K LoC. Выбрал Python? Получи после 100K LoC. JavaScript? Пусть 50K LoC.
Считаете иначе? Ну… Беглый тест: берёте Django (Python), берёте Spring (Java). Подгружаете в нормальную IDE (PyCharm и IDEA, соответственно). Ну и начинаете изучать код. Ходить туда-сюда, строить схемы, прикидывать кейсы. Если и после этого вам покажется, что разницы нет, эссе писалось не для вас.

Miscellanea III

Видят пользователи список. В списке значения. Имена. Или числа какие. Или картинки. И частенько пользователи гадают, как оно отсортировано. Теории сортировки. Может, по цвету? Или по первой букве? Только разработчик знает, что сортировки явной там нет. Есть неявная — какой-нибудь default базы, из которой выгребают. А она может сортировать по primary key. Или использовать какой-нибудь служебный порядок типа natural в MongoDB. Почему? Да потому. Страшная тайна “сортировок” этой планеты.

Уверен, следующий кардинально новый рывок разработки — софт не для людей, но для животных. И не залипухи с рыбками для котов, но полноценные системы. Шлем VR хомяку с богатым внутренним миром. Экзоскелеты для мопсов, чтобы ротвейлеров кошмарили. Управляемые настроением кормилки и поилки для коров. Всё такое. Возможно, животные начнут эволюционировать, развиваясь от использования интерфейсов, тут-то и наступит эра зоокиберпанка.

Не стесняйтесь устраивать своим сервисам нагрузочное тестирование. Даже если штатно собираетесь жить под 10 RPS, влепите 1K RPS и посмотрите, как себя ведёт потребление ресурсов, как и куда деградирует приложение, ловите баги, которые стреляют на 100500-м запросе. Скучно, банально, но важно.

Абзац итальянской кухни: помимо Spaghetti code (лапшевидный код с огромным количеством ветвлений) есть ещё Ravioli code и Lasagna code. Равиоли — исходник состоит из множества маленьких атомарных кусочков, апофеоз декомпозиции с инкапсуляцией, от чего ориентироваться в этом блюде сложно, да и мелкой копипасты хватает. Лазанья — исходник состоит из слоёв (layers), общающихся друг с другом строго через строго определённые строгие интерфейсы, в чём по сути нет ничего плохого, но при упоротой реализации приводит к тому, что в рамках сервиса передача одного байта из одного модуля в другой превращается в приключение “байт отдать в layer A, там его сунут в layer B, откуда он пойдёт в layer C, а там подхватится в layer D”.

И снова про AI. Вангую, что самой массовой стратегией борьбы (игровой или натуральной) с AI будет хаотичный рандом. Что-то вроде направленного fuzz testing’а. Вы должны быть тем голубем из анекдота (“Как с голубем в шахматы играть — прилетел, перевернул фигуры, насрал и улетел, считая себя победившим”). Взять тех же Терминаторов. У них нейронки и базы внутри заточены на 99.99% человеческих поведений. Вы даже не успеете подумать о выстреле, а уже ответка прилетает. А вот если человек перед Терминатором голышом начнёт прыгать и гимн СССР орать на туркменском, есть вероятность закоротить схемы и вызвать зависание.

Дональд Кнут

Не все знают, кто такой Дональд Кнут. Надо, чтобы все.
Кнут — автор классического “Искусства программирования”. Труд большей части его жизни (издаётся с 1968 года по 2015 год). Учебник / справочник алгоритмов, разобранных до мельчайших запчастей (и математически подкреплённых), снабжённый мегатонной упражнений. На текущий момент англоязычный оригинал в издании занимает 4 полных тома с дополнением — 3К+ страниц.
Вы обязаны читать / решать Кнута, если:

  • Хотите стать Б-гом алгоритмической разработки.
  • Хотите действительно понять какой-либо алгоритм [из тех, что описаны в ИП].
  • Хотите быть полноценным программистом.
  • Хотите получить перед глазами планку, на которую стоит взбираться.

Наконец, некоторые главы можно просто читать, возвращаясь к ним по мере профессионального развития.


Если Кнут настолько полезен, почему о нём потихоньку [в xUSSR] забывают? Не напоминают же про воду, воздух и колбасу. Фигня в том, что…
Во-первых, каждое новое поколение разработчиков всё менее нуждается в знании алгоритмов. Если вы получаете хорошее образование, обязательно узнаете и про Кнута. Если не получаете, оно вариативно. Научитесь прикладывать библиотеку к компоненте, подхватите из мануалов несколько интересных слов, с десяток раз споткнётесь об оптимизацию чего-нибудь. Но субъективно кажется, что только один из тысячи разработчиков сейчас сталкивается даже с теоретической нуждой в реализации собственных алгоритмов сортировки, например. Отсюда и забвение.
Во-вторых, Кнут не Мурзилка. Иные страницы надо раз двадцать прочесть, чтобы дошло. Современный вектор обучения — он развлекающий. Авторы танцуют, поют, кидают шарики и обливают читателей шампанским. Читатели тоскуют в потолок и мычат “многа букаф… чёт я ни асиливаю… а есть видос минут на десять?” Кнут (как и некоторые другие условно его “академического поколения”) не про это. Он по мере сил разбавляет тексты, но всё же нацелен на того, кто не ленивый, не дурак и кому абзац с формулами не выносит читательскую способность на месяц вперёд.
В-третьих, он дорого стоит. Со всеми скидками сейчас четыре переведённых тома влетят в 10К рублей. Это автоматически вышибает из потенциальных клиентов тех же студентов — самую целевую аудиторию Кнута. Когда же студент находит работу (возможность оплатить дорогую профессиональную библиотеку), продолжение “академической” учёбы в приоритетах заметно понижается. Йоу, чувак, у тебя дедлайн, но забей и выполни пять упражнений на комбинаторику, ага.
В-четвёртых, его не рекламируют. “Искусство программирования” занимает нишу, которая осваивается теми, кто знает о том, что ИП существует. Если книги нет в баннерах, в обзорах, в блогах, в почтовом спаме, на обложке Playboy, то в современном медиа-мире книги нет. При этом можно быть одной из “the best twelve physical-science monographs of the [XX] century by American Scientist”. Всё чаще при упоминании Кнута слышу “а кто это?”

Хоть скачайте. На трекерах есть. Но в бумаге он читабельнее.
И это… Не запускайте голову. Нельзя, чтобы болото цвело. А Кнут — отличное лекарство от такой фигни. На всю жизнь хватит.