it-swarm-eu.dev

Jak identifikujete případy „Edge“ u algoritmů?

V zásadě, jak zjistíte, který by mohl být váš nejhorší nebo nejlepší případ a další případy „okraje“, které byste mohli mít, než je budete mít, a jak na ně připravíte svůj kód?

27
Luis Armando

Na základě obsahu algoritmu můžete určit, jaké datové struktury/typy/konstrukty se používají. Poté se pokusíte porozumět (možným) slabým stránkám těch a pokusit se přijít s prováděcím plánem, který v těchto případech umožní jeho spuštění.

Algoritmus například vezme řetězec a celé číslo jako vstup a provede určité třídění znaků řetězce.

Zde máme:

String s některými známými zvláštními případy:

  • Prázdný řetězec
  • Dlouhý řetězec
  • Řetězec Unicode (speciální znaky)
  • Pokud je omezena na určitou sadu znaků, co se stane, když některé nejsou v dosahu
  • Lichá/sudá délka řetězce
  • Null (jako argument)
  • Ukončení bez null

celé číslo se známými zvláštními případy:

  • Min/MaxInt
  • Negativní pozitivní

Seřadit algoritmus, který by mohl selhat v následujících okrajových případech:

  • Prázdný vstup
  • Vstup 1 prvku
  • Velmi dlouhý vstup (možná délky max (typ dat použitý pro index))
  • Popel uvnitř kolekce, která bude tříděna
  • Nulový vstup
  • Duplicitní prvky
  • Kolekce se všemi prvky stejné
  • Vstup liché/sudé délky

Poté vezměte všechny tyto případy a vytvořte dlouhý seznam, který se snaží pochopit, jak se překrývají. Příklad:

  • Prázdné pouzdro na řetězec pokrývá prázdné pouzdro na shromažďování
  • Null string == null collection
  • atd.

Nyní pro ně vytvořte testovací případy :)

Krátké shrnutí: rozbijte algoritmus v základních blocích, pro které znáte okrajové případy a poté je znovu sestavte, čímž vytvoříte globální okrajové případy

30

„Edge“ má dva významy a oba jsou relevantní, pokud jde o případy Edge. Hrana je buď oblast, kde malá změna vstupu vede k velké změně výstupu, nebo na konec rozsahu.

Abychom identifikovali případy Edge algoritmu, nejprve jsem se podíval na vstupní doménu. Jeho hodnoty Edge by mohly vést k Edgeovým případům algoritmu.

Za druhé, podívám se na výstupní doménu a podívám se zpět na vstupní hodnoty, které by je mohly vytvořit. Toto je méně často problém s algoritmy, ale pomáhá najít problémy v algoritmech, které jsou navrženy tak, aby generovaly výstup, který pokrývá danou výstupní doménu. Např. generátor náhodných čísel by měl být schopen generovat všechny zamýšlené výstupní hodnoty.

Nakonec zkontroluji algoritmus, abych zjistil, zda existují podobné vstupní případy, které však vedou k odlišným výstupům. Nalezení těchto případů Edge je nejtěžší, protože zahrnuje domény i pár vstupů.

2
MSalters

Nemyslím si, že existuje nějaký algoritmus, který by určoval okrajové podmínky ... jen zážitek.

Příklad: pro bajtový parametr byste chtěli testovat čísla jako 0, 127, 128, 255, 256, -1, cokoli, co může způsobit potíže.

2
Steve Wellens

Toto je velmi obecná otázka, takže jediné, co mohu udělat, je vyhodit nějaké obecné, vágní nápady :)

- Případové hraniční případy. Př. pokud analyzujete řetězec, co se stane, pokud je řetězec prázdný nebo nulový? Pokud počítáte od x do y, co se stane v xay?
- Kód, který lze zjednodušit nebo D.R.Y.-ed. Jakákoli zbytečná složitost by mohla přidat věci, které by se mohly pokazit.

0
seand

Součástí dovedností při používání algoritmů je znát jejich slabiny a patholigické případy. Victorova odpověď dává několik dobrých tipů, ale obecně bych radil, že musíte téma důkladněji prostudovat, abyste se k tomu cítili, nemyslím si, že můžete dodržovat pravidla palce, abyste na tuto otázku mohli plně odpovědět. Např. viz Cormen , nebo Skiena (Zejména Skiena má velmi dobrou sekci o tom, kde používat algoritmy a co funguje dobře v určitých případech, Cormen jde do více teorie, myslím) .

0
Steve