Архив

Archive for the ‘Программирование’ Category

Песня о точке не на своём месте

Эта история — живая легенда из истории вычислительной математики и связанного с ней программирования. Сейчас, правда, уже изрядно подзабытая, но ей-же-ей, она стоит того, чтобы её рассказывали и помнили. 🙂

Итак, дело было в конце далёких 1960-х годов. Группа баллистиков из NASA считала какие-то очередные небесные траектории. Ничего, в общем-то, особенного.

Ан нет! Случилось почему-то так, что у них получалось нечто вовсе невообразимое. Ну то есть вообще ни уму, ни сердцу. Не могло быть таких результатов, просто потому, что не могло быть никогда!

Дело-то как бы тоже довольно обыденное для компьютерщиков. Поскольку математическая модель была уже неоднократно опробована и хорошо себя зарекомендовала, собака явно порылась где-то в её реализации. В программе то есть. Ну, стали отлаживать, разумеется.

Здесь, конечно, надо пояснить, что в те годы отладка была совершенно не похожа на нынешнюю. 🙂 Там, где нынешний программист легко прыгает отладчиком по точкам останова, имея возможность в любой момент посмотреть значения переменных, тогдашним программистам приходилось вставлять отладочную печать и искать ошибки по анализу её результатов.

Сами представьте, каково это было в эпоху перфокарт. (Вот вам, кстати, и повод для использования карт разных цветовых оттенков. Отладочные вставки гораздо легче было выбрасывать из программы, если они пробивались на картах другого цвета.) Медленно получалось, даже при том, что баллистики NASA никаких проблем с компьютерным временем и прочими ресурсами не имели.

А результаты-то нужны были к конкретным срокам! А программа не отлаживается никак…

В условиях жёсткого цейтнота было принято отчаянное решение: писать всю программу заново с нуля! Написали — и ведь заработало! Но кто-то из тех программистов из принципа решил найти-таки ошибку в первом варианте. И нашёл потом, спустя некоторое время.

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

Да вот, сами сравните две строчки на Фортране:

DO 10 I=1,5
DO 10 I=1.5

Они обе имеют смысл и отличаются только в одном-единственном знаке препинания. А делают совершенно разные вещи. 🙂

Зелёная строчка повелевает выполнять с повторением кусок кода отсюда и до метки 10, последовательно придавая переменной I значения от 1 до 5. А красная присваивает значение 1.5 переменной с именем DO10I. В тогдашних стандартах Фортрана пробелы вне строк игнорировались, а предварительное объявление переменных в этом языке не является обязательным и сейчас.

Вот примерно такая фигня — точка вместо запятой — и была допущена в тексте первоначального варианта. Почувствуйте, как говорится, разницу. 🙂

Ошибка была столь эпически-дивно-аццкой, что про неё ещё очень и очень долго предупреждали будущих математиков. 🙂 Нас, например, предупреждали. А в конце 1990-х на какой-то конференции, где я присутствовал, эта тема была мельком упомянута в разговоре во время перерыва, и куча народу засвидетельствовала, что их также предупреждали. Хотя учились все в разные времена и в разных местах.

По-моему, байка стоит того, чтобы рассказать её и сегодня… 🙂

Песня о скалярном произведении

Эта песня будет о старой и важной проблеме вычислительной математики. Собственно, проблема и сейчас живее всех живых, о чём стандартно предупреждается в любом мало-мальски приличном курсе численных методов… а студенты столь же стандартно об этом забывают… 🙂

Казалось бы, ну что может быть проще скалярного произведения? Пусть у нас речь идёт о векторах размерности, допустим, 100. Вроде, и не нужно быть крутым программистом, чтобы написать нечто вроде

float DotProduct(float x[],float y[]) {
    float r=0.0;
    for(int i=0;i<100;i++) r+=x[i]*y[i];
    return r;
}

Агащазблин. 🙂 Не работает-с. Вернее, работает только в игрушечных ситуациях.

Чтобы разобраться, почему не работает, давайте для простоты представим, что компьютер функционирует сразу в десятичной системе. Пусть формат хранения числа с плавающей точкой имеет вид

±#.#######e±##

Один символ «#» соответствует одному хранимому разряду.

Теперь мысленно промоделируем вычисление скалярного произведения вектора на себя. Вектор будет иметь следующий вид: первые 99 позиций заняты одним и тем же числом 0.0003 = 3е-4, а в последней позиции стоит единица 1 = 1е+0 = 1е-0.

Для i=0…98 будем иметь x[i]*y[i] = 9e-8. Суммируя это число 99 раз, получим 8.909е-6 = 0.000008909е-0. Для i=99 к этому числу прибавится единица:

