*** ВНИМАНИЕ: Блог переехал на другой адрес - demin.ws ***

среда, 28 апреля 2010 г.

Programming with GUTs


Вчера был на тренинге Kevlin’a Henny под названием «Programming with GUTs». (Кевлин автор нескольких книг, например «Things Every Programming Should Know»)

«GUT» – это сокращение от Good Unit Tests.

Также я узнал выражения «Programming with BUTs» (Brittle Unit Tests) и «Programming with NUTs» (No Unit Tests).

Итак, «...with GUTS» - это хорошо, «...with BUTs» - хуже, «...with NUTs» - безумие.

Вся эта терминология построена на игре слов guts, butt и nuts в английском языке, которые своим двойным смыслом примерно отражают ситуацию в проекте, когда тестирование находится на указанном уровне (Good, Brittle, No).

Дядька очень интересно ведет беседу, нескучно. Вовремя переходит от приколов к важным выводам, что, например, что ошибки – это не зло, а данность (процесс создания программа сложен, и ошибки – это часть процесса), поэтому очень важно уметь использоваться их для своих целей. Глупо исправлять баг, не написав для него unit- или regression- тест, так как без теста информация, которую несет в себе баг-репорт, будет потеряна по исправления ошибки.

Не могу сказать, что я узнал что-то радикально новое для себя, хотя услышал несколько интересных мыслей и аналогий.

Например, дежурный вопрос менеджера (не очень умного менеджера) проекта: «А если мы будем практиковать TDD в разработке, это замедлит процесс?». И ваш правильный и политический верный ответ будет решительное «ДА!». «А правда, что написание тестов вместе с кодом призвано затормозить работу разработчика?». «ДА!!!».

В короткой перспективе – да, но в долгосрочной – нет, а совсем наоборот.

Есть хорошая аналогия. Можно ли доехать из места А в место Б на машине, у которой нет традиционных тормозов (а например, только ручник)? Теоретически да. Очень очень медленно, правильно используя торможение двигателем и ручником. Задача будет решена, но очень не быстро, и вероятность облажаться очень высока. А вот если машину оборудовать нормальными тормозами (~unit-тестами), цель которых останавливать машину (и увеличивать время достижения цели), то они также позволят активно разгоняться между торможениями, и как результат – приехать быстрее.

Мораль – тесты позволяют взять ваш код под контроль, превратить его из телеги, несущейся с горы на огромной скорости, в гоночный болид, который ездит также быстро, как и останавливается. Тесты радикально затормозят вас, когда это нужно. Но с другой стороны они позволят не дрожать всем телом, когда надо потрогать какой-то очень важный кусок кода (например, библиотеку строчек), а спокойно провести рефакторинг и проверить результаты.

Все эти посылы просто TDD очевидны и однозначно разумны, но я был поражен до глубины души, когда кто-то таки спросил из зала, а если я, мол, просто буду писать много комментариев, чтобы всем было понятно, что код делает. И это был не вопрос-прикол. Кто-то спросил это на полном серьезе.

По поводу комментариев была приведена также интересная аналогия. Комментарии в коде – это золото. Но золото обесценивается, когда его становится слишком много. Комментариев много бывает (особенно бесполезных).

На лабах было интересное задание. Программисту дается задание написать класс и unit-тесты для него. Затем эти тесты уже без кода класса даются другому программисту, и его просят воспроизвести функционал класса, основываясь только на тестах к нему. Результаты порой «радуют» даже продвинутых бойцов TDD.

Вывод как всегда простой: тестируйте как можно раньше, тестируйте чаще, тестируйте автоматизировано. Тестирование – это часть работы программиста в первую очередь, а тестера – во вторую.

P.S. Небольшое задание для интересующихся. Допустим, вы написали собственный алгоритм сортировки. Как его тестировать? Каковы будут критерии проверки, что результат такой, какой вы ожидаете?

среда, 21 апреля 2010 г.

Смесь двоичной и десятичной арифметики

Многие знают, что происходит при выполнении присваивания "n &= (n - 1);" просто потому, что это весьма распространенный шаблон, и для чего может понадобиться выполнение его в цикле, пока n не станет нулем.

Интересно другое: четкое математическое (и/или алгоритмическое) объяснение, почему это работает именно так, строгое доказательство.


Update:

Чтобы разобраться в вопросе надо понять, что является корнем недопонимания.

