TDD как подход к алгоритмическим задачам

10

Я потерпел неудачу в алгоритмическом тесте с Codility, потому что пытался найти лучшее решение, и в итоге у меня ничего не было.

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

Если бы я писал алгоритм сортировки, я мог бы перейти от стандартной Bubblesort к двухсторонней пузырьковой сортировке, но тогда что-то более продвинутое, например, Quicksort, было бы «квантовым скачком», но по крайней мере у меня были бы тестовые данные, которые я мог бы легко проверить.

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

Под «Алгоритмическими» против «обычных» задач я имею в виду проблемы, в которых важна временная сложность. Таким образом, вместо того, чтобы проходить больше тестов, как в TDD, вы должны заставить его «вести себя лучше».

С "подобным TDD" я имею в виду:

  1. Напишите относительно автоматический тест, чтобы сэкономить время при ручном тестировании или приращении.
  2. Инкрементальное развитие.
  3. Регрессионное тестирование, способность обнаруживать, если код нарушается или, по крайней мере, если функциональность изменяется между приращениями.

Я думаю, что это должно быть довольно легко понять, если вы сравните

  1. Написание шелл-сортировки напрямую
  2. Переход от пузырьковой сортировки к быстрой сортировке (полное переписывание)
  3. Переход от односторонней сортировки пузырьков к сортировке оболочек (если возможно).
Олав
источник
Что вы подразумеваете под "похожим на TDD"? Очевидно, вы можете попытаться использовать TDD для разработки функции сортировки, а затем использовать модульные тесты для проверки функции, которая по-прежнему работает, когда вы заменяете алгоритм сортировки на более эффективный, но, похоже, у вас другой вопрос?
Док Браун
"постепенно" :-) - см. последнее предложение с добавлением "Так что вместо этого ..."
Олав
2
Конечно, вы можете сначала попытаться решить множество проблем с помощью рабочего (но не очень эффективного) решения, а затем улучшить его. Это никоим образом не ограничивается алгоритмическими или программными проблемами и не имеет ничего общего с TDD. Отвечает ли это на ваш вопрос?
Док Браун
@DocBrown No - см. Пример Bubblesort / Quicksort. TDD "работает" хорошо, потому что инкрементальный подход хорошо работает для многих типов проблем. Алгоритмические проблемы могут быть разными.
Олав
Таким образом, вы имели в виду «возможно ли решать вопросы разработки алгоритма поэтапно» (точно так же, как TDD - инкрементальный подход), а не «TDD», верно? Просьба уточнить.
Док Браун

Ответы:

9

Смотрите также попытку Рона Джеффриса создать решатель судоку с TDD , который, к сожалению, не сработал.

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

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

Вот почему базовое образование по теории CS в сочетании с большим количеством практики программирования алгоритмов одинаково важны. Знание того, что существует особая «техника» (небольшие строительные блоки алгоритмов), - долгий путь к этим постепенным квантовым скачкам.


Однако есть некоторые важные различия между постепенным прогрессом в алгоритмах и TDD.

JeffO упомянул одно из различий : тест, который проверяет правильность выходных данных , отделен от теста, который утверждает производительность между различными реализациями одного и того же алгоритма (или различными алгоритмами, претендующими на то же решение).

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

При разработке алгоритма требование обычно не меняется. Тест проверки правильности результата пишется первым или вскоре после завершения черновой (очень уверенной, но медленной) реализации алгоритма. Этот тест на корректность данных редко изменяется; никто не меняет его на неудачный (красный) как часть обряда TDD.

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

Если требование изменяется, оно обычно требует другого алгоритма.

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

Следовательно, при разработке алгоритма тест на корректность и тест производительности не являются тестами TDD. Вместо этого оба являются регрессионными тестами . В частности, регрессионный тест на корректность не позволяет вносить изменения в алгоритм, которые нарушают его корректность; Тест производительности не позволяет вносить изменения в алгоритм, который замедляет его работу.

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

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


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

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

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

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

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


В TDD акцент также делается на «микро-требованиях» (или скрытых качествах). Например, валидация параметров, утверждения, создание и обработка исключений и т. Д. TDD помогает обеспечить правильность путей выполнения, которые не часто используются при нормальном ходе выполнения программного обеспечения.

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