1.0000000е-0 + 8.909е-6 = 1.0000000е-0 + 0.000008909е-0 = 1.0000089е-0

Два последних разряда не вписываются в сетку, и происходит округление. С поправкой на этот факт, ответ правилен.

А теперь представим, что вектор тот же самый, но его компоненты идут в обратном порядке. 🙂 Чисто математически его скалярное произведение на себя никак не должно измениться.

А что же происходит в программе?

А вот что. После итерации i=0 будем иметь r=1e-0. Итерация i=1 добавляет к нему число 9е-8. Которое, обратим внимание, с разрядной сеткой единицы несоизмеримо!

И вот тут возможны два варианта, в зависимости от реализации арифметики с плавающей точкой. В первом — тупом — несоизмеримое 9е-8 будет просто отброшено. Как нетрудно догадаться, в итоге мы так и получим единицу ответом.

Во втором — умном — будет замечено, что несоизмеримое число «занимает более половины последнего разряда». И с округлением получится r=1.0000001е-0. В итоге, как опять же нетрудно догадаться, ответом будет 1.0000099е-0.

Итого: в ситуации, где ответ один и тот же, их легко может на самом деле получиться три разных. 🙂 С учётом того, что в вычислительных методах скалярное произведение векторов является одной из самых распространённых операций, возможные последствия представить нетрудно.

Этот пример, конечно, игрушечен, но и для реальных ситуаций настроить таких примеров очень нетрудно. Могу, например, с ходу сказать, что «отбрасыванием несоизмеримого» одно время грешили компьютеры от фирмы Fujitsu…

Математики-вычислители столкнулись с этой проблемой ещё в 1950-х годах. Решение её, казалось бы, очевидно: складывать произведения x[i]*y[i] не по возрастанию индексов, а по возрастанию их абсолютных значений. Что естественным образом означает сортировку массива. Способ дико затратный, но иногда приходилось делать и так. Потому что по-другому вообще не получалось.

Сейчас, конечно, делают проще. Просто-напросто объявляют накопитель r типа long double — максимально длинного доступного типа. Либо для накопления применяют специализированные подпрограммки с собственной длинной арифметикой — их немало гуляет в научном мире.

И студентов, конечно, предупреждают, да. Но они таки считают себя крутыми программёрами и редко слушают подобные предупреждения своих старых пердунов преподавателей. За что потом бывают тыкаемы носом в свои дурацкие ошибки… 😉

Старый тест для начинающих программистов. Разбор.

Итак, два дня назад я рассказал об одной задачке, некогда предлагавшейся для проверки мышления студентов — будущих программистов. Это было здесь.

Давайте посмотрим, что же в этой задачке такого хитромудрого, как её обычно решают, и как её надо решать.

Для начала посмотрим на лобовое решение, которое чаще всего и предлагают в качестве ответа. Вот оно:

long fact(long k) {
    long r=1;
    for(long i=1;i<=k;i++) r*=i;
    return r;
}

long C1(long m,long n) {
    return fact(n)/(fact(m)*fact(n-m));
}

Примерно так. Здесь нечего комментировать. Число сочетаний считается прямо по формуле, как отношение трёх факториалов, причём вычисление факториала вынесено в отдельную функцию.

На самом деле это вообще не решение. 🙂 Почему — станет понятно через несколько абзацев.

Реже предлагают следующий вариант:

long C2(long m,long n) {
    long mf=1, nf=1, nmf=1;
    for(long i=1;i<=n;i++) {
        nf*=i;
        if(i==m) mf=nf;
        if(i==n-m) nmf=nf;
    }
    return nf/(mf*nmf);
}

С точки зрения конечного результата он столь же никудышен, как и предыдущий. 🙂 Но идеологически авторов такого варианта уже есть за что похвалить — здесь замечено, что из трёх факториалов n!, m! и (n-m)! два последних сами по себе не нужны. Оба они меньше первого и de-facto всё равно считаются в процессе нахождения n! как промежуточные этапы. То есть наличествует анализ проводимых вычислений и определённая оптимизация программы.

А чем же плохи оба этих варианта? Очень просто: попробуйте для проверки посчитать любым из них… ну, например, следующее:

Сейчас угадаю — программа либо вылетит, либо даст неправильный ответ. 🙂

