Неспешно читаю-решаю упражнения из SICP. Дошел где-то до середины книги, так что могу написать какое-то более развернутое мнение.
Начну с плюсов. Как недавно заметил infowatch, в «околокомпьютерных» областях достаточно велико количество самоучек, а «официальные» учебные планы зачастую неадекватны — следовательно, любой более-менее приличный «компьютерщик» в той или иной степени оказывается «самоучкой». Недостатки такого подхода очевидны — нет «систематичности» знаний и «единой картины мира».
Вообще, складывается такое впечатление, что отечественное программирование во многом представляет собой некий «карго-культ», копирующий внешние стороны такового в США. Кто-то рассказал про интервью при приеме на работу в Google и Microsoft — и все-все-все, включая распоследнюю «веб-студию», бросаются спрашивать про сортировку и красно-белые деревья. То, что когда-то эти вопросы позволяли Google и Microsoft набирать исключительно студентов-отличников ведущих американских ВУЗов — в расчет не принимается. Аналогичное впечатление производят и учебные планы — например, вопросы, связанные с индуктивными вычислениями и прочей рекурсией явно заимствованы из курсов с использованием Lisp наподобие SICP. На «традиционных» у нас C и Pascal они выглядят довольно дико. В общем, самоучки учат самоучек.
Что делать в такой ситуации? Наверное, лучше всего «забить» на попытки Рабиновича напеть Паваротти и «самоучиться» по первоисточникам — тем более, что ситуация с ними сегодня лучше, чем десяток лет назад. Например, SICP достаточно неплохо переведена, и теперь не придется вычленять «разумное, доброе, вечное» из кривого пересказа. Не надо «плеваться» от того, что эта книга — всего лишь «вводный курс» программирования. В свое время, например, кто-то обратил внимание на возраст присутствующих в аудитории на видеолекциях (в интернете выложены видеозаписи лекций по этому курсу) — и там было немало вполне взрослых людей, возможно даже и с опытом работы.
Более того, из-за особенностей применяемого диалекта Lisp, в SICP уже в конце первой главы переходят к вполне содержательным задачам — то есть демонстрирующим не какие-то конструкции языка, а различные подходы к программированию. Это отличает ее от других «вводных курсов», где берется какой-то язык программирования (раньше дико модным был Pascal), подробно изучаются его конструкции, а из «программирования» до обучающихся доводится лишь одна истина — что, оказывается, можно набрать на клавиатуре какой-то текст, затем нажать нужные кнопки и компьютер волшебным образом выполнит то, что хотел программист.
Что меня особенно удивило — я ни разу не видел более краткого описания ООП, чем один-единственный абзац в SICP (в начале 3 главы):
Существует мощная стратегия разработки, которая особенно хорошо подходит для построения программ, моделирующих физические системы: воспроизводить в структуре программы структуру моделируемой системы. Для каждого объекта в системе мы строим соответствующий ему вычислительный объект. Для каждого действия в системе определяем в рамках нашей вычислительной модели символьную операцию. Используя эту стратегию, мы надеемся, что расширение нашей модели на новые объекты или действия не потребует стратегических изменений в программе, а позволит обойтись только добавлением новых символьных аналогов этих объектов или действий. Если наша организация системы окажется удачной, то для добавления новых возможностей или отладки старых нам придется работать только с ограниченной частью системы.
Между прочим, волшебные слова «инкапсуляция, наследование и полиморфизм» в книге не встречаются ни разу. В любой «нормальной» книжке утверждается, что якобы они и составляют так называемое «объектно-ориентированное программирование» (которого не существует — но это отдельная тема), а здесь удалось обойтись вообще без них.
Разумеется, что все рассматриваемые в SICP подходы к программированию можно показать и с использованием других языков. Например, встречаются решения задач оттуда на Common Lisp (это, правда, не считается — так как он все равно достаточно близок к Scheme), Python, Javascript и даже на C# — в общем, «на чем угодно». Правда, ни один из этих языков (за исключением, разве что, Common Lisp) не подходит для того, чтобы продемонстрировать все эти подходы сразу.
Теперь к недостаткам — благо «хвалебных» отзывов о SICP и без меня предостаточно. Можно было бы начать с классического «Не покупайте эту книгу«, но у меня к SICP другие претензии. Меня, как математика, поражают вольности с численными методами. Любой программист считает себя непревзойденным специалистом в этой области — но это далеко не так. Не последнее место в формировании этого заблуждения занимают книги по программированию, в которых численные методы рассматриваются в отрыве от их «содержания», как обычные алгоритмы.
Например, в главе 1.3.1 приводятся формулы численного интегрирования, и утверждается, что «определенный интеграл … можно численно оценить с помощью формулы» («the definite integral … can be approximated numerically using the formula «) — при этом не раскрывается ни законность этой оценки (что можно «простить»), ни ее точность. Правда, вычисляются два приближения для одного интеграла, меньшее значение переменной dx
соответствует большей точности — и только! В упражнении 1.29 приводится формула Симпсона, утверждается, что она представляет собой «более точный метод численного интегрирования» (в чем эта точность заключается — не объясняется), а затем предлагается проинтегрировать с ее помощью кубический многочлен — якобы это должно «доказать», что она «более точна». Удивительно, но результат оказывается ближе к истинному значению — но это не сходимость, как в первом случае, а просто свойство формулы Симпсона — она дает точное значение при интегрировании кубических многочленов.
Чуть дальше появляются более «страшные» вольности. Например, в «определении» производной (оно необходимо для метода Ньютона) предлагается заменить стремящееся к 0 dx
каким-то «очень малым» значением. Сказать, что это приближение, видимо, религия не позволяет.
В конце раздела 1.3 находим упражнение 1.45 — от которого я пришел в ужас. Сообщается, что метод Ньютона не работает для некоторых функций, например, для извлечения корня n-й степени. Предлагается использовать многократное «торможение усреднением» (average damping — этот термин я не встречал нигде, кроме SICP), а «кратность» его применения установить — держитесь — экспериментально! Да, читатель SICP, скорее всего, не сможет доказать полученное утверждение — но предложение «экспериментально» доказать математическое утверждение, согласно современным представлениям, дико само по себе. Может, не стоит вообще давать такие задачи?
Практически весь раздел 1.3 посвящен численным методам в том или ином виде — и везде есть какие-то «косяки». Да, большинство читателей их не заметит — но здесь я не могу разделять их восторгов по поводу книги. Тут требуется несколько более высокий уровень строгости в изложении. В целом книга крайне хороша с «программистской» точки зрения, но как только речь заходит о математических вопросах — то начинается «тушите свет, сливайте воду». Численные методы — хорошая демонстрация для абстракций, связанных с использованием «функций высших порядков» (для которых, правда, в математике придуманы свои термины — например, «функционал» или «оператор»), но они требуют все же несколько другого подхода.
Продолжение, как говорится, следует.
>красно-белые деревья
красно-чорные же.
>как только речь заходит о математических вопросах – то начинается “тушите свет, сливайте воду”
Думаю это потому что на Западе образование более-менее отражает рынок труда.
Только единицы процентов разработчиков ПО пойдут разрабатывать шо-то наукоёмкое, где нужно знать дифференциальное исчисление и численные методы.
Для этих единиц процентов наверняка есть куча спец.курсов по applied math.
> Думаю это потому что на Западе образование более-менее отражает рынок труда.
Почему же тогда в книжке не изучается Java?
> Только единицы процентов разработчиков ПО пойдут разрабатывать шо-то наукоёмкое
Чота ржал. Вот, например, совершенно ненаукоемкая задачка — есть тайловая электронная карта, известны координаты (широта-долгота) углов этих тайлов, мышка ползает по карте, найти широту-долготу точки, в которую попал курсор. Достаточно какого-то «приближенного» решения, точность попадания компенсируется мощностью заряда. Вроде бы простая задача, методы интерполяции хорошо известны — но все предпочитают изобретать велосипеды.
>в книжке не изучается Java?
Потому шо из всего многообразия книжек, ты выбрал книжку 1996 года.
Java стала играть значимую роль на рынке бизнес-софта только с версии 2, т.е. с 1998. До этого Java была для кофеварок (но не выстрелила, PIC дешевле, а для кофеварок решает именно стоимость экземпляра) и апплетов (тоже не фонтан, производительности не очень хватало, в то время IMO чаще писали native code в виде ActiveX, чем java applets).
>ненаукоемкая задачка
>тайловая электронная карта, известны координаты
Задачка чо-то не особо характерна.
Прикладной разработчик не будет её решать.
Он вызовет у объекта «карта» метод [convertPoint:toCoordinateFromView:] или TryViewportPointToLocation.
Разработчик игр тоже не будет, он напишет хитрожопый шейдер, и искать координаты будет видеокарта.
Лично я тоже бы не стал.
Обычно правильный способ искать координаты, это таки инвертировать проекцию: и вычислительно намного дешевле чем тайлы перебирать, и точнее.
По мне так «изобретать велосипеды» это в данном случае самому реализовывать хорошо известные методы интерполяции..
Еще раз намекну, что это MIT и клали они на «специфику рынка труда» с большим прибором.
Теперь про карту. Метод «toCoordinateFromView» как раз и надо реализовать. Проблема в том, что ГИС-ядро, которое знает параметры проекции, висит на веб-сервере, и спрашивать у него координаты на каждое движение мышки просто нельзя. При перезагрузке тайлов кидают координаты их углов — а дальше «ебитесь, как хотите».
>ГИС-ядро, которое знает параметры проекции, висит на веб-сервере
Мнда.
Зачем серверу-то знать параметры проекции? Он же бедный сломается уже порядка при 10k одновременных пользователей.
Не судьба что ль было посмотреть, как это сделано у google/bing/yandex/yahoo/OpenStreetMap/всех остальных, и повторить то же самое?
Anyway.
Тебе с сервера прислали набор картинок, для каждой картинки — 4 точки на плоскости экрана.
Ты каким-то образом натягиваешь текстуры на 4-угольники.
Так вот, алгоритм должен быть не «как хотите», а соответствовать тому, как именно тексели из картинок ложатся на экран.
Очевидно, о деталях того как именно это происходит, написано в документации graphic API, которое ты используешь для рисования затекстуренных 4-угольников.
Мне кажется для того шоб это сделать, не нужно почти ничего знать про интерполяцию и численные методы?
> Зачем серверу-то знать параметры проекции? Он же бедный сломается уже порядка при 10k одновременных пользователей.
10k одновременных пользователей там не планировалось. А знать надо для того, чтобы отрисовывать карту. Тайлы по мере отрисовки (ну или заранее) кешируются. Параметров проекции никто, кроме ГИС-ядра, в общем случае не знает.
> и повторить то же самое?
Напомню, что проекция Меркатора — далеко не единственная. Она замечательна тем, что параллели и меридианы представляют собой прямоугольную сетку и пересчет «пиксельных» координат на экране в геодезические координаты происходит легко и непринужденно. Кроме интернетовских карт, используют ее только в морской навигации. Недостатков у нее полно, чего стоит одно искажение площадей — сравни хотя бы Гренландию с Южной Америкой на гугломапсе.
> Ты каким-то образом натягиваешь текстуры на 4-угольники.
Какие нах текстуры? Мне прислали нарезанную квадратиками карту — допустим, такую:
http://egsc.usgs.gov/isb/pubs/MapProjections/graphics/bipolar.gif
Вместе с квадратиками имеется таблица, где указаны координаты (широта-долгота) углов квадратиков. Никаких graphics api, ничего нет (а чтобы отрисовать векторную карту с заданной проекцией, надо уметь рисовать лишь ломаные линии, возвожно, с заливкой).
> не нужно почти ничего знать
Задача определения координат внутри порезанных квадратиков почти тривиальная, и для ее правильного решения (например, билинейная интерполяция внутри каждого из квадратиков вполне удовлетворительна) действительно ничего знать не нужно. Но при этом при том же незнании можно придумать какой-нибудь чудовищный «велосипед».
Да, про карту.
Отклонения между наивной реализацией «хорошо известные методы» и тем как на самом деле рендерится карта, могут достигать довольно существенных значений.
Детали вот тут например:
http://en.wikipedia.org/wiki/Texture_mapping#Perspective_correctness
Так дело не в недостатках реализации, а в изобретении чудовищных велосипедов. Вот сравни, как надо:
http://reslib.com/book/Praktikum_na_EVM__Metodi_priblizheniya_funkcij_#140
И что придумывают:
http://ru-algorithms.livejournal.com/24344.html
Да, про карту. Проекция — не меркаторовская (а вообще неизвестно какая), а то неинтересно.
А может наоборот, предполагалось, что у слушателей имеется достаточная математическая подготовка? Когда курс создавался? В 80е?
В американских университетах не предполагают ничего. Я как-то хотел написать гадостей про книжку Кормена (это следующий курс по алгоритмам и структурам данных), там целая глава посвящена «избранным местам» алгебры и анализа, а все оценки сложности получаются чудовищно сложными методами — чтобы было понятно студентам, ни разу не изучавшим математику за пределами школьного уровня.
> все оценки сложности получаются чудовищно сложными методами
Да, помнится был срач насчёт програзма и высшей математики. :-) Как раз приводились аргументы, что знание рядов и интегралов делает оценку сложностей алгоритмов простой и понятной. А иначе приходится изобретать велосипеды. И хорошо ещё, что с двумя квадратными колёсами, а не сложнее. :-)