Для людей, не часто имеющих дело с двоичной системой, обычно не совсем очевидна суть трансформации внутреннего двоичного представления числа при выполнении арифметической операции в десятичной нотации. Кажется, что если вычесть единицу, то расположение битов после операции будет иметь мало общего с тем, что было до вычитания. И дальнейшее выполнение "and" вообще не имеет смысла.

С точки зрения битового представления любого числа, есть только два случая:

1. Если число нечетное, на конце будет единица: "xx...xx1". Вычитание из такого числа даст: "хх...хх0". Поэтому "(xx...xx1) & (xx...xx0)" даст "(xx...xx0)". Фактически, мы убрали младший бит.

2. Если число четное, на конце будет ноль (или несколько нулей): "xx...xx100...00". Видно, что вычитание единицы из такого числа однозначно не изменит разряды "xx...xx", стоящие слева после первой единицы. Более того, результат вычитания единицы однозначно предсказуем: "xx...xx011...11". Теперь точно видно, что будет после операции "and": ("xx...xx100...00") & ("xx...xx011...11") даст ""xx...xx000...00". То есть мы убрали единицу из самого младшего ненулевого разряда.

Теперь ясно видно, что именно проиходит в присваивании "n &= (n - 1);". А именно, обнуление самого младшего ненулевого разряда.

Использование этого трюка в цикле, пока n не равно нулю, позволяет подсчитать количество ненулевых бит. На каждой итерации мы "выбиваем" ровно один бит, поэтому Число итераций будет равно количеству единиц в n.

понедельник, 19 апреля 2010 г.

Презентация про HTML5

HTML5 презентует сам себя: http://apirocks.com/html5/html5.html

На меня это произвело весьма сильное впечатление, особенно, когда многое собрано в одном месте и работает прямо в самой "презентации".

У меня под Chrome все работает. Не уверен про IE, но, говорят, что под FireFox тоже все работает.

пятница, 16 апреля 2010 г.

Можно ли memset'ить float и double?

В финансовой области постоянно приходится иметь дело с ценами, а цены удобно держать как float или double. Также финансовой сфере много старого когда, написанного на С или Фортране.

А в мире языке С практика инициализации структур нулем через memset является весьма распространенной и в целом не самой плохой практикой.

Вопрос: а что, если в структуре есть поля типа double или float. Что будет, если поля этих типов будут тупо забиты нулями, каково будет значение этих полей?

Для начала я проверил у себя на Солярисе и в Visual Studio 9 - все вроде нормально. После memset'а нулем и float и double тоже равны нулю.

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

Вышла новая версия Google Test 1.5.0

Сегодня вышла новая версия правильной библиотеки для unit-тестирования Google C++ Testing Framework 1.5.0.

Пока обзор будет краткий (фактически, это просто перевод официального анонса):
  • assert'ы теперь можно безопасно запускать из разных потоков (работает на платформах, где есть pthreads)
  • при использовании предикатов в EXPECT_TRUE() теперь можно самому задавать сообщения их ошибках
  • библиотеку теперь можно собрать как DLL (эту возможность многие ждали)
  • "упакованная" версия теперь входит состав дистрибутива, и ее не надо создавать самому через скрипт ("упакованная" версия - это просто два файла "gtest.h" и "gtest-all.cc", которые можно добавить в проект и не возиться с двоичной библиотекой)
  • система сборки теперь работает через CMake (это фантастически удобно)
  • добавлены две новые платформы: Solaris и AIX
  • убрана поддержка VC++ 7.1 с отключенными исключениями (если исключения включены, то все еще можно компилировать в VC++ 7.1)
Для тех, кто слышит про Google Test впервые, ниже предыдущие посты о Google Test и о тестировании в целом (многие на русском языке):

Задача про поиск середины связного списка

Сегодня был озадачен следующим вопросом (у нас его иногда задают на интервью), требующим потенциально ответа в 5-10 минут, желательно с примером кода.

Найти середину связного списка за один проход. Длина заранее не известна, а есть только указатель на голову.

Кто не догадается, смотрите комментарии. Уверен, там задачу быстро "возьмут".

Задача очень жизненная, и реально полезно знать решение.

Как научиться решать задачи подобного рода? алгоритмические программистские задачи? В чем суть обучения?

Есть определенная категория программистов, которым я профессионально завидую. Это бойцы спортивного программирования типа TopCoder'а, Google Code Jam'а и прочих контестов. Для которых что-то вроде поиска цепочек в частично упорядоченном множестве как для меня сложить две переменные. Там, где мне надо открыть книгу или хотя бы Википедию, они это пишут сходу из головы.

