Шура Люберецкий

На днях видел на хабре две записи, можно либо смеяться, либо плакать.

Первая — «как правильно писать на Javascript». Первый же совет звучал примерно так:

Никогда-никогда не используйте eval()! Даже если очень надо — все равно не используйте! eval() позволяет порождать код, а это очень-очень нехорошо! Так делать нельзя, потому что так делать нельзя никогда!

В общем, аргументация была примерно на таком уровне — я только чуть-чуть преувеличиваю, «дабы дурость каждого видна была». Вопрос: почему порождать код нехорошо? Ответ: это нарушает привычную тем, кто всю жизнь писал на Паскале, «логику работы программы».

Доводя это до абсурда, скажу, что самые true-программисты никогда не используют операторы цикла, а обходятся только goto и if в виде

if(condition) goto somewhere;

Всякие бесполезные циклы нарушают логику работы программы, привычную тем, кто всю жизнь писал на FORTRAN-77.

Вторая — чувак для понтов реализовал в C++ вычисления, как он сам сказал, «с плавающей точкой» на этапе компиляции (с использованием шаблонов, разумеется). Я не буду придираться к тому, что на постсоветском пространстве вместо точки «плавает» запятая, потому как заголовок неправильный с самого начала. Число с плавающей запятой — это представление числа в виде мантиссы с фиксированным количеством знаков и порядка. У автора реализовано представление в виде отношения двух целых чисел, это несколько другое «решение». Обычно в программировании это называют «рациональными числами», не заботясь, правда, о полной корректности этой формулировки. Подходы эти принципиально разные и путать одно с другим не надо.

В общем, как кто-то заметил, «Русская Википедия — это деревенский кружок любителей истории». Хабр в таком случае — деревенский кружок любителей так называемых «информационных технологий».

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

Как я уже говорил, описаний «делай раз, делай два» для триангуляции Делоне в Интернете практически нет. Есть книга А. В. Скворцова, есть несколько разной подробности описаний на сайтах американских университетов, например, из курса CS 294-5 Университета Беркли. Но я пишу этот пост не оттого, что хочу пожаловаться на жизнь — изобретателю велосипедов так делать нельзя, он сам себе злобный Буратино. Я хочу предложить уважаемой публике сравнить программу курса в Беркли с «Практикумом по компьютерной геометрии«, который с 2009 года включен в программу мехмата МГУ.

Согласитесь, что сравнение «практикума по Wolfram Mathematica» и очень серьезного курса в Беркли (предполагающего немалую самостоятельную работу) как-то не вяжется с представлением о «тупых американцах». Правда, компьютерной геометрии я не застал, а вот чему учат в «Практикуме на ЭВМ» на мехмате — рассказать могу. Предлагаю еще, для полного счастья, открыть пару хороших переводных учебников, типа SICP и Кормена и сравнить все происходящее.

Итак, на первом курсе сей предмет называется «Программирование и работа на ЭВМ» и предполагает сдачу двух зачетов — в осеннем и весеннем семестрах. Твердо установленной программы нет, все зависит от преподавателя, но подразумевается, что два сданных зачета доказывают умение студента писать программы на языке Си. Говорят, что иногда разрешают писать чуть ли не на Паскале. Занятия проходят попеременно в виде занятий за компьютерами и «обычных» семинаров, где препод рассказывает о том, что считает нужным. Например, А. Г. Кушниренко рассказывал про индуктивные функции, про некоторые нюансы языка Си типа арифметики указателей и правильного хранения двумерных матриц, а также — про своих (разумеется, тупых) американских студентов. Кроме того, он пугал нас тем, что на госэкзаменах мы забудем, что такое функция. К сожалению, мне на госах такой вопрос не задали, а я готовился :) Для получения зачета достаточно сдать три-четыре задачи из некоего списка (после этого преподаватель обычно убежден в том, что и остальные задачи студент сдаст, и больше не докапывается). Задачи простые (вот, например, список чего-то подобного), при минимальном знании Си решаются за полчаса каждая (и то время взято с большим запасом). У меня, например, от этого сложилось ложное впечатление, что и дальше все будет так просто.

