Czy należy przetestować złożoność algorytmiczną? Jeśli tak to jak?

Powiedzmy, że implementuję coś prostego, na przykład wyszukiwanie posortowanej listy / tablicy. Funkcja (w c #) wyglądałaby podobnie do:

static int FindIndex(int[] sortedList, int i);

Mogłem to zaimplementować i przetestować pod kątem funkcjonalności, ale z oczywistych powodów zwykle wolę wyszukiwanie binarne niż wyszukiwanie liniowe lub coś celowo głupiego.

Więc moje pytanie brzmi: czy powinniśmy pisać testy gwarantujące wydajność pod względem złożoności algorytmicznej, a jeśli tak, to w jaki sposób?

Zacząłem kłócić się po obu stronach części „czy powinieneś” tego pytania, ale chciałbym zobaczyć, co mówią ludzie bez moich argumentów, aby ich podpowiedzieć.

Jeśli chodzi o „jak”, to staje się bardzo interesujące :) Można było sparametryzować operator porównania i mieć test, którego operator porównania liczy porównania lub coś w tym rodzaju. Ale tylko dlatego, że możesz, nie oznacza, że ​​powinieneś ...

Czy ktoś jeszcze to rozważał (prawdopodobnie)? Dzięki.

Złożoność algorytmiczna jest konstrukcją teoretyczną i jako taka najlepiej „przetestować” ją ołówkiem i papierem. Nie można go skutecznie przetestować mechanicznie.

Absolutną wydajność można przetestować mechanicznie i przeprowadzić przydatne testy jednostkowe. Jeśli wydajność ma znaczenie, możesz określić próg: „zapytanie to nie powinno zająć więcej niż 50 ms na 10 ⁶ liczbach i nie więcej niż 60 ms na 10 ⁷ liczbach”. Dla którego możesz zbudować test jednostkowy.

Użytkownikowi końcowemu nie zależy na tym, czy algorytm jest liniowy czy logarytmiczny; dbają o to, czy ich interfejs nadal reaguje natychmiast, nawet jeśli mają w aplikacji dane roczne.

Chociaż nie jestem pewien, czy to narzędzie będzie szczególnie przydatne do testów jednostkowych, artykuł „Empirical Computational Complexity” autorstwa Goldsmitha, Aikena i Wilkersona opisuje metodę instrumentowania kodu i obserwowania jego dynamicznego zachowania na zestawie różnych danych wejściowych do badań empirycznych czerpać jego asymptotyczną złożoność. Program opisany w artykule jest oprogramowaniem typu open source i jest dostępny tutaj .

Mam nadzieję że to pomoże!

Najważniejsze jest, aby wypróbować go z dużymi zbiorami danych i sprawdzić, czy zajmuje to zbyt dużo czasu.

W moim doświadczeniu dostrajania wydajności, tak jak w tym przykładzie , dzieje się tak, jeśli jakiś algorytm to (na przykład) O (n ^ 2), może być w porządku, o ile procent czasu, jaki zajmuje, nigdy nie dostaje się na radar.

Jednak po otrzymaniu zestawu danych o rozmiarze, który może nie być widoczny, ale raz w roku, część całkowitego czasu pochłoniętego przez ten algorytm może stać się katastrofalnie dominująca.

Jeśli potrafisz to zrobić podczas testowania, jest to bardzo dobra rzecz, ponieważ niezwykle łatwo jest znaleźć problem, tak jakby to była prawdziwa nieskończona pętla.

Nie sądzę, że chcesz testować jednostki.

AFAIK, testowanie jednostkowe ma na celu upewnienie się, że kod robi to, co powinien, i że nie koncentruje się na wydajności.

Z Wikipedii : Nie można oczekiwać, że testy wykryją każdy błąd w programie: nie można ocenić każdej ścieżki wykonania we wszystkich programach oprócz najbardziej trywialnych. To samo dotyczy testów jednostkowych. Ponadto testy jednostkowe z definicji testują tylko funkcjonalność samych jednostek. Dlatego nie będzie wychwytywał błędów integracji ani szerszych błędów na poziomie systemu (takich jak funkcje wykonywane na wielu jednostkach lub niefunkcjonalne obszary testowe, takie jak wydajność). Testy jednostkowe powinny być wykonywane w połączeniu z innymi czynnościami testowania oprogramowania. Podobnie jak wszystkie formy testowania oprogramowania, testy jednostkowe mogą wykazywać tylko obecność błędów; nie mogą pokazać braku błędów.

Istnieją inne rodzaje narzędzi i wzorców do pomiaru wydajności. Jedno, co pamiętam, to testy akceptacyjne ukierunkowane na wymagania niefunkcjonalne.

Istnieje kilka innych, takich jak testy wydajności (które wykorzystują testy warunków skrajnych, testy obciążenia itp.).

Możesz również użyć narzędzi stresowych wraz z narzędziem kompilacji (mrówka, automatyczne studio kompilacji) jako części kroków wdrażania (to właśnie robię).

Krótka odpowiedź brzmi: nie, nie powinieneś się tym przejmować podczas testowania kodu przez jednostkę.

Przekazywanie komparatora i sprawdzanie, ile razy jest wywoływany, zadziała w prostych celach, takich jak sprawdzenie, czy liczba porównań podczas wyszukiwania w ustalonych danych wejściowych (powiedzmy new int[] { 1,2,3, ... , 1024 }) pozostaje poniżej 10. To przynajmniej wyjaśnij swoje zamiary dotyczące zachowania algorytmu.

Nie sądzę, aby testy jednostkowe były właściwą drogą do sprawdzenia, czy twój algorytm to O (log n); wymagałoby to losowego generowania danych, dopasowania krzywej i prawdopodobnie ogólnych statystyk w celu ustalenia, czy wiązka punktów danych pasuje do oczekiwanego czasu działania. (W przypadku tego algorytmu jest to prawdopodobnie wykonalne, ale jeśli zaczniesz sortować itp., Trudne będzie powtarzanie najgorszych scenariuszy).