Как QuickSort правильно юнит-тестами покрыть? Как вообще алгоритмы сортировок тестировать?

Здравствуйте, BlackEric, Вы писали:

BE>Как QuickSort правильно юнит-тестами покрыть? Как вообще алгоритмы сортировок тестировать?

подавать на вход массивы разной степени сортированности, например, и разных размеров.
Попробовать раные типы данных, если реализация обобщенная.
Ну и сравнивать результат с эталонным.

Здравствуйте, BlackEric, Вы писали:

BE>Как QuickSort правильно юнит-тестами покрыть? Как вообще алгоритмы сортировок тестировать?

Вот пример тестов:
https://github.com/brazzy/scrapbook/blob/master/quicksort/QuickSortTest.java

Здравствуйте, BlackEric, Вы писали:

BE>Как QuickSort правильно юнит-тестами покрыть? Как вообще алгоритмы сортировок тестировать?
генерить массивы:
1. из одного элемента
2. Из двух элементов (3 варианта: одинаковые, отсортированные по возрастанию, отсортированные по убыванию)
3. Генерить массивы n элементов: одинаковые, несортированный, сортированные по убыванию, сортированный по возрастанию.
Ну, и вообще пустой массив.

Здравствуйте, Михaил, Вы писали:

М>Здравствуйте, BlackEric, Вы писали:

BE>>Как QuickSort правильно юнит-тестами покрыть? Как вообще алгоритмы сортировок тестировать?

М>Вот пример тестов:
М>https://github.com/brazzy/scrapbook/blob/master/quicksort/QuickSortTest.java

Ну вот последний тест (testScrambled) — очевидная лажа. Без вывода исходного массива, который мы пытались отсортировать этот тест практически ничего не дает.

BE>Как QuickSort правильно юнит-тестами покрыть? Как вообще алгоритмы сортировок тестировать?

с помощью property-based testing, конечно. Самый что ни на есть классический пример применения оного вида тестирования.
Начинать с quickcheck (google: quicksort property based testing).

Здравствуйте, SkyDance, Вы писали:

BE>>Как QuickSort правильно юнит-тестами покрыть? Как вообще алгоритмы сортировок тестировать?

SD>с помощью property-based testing, конечно. Самый что ни на есть классический пример применения оного вида тестирования.
SD>Начинать с quickcheck (google: quicksort property based testing).

А зачем тестирование на случайных данных назвали property-based testing?

BFE>А зачем тестирование на случайных данных назвали property-based testing?

Потому что эти тесты проверяют соблюдение определенных свойств (properties).
А потом не просто вываливают на тебя "вот эта случайная последовательность из 10,000 шагов провалила тест", а вычисляют минимальную последовательность, которая проваливает тест (при условии отсутствия побочных эффектов, которые, очевидно, должны отсутствовать у алгоритов сортировки).

Это, как ни крути, будущее тестирования. Для тех, кто серьезно относится к тестированию — это даже не будущее, а настоящее.

Здравствуйте, SkyDance, Вы писали:

BFE>>А зачем тестирование на случайных данных назвали property-based testing?
SD>Потому что эти тесты проверяют соблюдение определенных свойств (properties).

А как тест на случайных данных может проверять что-то отличное от свойств ожидаемого результата?

SD>А потом не просто вываливают на тебя "вот эта случайная последовательность из 10,000 шагов провалила тест", а вычисляют минимальную последовательность, которая проваливает тест (при условии отсутствия побочных эффектов, которые, очевидно, должны отсутствовать у алгоритов сортировки).

Я правильно понимаю, что это "вычисление" минимальной последовательности выполняется перебором всех сокращённых вариантов путём отбрасывания части входных данных первой случайной последователности проволившей тест?

Здравствуйте, SkyDance, Вы писали:


SD>Потому что эти тесты проверяют соблюдение определенных свойств (properties).
SD>А потом не просто вываливают на тебя "вот эта случайная последовательность из 10,000 шагов провалила тест", а вычисляют минимальную последовательность, которая проваливает тест (при условии отсутствия побочных эффектов, которые, очевидно, должны отсутствовать у алгоритов сортировки).
SD>Это, как ни крути, будущее тестирования. Для тех, кто серьезно относится к тестированию — это даже не будущее, а настоящее.

О чем речь, можно подробнее с ссылками.

S>О чем речь, можно подробнее с ссылками.

Не знаю, насколько вы знакомы вообще с теорией тестирования, но если достаточно глубоко, и хочется понять, почему PBT это не "тестирование на рандомных данных", стоит взглянуть сюда: http://proper.softlab.ntua.gr/Tutorials/PropEr_testing_with_search_strategies.html

(один из авторов работает в моей команде)