На втором курсе было уже что-то похожее на вводный курс по Computer Science (с экзаменом в весеннем семестре и все тем же названием). Как всегда, было намешано все и сразу. В два семестра «у нас» запихнули четыре «американских» семестровых курса (вводный курс по C++, алгоритмы и структуры данных, формальные языки и грамматики, и понемногу, для общего знакомства — из курсов по операционным системам и компьютерным сетям). Все это прочитать за указанное время невозможно, поэтому реально программа несколько сокращается. Из лекций (их у нас читал В. В. Борисенко) я помню рассказ про машинную арифметику и стандарт IEEE 754, немного — про вызов функций с передачей параметров через стек в языке Си и ему подобных, было что-то про Register Transfer Language компилятора gcc, про «классические» алгоритмы и структуры данных, типа сортировок, разнообразных стеков, очередей и деревьев, кроме того, студентов развлекали байками о том, как горят в грозу сетевые карточки, и как отличить толстый Ethernet от тонкого. Формально для получения оценки нужно уметь решать задачи из опубликованного в Интернете списка и уметь отвечать на вопросы по программе, реально — надо решить по одной-две задачи из каждой темы или, допустим, найти ошибку в классе, реализующем арифметику произвольной точности (это приравнивается к решению соответствующей задачи). Этого достаточно для того, чтобы получить «пятерку» досрочно, а что происходит на основном экзамене — я не знаю. Говорят, что безбожно списывают, и положительные оценки получают даже полные «нули» по предмету.

В самом начале 2000-х на втором курсе пытались преподавать Java, но в итоге поимели кучу жалоб от студентов, от которых на третьем курсе внезапно потребовали знания Си или Фортрана. Борисенко говорил, что ничего «такого», что есть только в Си, использоваться не будет (а общее подмножество Java, Си и Фортрана осваивается в режиме «не приходя в сознание» за пять минут), но отечественный студент прекрасно умеет пользоваться фразой «а нас этому не учили!«.

Кстати, нельзя не упомянуть матчасть. Нет, это уже не старенький VAX, которому даже посвящен специальный сайт, сейчас мехмат полностью перешел на относительно современные персоналки. Ничего старше Pentium III я уже не застал. Гораздо интереснее софт. Стараниями К. Ю. Богачева на этих компьютерах стоит хитро настроенный Linux, запортить который студенты не могут. Чтобы жизнь малиной не казалась, задачи надо сдавать, используя хитро настроенный gcc (его еще называют «компилятор Богачева»). Там включена опция -Werror, приравнивающая предупреждения компилятора к ошибкам. В результате те, кто пишет дома в более лояльно настроенных компиляторах, сталкиваются с тем, что их программы просто не работают (в частности, компилятор матерно ругается на отсутствие пустой строки в конце файла, или на функцию main, возвращающую нецелое значение).

На третьем курсе начинается «Практикум на ЭВМ». Когда-то давно надо было писать на Фортране под СМ-4. Теперь, когда СМ сдана на цветмет, люди пишут на Си на тех же персоналках. Правда, говорят, что некоторые преподаватели принимают задачи и на Фортране. Не знаю, у нас этого никто не пробовал. Сей практикум растянут на четыре семестра, обо всем по порядку.

Третий курс в основном посвящен реализации алгоритмов из книжки «Методы решения линейных систем и нахождения собственных значений» все того же К. Ю. Богачева. В первом семестре надо написать две программы по 300-400 строк. В первой надо обратить матрицу размера около 1000×1000 (или решить аналогичных размеров линейную систему, это задачи равноценные), во второй — найти собственные значения той же матрицы. Пишутся они совершенно бездумно, простым переписыванием из книжки. Кстати, с точки зрения «справочника рецептов», написана она очень неплохо. Если преподаватель — не К. Ю. Богачев, то этого будет достаточно. Богачев требует несколько большего — а именно, ускорения этих методов в два-три раза. Правда, он еще и объясняет, как это сделать. После того, как сдана «практическая» часть — следует «теоретический» зачет. Всех студентов, сдавших программы, загоняют в аудиторию 14-08 и раздают письменное задание. Необходимо изложить три-четыре метода из книжки, если не полностью — то хотя бы в устраивающем Богачева объеме. Второй семестр — примерно то же самое, только книжка другая. На этот раз — «Методы приближения функций».

Я не буду говорить ничего про Н. Н. Ченцову, которая вела у нас эти занятия, желающие могут составить представление о ее методах обучения, почитав один из околомехматовских форумов.

