Thursday, December 22, 2011

Зачетный пример на TDD - Prime Factors

Недавно мне посчастливилось попрактиковаться в парном программировании с Johannes Brodwall во время его визита в Киев на конференцию XP Days. Мы, играючи в ТДД пинг понг, за пару часов реализовали 2 довольно сложных примерчика, так называемых kata для его coding dojo сессии на XP Days. Причем успели один из примеров реализовать не только на Java, но еще на CoffeScript.

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

Если ты еще не знаком с правилами ТДД пинг понг, то рекомендую посмотреть как это делается здесь или попрактиковаться на нашем треннинге по ТДД.

"Prime Factors" (не знаю как по-русски).
Разложить целое число на множители из простых чисел:
2 -> [2]
3 -> [3]
4 -> [2,2]
6 -> [2,3]
9 -> [3,3]
12 -> [2,2,3]
15 -> [3,5]
и так далее...

Итак, начали...
Johannes. Естественно с теста:

public class PrimeTest {
@Test
public void primeFactorOfOne() {
assertEquals("[]", Prime.factorsOf(1).toString());
}
Я. А че тут думать? Самая простая реализация - вот:
Тесты прошли, пишу следующий тест:
junit.framework.ComparisonFailure:
Expected  :[2]
Actual    :[]

Johannes. Тоже не особо думая
и, после запуска тестов - пытается отдать мне это:
Oops... тест зеленый, сори, мне идет эта подача:
junit.framework.ComparisonFailure:
Expected  :[2, 2]
Actual    :[4]

Я. Лень что-то придумывать сложное. Первая мысль - добавить тупой if и разделить на 2
как ни странно, но прошло. Тихо радуюсь про себя, что не мне реализовывать следующий тест:
junit.framework.ComparisonFailure:
Expected  :[5]
Actual    :[2, 2]

Johannes. Видимо, почувствовал мое злорадство и тоже долгими раздумьями над идеальным решением себя не утрудил:
и, как говорится, "получите, распишитесь" - забираю клавиатуру с таким красным тестом:
junit.framework.ComparisonFailure:
Expected  :[2, 3]
Actual    :[3, 3]

Я. Тут я немного подвис. Смотрю на то, как падает тест и не без помощи напарника понимаю, что для того, чтобы в списке появилась 2, а потом 3, нужно организовать цикл:
Ура! Работает! Все тесты зеленые. Пробую добавить тест на семерку - проходит. Поправляю на 8 и отдаю клавиатуру
junit.framework.ComparisonFailure:
Expected  :[2, 2, 2]
Actual    :[2, 4]

Johannes. Все, что надо сделать - это заменить if на while:

Все тесты зеленые! Я пытаюсь добавить тест на двухзнчные числа, потом думаю подловить, предав что-то вроде такого 2*3*5*7*11*13*17*19*23, потом отнимаю от этого выражения 1, затем 2 но поломать код не получается - тесты зеленые! Все, сдаюсь и соглашаюсь: РАБОТАЕТ!

На этом бы и поставить точку, но в вообще существуют еще нефункциональные требования, которые зачастую не так легко проверить при помощи TDD.
Этот алгоритм еще можно оптимизировать по скорости, но чтобы это почувствовать мы добавили такой тест, который выполнялся около 23 секунд:

И "пофиксили" его вот таким изменением:

Все, теперь не только РАБОТАЕТ, но и работает БЫСТРО!

7 comments:

  1. Отличный пример! Сразу начинаешь понимать зачем нужно TDD и параллельная разработка.

    Я вот только не до конца понял последний фикс. number/(i-1) - как это понимать?
    Еще интересный момент в C# такой фикс не дает прироста производительности.

    ReplyDelete
  2. Хороший вопрос :). Когда используешь ТДД не всегда задумываешься почему это работает. Работаешь по циклу: написал тест, пофиксил, заработало - поехали дальше :). В этом примере я тоже попал в этот водоворот и не сильно раздумывал почему этот алгоритм работает.
    Попробую объяснить почему работает на примере. Допустим, нам надо вычислить простые множители для числа 6.
    В случае с "неоптимизированным" алгоритмом были бы такие значения переменной цикла i и условие цикла:
    2 -> 2 < 6
    3 -> 3 < 6
    4 -> 4 < 6
    5 -> 5 < 6

    Как видишь последние две итерации лишние, т.к. 6 / 4 или 6 / 5 не даст целого результата. Поэтому условие цикла можно изменить разделив на последнее пройденное значение переменной цикла.

    ReplyDelete