Да, если нужно саму paper, то — здесь: http://proper.softlab.ntua.gr/papers/issta2017.pdf

Здравствуйте, SkyDance, Вы писали:

SD>Не знаю, насколько вы знакомы вообще с теорией тестирования, но если достаточно глубоко, и хочется понять, почему PBT это не "тестирование на рандомных данных", стоит взглянуть сюда: http://proper.softlab.ntua.gr/Tutorials/PropEr_testing_with_search_strategies.html

А если не очень глубоко знаком на уровне написания интеграционных и ютестов, где почитать эту теорию?

BFE>А как тест на случайных данных может проверять что-то отличное от свойств ожидаемого результата?

1. Потому что данные не обязательно случайные, их просто много.
2. Потому что проверяют не только полтора варианта, которые вспомнил/придумал программист, а огромное количество вариантов, включая те, о которых программист забыл.

Например: https://medium.com/@jlouis666/breaking-erlang-maps-1-31952b8729e6

Ввели в язык новую структуру данных, maps. Там были ограничения, и их пофиксили, ввели Big Maps. Вроде все работает. Генерируем данные, и:

13> eqc:quickcheck(maps_iso_eqc:prop_binary_iso_fg()).
....Failed! After 5 tests.
#{-3878269413 => hill,
  -1 => stone,
  #Fun<eqc_gen.133.121384563> => sand,
  <<3:2>> => 0.0} /= 
#{-1 => stone,
  -3878269413 => hill,
  #Fun<eqc_gen.133.121384563> => sand,
  <<3:2>> => 0.0}
Shrinking xxxx.x.xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx................................xxxxxxxxxxxxxxxxxxxxxxxxxxxx(x10)xxxxxxx(x1).x(35 times)

#{-1 => flower,2147483647 => flower} /=
#{2147483647 => flower,-1 => flower}
false

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

Aha! Failed after 5 tests, and it looks suspicious! The internal ordering of the map is suddenly reversed. This violates the assumption about the internal flatmap representation. Indeed, Wolfram Alpha reports that — apart from being a prime — 2147483647 is also 2³¹-1. It set off some alarm bells when I reported it[4], and a newer stable version of Erlang will have a fix

Пошли ковырять глубже, и начали генерировать наборы потенциальных коллизий: https://medium.com/@jlouis666/breaking-erlang-maps-4-4ebc3c64068c

The result was that we found some very subtle C promotion rule faults, where certain types did not retain the correct sign — and it was fixed in hours by the OTP team. The following counter example crashed the system:

L = 
    [{58550737262493, <<>>},
     {<<>>, foo},
     {85341895822066, <<>>}, {19777509566621, <<>>},
     {51721575960328, 0}, {58550737262493, 0.0},
     {<<>>, false}, {0.0, 97}, {<<>>, <<>>}, {97, flower},
     {74297973216378, []}, {<<>>, 0.0},
     {58550737262493, foo},
     {<<>>, 97}, {0.0, 97},
     {63445773516557, foo},
     {273492717750246, <<>>}, {flower, <<>>},
     {<<>>, flower}, {266279278943923, <<>>},
     {224705626119556, 0}, {<<>>, false}, {97, foo},
     {31395337272657, <<>>}, {31395337272657, 0},
     {20062927283041, false}, {184642643042326, <<>>},
     {94403308189279, <<>>}, {<<>>, false}, {0, 97},
     {10645228898670, 97}, {0, <<>>},
     {177142907243411, foo}].
M = maps:from_list(L).
Segmentation fault (core dumped)

Смог бы ты вручную такое найти? Да вряд ли.

Здравствуйте, Mamut, Вы писали:

BFE>>А как тест на случайных данных может проверять что-то отличное от свойств ожидаемого результата?

M>1. Потому что данные не обязательно случайные, их просто много.
Это дилетантский подход — проверять "много данных". Следует либо покрывать весь диапазон данных (если возможно), либо тесты на граничных условиях + тесты на случайных данных + тесты на невалидных данных.

M>2. Потому что проверяют не только полтора варианта, которые вспомнил/придумал программист, а огромное количество вариантов, включая те, о которых программист забыл.

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

M>Например: https://medium.com/@jlouis666/breaking-erlang-maps-1-31952b8729e6

Собственно, по ссылке в разделе Strategy излагается методологический подход используемый в данном случае.
(Правда я не заметил теста для пустого map)

M>Ввели в язык новую структуру данных, maps. Там были ограничения, и их пофиксили, ввели Big Maps. Вроде все работает. Генерируем данные, и:

M>#{2147483647 => flower,-1 => flower}
M>...
M>Смог бы ты вручную такое найти? Да вряд ли.

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

Но мой вопрос совсем о другом. Зачем property-based testing имеет такое вводящие в заблуждение название?

