пятница, 28 ноября 2008 г.

Кризисный оффтоп: "увольнения"

То, что экономический кризис не коснулся меня лично, не значит, что его нет. Среди моих знакомых, работающих в банках и тому подобных организациях, уже есть пострадавшие, которых "уволили". Я не зря взял это слово в кавычки - странно называть увольнением, когда человека вынуждают писать заявление по собственному желанию. Я сужу со своей колокольни и поэтому не понимаю, что значит вынуждают? Что мешает человеку, отработавшему на одном месте больше года, отказаться писать заявление по собственному желанию? Страх, что в трудовую напишут какую нибудь гадость? Но насколько я знаю, написать гадость не так то просто, КЗОТ хоть как-то от этого должен защищать. Возможно дело именно в незнании своих прав и вынуждение - это эксплуатация работодателями этого незнания?

Получаются одни вопросы. Может ли кто-нибудь объяснить мне такое положение дел?

Read More...

четверг, 27 ноября 2008 г.

Тестирование "белого ящика"

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

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

// типы треугольников
enum type_t {t_scalene=1, t_isosceles=2,
t_equilateral=3, t_error=4};

type_t triangle_type(int sideA, int sideB, int sideC)
{
// проверка валидности треугольника -
// сумма длин двух любых сторон не должна превышать
// длину третьей стороны
if((sideA>0 && sideB>0 && sideC>0) && // 1
(sideA<(sideB+sideC))&&
(sideB<(sideA+sideC))&&
(sideC<(sideA+sideB)))
{
int ab = (sideA==sideB)?1:0; // 2
int ac = (sideA==sideC)?1:0; // 3
int bc = (sideB==sideC)?1:0; // 4

int num = ab+ac+bc;

// if num==0 - scalene
// if num==1 - isosceles
// if num==3 - equilateral
type_t types [] = {t_scalene, t_isosceles,
t_error, t_equilateral};
return types[num]; // 5
}

return t_error;
}

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

Почему одного запуска функции и получение нужного результата недостаточно? Программы очень редко выполняются строчка за строчкой - этому препятствуют всевозможные логические операторы if, for, while, until, or, and, switch. Они разветвляют код, создавая сложные пути исполнения одной и той же программы при разных входящих данных. И по всем этим путям нужно пройти, один запуск с одними параметрами - это проверка одного пути из многих. Значит тестов нужно не меньше, чем перечисленных выше ключевых слов в коде. (В рассматриваемом случае под тестами я понимаю вызов функции с различными наборами параметров.)

Первый if, в приведенной выше функции, проверяет четыре условия - длины сторон треугольника должны быть неотрицательными и длина каждой из сторон должна быть меньше суммы длин двух других. Все условия объединены операторами &&, поэтому достаточно невыполнения одного из них, что бы не выполнился код, следующий за if. Но неплохо бы знать, все ли условия вычисляются правильно. Поэтому нужно передать функции значения, которые будут true и значения, которые будут false для каждого из условий. Проверить это можно по возвращаемому значению t_error, в случае если любое из условий не выполняется. Хотя первое из условий является само по себе составным, но все проверки в нем довольно простые и объеденены оператором &&, поэтому допустим, что достаточно будет проверки, когда одна длина отрицательная и когда все длины положительные.

В случае успешного прохождения if, выполняются проверки, помеченные как 2, 3, 4. Они не создают больших ответвлений, но вычисляют значения, которые влияют на выбор нужного элемента массива types в строке 5. Количество выполненных условий записывается в переменную num, которая может принимать только три значения 0, 1, 3 (2 не может быть, так как при выполнении двух автоматически выполняется третье). Значит для тестирования этой части кода достаточно 3-х наборов входящих параметров - все стороны неравны (num==0), все стороны равны (num==3), равны только 2 стороны (num==1).

Больше ответвлений в программе не наблюдается, поэтому можно подводить итог. Для тестирования функции triangle_type, нужно передать ей 14 наборов входящих параметров (8 для условия 1, 6 для условий 2, 3, 4) и проверить возвращаемый результат. После этого можно быть уверенным, что в большинстве случаев поведение функции будет предсказуемым. Хотя нет... это только часть возможных проверок. Еще можно проверять передаваемые параметры, например, как будет вести себя функция при максимально и минимально допустимых значениях, но это уже отдельная тема. Я хотел рассказать только о тестировании, базирующемся на изучении кода. Это как раз то, что теоретически отличает тестирование программистами от тестирования тестировщиками - программисты тестируют не "черный ящик".

PS: Не смотря, на то что получилось много текста, на практике это занимает не так уж много времени :)

Read More...

суббота, 22 ноября 2008 г.

Задача про банку и дробь

В полевых условиях нужно получить свинцовую пластинку определенного объема. Из инструментов и материалов есть только охотничья дробь и политровая стеклянная банка с делениями, как мензурка. Есть так же все необходимое для плавления свинца, но это не поможет для решения задачи. А задача такая: как определить достаточный объем дроби? Дополнительное условие - при расчетах можно использовать только одно действие - вычитание.

Read More...

среда, 19 ноября 2008 г.

Удивительное рядом - shared_ptr и виртуальный деструктор

Интересную штуку про boost::shared_ptr прочитал здесь Storing dynamicly created objects in a container. Для shared_ptr не обязательно наличие виртуального деструктора у базового класса. Это не значит, что виртуальные деструкторы теперь не нужны, но может быть полезно, когда есть legacy-код без них и менять его нельзя.

Read More...

воскресенье, 16 ноября 2008 г.

Объединение двух отсортированных массивов