Четвертый курс несколько забавнее. Например, такого исчерпывающего руководства по всем вопросам, как методички Богачева, больше нет. Кроме того, надо написать не только программу, но и отчет — связный текст на 5-6 страниц, описывающий метод решения и убеждающий преподавателя в его правильности. Конкретные задачи зависят от «препода». Например, кто-то вычисляет интегралы всякими там «методами трапеций» или решает методом Ньютона нелинейные уравнения. У И. С. Григорьева задачи поинтереснее — решение дифференциальных уравнений методом Рунге-Кутта с автоматическим выбором шага и применение принципа максимума Понтрягина в задачах оптимизации (то есть сведение задачи оптимизации, которую человечество в целом решать не умеет, к «решабельной» системе дифференциальных уравнений). Сам Илья Сергеевич регулярно выигрывает некие международные соревнования по решению задач оптимизации и вообще, любит эту тему. Правда, с точки зрения программирования тут все довольно просто и «концептуально» не отличается от, скажем, метода Ньютона решения тех же дифференциальных уравнений. Если имеется «рыба» отчета, то программа вместе с отчетом пишутся за 5-6 часов (а их надо две штуки). Эта простота развращает, но благодаря ей я все-таки увидел Е. А. Лапшина, которого «надо бояться«.

Во втором семестре так же незамысловато решаются уравнения в частных производных. Все еще проще. Собственно, происходящее на третьем и четвертом курсах не имеет никакого отношения к тому, что на Западе называют Computer Science. Это просто практикум по численным методам, но, надо сказать, неплохой — если повезет с преподавателем. У вышеназванной Ченцовой, например, интересных задач не будет — зато будет много геморроя со сдачей отчета. Сегодня она не хочет брать его в руки, потому как «жалко, такой чистый», а завтра будет — «противно, такой грязный». На программу она даже не смотрит, кое-кто даже сомневается в том, что она знает Си.

Кстати, четвертый курс занимается в так называемом «классе Эйч-Пи» (я специально не пишу HP, чтобы не путали с русскими буквами). Это аудитория во «Втором гуманитарном корпусе» (хотя гуманитарность его ставится под сомнение наличием там ВМК и оккупацией мехматом нескольких этажей), где когда-то давно стоял миникомпьютер HP-810 (возможно, название неправильное, так его обозвали на страничке «Компьютеры, которые выбираем не мы«) с пятнадцатью терминалами. Сейчас там стоят обычные персоналки с Windows XP производства, кажется, того же Hewlett-Packard. Так как студенты таскают программы на дискетках, перед тем, как засунуть что-то в компьютер, надо это что-то дать на проверку специально обученной тетеньке, сидящей у входа в класс и умеющей пользоваться Dr. Web с безбожно устаревшими базами и пасьянсом «Косынка». Как нетрудно догадаться, вся зараза первым делом попадает на компьютер с антивирусом, откуда разносится по классу. Систему там переустанавливают по три-четыре раза за семестр. Впрочем, пора бы заканчивать с ностальгическими воспоминаниями.

Если принять «интенсивность работы» в американских ВУЗах из «первого десятка» за эталон — то первый курс мехматовского «Программирования и работы на ЭВМ» — это чистое жевание соплей. Второй курс более-менее похож на что-то нормальное (какие-нибудь «Алгоритмы и структуры данных»), «Практикум на ЭВМ» третьего и четвертого курсов из четырех семестров мог бы сжаться до двух (и идти параллельно с курсом лекций по численным методам). В общем, из восьми семестров получается четыре без особых потерь в содержании (а если так уж хочется оставить восемь — можно добавить столько полезных вещей, типа нормальной вычислительной геометрии…). Вот только с подобной интенсивностью попросту не справится половина студентов, а отчислить столько даже Лапшин не сможет.

Я уже упоминал, почему в американских ВУЗах программа курса строится не по принципу «меньше тройки не получишь», а исходя из того, что может/хочет рассказать преподаватель. Они могут позволить себе такую роскошь, как заваливающие экзамен 3/4 слушателей, у нас этого просто не поймут. Зато троечникам напрягаться не надо.

UPD http://shura.luberetsky.ru/2011/08/05/neobkhodimye-poyasneniya/ — я отвечаю на некоторые вопросы.

В продолжение вот этой задачки:

http://shura.luberetsky.ru/2011/07/19/algoritmicheskaya-zadacha/

Я реализовал алгоритм выбора точек, описанный в статье Systematic selection of Very Important Points from Digital Terrain Model for constructing Triangular Irregular Network без каких-либо изменений. Особо не заморачиваясь с производительностью, я добился того, что из миллиарда точек выбиралось порядка миллиона «очень важных» где-то минут за 40. Такое время меня вполне устраивало. Думаю, при желании можно сократить его в два-три раза, но делать этого я не буду, и вот почему.