rwong
источник
Что означают первые два цитируемых слова в вашем посте («Дядя Боб»)?
Роберт Харви
@ RobertHarvey По словам дяди Боба, TDD можно использовать для обнаружения алгоритма. Согласно другому светилу, это не работает. Я думал, что следует упомянуть и то, и другое (то есть каждый раз, когда кто-то упоминает один пример, один также обязан упомянуть другой пример), чтобы люди получали сбалансированную информацию о положительных и отрицательных примерах.
Руонг
ХОРОШО. Но ты понимаешь мое замешательство? Ваш первый абзац, кажется, цитирует кого-то, произносящего слова «Дядя Боб». Кто это говорит?
Роберт Харви
Заказ @RobertHarvey выполнен.
17
2

Для вашей проблемы у вас будет два теста:

  1. Тест, чтобы убедиться, что алгоритм все еще точен. например, правильно ли отсортировано?
  2. Тест сравнения производительности - имеет улучшенную производительность. Это может быть сложно, поэтому помогает запустить тест на той же машине, с теми же данными и ограничить использование любых других ресурсов. Выделенная машина помогает.

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

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

JeffO
источник
1

Таким образом, вместо того, чтобы проходить больше тестов, как в TDD, вы должны заставить его «вести себя лучше».

Вроде.

Вы можете проверить время выполнения и сложность. Испытания во время выполнения должны быть немного прощающими, чтобы допустить конкуренцию за системные ресурсы. Но во многих языках вы также можете переопределять или внедрять методы и считать реальные вызовы функций. И, если вы уверены , что ваш текущий алгоритм не является оптимальным, вы можете ввести тест , который просто требует , чтобы sort()Invoke compare()меньшего количества раз , чем наивная реализация.

Или вы можете сравнить sort()два набора и убедиться, что они масштабируются в compare()вызовах в зависимости от вашей целевой сложности (или около того, если вы ожидаете некоторой несогласованности).

И, если вы не можете теоретически доказать , что множество размеров Nдолжно требовать строго не более N*log(N)сравнений, это может быть разумно ограничить уже работает sort()на N*log(N)призывания compare()...

Однако ...

Выполнение требования к производительности или сложности не гарантирует, что базовой реализацией является {AlgorithmX} . И я бы сказал, что это нормально. Неважно, какой алгоритм используется, при условии, что ваша реализация соответствует вашим требованиям, включая любые важные требования к сложности, производительности или ресурсам.

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

  • Обеспечение выполнения именно ожидаемого количества вызовов compare()и swap()(или чего-либо еще)
  • Обертывание всех основных функций / методов и обеспечение, с предсказуемым набором данных, что вызовы происходят в точно ожидаемом порядке
  • Изучение рабочего состояния после каждого из N шагов, чтобы убедиться, что оно изменилось точно так, как ожидалось

Но опять же, если вы пытаетесь убедиться, что {AlgorithmX} используется в частности, вероятно, есть какие-то особенности {AlgorithmX}, которые вас интересуют, которые важнее проверить, чем то, использовался ли {AlgorithmX} в конце концов ...


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

svidgen
источник
Отличное замечание относительно возможности установления границ по количеству операций. Я бы сказал, что это сила (издевательства, заглушки и шпионы), то, что может быть использовано в TDD, которое также может быть использовано в других видах испытаний.
rwong
Я не вижу особого смысла в написании тестов перед кодом в тестовом сценарии. Обычно это последний критерий после выполнения функциональных критериев. Иногда вы можете использовать случайные числа вначале и наихудший случай после, но все равно написание теста займет много времени по сравнению с некоторыми умными распечатками. (С некоторой статистикой вы, вероятно, могли бы написать некоторый общий код, но не во время теста.) В реальном мире, я думаю, вы хотели бы знать, вдруг ли производительность падает в определенных случаях.
Олав
Если вы посмотрите на codility.com/programmers/task/stone_wall, вы узнаете, если у вас сложность больше N, за исключением особых случаев, когда вам приходится работать, например, на очень длинных отрезках .
Олав
@Olav «написание тест может занять много времени , по сравнению с некоторыми умными распечатками» ... чтобы сделать один раз ... гм .. возможно , но и очень спорно. Делать многократно при каждой сборке? ... Точно нет.
svidgen
@Olav "В реальном мире, я думаю, вы захотите узнать, не снижается ли производительность в некоторых случаях." В реальных сервисах вы будете использовать что-то вроде New Relic для мониторинга общей производительности, а не только для определенных методов. И в идеале ваши тесты сообщат вам, когда критически важные для производительности модули и методы не соответствуют ожиданиям перед развертыванием.
svidgen