Из личного опыта, перед некоторыми интервью, я мог на память сходу написать любую базовую сортировку, вставку в красно-черное дерево, послойный обход дерева и многое другое. Но проблема в том, что это ни разу не помогало на интервью! Все что я в итоге решал (или не решал), было связанно с задачами, которые могли быть в разы проще любой сортировки или дерева, но требовали "догадаться". И основном спортивное программирование построено на теме "догадаться как".

Но как научиться догадываться? Есть ли какая-то методика обучения? Именно методика, а не "решай все подряд, и все тебе будет". Второй подход, конечно, работает, но методика могла бы ускорить процесс, сделать его более эффективным.

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

То есть тут есть методика, которая помогает тебе найти связь между теорией и задачей. Конечно, есть задачи, в которых "надо догадаться", но это как опция, нежели норма. Тебе дается инструмент, когда зная малое, можно решать многое.

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

Кстати, сравним среднего выпускника MIT и МАИ (я там учился). Наверное, выпускник MIT потенциально "сильнее" выпускника МАИ (при всей моей любви и уважении к Альма-матер). Почему? Там книги другие? Там профессора хуже? Я не могу пожаловаться, что мой курс программирования, где изучались алгоритмы был недостаточен.

Пока у меня только одно объяснение - скажем так, в объективно престижных ВУЗах просто больше прессуют и фактически заставляют учиться (иначе - это пустая трата денег и большой шанс вылететь).

Выходит, что количество так или иначе переходит в качество. И никакой магии.

четверг, 8 апреля 2010 г.

Задачи на интервью

Лично я считаю, что задавать на интервью программиста около математические задачки или задачи типа «на сообразительность» – это бесполезно (а значит не нужно). Почему? Моя логика крайне проста. Какова цель интервью? Как можно точнее понять, подходит ли вам человек по нужным критериям. А что именно скажет вам о человеке факт того, что он решил или не решил математическо-логическую задачу? Поможет ли это оценить уровень знаний кандидата в матанализе или теории вероятности, алгебре и даже арифметике? Нет. Ибо подобные задачи нельзя классифицировать по сложности, а значит и по ожидаемому уровню знаний, необходимому для их решения.

Например, задача, часто применяемая (не мной) на интервью.

Из двух городов навстречу друг другу едет велосипедист и летит муха. Скорость мухи в четыре раза быстрее велосипедиста. Когда велосипедист и муха встречаются где-то по середине, муха разворачивается и летит назад, а велосипедист также едет себе дальше. Когда муха возвращается в исходную точку, она разворачивается и снова летит на встречу велосипедисту. Когда они встречаются, все повторяется снова. Муха курсирует подобным образом от своего города до велосипедиста и назад то тех пор, пока велосипедист не приедет в ее город. Вопрос: каково соотношение расстояний, пройденных мухой и велосипедистом?

Задача для средней школы. Хотя лично мне будет без разницы, решит ее человек или нет. Ибо есть гораздо более конкретные вопросы и задачи, чтобы понять, что человек знает, умеет и любит делать. Обычно использование подобных задач призвано потешить самолюбие самого интервьюера типа «ну я то это решил в свое время!», но вот только не уточняется, за какое время.

В плане именно вопросов-задач, куда полезнее попросить написать небольшой код для обхода дерева (например, для поиска медианы в BST), или поиска кратчайшего пути в графе, или придумать на месте хеш-функцию для каких-то данных, или, например, спросить: до N какого порядка реально решать задачи с O(N^2), а O(N^3), а на кластере? и т.д. Подобные вопросы дают реальный выхлоп, который применим в жизни.

А уж если есть желание «проверить сообразительность», то куда полезнее вопросы на общее представления о мире вокруг и взаимосвязях в нем. Я как-то был реально озадачен, когда меня спросили «А сколько весит Боинг-747?». Я хоть и учился в МАИ, но точной цифры ни разу не знал. Но исходя и элементарных понятий и количестве людей в самолете, грузе, соотношении топлива и массы и т.д. – можно дать оценку, или что более важно, показать умение логически и реально мыслить.

Интервью – это не бенефис интервьюера. Это решение конкретной задачи поиска человека, максимально подходящего вашим требованиям (а неужели у кого-то в требованиях написано «должен уметь решать задачи школьной программы»? если да, это наем учителя средних классов, а не программиста).

Update: В комментариях подсказали полезную ссылку по теме.