1. К черту!
Когда я был маленький, то на меня снизошла милость божЫя и ниспослала мне две книжки. Одна книжка была про бейсик для студентов каких-то там ВУЗов, а вторая - «Паскаль в иллюстрациях». По одному из абзацев первой книжки я в принципе научился программировать в пятом классе - там был мозголомающий отрывок с программой, заставляющей нолик летать по экрану, отталкиваясь от стенок. Вторая книжка, отданная мне соседом-алкашом, познакомила с алгоритмами. На дворе стояли 90-е — начало компьютерной эры человечества. Компьютера у меня при этом не было — я видел его пару раз в неделю на компьютерном кружке, ведущей которого была вчерашняя или даже сегодняшняя студентка, отпирающая и запирающая дверь — большего от неё нам и не требовалось.
И этот исторический экскурс в чертоги памяти заставил меня поразмышлять на тему возможности программировать без алгоритмов. И я подумал, что прекрасно делал это, и до сих пор продолжаю подобным заниматься, хоть и прошло с тех давних времён тридцать лет и три года.
В конце концов я определил для себя, что алгоритм — это такой порядок действий, который позволяет решить задачу быстрее, чем самый простой - «наивный» - способ.
В качестве примера давайте рассмотрим элементарный алгоритм сортировки. Наивным способом детвора в детском саду собирает пирамидку. Ну как малыш это делает? Правильно, берет самую большое колечко и нанизывает его на палочку. Потом из оставшихся колечек берет следующее самое большое. Ну и так далее. Можно ли считать такой наивный способ «алгоритмом»? Ну, наверное можно, но такой способ даже в школах не проходят как мне кажется. При том я видел взрослых людей, которые этот способ даже сформулировать не могут. Учил знакомого юриста, желающего войти в ИТ, но он мне не смог ответить, как бы он отсортировал массив, хотя я приветствовал любой способ и задавал наводящие вопросы. Получается, что ребёнок трёх лет умнее взрослого с высшим образованием? Видимо…
Давайте рассмотрим алгоритмы сортировки, которые понапридумывали разнообразные математики. Ну сразу же на ум приходит тот самый пресловутый «пузырёк». Можно ли научить его ребёнка о трёх годах, который собирает пирамидку? Элементарно! Просто попросить его переложить колечки попарно, чтобы слева оказалось колечко меньше, а справа больше. Я проверил на четырёхлетней деточке за неимением под рукой трёхлетки — все сработало. Но когда я вижу взрослого дядю, который не может в это «вдуплить», я огорчаюсь мыслью, старой как сам мир: «куда, собственно, он (мир) катится?»
Ну ладно, расскажу про своё житие дальше. После школ я пошёл работать. Но т. к. открывал с ноги дверь кафедры информатики в институте переподготовки педагогических кадров, то работу мне подыскали легко и не принужденно — лаборант компьютерного класса в местном педагогическом университете. По соседству с кафедрой располагалось научно-исследовательское бюро, в котором на деньги соросов и иже с ними было накуплено древнего компьютерного барахла, видимо списанного где-то. И на нем крутились программы, на которые без слез не взглянешь. Суть всего этого древнего железа и софта была в обеспечении работы лаборатории дендрохронологии.
Ну не сказать, что наши западные партнёры задарили нас совсем уж мамонтовыми какашками, но комплекс измерения был на базе крайне древней ХТ с монохромным зелёным монитором, а ввод данных осуществлялся нажатием кнопки, когда под микроскопом поздняя древесина сменялась ранней и наоборот. Девочки-лаборантки крутили «крутилку», керн, начищенный зубной пастой для того, чтобы древесные кольца были хорошо видны, двигался вдоль оси мкроскопа, девочки смотрели в этот микроскоп и нажимали «большую красную кнопку» при достижении границы. Старый ХТ выдавал файл формата «Tucson sample» (видимо, по названию университета), который потом дискетами переносился на стоящий рядом 386-й, к которому был подоткнут широкоформатный матричный Epson, в который, в свою очередь, был заправлен рулон кальки. Для печати таким образом полученного временного ряда использовался Quattro pro — этакий эксель под MS DOS. Умный математик с Уральских гор нарисовал для него какой-то скрипт, но чтобы он сработал, временной ряд надо было из формата «Tucson sample» превратить в формат «prn». Разница была существенна — в американском формате в строка начиналась с имени серии (6 букв вроде бы), дальше через ТАБ (оформленный пробелами) шли 10 чисел с показателями (1-999), потом следующая строка с именем серии и числами. Где-то там был еще и год, но я уже забыл, где. А формат «prn» с Уральских гор начинался с года и представлял из себя столбик показателей, заканчивающихся значением «999».
Ну вот и попросили меня для начала так сказать научной деятельности сделать конвертор из формата Туссона в формат Урала, а то девочки теряли по две недели времени, превращая одно в другое путём нажимания энтеров, делитов и «999».
Можно ли решать такую простую задачу, не особо разбираясь в алгоритмах, но умея программировать? Конечно! Все методы, которые я использовал, мало отличались от того, что делали девочки, стирая пробелы, переводя каретки и завершая файл тремя девятками. Здесь алгоритмы были не нужны. Не нужны они были и далее, когда начались хотелки о предварительной датировке образцов друг относительно друга (коэффициент синхронности), не нужны они были и после того, когда математика вышла за пределы школьной программы и достигла функций корреляции, стандартного отклонения, коэффициента чувствительности и прочего, что решалось предельно наивно проходом по массиву значений и аккумулированием результата. Поэтому когда мне говорят, что программисту нужна математика, то я прошу, обычно, показать мне конкретную функцию, а не лить в уши общими фразами.
Я работал программистом в научной лаборатории уже третий год, но так и не встретил надобности в алгоритмах. Неужели все так плохо? Неужели программисту и правда не нужны алгоритмы? Ведь я, не понимая ни в математике, ни в программировании, за условные три копейки двигал вперёд и вверх российскую науку. И софт, который я делал, был куда более юзер-френдли, чем американский (библиотека DPL доктора Грызино-Майера (Grissino-Mayer, H.D.)) и даже немецкий (TSAP, который толкал за 3 косых Франк Ринн). Американцы осилили командную строку, немцы сделали интерфейс. Но оба продукта с трудом читали даже свои собственные файлы, не говоря о чужих. А я за три года сделал вьювер, который интегрировался в Нортон Коммандер, который по кнопке F3 визуализировал временной ряд, после чего по кнопке F4 отправлял его на кальку с помощью поскрипывающего Epson’а. Он умел предварительно датировать набор серий из формата «Tusson», умел читать кривой «Tusson», сохраняемый из немецкого TSAP, который сам его обратно прочитать уже не умел (как минимум три последних версии программы на 1999-й год — точно не умели), умел он читать и уральский «prn», и родной немецкий формат «Heidelberg», отличавшийся большим заголовком с кучей информационных полей.
Периодически дорабатывая вьювер (добавляя новые фичи), я занялся разработкой CDS — большой и красивой программы для комплексной работы с временными рядами. И да, там я тоже не использовал другие алгоритмы, помимо наивных. Запускался CDS с картинкой из файла, поверх которой звучала музыка, выдранная из второго варкрафта (при нажатии на замок рыцарей). Дальше появлялись знакомые всем две панели аля Нортон Коммандер, которые на 146% реализовывали функции файлового менеджера (копирование, переименовывание, удаление и все прочее, что можно было сделать с файлами). Система позволяла подключать внешние программы для просмотра и редактирования файлов в соответствии с их расширением, помимо прочего имела возможность запоминать каталоги — этакая панель избранного. Мелкомягкие явно свистнули эту идею у меня. Помимо прочего, программа делала все то, что делал вьювер, но уже не в режиме 640х480х4 (16 цветов), а в режиме VESA 800х600х16 (65536 цветов). Ну и куча математики и статистики, визуализация графика в обычной и полулогарифмической шкале, визуализация автокореляции.
И, поверьте, все это было сделано наивными методами.
Дальше я написал достаточно большую программу для работы с флористическими данными. Систему назвали FLORIST. Она позволяла считать коэффициенты родственности флор по десятку коэффициентов с самого простого коэффициента Джакара до коэффициента Сьёренсена-Чекановского. И опять мне не понадобилась ни математика, ни алгоритмы — за меня считал компьютер, и, поверьте, делал это лучше человека и, разумеется, гораздо быстрее.
И да, весь этот софт не тормозил вот вообще. Даже автоматическое распознавание 39-ти различных дендрохронологических форматов происходило куда быстрее, чем проведение документа в современных 1С на куда более продвинутом железе. И да, никаких алгоритмов, никакой математики — обход массивов данных с по большому счёту четырьмя арифметическими действиями. Если у кого-то язык повернётся назвать это математикой, то можете первыми кинуть в меня какашкой.
И да, писалось все это на Borland Pascal 7.1. CDS работал в защищённом режиме под DOS, остальные продукты работали в обычном режиме. Я не использовал чужие библиотеки — если только работу с мышью. Стек окон в текстовом режиме был написан на ассемблере, obj-файлы которого импортировались в паскаль. Также на ассемблере был написан механизм печати графиков на принтере — я его ещё для вьювера написал.
И т. к. это все писалось на паскале, то оно не взлетело в Туссоне, т. к. у них там стояли более быстрые компьютеры, а паскаль на быстрых компьютерах не умел — валился с делением на ноль. И да, мы это пропатчили, но я уже свалил с трёх институтских копеек на три рубля в программирование на 1С, т. к. другое программирование в нашей деревне было особо никому не нужно. Не, иногда я помогал друзьям и знакомым курсовики писать, дипломы, диссертации даже, но за 1С платили куда больше, а дома жена…
2. А всё-таки они вертятся!
И вот наступила эра винды. Вообще, она наступила раньше, но до меня дошла ближе к 00-м. В первой конторе, куда я вообще пошёл работать менеджером, меня взяли программистом, т. к. у директора хватило ума поинтересоваться, чем я вообще занимался-то. Ну а у меня хватило ума ответить, что программы писал. В итоге я познакомился с кривой и косой 1С 6.0, деланной явно пальцем, но не ясно, каким. Потом с 7.7 и далее. И до сих пор мне не нужны были никакие алгоритмы — все продолжало решаться наивными методами, а для сортировки можно было использовать соответствующие методы.
А потом я вернулся в университет. Там мой приятель уже нехило так понаписал на С++, но я, будучи верен паскалю, начал творить на Delphi. И вот тут, внезапно, мне понадобились эти чертовы алгоритмы.
Фактически, я занимался продолжением FLORISTа — этакого пакета для классификации и исследования биоразнообразия региона. К этому моменту тот человек, который занимался дендрохронологией, стал работать в организованной лаборатории биоразнообразия. Они там провели большую работу по формированию классификатора и засунули в него около 50к видов различных растений, а может быть ещё грибов и лишайников. И с первым, с чем я столкнулся, так это с тем, что 50к видов грузились не быстро, т. к. одновременно грузились ТРИ классификатора: вид, род и семейство. И если виды нужно было загрузить все, то семейства и роды у разных видов могли совпадать. Вот тут-то мне и понадобилась книжка «Паскаль в иллюстрациях», которую, как вы несомненно помните, подарил мне сосед-алкаш.
Попытка решить загрузку наивным методом упёрлась в то, что классификатор грузился минуту. Т.е. грузился вид с его родом и семейством, потом в коллекции семейств и родов искались соответствующие род и семейство, и если чего-то не было, то в коллекцию добавлялись новые род, семейство или и то, и другое.
И так, дамы и господа, встречайте! Первый алгоритм, который мне понадобился при разработке программного обеспечения — это «бинарный поиск», т. е. «поиск методом листания словаря» (открыли посредине, посмотрели, если буковка больше, то вправо на пол-оставшегося, если меньше — влево, ну и пока не найдем). Одна загвоздочка — список должен быть упорядочен. В итоге загрузка классификатора с минуты ускорилась до долей секунды на достаточно древнем третьем пентиуме.
Следующий раз, когда мне понадобились алгоритмы, наступил через 10 лет после этого замечательного случая с двоичным поиском — в остальном хватало наивных вычислений. Это был алгоритм рюкзака. Подробности не расскажу.
Третий раз, когда мне пригодилось знание алгоритмов, произошёл в 2018-м году, когда ФМС ещё предоставляло на своём сайте файл со стопиццот миллионов недействительных паспортов. И эта история прям вот кричит о том, что алгоритмы лучше знать, чем не знать. Тут как раз подробности прям вот топят за то, чтобы разработчики иногда думали . А то, что ФМС перестала предоставлять этот файл, выводит раскрытие этих подробностей за пределы NDA.
История была такая. Я сидел на своём рабочем месте, клацал по кнопкам, не особо вдаваясь в алгоритмы и продолжая решать большую часть работы наивным методом. Нужно сводимость — нате вам градиентный спуск, который я бы не стал называть алгоритмом, т. к. оное доступно тем же трёхеткам, неоднократно наблюдавшим, как мячик на неровном полу с помощью сил притяжения находит локальный минимум. Нужен расчёт себестоимости — сложим затраты. Какие тут алгоритмы? Может быть XBRL, которым я в основном и занимался, требует алгоритмов? Нет — это просто текстовый файл с уникальными контекстами, а проверить на уникальность — способов масса, наивные среди них тоже есть и не менее эффективны.
И вот сижу я, скучаю, и внезапно узнаю, что добрые разрабы 1С решают задачу загрузки сотни миллионов чисел наивным методом — просто засовывая это в таблицу СУБД. Знаете, сколько занимает это на 1С? Наивно на тех серверах, которые у нас были, это занимало сутки. Ага-ага. Сутки прошли — пора грузить новый файл. Зато железо загружено на 100%. Дальше программисты начали думать, напрягли лучших из лучших. И решили грузить по 50к. Не помогло — при каждой вставке СУБД формировала индекс для номера и серии. И тут программистов посетило первое озарение — нужно сначала отсортировать, а потом грузить! Ура, стало работать за 8 часов: 4 часа сортировало, 4 часа грузило. Потом пришел я и сказал: а давайте попробуем многопоточно! Ура, 4 часа. Но если первый миллион грузился без блокировок, то последний миллион падал 9 раз, прежде чем загрузиться.
Итак, наивным методом на платформе 1С решить не удалось. Начали грузить напрямую в SQL. 30 минут — и все дела. Я предложил засунуть в Redis — 5 минут, куча памяти. Но 1С не умела с Redis вот так вот прямо, да и у многих клиентов не было такой инфраструктуры.
А потом я вспомнил про алгоритмы. Ведь 4 цифры серии (0-9999) и 6 цифр номера (1-999999) — это не фиг чего вариантов, поэтому можно сотворить битовую матрицу в 10 миллиардов бит (1,2 Гигабайта, что для современного компьютера ниачём). Но т. к. половина серий еще не выдавалась, то вполне хватало и половины от этого объёма, если выделять память на каждую серию отдельно.
В итоге я написал прототип на С, коллеги взяли идею и реализовали на 1С. И если на С из кеша ОС битовая матрица формировалась за какую-то долю секунды, то на 1С достаточно мощный компьютер формировал её за 8 минут. 8 часов и 8 минут — хорошая оптимизация, да?
Заключение
Программист вполне может обойтись и без математики, и без алгоритмов. И при этом он может быть очень хорошим программистом, владеющим обширным стеком технологий. Я в своей работе по большому счёту без всего этого обхожусь, ибо не считать же знанием математики способность создать программу, вычисляющую стандартное отклонение или что-то в этом духе. Математику пусть знает заказчик или бизнес-аналитик — вот им она полезна, т. к. позволит правильно поставить задачу. А программист должен уметь массив обойти какой, дерево, может быть связанный список. Этого достаточно, чтобы не пропасть в своих перекладываниях джисонов.
Но всё-таки иногда знание алгоритмов помогает увеличить скорость работы продукта на несколько порядков. И достаточно одного человека в команде, который был бы способен увидеть решение, поразмыслив над тем, какой алгоритм сюда вписать. И давайте дадим ему медаль...
Подписывайтесь на мой канал, ставьте лайк, ... (с)
Автор: Sergey Andreev
