C: Třídění analytické metody

hlasů
7

Mám spoustu různých třídicích algoritmů, které mají všechny následující podpis:

void <METHOD>_sort_ints(int * array, const unsigned int ARRAY_LENGTH);

Existují nějaké testování apartmány pro třídění, které bych mohl použít pro účely výroby empirické srovnání?

Položena 27/08/2009 v 04:52
zdroj uživatelem
V jiných jazycích...                            


4 odpovědí

hlasů
10

Tento podrobný diskuze , stejně jako napojení na velké množství souvisejících webových stránek, které by mohly být užitečné, také popisuje užitečný soubor vstupních dat pro testování třídění algoritmy (viz odkazované stránky důvodů). Shrneme-li:

  1. Zcela náhodně zamíchány pole
  2. Již řazeno array
  3. Již řazeny v poli opačném pořadí
  4. Chainsaw array
  5. Pole stejné prvky
  6. Již řazeny pole s N permutací (s n od 0,1 do 10% velikosti)
  7. Již řazeny pole v obráceném pořadí pole s N permutací
  8. Údaje, které mají normální rozdělení s tlačítky duplicitní (nebo v blízkosti) (pro stabilní třídění pouze)
  9. Pseudonáhodná data (denní hodnoty S & P500 nebo jiným indexem za deset let by mohl být dobrý test Zde se nastavuje, jsou k dispozici od Yahoo.com)
Odpovězeno 02/09/2009 v 11:10
zdroj uživatelem

hlasů
7

Definitivní Studie třídění je Bob Sedgewick ‚s disertační práce. Ale je tu spousta dobrých informací v jeho algoritmy učebnicích, a ty, které jsou první dvě místa bych hledat testovací sady a metodiky. Pokud jste měli nedávno kurzu budete vědět víc než já; Naposledy jsem měl kurz, nejlepší metoda měla používat quicksort až do oddílů o velikosti 12, spusťte vložení druh na celé pole. Ale odpovědi změnit tak rychle, jak hardware.

Jon Bentley programování Perlse knihy mají nějaké další informace o řazení.

Můžete rychle vybičovat testovací soupravu obsahující

  • náhodná celá čísla

  • tříděné celá čísla

  • Zvrátit seřazené celá čísla

  • Tříděné celá čísla, mírně rozrušený

Pokud mi paměť slouží, to jsou nejdůležitější věci pro algoritmus třídění.

Pokud hledáte pro třídění pole, která se nevejde do vyrovnávací paměti, budete muset měřit mezipaměti účinky. valgrindJe efektivní, pokud pomalý.

Odpovězeno 27/08/2009 v 05:22
zdroj uživatelem

hlasů
3

sortperf.py má dobře vybraný sadu referenčních testovacích případů a byl použit k podpoře esej našel tu a aby timsort druhu v Python lo, že před mnoha lety. Všimněte si, že po dlouhé době konečně Java může být přechod na timsort také díky Josh Block (viz zde ), takže jsem si představit, že psali své vlastní verze z referenčních testovacích případů - ale nemohu snadno najít odkaz k němu. (timsort, stabilní, přizpůsobivý, opakující přírodní mergesort varianta je zvláště vhodný pro jazyky s odvoláním-to-objektu sémantiky jako je Python a Jáva, kde se „hnutí data“ je relativně levné [[protože všechno, co kdy přesouvány je reference aka ukazovátka ne kuličky neohraničené velikosti ;-)]], ale srovnání může být poměrně nákladná `, protože neexistuje žádná horní mez složitosti funkce porovnání - ale pak to platí pro jakýkoli jazyk, kde třídění může být upravena pomocí vlastního srovnání nebo klíč extrakce function`).

Odpovězeno 06/09/2009 v 02:15
zdroj uživatelem

hlasů
3

Tato stránka ukazuje různé třídící algoritmy pomocí čtyř skupin: http://www.sorting-algorithms.com/

Kromě čtyř skupin v Normana odpověď Chcete-li zkontrolovat třídění algoritmy s kolekci čísel, která mají několik podobností v číslech:

  • Všechna čísla jsou jedinečné
  • Stejné číslo v celé sbírky
  • Několik Unikátní Keys

Změna počtu prvků v kolekci je také dobrým zvykem zkontrolovat každou algoritmus s 1K, 1M, 1G atd vidět, jaké jsou důsledky paměť tohoto algoritmu.

Odpovězeno 02/09/2009 v 10:51
zdroj uživatelem

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more