Как объединить два отсортированных массива (n1 и n2 элементов) в один отсортированный массив? Такой вопрос мне неоднократно попадался на собеседованиях и даже пару раз сталкивался с ним на практике. Вся сложность этого вопроса не в том как это сделать, а как это сделать максимально быстро.

Быстрее всего это делается за n1+n2 итераций (линейное время). Пусть есть два отсортированных по возрастанию массива A1 и A2. Можно легко определить первый элемент результирующего массива - им будет либо первый элемент первого массива, либо первый элемент второго массива, в зависимости от того, что меньше. Допустим, наименьший - это A1[0]. На следующей итерации при помощи одного сравнения определяется второй элемент результирующего массива - опять сравниваются первые элементы исходных массивов, при условии, что для A1 первый элемент - это A1[1], так как A1[0] - уже выбыл из игры. И так продолжается пока не будет заполнен результирующий массив. На картинке это выглядит так:


Как видно, ничего сложного в этом алгоритме нет. Самое интересное в нем - это возможность использования для сортировки. Любой массив размера n можно представить в виде n массивов, состоящих из одного элемента. Пары соседних элементов, представленных ввиде массивов можно объединять по описанному выше алгоритму. Получится примерно в 2 раза (примерно, потому что n может быть как четным так и нечетным числом) меньше отсортированных массива по 2 элемента, которые в свою очередь тоже можно объединить. И так пока не получится один отсортированный массив.
А все это называется сортировка слиянием.

Read More...

суббота, 15 ноября 2008 г.

Concepts в C++0x

Наконец то удалось посмотреть видео о новых расширениях С++ Concepts: Extending C++ Templates For Generic Programming. Решил поделиться своими впечатлениями.

Concepts - это расширение существующих шаблонов С++, позволяющие устанавливать требования к параметрам шаблона. Концепция позволяет ответить на несколько вопросов:

  • чем должен быть параметр?
  • что он должен уметь делать?
  • как установить соответствие между параметром и тем, чем он должен являться?

В ролике это называлось Concept definitions, Where clauses и Concept maps соответственно. Насколько я понимаю, то, что было озвучено и то, что будет в стандарте немного отличается, по крайне мере вместо where будет использоваться requires, поэтому пример будет выглядеть не как в видео:
// Вычисление суммы элементов последовательности

// Параметр шаблона должен быть Forward Iterator -
// позволяет двигаться только в перед
template< ForwardIterator Iter >
// два значения, на которые указывают итераторы,
// могут быть сложены при помощи оператора +
requires Addable< Iter::value_type >,
// объект, на который указывает итератор,
// должен иметь оператор присваивания
&& Assignable< Iter::value_type >
Iter::value_type sum(Iter first, Iter last,
Iter::value_type result)
{
for (; first != last; ++first)
result = result + *first;
return result;
}

// у типа double* нет оператора сложения, присваивания,
// получения следующего элемента последовательности,
// но реализация алгоритма sum будет корректно работать
// с этим типом, поэтому устанавливается соответствие
// между ForwardIterator и double*
concept_map ForwardIterator {
typedef double value_type;
};

Надеюсь, теперь понятно, зачем вводятся concepts, если нет, то подробней можно почитать здесь: ConceptC++ Tutorial.

На видео, дядька приводит другой пример, знакомый всем, кто использовал STL: простой алгоритм поиска, реализованный в соответствие с требованиями STL, отлично работает с вектором, но не хочет работать со списком. Хотя внешне все вписывается в общую структуру библиотеки: контейнеры - итераторы - алгоритмы. Для того, что бы понять, что не так с алгоритмом нужно копаться в его коде либо использовать concepts. Начиная с этого места у меня появилось чувство, что concepts - это костыль, который подсовывают С++. Проблема как была, так и осталась, но теперь можно уверенно хромать в перед. Лечится только следствие проблемы - теперь компилятор будет сам говорить, что хотя все вписывается в рамки, но работать все равно не будет. При этом, возможность писать неработающий код так и остается - для совместимости с предыдущими версиями.

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

Это первое впечатление, основанное на двухчасовом знакомстве с этим нововведением. Надо будет еще обдумать прочитанное и просмотренное, а то прям бесполезная какая-то штука получается :) Поэтому интересно было бы услышать критику моего обзора и мысли по поводу concepts.

Read More...

четверг, 13 ноября 2008 г.

Задачка про прилив

Нашел в шкафу старую книгу "Математическая смекалка". Замечательная книга! Теперь по вечерам сижу с удовольствием решаю задачки - неплохая гимнастика для мозгов и хорошая альтернатива вечернему созерцанию интернета. Вот одна из задач, которая мне понравилась (кстати, ничем не хуже майкрософтовских :)

Недалеко от берега стоит корабль со спущенной на воду веревочной лестницей вдоль борта. У лестницы 10 ступенек; расстояние между ступеньками 30 см. Самая нижняя ступенька касается поверхности воды. Океан сегодня очень покоен, но начинается прилив, который поднимает воду за каждый час на 15 см. Через сколько времени покроется водой третья ступенька веревочной лесенки?

Read More...

вторник, 11 ноября 2008 г.

Python 3 Patterns & Idioms

Стала доступна open source книга Python 3 Patterns & Idioms, написанная Bruce Eckel при содействии Python community. Она распространяется под лицензией Creative Commons Attribution-Share Alike 3.0 (первый раз о такой слышу :).

Книга еще сыровата, по крайне мере в содержании все перемешано в кучу и некоторые главы отсутствуют. Большая часть посвящена паттернам, например, есть много про singleton, есть много про Jython, немного про юнит тестирование и TDD, рефакторинг, а так же упражнения к каждой главе. Самое интересное, что здесь кода больше, чем букафф :)

Read More...