А чего ж вы хотели, считая факториалы?! 🙂 Факториал — это, знаете ли, такая штука, которая возрастает не очень быстро, а потрясающе быстро. В 2 байта (16 бит) не влезет уже 9!. В 4 байта (32 бита) не влезет уже 13!. В 8 байт (64 бита) не влезет уже 21!. В 16 байт (128 бит) не влезет уже 35!. Ну, вы поняли. При этом результаты, как видно из приведённого примера, вовсе не обязательно являются астрономическими числами.

Посмотрим на формулу внимательнее. Вот она ещё раз:

Давайте обозначим k=min(m,n-m) и K=max(m,n-m). В этих терминах можно записать, что

Теперь замечаем, что множители, образующие К!, полностью сокращаются. Итого в числителе и знаменателе остаётся по k сомножителей:

А зачем я написал сомножители в числителе по убыванию, а не по возрастанию? А вот зачем.

Смотрите. Всегда n будет нацело делиться на 1. Всегда n·(n-1) будет нацело делиться на 1·2, ведь из двух идущих подряд натуральных чисел одно обязательно делится на 2. Всегда n·(n-1)·(n-2) будет нацело делиться на 1·2·3, и так далее.

Вот так-то, парными умножениями-делениями, и надо накапливать результат. Соответствующий код очень прост:

long C3(long m,long n) {
    long k,r=1;
    k=(m<n-m)?m:n-m;
    for(long i=0;i<k;i++) r=(r*(n-i))/(i+1);
    return r;
}

Эта функция будет работать, если только ответ вообще влазит в разрядную сетку. Заметьте — никаких рекурсий, массивов, треугольников Паскаля, динамического программирования и прочих хитростей. 😉

Тут есть только одна тонкость. Обратите внимание на накопление результата r=(r*(n-i))/(i+1). Почему нельзя писать без скобок просто r=r*(n-i)/(i+1)? Да потому что умножение и деление имеют одинаковый приоритет — где гарантии, что компилятор не сгенерирует код, в котором сначала производится деление?! А вот оно делиться нацело вовсе не обязано!!! По той же причине нельзя писать в исконно С-шном стиле r*=(n-i)/(i+1) — здесь деление гарантированно выполняется первым, и результат будет заведомо неправильным.

Такая вот старая задачка. Надеюсь, вам понравилось. 🙂

Старый тест для начинающих программистов :-)

Последний мой пост вызвал вполне предсказуемую реакцию. 🙂 Точнее, целый набор легко предсказуемых реакций. Из которых я хотел бы затронуть лишь одну.

Типичным мнением старшеклассников и первокурсников является следующее: дело математиков формулы выводить, а мы, крутые программёры, будем их прогать. Математики всё равно в программёрстве не шарят нифига, полвека уже застряли на своём допотопном фортране, ну да ведь и нам их математика нужна лишь ровно настолько, чтоб эти формулы понимать.

Я думаю, не очень ошибусь, если предположу, что почти каждый современный школьник, написав первую в своей жизни программу, и решив учиться на программёра, хоть раз в жизни, да подумал нечто подобное. 😉 Другое дело, что у большинства хватает ума не ляпать такое вслух, а из них значительная часть в процессе учёбы быстро понимает, что к чему. 🙂

Заблуждение это настолько старо, глупо и дремуче, что уже давно перестало вызывать улыбку, и тем более — желание с ним спорить. Но я в этой связи вспомнил один тест, который некогда предлагали студентам младших курсов — будущим программистам.

Вот он весь: необходимо написать программу для нахождения так называемого числа сочетаний (оно же — биномиальный коэффициент) по следующей формуле:

Не нужно даже компьютера, вполне достаточно написать на бумаге. И не стоит тратить время на проверку условий относительно n,m — будем считать, что входные данные задаются всегда корректно. На всякий случай напоминаю, что 0!=1.

Желающие могут попробовать, а я обещаю через пару дней разобрать этот тест. 🙂

Только не надо исходники и алгоритмы в комментарии. 😉

Scalability

Есть в цифровой фотографии — точнее, в её маркетинге — одна вещь, которая меня периодически раздражает.

Купите любую камеру, и в комплекте поставки вы найдёте диск с «программным обеспечением». С этим, думается, никто спорить не будет. Как же без него-то.

А вот теперь — на что спорим? Софт, который содержится на диске, обязательно будет отстойным. 🙂 У одних производителей бóльшим, у других меньшим, но отстоем. Я пока не встречал исключений из этого правила.

Во-первых, этот софт всегда очень тяжёлый, и его дистрибутив «весит» сотни мегабайт. Во-вторых, если его таки поставить, то вы увидите нечто, вусмерть обвешанное рюшечками, оборочками, звоночками и свисточками. Что никак не согласуется с понятием удобного интерфейса. В-третьих, функционал этого софта… Здесь одно из двух. Либо он в принципе нормален, но за рюшечками и оборочками им совершенно немыслимо комфортно пользоваться. Либо же он очень сильно урезан, и производитель услужливо предлагает вам купить «профессиональную» версию софта.

