Как проверить реализацию алгоритмов?

Question

Я думаю о тестировании реализации некоторых алгоритмов

Если вы думаете о фокусе TDD / BDD ... тест будет

 Scenario: doubling search
 Given an ordered array "[2,3,4,5,6,7]"
 When I look for "4" with "doubling search" in it
 Then the result must be "2"

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

Answer 1

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

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

// double search implemented by using the search and multiplying by 2
algorithm multDoubleSearch
   define input array
   define input search

   for each i in array
      if i = search * 2
           return index of i
   end
   return -1
end.

// double search implemented by dividing the values by 2
algorithm divDoubleSearch
    define input array
   define input search

   for each i in array
      if i / 2 = search
           return index of i
   end
   return -1
end.


test mytest
     define array {2 3 4 5 6 7}
     define search 2

     define resultMult = multDoubleSearch(array,search)
     assert resultMult == 2 // 4 is index 2, assuming 0 indexed

     define resultDiv = divDoubleSearch(array,search)
     assert resultDiv == 2 // 4 is index 2, assuming 0 indexed
end.

Answer 2

Ну, это зависит от того, ЧТО у вас под рукой.

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

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

В вашем конкретном случае вы можете просто сравнить свою версию с простым двоичным файломпоиск - который наверняка уже есть в стандартной библиотеке - создание массивов случайного размера со случайным вводом также не должно быть проблемой.