Во-первых, модель с миллиардом точек оказалась бесполезной. Выяснилось (после выбора «очень важных точек»), что расположены они как-то странно — вдоль сторон и диагоналей квадратиков регулярной сетки. Оказывается, что кто-то взял за основу матрицу высот с большим шагом, преобразовал в триангуляционную модель (тривиальным образом, без выбора «важных точек»), а затем снова преобразовал в растр с меньшим в 10 раз шагом.

Во-вторых, чудес не бывает. Более-менее адекватное количество «важных точек» можно выбрать тогда, когда их количество меньше общего количества точек где-то на два порядка. Итого миллиард точек исходника даст 10 миллионов точек TIN, или около 20 миллионов треугольников. Это много.

Если «сложить» эти пункты, то можно преобразовать исходный миллиард точек в 10 миллионов (с которых все и началось), а затем сделать из них 100 000 «важных точек» — около 200 тысяч треугольников, сущая ерунда по нынешним временам.

Кстати, хочу поплакаться на жизнь. Пол-пятницы искал нормальное описание того, как алгоритмически сделать триангуляцию Делоне. В интернетах встречается описание алгоритма со сложностью O(N²) — последовательно добавляем точки к существующей триангуляции, при необходимости перестраивая ее. Каждый шаг в худшем случае требует перестроения всех треугольников, и это мне не нравится. Иногда в довольно общих чертах описывают алгоритм типа «divide and conquer» — разбиваем множество точек надвое, строим для подмножеств триангуляции, а затем объединяем их. Сложность, как можно показать, асимптотически оптимальная, O(N ln N). Описание того, как именно надо объединять, обычно отсутствует. В книге Препараты и Шеймоса подробно разбирается задача построения диаграммы Вороного — графа, двойственного триангуляции Делоне, и вскользь делается упоминание о том, что построив диаграмму Вороного за асимптотически оптимальное время O(N ln N), можно преобразовать ее в триангуляцию. Этот подход тоже мне не нравится, так как для построения диаграммы Вороного требуется выполнять несколько более сложные операции.

Конечно, я нашел относительно адекватное описание всего этого безобразия, но как-то странно — вроде задача довольно классическая, а описаний решения «для тупых» нет.

Дано: есть матрица высот, то есть (грубо говоря) равномерная сетка точек на поверхности Земли, для каждой из которых приведена ее высота. Точек много, порядка миллиарда. Нужно построить TIN-модель (triangular irregular network), то есть сетку из треугольников с «абы где» расположенными вершинами, «похожую» на исходную матрицу высот. Треугольников должно быть много меньше — несколько десятков тысяч это максимум.

Стандартные алгоритмы построения TIN построены по общему принципу — для каждой точки матрицы высот (всего их N) вычисляется какая-то численная характеристика, связанная с локальными свойствами этой точки, в качестве вершин треугольников выбираются точки с максимальным значением этой характеристики (а их число обозначим M), а затем для построенных вершин строится триангуляция Делоне. Так вот, поговорим про выбор вершин этих треугольников.

В руководстве, откуда я взял это описание, предлагается сначала вычислить характеристику, а уж потом выбрать точки, где она принимает наибольшие значения. Если прикинуть расход памяти для такого действия, то становится очень грустно (не забываем о том, что у нас уже есть загруженная матрица высот). Хочется сделать это несколько более эффективно.

Легко понять, что функция f, выбирающая из последовательности x₀, …, x_n M максимальных элементов, является индуктивной, то есть f(x₀, …, x_n) зависит только от f(x₀, …, x_n-1) и x_n. Можно записать это следующим образом: f(x₀, …, x_n) = F(f(x₀, …, x_n-1), x_n). Индуктивная функция от последовательности длины N вычисляется за N шагов очень простым циклом, надо знать лишь значение f на пустой или одноэлементной последовательности и функцию F.

Очень просто написать функцию, находящую M «наибольших» элементов в N-элементной последовательности за O(N*M) с расходом памяти O(M) — выбранные элементы хранятся в массиве, каждый новый элемент сравнивается со всеми выбранными до этого. Если включить мозг, то можно улучшить оценку до O(N*log M) с той же оценкой расхода памяти (храним выбранные M элементов в самобалансирующемся дереве). А можно ли сделать это еще быстрее, возможно, отказавшись от подхода с индуктивными функциями? Я ответа пока что не знаю.