(Любопытно, что, например, бесплатная Picasa весит в дистрибутиве всего 10 Мб, а при этом имеет функционал, способный полностью удовлетворить абсолютное большинство фотографов-любителей…)

Нет, я прекрасно понимаю: у маркетологов есть свои причины на такие решения, и вообще я не являюсь типичным потребителем цифровых фотокамер, так что не мне их учить, и не мой это собачий бизнес. 🙂 Да и речь вообще пойдёт не о том. Просто с моей точки зрения это выглядит так.

А вот есть ещё такое понятие, как scalability. Очень важная штука в IT-сферах. Да и не только там. На русский его обычно переводят как «масштабируемость», но это в данном контексте не совсем адекватно.

Суть scalability проста: если ты придумал рабочую идею, то этого мало. Её ещё нужно реализовать так, чтобы она оставалась рабочей в реальных условиях и при реальных нагрузках.

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

Умение анализировать и решать такие проблемы составляет отдельную часть программёрского искусства. Люди, владеющие таким умением, ценятся весьма высоко… равно как и результаты их трудов, кстати. Высокая цена программных продуктов, чьи названия содержат в себе слова типа «Enterprise Version», берётся вовсе даже не с потолка. Чего бы там по этому поводу не орали кулхацкеры-линуксоиды…

Казалось бы, ну при чём тут цифровая фотография? 🙂 А вот мы уже и подошли к этому моменту.

При всех своих достоинствах мой новый Panasonic LX3 подтвердил сформулированное в самом начале правило. 🙂 Тот софт, который фирма положила в комплект от себя, оказался фуфлом. 🙂 Но они положили в комплект ещё и Silkypix, а это уже отдельный разговор.

Silkypix — очень хороший, известный и любимый многими фотографами RAW-конвертор. Умеет работать и со JPEG. Приятное дополнение, и я было обрадовался.

Рано обрадовался. 🙂

Это была SE-версия приложения. Special Edition, то есть. Special’ьность заключалась в том, что приложение лишили части функциональности. Так, чтобы оно работало только с файлами от камер Panasonic.

Чисто логически тут вообще возразить нечего. Чувак, ты стал владельцем камеры Panasonic. Поздравляем. Вот тебе к ней софтина, которая позволяет обрабатывать любые снимки с наших камер. Но работать с файлами от оборудования других производителей — извини, тут мы тебе помогать не обязаны. Это тебе нужно обращаться либо к ним, либо на рынок независимых решений.

Выкинуть поддержку чужих RAW-файлов — это легко. У них у всех даже и расширения разные. Закомментарить соответствующий кусок кода, да профильтровать список файлов в диалоге открытия так, чтобы кроме *.RW2 ничего не показывал.

А вот файлами JPEG гораздо забавнее. Их умеют снимать все камеры, и формат везде одинаков. 🙂 Как тут отличишь своё от чужого?

Способ на самом деле есть, и не такой уж он и мудрёный:

  1. Открыть файл на чтение;
  2. Считать начальный кусок файла (около трёх десятков Кб);
  3. Закрыть файл;
  4. Найти в считанном куске EXIF;
  5. Отпарсить (разобрать) найденный EXIF;
  6. По результатам парсинга принять решение;

Это реально работает, но вот тут-то в дело и вступает scalability!

Представим, что мы лазим по диску и его папкам диалогом открытия файлов. И в каждой папке при заходе в неё приложение пытается определять «свои» файлы.

Если папка содержит пару-тройку десятков файлов, то всё чудесно. А если там этих файлов несколько сотен? А — несколько тысяч?!  Опаньки.

Тут даже не нужно быть специалистом-девелопером, чтобы уверенно ответить: приложение будет глючить, гоняя диск в хвост и в гриву.

Ну вот оно и глючит не по-детски. 🙂 С моим фотоархивом, в котором папки содержат по несколько тысяч файлов с нескольких камер, это самое SE не способно работать в принципе. Посему и было снесено нафиг.

То есть с точки зрения scalability разработка Silkypix SE представляет собой образцовый пример того, как делать не надо. Отличное приложение доведено до совершенно непотребного состояния. Непотребного в самом буквальном смысле: оно перестало быть пригодным к употреблению.

Казалось бы, чего проще: взять готовый и рабочий софт, после чего отломать от него часть функционала. Агащазблин. Конечно, ломать всегда проще, чем строить. Но и ломать, блин, нужно с умом!