M>>1. Потому что данные не обязательно случайные, их просто много.
BFE>Это дилетантский подход — проверять "много данных"

Ничего дилетантского в этом нет

BFE>Следует либо покрывать весь диапазон данных (если возможно)

Property-based тесты позволяют тебе покрыть этот диапазон.

BFE>, либо тесты на граничных условиях + тесты на случайных данных + тесты на невалидных данных.

Свежо предание. Программисты, способные грамотно написать тесты на все граничные условия, все negative тесты и все positive тесты, настолько же редки, как и сверовакуумные лошади.

BFE>Вообще-то, программист не должен вспомнинать/придумывать, а должен действовать по известным методологиям.

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

BFE>Собственно, по ссылке в разделе Strategy излагается методологический подход используемый в данном случае.
BFE>(Правда я не заметил теста для пустого map)

Потому что пустой мап сгенерируется среди прочих данных.

BFE>Я находил такие и подобные ошибки как вручную, так и с помощью тестов. Так что, если я вижу число два миллиарда сто сорок семь миллионов четыреста восемьдесят три тысячи шесот сорок семь, то я уже знаю природу ошибки.

Как ты увидел это число? Оно тебе пришло во сне?

BFE>Но мой вопрос совсем о другом. Зачем property-based testing имеет такое вводящие в заблуждение название?

Твой вопрос не об этом. Ничего вводящего в заблуждение в названии нет.

Здравствуйте, Mamut, Вы писали:

BFE>>Следует либо покрывать весь диапазон данных (если возможно)
M>Property-based тесты позволяют тебе покрыть этот диапазон.

Как нельзя объять необъятное, так невозможно покрыть весь диапазон входных данных для функции сортировки.

BFE>>, либо тесты на граничных условиях + тесты на случайных данных + тесты на невалидных данных.

M>Свежо предание. Программисты, способные грамотно написать тесты на все граничные условия, все negative тесты и все positive тесты, настолько же редки, как и сверовакуумные лошади.

Зависит от области в который вы работаете.

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

BFE>>Я находил такие и подобные ошибки как вручную, так и с помощью тестов. Так что, если я вижу число два миллиарда сто сорок семь миллионов четыреста восемьдесят три тысячи шесот сорок семь, то я уже знаю природу ошибки.
M>Как ты увидел это число? Оно тебе пришло во сне?

Не. Когда меня учили программированию, мне сказали, что я должен его запомнить. С тех пор помню.

BFE>>Но мой вопрос совсем о другом. Зачем property-based testing имеет такое вводящие в заблуждение название?
M>Твой вопрос не об этом. Ничего вводящего в заблуждение в названии нет.
Ну рассажите мне, что я спрашиваю.

Здравствуйте, Mamut, Вы писали:


BFE>>Я находил такие и подобные ошибки как вручную, так и с помощью тестов. Так что, если я вижу число два миллиарда сто сорок семь миллионов четыреста восемьдесят три тысячи шесот сорок семь, то я уже знаю природу ошибки.
M>Как ты увидел это число? Оно тебе пришло во сне?

Классика, переполнение. Я как увидел 2147... срзу все понял. Вы, наверное, троллите?

M>>Как ты увидел это число? Оно тебе пришло во сне?
S>Классика, переполнение. Я как увидел 2147... срзу все понял. Вы, наверное, троллите?

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

BFE>>>Следует либо покрывать весь диапазон данных (если возможно)
M>>Property-based тесты позволяют тебе покрыть этот диапазон.
BFE>Как нельзя объять необъятное, так невозможно покрыть весь диапазон входных данных для функции сортировки.

Зависит от функции сортировки и данных. Так же как и возможность человеку написать все возможные тесты зависит от области в которой работаешь.

BFE>Зависит от области в который вы работаете.

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

Што.

M>>Как ты увидел это число? Оно тебе пришло во сне?
BFE>Не. Когда меня учили программированию, мне сказали, что я должен его запомнить. С тех пор помню.

И ты, безусловно, всегда пишешь тесты с этим числом?

BFE>>>Но мой вопрос совсем о другом. Зачем property-based testing имеет такое вводящие в заблуждение название?
M>>Твой вопрос не об этом. Ничего вводящего в заблуждение в названии нет.
BFE>Ну рассажите мне, что я спрашиваю.

Я тебе уже конкретно ответил. Но тебе мои ответы не нравятся. Более того, у тебя и программисты идеальные и пишут все тесты, и какие-то отдельные организации проверяют работу программистов, и так далее и тому подобное.

Здравствуйте, Mamut, Вы писали:

M>Именно. Ты его увидел после того, как его тебе уже показали. Ты готов его увидеть сразу и написать тест для него?

Для словаря сходу не додумался бы. Для арифметический операций или ф-ий да.