Jak rozpoznać przypadki „krawędziowe” w algorytmach?

Zasadniczo, w jaki sposób możesz dowiedzieć się, która może być twoją najgorszą lub najlepszą sprawą i jakimiś innymi „przypadkowymi” sprawami, które mógłbyś PRZED ich posiadaniem, a więc jak przygotować dla nich swój kod?

Na podstawie zawartości algorytmu można określić, jakie struktury danych / typy / konstrukcje są używane. Następnie próbujesz zrozumieć (możliwe) słabe punkty tych i próbujesz wymyślić plan wykonania, który sprawi, że będzie działać w takich przypadkach.

Na przykład algorytm pobiera ciąg znaków i liczbę całkowitą jako dane wejściowe i dokonuje sortowania znaków ciągu.

Mamy tutaj:

Łańcuch ze znanymi specjalnymi przypadkami:

• Pusta struna
• Długi sznurek
• Ciąg Unicode (znaki specjalne)
• Jeśli ogranicza się do określonego zestawu znaków, co dzieje się, gdy niektóre nie są w zasięgu
• Łańcuch o nieparzystej / parzystej długości
• Null (jako argument)
• Zakaz zakończony zerem

Liczba całkowita ze znanymi przypadkami specjalnymi:

• 0
• Min / MaxInt
• Negatywne / pozytywne

Algorytm sortowania, który może się nie powieść w następujących przypadkach granicznych:

• Puste wejście
• 1 element wejściowy
• Bardzo długie dane wejściowe (być może długości maks. (Typ danych używany do indeksu))
• Śmieci w kolekcji, która zostanie posortowana
• Brak danych wejściowych
• Zduplikowane elementy
• Kolekcja z wszystkimi elementami równymi
• Wprowadzanie nieparzystej / parzystej długości

Następnie weź wszystkie te przypadki i utwórz długą listę, próbując zrozumieć, w jaki sposób się pokrywają. Dawny:

• Pusta skrzynka na łańcuch obejmuje pustą skrzynkę kolekcji
• Ciąg zerowy == kolekcja zerowa
• itp.

Teraz utwórz dla nich skrzynki testowe :)

Krótkie podsumowanie : podziel algorytm na podstawowe bloki, dla których znasz przypadki graniczne, a następnie ponownie je złóż, tworząc globalne przypadki graniczne

Nie sądzę, aby istniał jakiś algorytm określający warunki brzegowe ... po prostu doświadczenie.

Przykład: dla parametru bajtu chciałbyś przetestować liczby takie jak 0, 127, 128, 255, 256, -1, wszystko, co może powodować problemy.

„Krawędź” ma dwa znaczenia i oba są istotne, jeśli chodzi o przypadki krawędzi. Krawędź jest albo obszarem, w którym niewielka zmiana na wejściu prowadzi do dużej zmiany na wyjściu, albo koniec zakresu.

Tak więc, aby zidentyfikować przypadki skrajne algorytmu, najpierw patrzę na domenę wejściową. Jego wartości krawędzi mogą prowadzić do przypadków krawędzi algorytmu.

Po drugie, patrzę na domenę wyjściową i patrzę wstecz na wartości wejściowe, które mogą je utworzyć. Rzadziej jest to problem z algorytmami, ale pomaga znaleźć problemy w algorytmach zaprojektowanych do generowania danych wyjściowych obejmujących daną domenę wyjściową. Na przykład generator liczb losowych powinien być w stanie wygenerować wszystkie zamierzone wartości wyjściowe.

Na koniec sprawdzam algorytm, aby sprawdzić, czy istnieją przypadki wejściowe, które są podobne, ale prowadzą do różnych wyników. Znalezienie tych przypadków brzegowych jest najtrudniejsze, ponieważ obejmuje zarówno domeny, jak i parę danych wejściowych.

To bardzo ogólne pytanie, więc wszystko, co mogę zrobić, to wyrzucić ogólne, niejasne pomysły :)

-Examine przypadków granicznych. Dawny. jeśli parsujesz ciąg, co się stanie, jeśli ciąg będzie pusty lub zerowy? Jeśli liczysz od x do y, co dzieje się w xiy?
-Kod, który można uprościć lub DRY-out. Każda niepotrzebna złożoność może dodać do rzeczy, które mogą pójść nie tak.

Częścią umiejętności korzystania z algorytmów jest znajomość ich słabości i przypadków patologicznych. Odpowiedź Victora zawiera kilka dobrych wskazówek, ale ogólnie radziłbym, abyś przestudiował ten temat głębiej, aby się zorientować, nie sądzę, że możesz przestrzegać ogólnych zasad, aby w pełni odpowiedzieć na to pytanie. Na przykład zobacz Cormen lub Skiena (w szczególności Skiena ma bardzo dobrą sekcję o tym, gdzie używać algorytmów i co działa dobrze w niektórych przypadkach, Cormen przechodzi do większej teorii, jak sądzę).