И ещё головоломки для программистов

Эти задачки я всегда считал гораздо более простыми, нежели опубликованные здесь и здесь. Однако опыт занятий со школьниками показал, что для них это не так. Посему — вот ещё одна порция.

Перестановка массива

Имеется одномерный числовой массив (целый или вещественный — неважно) известной размерности. Переставьте его элементы в обратном порядке, не пользуясь циклами. (Эмулировать цикл условным оператором и переходом по метке также нельзя!)

Приближение числа “е”

Основание натуральных логарифмов может быть приближённо найдено как сумма

е ≈ 1/(0!) + 1/(1!) + 1/(2!) + … + 1/(n!),

причём это приближение тем точнее, чем больше n. Напишите программу, вычисляющую данную сумму для указанного n без использования циклов. (См. замечание к предыдущей задаче.) На всякий случай напоминание: 0!=1

Счастливые билеты

Автобусные билеты нумеруются шестизначными числами от 000000 до 999999. Напишите программу, подсчитывающую количество «счастливых» билетов (сумма первых трёх цифр равна сумме трёх последних), не используя циклы с глубиной вложения больше трёх.

Интроспективное программирование

В далёком 1988 году, учась в девятом (по-нынешнему — десятом, предпоследнем) классе, на уроке информатики…

Тогдашняя информатика — это особая песня. Мне дважды повезло: в школе стояло несколько комплексов ДВК, а дома имелся спектрум (играться на котором ко мне бегало полкласса). Это были примитивные, но настоящие компьютеры, на которых можно было реально что-то освоить. Абсолютное большинство школ и школьников похвастаться этим отнюдь не могло.

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

На одном из занятий преподаватель поведал нам о хитрой программистской проблеме: написать такую программу, которая выдавала бы на печать собственный текст. Проблема действительно хитрая, начинающим программистам она кажется неразрешимой, ибо требует определённого выверта мышления.

Через пять минут (речь уже шла о чём-то другом) я поднял руку и заявил, что могу привести решение этой задачи в одну строку. Натурально, мне было тут же предложено обосновать своё заявление. Я взял мел и написал на доске:

10 LIST

У преподавателя отвисла челюсть. Одноклассники (те, которые на информатике не только штаны просиживали) заржали. Когда ситуация успокоилась, преподаватель стал объяснять мне, что это решение является нечестным, ибо использует специфическое языковое средство, очень сильно завязанное на среду программирования и т.п. В общем, я сам это вполне осознавал, однако требовательно спросил:

— Но ведь — сработает?!

Мы проверили. Оно действительно сработало. Дома я проверил на спектруме — оно сработало и там.

На следующее занятие преподаватель притащил журнал (кажется, это была «Наука и жизнь») со статьёй об этой задаче, показал мне в ней набор канонических ограничений на проблему и объяснил, почему моё решение ему не удовлетворяет. Я покивал и согласился. Мне было уже неинтересно: я нашёл своё решение, и тот факт, что оно было наглым и вызывающим, придавал ему в моих глазах лишь бóльшую привлекательность.

Три года спустя, уже в институте, я познакомился с теорией алгоритмов и вычислимых функций. Из тамошней теоремы о неподвижной точке следовало, что такая программа обязательно существует на любом алгоритмически полном языке. Тогда же я узнал, что такие программы называются интроспективными и после долгих раздумий написал настоящую программу — как сейчас помню, на Фортране-77 (но текст, к сожалению, не сохранился).

Но школьное решение по-прежнему казалось мне самым изящным: оно было кратким, лаконичным и, как я уже сказал, неожиданно-наглым. И я придумал его сам, причём практически моментально.

Позднее, в 2001 году я увидел в каком-то компьютерро-подобном журнальчике обзор интроспективной проблемы, где приводилось и моё «лист-решение». Разумеется, нашлись и другие оригиналы, додумавшиеся до того же хода. Но моё удовлетворение от этого ничуть не убавилось.

А вчера на функциональном анализе (бог знает, почему именно на нём — возможно, потому что там тоже есть теорема о неподвижной точке) студенты спросили меня об этой проблемке. Я подтвердил существование интроспекции и сказал, что мне известно решение на Бейсике, укладывающееся в десяток символов.

Остаток занятия безнадёжно пропал. 🙂 Они искали это решение, орали друг на друга и напрочь забыли о моём и функционального анализа существовании. 🙂 Не нашли. 🙂

Интересно, найдут ли? Всё-таки они не имели дела с терминальным Бейсиком…