Funkční quicksort

14.7.2006 16:05 | Přečteno: 1897× | Linux

Radujme se. Dokončil jsem konečně quicksort a je to opravdu o dost rychlejší než posledně. 1500 položek to seřadí během okamžiku. Funkce compare_*( FileInfo *fi1, FileInfo *fi2, bool ascending ) a sort( FileInfoList* list, int column, bool ascending ) jsou deklarovány jako chráněné a statické. K použití je určena veřejná fce sort( int column, bool ascending )

Budu rád za jakékoliv další návrhy vedoucí ke zrychlení.

int FileInfoList::compare_size( FileInfo *fi1, FileInfo *fi2, bool ascending )
{
	int asc = ( ascending ? 1 : -1 );
	if( fi1->isDots() ) return -1;
	if( fi2->isDots() ) return 1;
	if( fi1->isDir() && !fi2->isDir() ) return -1;
	if( fi2->isDir() && !fi1->isDir() ) return 1;
	if( fi1->isDevice() && !fi2->isDevice() ) return -1 * asc;
	if( fi2->isDevice() && !fi1->isDevice() ) return 1 * asc;
	if( (fi1->isDir() && fi2->isDir()) || (fi1->isDevice() && fi2->isDevice()) ) return 0;
	off64_t size1, size2;
	fi1->getSize(size1);
	fi2->getSize(size2);
	if( size1 > size2 ) return 1 * asc;
	if( size2 > size1 ) return -1 * asc;
	return 0;
}

int FileInfoList::compare_name( FileInfo *fi1, FileInfo *fi2, bool ascending )
{
	int asc = ( ascending ? 1 : -1 );
	if( fi1->isDots() ) return -1;
	if( fi2->isDots() ) return 1;
	if( fi1->isDir() && !fi2->isDir() ) return -1;
	if( fi2->isDir() && !fi1->isDir() ) return 1;
	return g_utf8_collate( fi1->getName().c_str(), fi2->getName().c_str() ) * asc;
}

int FileInfoList::compare_ext( FileInfo *fi1, FileInfo *fi2, bool ascending )
{
	int asc = ( ascending ? 1 : -1 );
	if( fi1->isDots() ) return -1;
	if( fi2->isDots() ) return 1;
	if( fi1->isDir() && !fi2->isDir() ) return -1;
	if( fi2->isDir() && !fi1->isDir() ) return 1;
	if( fi1->isDevice() && !fi2->isDevice() ) return -1 * asc;
	if( fi2->isDevice() && !fi1->isDevice() ) return 1 * asc;
	if( (fi1->isDir() && fi2->isDir()) || (fi1->isDevice() && fi2->isDevice()) ) return 0;
	return g_utf8_collate( fi1->getExt().c_str(), fi2->getExt().c_str() ) * asc;
}

int FileInfoList::compare_attrs( FileInfo *fi1, FileInfo *fi2, bool ascending )
{
	int asc = ( ascending ? 1 : -1 );
	if( fi1->isDots() ) return -1;
	if( fi2->isDots() ) return 1;
	if( fi1->isDir() && !fi2->isDir() ) return -1;
	if( fi2->isDir() && !fi1->isDir() ) return 1;
	return g_utf8_collate( fi1->getAttrs().c_str(), fi2->getAttrs().c_str() ) * asc;
}

int FileInfoList::compare_owner( FileInfo *fi1, FileInfo *fi2, bool ascending )
{
	int asc = ( ascending ? 1 : -1 );
	if( fi1->isDots() ) return -1;
	if( fi2->isDots() ) return 1;
	if( fi1->isDir() && !fi2->isDir() ) return -1;
	if( fi2->isDir() && !fi1->isDir() ) return 1;
	return g_utf8_collate( fi1->getOwner().c_str(), fi2->getOwner().c_str() ) * asc;
}

int FileInfoList::compare_group( FileInfo *fi1, FileInfo *fi2, bool ascending )
{
	int asc = ( ascending ? 1 : -1 );
	if( fi1->isDots() ) return -1;
	if( fi2->isDots() ) return 1;
	if( fi1->isDir() && !fi2->isDir() ) return -1;
	if( fi2->isDir() && !fi1->isDir() ) return 1;
	return g_utf8_collate( fi1->getGroup().c_str(), fi2->getGroup().c_str() ) * asc;
}

int FileInfoList::compare_date( FileInfo *fi1, FileInfo *fi2, bool ascending )
{
	int asc = ( ascending ? 1 : -1 );
	if( fi1->isDots() ) return -1;
	if( fi2->isDots() ) return 1;
	if( fi1->isDir() && !fi2->isDir() ) return -1;
	if( fi2->isDir() && !fi1->isDir() ) return 1;
	time_t modDate;
	struct tm tm1;
	struct tm tm2;
	struct tm *ctm;
	fi1->getDate( modDate );
	ctm = localtime( &modDate );
	memcpy( &tm1, ctm, sizeof(tm1) );
	fi2->getDate( modDate );
	ctm = localtime( &modDate );
	memcpy( &tm2, ctm, sizeof(tm2) );
	if( tm1.tm_year > tm2.tm_year ) return 1 * asc;
	if( tm1.tm_year < tm2.tm_year ) return -1 * asc;
	if( tm1.tm_mon > tm2.tm_mon ) return 1 * asc;
	if( tm1.tm_mon < tm2.tm_mon ) return -1 * asc;
	if( tm1.tm_mday > tm2.tm_mday ) return 1 * asc;
	if( tm1.tm_mday < tm2.tm_mday ) return -1 * asc;
	if( tm1.tm_hour > tm2.tm_hour ) return 1 * asc;
	if( tm1.tm_hour < tm2.tm_hour ) return -1 * asc;
	if( tm1.tm_min > tm2.tm_min ) return 1 * asc;
	if( tm1.tm_min < tm2.tm_min ) return -1 * asc;
	if( tm1.tm_sec > tm2.tm_sec ) return 1 * asc;
	if( tm1.tm_sec < tm2.tm_sec ) return -1 * asc;
	return 0;
}

void FileInfoList::sort( FileInfoList* list, int column, bool ascending )
{
	if( list->count() <= 1 ) return;
	// false = dont free items
	FileInfoList before( false );
	FileInfoList behind( false );
	FileInfoList same( false );
	FileInfoList::size_type nCentral = list->count() / 2;
	int compareRes;
	for( FileInfoList::size_type i = 0; i < list->count(); ++i )
	{
		if( i == nCentral ){
			same.push_back( list->at(nCentral) );
			continue;
		}
		switch( column )
		{
			case 0:
				compareRes = FileInfoList::compare_name( list->at(nCentral), list->at(i), ascending );
				break;
			case 1:
				compareRes = FileInfoList::compare_ext( list->at(nCentral), list->at(i), ascending );
				break;
			case 2:
				compareRes = FileInfoList::compare_size( list->at(nCentral), list->at(i), ascending );
				break;
			case 3:
				compareRes = FileInfoList::compare_date( list->at(nCentral), list->at(i), ascending );
				break;
			case 4:
				compareRes = FileInfoList::compare_attrs( list->at(nCentral), list->at(i), ascending );
				break;
			case 5:
				compareRes = FileInfoList::compare_owner( list->at(nCentral), list->at(i), ascending );
				break;
			default:
				compareRes = FileInfoList::compare_group( list->at(nCentral), list->at(i), ascending );
				break;
		}
		if( compareRes == 0 ) same.push_back( list->at(i) );
		if( compareRes > 0 ) before.push_back( list->at(i) );
		if( compareRes < 0 ) behind.push_back( list->at(i) );
	}
	if(before.count()>1) FileInfoList::sort( &before, column, ascending );
	if(behind.count()>1) FileInfoList::sort( &behind, column, ascending );
	FileInfoList::size_type pos = 0;
	for( FileInfoList::size_type i = 0; i < before.count(); ++i )
		list->at(pos++) = before.at(i);
	for( FileInfoList::size_type i = 0; i < same.count(); ++i )
		list->at(pos++) = same.at(i);
	for( FileInfoList::size_type i = 0; i < behind.count(); ++i )
		list->at(pos++) = behind.at(i);
}

void FileInfoList::sort( int column, bool ascending )
{
	sort( this, column, ascending );
}

       

Komentáře

[Heron]

Quick sort je pěkný. Dá se ještě urychlit. Málo položek je dobré setřídit jinak (ve skriptech se píše 12 položek a insertsort). Je to jasné, pak se ta rekurze dělá vlastně pro dva prvky, tak to žere čas a paměť na stacku. insertem pro 12 položek se to eliminuje.

[Filip Jirsák]

Ona ta regurze jde vůbec urychlit tak, že se úplně vynechá a implementuji si vlastní zásobník, kde si budu pamatovat jen hodnoty pro "rekurzi" potřebné, v tomto případě tedy začátek a konec řazeného (pod)seznamu. Druhá výhoda tohoto řešení je ta, že si můžu udělat zásobník velký jak je potřeba a nemusím se bát, že rekurzivním voláním přelezu nějaký limit vnořených volání podprogramů…

[machr]

> Ona ta regurze jde vůbec urychlit tak, že se úplně vynechá a implementuji si vlastní zásobník

- no jasne, proc pouzivat uz implementovanej a optimalizovanej zasobnik, podporovanej primo CPU, kdyz si muzu vytvorit vlastni...

[Michal Kubeček]

Třeba proto, aby to bylo rychlejší a sežralo to méně paměti?

[machr]

hahaha. nemas tuseni o cem mluvis. Prepisovat to do nerekurzivni podoby by melo smysl snad jenom, kdybys to portoval na nejakej system bez rekurze...

zasobnik, ktery se vyuziva pro volani funkci je velmi rychlej a neni duvod ho nevyuzit.

Navic pokud si chces implementovat vlastni zasobnik, tak mas 2 moznosti:

1. pridelis mu jenom tolik pameti, kolik v danou chvili potrebuje - v tom pripade pudes neustale provadet realokace a vysledek bude monstrozne pomalej !!!!

2. vytvoris si pole, ktery nehoraznym zpusobem predimenzujes - v tom pripade budou naprosto monstrozni pametovy naroky !!!!

takze priste bych doporucoval mluvit jen k tematu, o ktery neco vis...

[Michal Kubeček]

Nech si urážky pro své kamarády, broučku, buď tak laskav. A teď k věci:

1. Klasický zásobník je samozřejmě rychlý, ale rekurzivní implementace na něj ukládá mnohonásobně víc dat, než je potřeba. Jeho velikost je navíc omezena a na některých platformách je to omezení dost výrazné. Navíc je to omezení, se kterým prostě nehnete.

2. Realokovat není (obecně) potřeba a není ani nutné alokovat obrovské pole předem. Zásobník totiž vůbec nemusí být realizován jako lineární pole.

3. Snadno nahlédneme, že paměťové nároky řešení s vlastním zásobníkem jsou už z principu nižší než paměťové nároky řešení pomocí rekurze. Navíc s tím rozdílem, že pokud dojde místo na systémovém zásobníku, máme smůlu; dojde-li místo v našem zásobníku, dá se s tím něco dělat.

Sečteno a podtrženo: než někoho nařknete, že o problematice nic neví, nebývá od věci ověřit, zda toho sám víte aspoň tolik co on. Vyhnete se tak zbytečné blamáži…

[Luk]

Zásobník totiž vůbec nemusí být realizován jako lineární pole.

A třeba takový std::stack ani není. Protože bývá typicky implementován pomocí std::deque, nepotřebuje souvislý úsek paměti.

[machr]

> 1. Klasický zásobník je samozřejmě rychlý, ale rekurzivní implementace na něj ukládá mnohonásobně víc dat, než je potřeba. Jeho velikost je navíc omezena a na některých platformách je to omezení dost výrazné. Navíc je to omezení, se kterým prostě nehnete.

treba na 8051 ?? tak to je vazne problem...

2. Realokovat není (obecně) potřeba a není ani nutné alokovat obrovské pole předem. Zásobník totiž vůbec nemusí být realizován jako lineární pole.

- jeste je mozny ho udelat jako spojovej seznam, ale to by bylo pomaly kvuli alokacim a dealokacim polozek a zbytecne pametove narocny, protoze si musi pamatovat link na predchozi polozku a buhvico si musi pamatovat memory manager kvuli kazdymu takovimu ukazateli... jednoduse reseno: kombinace toho nejhorsiho

> 3. Snadno nahlédneme, že paměťové nároky řešení s vlastním zásobníkem jsou už z principu nižší než paměťové nároky řešení pomocí rekurze. Navíc s tím rozdílem, že pokud dojde místo na systémovém zásobníku, máme smůlu; dojde-li místo v našem zásobníku, dá se s tím něco dělat.

- jo, ale jenom pokud provadis realokace

PS: na mym kompu, kterej povazuju za reprezentativni vzorek soucastnejch pc, a za stroj, na kterym by priblizne moh bezet ten program sem spustil tento program:

#include <stdio.h>
int q(int i) {
	printf("%d\n", i);
	q(i+1);
}
int main(int argc, char** argv) {
	q(0);
}

a nez to spadlo, tak napocital do 523 722. A dost pochybuju, ze by se algoritmus pri razeni nekolika souboru v adresari nekdy dostal do srovnatelny hloubky

[#Tom]

A dost pochybuju, ze by se algoritmus pri razeni nekolika souboru v adresari nekdy dostal do srovnatelny hloubky

Hehe. Takto by programátor uvažovat neměl.

[machr]

> Hehe. Takto by programátor uvažovat neměl.

ne, to asi ne , ale pokud provedu jenom hrubej vypocet, tak v idealnim pripade (pokud by se mu podarilo pole rozdelit vzdy presne na pul) by se do tyto hloubky dostal az pri poli velkym 2**523722 = 10e19 polozek. ono se mu to sice pravdepodobne vetsinou nepodari rozdelit presne na pul, ale stejne by to melo stacit na hodne hodne hodne velky pole...

[machr]

pardon. chyba ve vypoctu:

2 ** 523 722 == 10 ** 157 656, ne 10 ** 19

takze bysme se zasobnikem na mym skromnym pc byli schopni seradit vsechny atomy ve vesmiru - a klidne i ve vsech paralelnich vesmirech, a jeste by stejne nebyl zdaleka plnej

[Michal Kubeček]

Tři technické poznámky. Za prvé 2^523722 je podstatně více než 10^19. Za druhé: v praxi nebude velikost dat na jednu instanci taková jako u vás, ale vyšší. Za třetí: odhadujete to ze špatné strany.

[Michal Kubeček]

1. Se znepokojením sleduji, jak omezený rozhled má většina uživatelů Linuxu na PC. Naivně jsem si myslel, že útlak od windowsové majority je naučí chápat, že jejich platforma není středem světa a že i jiné mají právo na existenci. Bohužel to vypadá, že většina z nich by jen ráda nahradila hegemonii Windows hegemonií Linuxu (ovšem ne Linuxu obecně, jen Linuxu na jejich hardwarové platformě). Je mi z toho trochu smutno.

2. A co takhle spojový seznam z jednotlivých polí vhodně zvolené velikosti? Realokovat není potřeba nic, alokovat nemusím tak často, overhead na spojovací pointer je zanedbatelný. Jinak ani kdyby to byl opravdu čistý spojový seznam, nemáte pravdu, protože ten pointer má z podstaty věci přesně stejnou velikost jako návratová adresa (kterou tam pro změnu nutně potřebujete vy) - a pořád ušetřím nějaké ty lokální proměnné.

3. Ne. Opakuji, že při rozumné implementaci zásobníku není potřeba nic realokovat.

Ad P.S.: porovnejte si celkovou velikost lokálních proměnných a argumentů u vašeho testovacího prográmku a u implementace, o níž tu byla řeč. Pořád sice zbyde relativně velké číslo, ale jak už jsem řekl, existují i jiné platformy.

Mimochodem, netvrdím, že rekurze je vždy špatná. Jen zásadně nesouhladím s důvody, které pro její upřednostnění uvádíte.

[Filip Jirsák]

Zásobník, který se využívá pro volání funkce, si hlavně musí pamatovat spoustu údajů, které jsou pro quicksort zbytečné.

Nehorázně předimenzovaný zásobník pro rekurzivní quicksort bude mít počet prvků = počet tříděných prvků / 2, tedy např. pro třídění pole int indexované int bude mít stejnou velikost, jako tříděné pole, pro třídění řetězců bude zabírat zlomek paměti zabrané tříděným seznamem. Opravdu monstrózní paměťové nároky…

[Kyosuke]

Rekurze nemá inherentní nevýhody. To jen kompilátory jsou buď blbý, nebo si ji nemůžou dovolit kvůli sémantice (Cčko, myslím...doufám. Gcc umí aspoň tail recursion, aspoň občas, když už ne obecně.) Hromada rekurzivních volání jsou jen skoky s přejmenováním parametrů. Jak je to u quicksortu, to se budu muset podívat – docela mě to zajímá a už byh si ho měl konečně taky jednou naimplementovat. Ale přesto mi přijde, že hromada lidí šmahem odsuzuje rekurzi proto, že nikdy neviděli kompilátor, který ji dokáže vyeliminovat. A přitom to může být tak pěkné (a bezpečné) goto s parametry...

[happy barney]

ano, rekurzia casto byva pekna, zorzumitelnejsia. Ale presadzovat ju za kazdu cenu je imho rovnaka blbost ako ju odmietat. Vzdy zalezi na situacii.

btw, ked uz vykon (a pamat), radsej by som pouzil radix sort

[Filip Jirsák]

Kompilátor možná rekurzy dokáže vyeliminovat, pokud mu dám najevo, o co se snažím. Což v uvedené části kódu není tak úplně jasné. Pro rozumnou implementaci quicksortu potřebuju do rekurzivního volání dostat dva parametry – začátek a konec tříděného (pod)seznamu. Ve zde uvedené implementaci se tam navíc předávájí i dva objekty, v rozumné implementaci by se předával jeden. A to tady ještě nejsou použité virtuální členské funkce, které by to nejspíš zase ještě zpomalily. Další věc, co celou rekurzi komplikuje, jsou výjimky – nevím, zda kompilátor z tohoto kódu dokáže poznat, že v příslušných funkcích nemusí být kód pro ošetření výjimek, který zase činí volání funkce složitější.

Rekurzi rozhodně šmahem neodsuzuju, dokonce jsem spíš pro to, aby byl program především čitelný pro programátora, i když bude třeba o něco méně efektivní. Ale u quicksortu jde snad především o rychlost, navíc zrovna tady je implementace zásobníku místo rekurze triviální.

[lankvil]

Pekne :)

jeste trochu urychlit by se to dalo, kdybys dal ten switch pred hlavni smycku a adresu funkce si ulozit do ukazatele, aby se column neporovnaval zbytecne casto. asi nejak takhle:

        int (*compare)(FileInfo *, FileInfo *, bool);

        switch( column )
        {
                case 0:
                        compare = &FileInfoList::compare_name;
                        break;
                case 1:
                        compare = &FileInfoList::compare_ext;
                        break;
                case 2:
                        compare = &FileInfoList::compare_size;
                        break;
                case 3:
                        compare = &FileInfoList::compare_date;
                        break;
                case 4:
                        compare = &FileInfoList::compare_attrs;
                        break;
                case 5:
                        compare = &FileInfoList::compare_owner;
                        break;
                default:
                        compare = &FileInfoList::compare_group;
                        break;
        }
        for( FileInfoList::size_type i = 0; i < list->count(); ++i )
        {
                if( i == nCentral ){
                        same.push_back( list->at(nCentral) );
                        continue;
                }
                compareRes = (*compare)( list->at(nCentral), list->at(i), ascending );
                
                /* ... */

a taky porovnavani ascending bych nepsal do kazdy compare fci zvlast ale primo do sort, je to min prace. ale to uz byl jenom takovej kosmetickej detail ;)

[Michal Kubeček]

Nebo rovnou použít pointer na metodu, tohle je typická ukázka toho, k čemu jsou dobré.

[Jardík]

Výborný nápad.

[Kyosuke]

Řídicí struktury jsou zlo, obzvlášť switch!

[b*d]

Takze pole pointru na fce. Co mne nejak nenapada, ale neni switch jenom if () { } else if () { } else { } ?

[Luk]

Co mne nejak nenapada, ale neni switch jenom if () { } else if () { } else { } ?

Obecně být nemusí. Pokud bude kompilátor dostatečné chytrý, může to v řadě případů optimalizovat. Bohužel nevím, jestli to GCC dělá (případně které verze).

[Kyosuke]

Pole pointerů na funkce...hmm, neříká se tomu „tabulka virtuálních metod“?

[Michal Vyskočil]

Samozřejmě, ale co mají ti chudáci, používající silně staticky typované jazyky dělat? Konec programátora v C++ nastává v okamžiku, kdy pochopí Smalltalk

[Kyosuke]

No zrovna v případě C++ kódu by stačilo sáhnout do kuchařky a nahradit řídicí strukturu polymorfismem. Je pravda, že virtual call něco stojí, ale v případě poměrně primitivních mechanismů C++ a relativně složitých porovnávacích funkcí, která vidím v kódu, mi to přijde docela levné. A líp by se to četlo.

[Michal Kubeček]

Problém je v tom, že tady se kritérium řazení mění na základě požadavu uživatele a bylo by nepraktické kvůli tomu vytvářet novou instanci seznamu. Leda že byste měl na mysli jen hierarchii tříd, které by pouze nahrazovaly jednotlivé porovnávací funkce. Jenže jedna z věcí, které jsou mi na C++ sympatické, je právě to, že mne ve jménu pochybných vyšších ideálů nenutí vyrábět třídy bez datových polí s jednou metodou místo obyčejných funkcí, pokud to pro mne nemá nějaký přínos.

[Kyosuke]

Když já si nemůžu pomoci v jedné věci: Ten kód prostě smrdí. Hromada těch porovnávacích metod je příliš dlouhá, příliš mnoho věcí se v nich několikrát opakuje...musel bych se trošku víc ponořit do celého toho (fajlmenedžrového? ) problému, ale právě jsem se vrátil z...společenské události... ...a vůbec, budu se potřebovat pořádně vyspat.

Ovšem po čtení knihy Thinking Forth (ve které každá třetí věta obsahuje sloveso „factor out“ ) cestou domů ovšem působí takovýhle kód prostě jako rána palici do hlavy.

[Michal Kubeček]

Ale to máte samozřejmě naprostou pravdu, neobhajuji ten kód jako takový, ostatně některé výhrady už jsem tu napsal. Když už se bavíme o polymorfismu, podle mne by se hodilo pojmout polymorfně už přímo samy atributy - jako potomky společného abstraktního rodiče, který by deklaroval základní interface (např. jak ten atribut získat, jak ho zobrazit, jak ho porovnávat) a jednotlivé třídy by pak tyto virtuální metody implementovaly.

Nemluvě o tom, že už jsem asi hodně odvykl používání Windows, takže samotná myšlenka dělení jména souboru na jméno a příponu mi připadá poněkud nepatřičná…

[Michal Kubeček]

1. Nejsem si jistý, jestli běžné řadící algoritmy trochu nevyvede z rovnováhy, když jim vaše porovnávací funkce vrátí pro dva stejné prvky -1.

2. Jeslti dobře vidím, porovnáváte timestampy tak, že je převedete struct time a ty pak složitě porovnáváte po složkách. Nebylo by praktičtější porovnat je rovnou nebo, bojíte-li se tolik o přenositelnost na obskurní platformy, použít difftime()?

[Jardík]

Sakra, s tím časem máte pravdu. Jdu provést úpravu. Co jste myslel tím, že pro dva stejné prvky vrátím -1?

[Michal Kubeček]

Když porovnáte dva prvky, pro které platí isDots(), dostanete vždy -1.

[happy barney]

preco nie takto?

class Comparator;
class CompareFileSize : Comparator; // atd

class FileListInfo {
  public static COMPARE_BY_FILE_SIZE;
}

FileInfoList::sort (const Comparator &);

...

file_list->sort (FileListInfo->COMPARE_BY_FILE_SIZE);
file_list->sort (new MyCrazyComparator);
file_list->reverse;

[Michal Kubeček]

Tady

  public static COMPARE_BY_FILE_SIZE;

asi něco chybí.

[happy barney]

hmm, neberte to tak detailne, povazujte to za pseudokod
na C++ by som sa musel rozpamatat, oprasit stroustroupa ...

[Michal Kubeček]

No jo, on ten příklad vůbec působil podobným dojmem, jako když Francouz mluví anglicky - člověk má pocit, že mluví francouzsky, jen při tom používá anglická slova… :-)

[Jardík]

file_list->sort(new MyCrazyComparator);

Typická ukázka ztracení pointeru (leda, že by pak ta fce na konci volala delete).
Jinak myslím, že něco takového by to asi moc neurychlilo.

[Jardík]

I když ... ještě o tom budu chvilku přemýšlet.

[Kníže Ignor]

i pro C++ existují garbage collectory

[Michal Kubeček]

Ne ovšem proto, že by byly potřeba, ale kvůli lidem, kteří píší podobné čuňárny… :-)

[Michal Kubeček]

Třídy by byly výhodné hlavně v případě, že by se jednalo o knihovnu, kterou by využívaly cizí programy, což není tento případ.

[happy barney]

podobne, nadavajme tomu pseudokod

[raslent]

Toto sú veľmi poučné blogy, kiež by ich bolo viac. Možno by abicko mohlo urobiť nejakú rubriku vývoj:)

[Heron]

Mno ....

Autor blogu promine, ale daleko lepší ukázku quick sortu naleznete v kterýchkoliv skriptech. Nechci autora nějak kritizovat, psát si může cokoliv, ale (a psal jsem to už jinde), má ten celý program nějaký návrh? Nebo (a to je můj pocit), píše ad hoc kód a modul co ho zrovna napadne?

[raslent]

Nedokážem zhodnotiť kvalitu toho čo produkuje, len som chcel vyjadriť názor a zároveň mu medzi riadkami napísať, že to o čo sa snaží má možno zmysel. A z môjho pohľadu to ma isto väčší prínos než iný blog(nenarážam na žiaden konkrétny).

[Heron]

Ten blog přínosem jistě je. Vytváří se něco konkrétního. Způsobem, který se mi sice nelíbí, ale pokud to nakonec bude fungovat, tak proč ne.

[raslent]

Prečo sa vám nepáči spôsob ?

[Heron]

Jde o to, že nikde není návrh toho programu. Vlastně ani seznam věcí, které by ten program mohl umět. Takhle se větší projekty psát nedají.

Snadno se stane, že tam po nějakém čase bude chtít doprogramovat nějakou featuru, se kterou původní kód nepočítá. Takže se celý kód musí přepsat. Nebo dobastlit. Ale dobastlíte-li jednu funkci už si obvykle velmi stížíte cestu pro další fce.

Když si vezmu třeba jen tohle třídění. Tohle je typická ukázka procedurálního kódu přepsaného do objektového. Takhle se přece vůbec netřídí. On chce po seznamu, aby uměl porovnat dva prvky. (Seznam vůbec nemá/nemusí vědět, jaké prvky obsahuje). To je přece blbost, prvky by se měli umět vzájemně porovnat sami (nebo to dělat přes externí komparátor). Druhá chyba je to samotné třídění. Buď to má umět přímo nejaká externí metoda, kterou pak poštvete na ten seznam (libovolný seznam).

[raslent]

Aha, čiže mali ste namysli takýto spôsob z pohľadu technického. Je to iba nápad, no nemuselo by byť zlé ak by bola na abicku rubrika vývoj.

[Käyttäjä 11133]

Není návrh, není dokumentace, píše se on demand

[Heron]

To je cesta do pekel

[happy barney]

Kto si hraje, nezlobi ) ved ich nechajme, nech sa hraju )

[Filip Jirsák]

Může mi někdo ze zde přítomných znalců C++ vysvětlit význam následujícího kódu? Mně to připadá, že třída FileInfoList má členskou funkci, která umí setřídit jinou instanci FileInfoList a pak další členskou funkci, která té první předá svou instanci. To je poněkud avantgardní řešení, ne?

void FileInfoList::sort( FileInfoList* list, int column, bool ascending )
{
…
}

void FileInfoList::sort( int column, bool ascending )
{
	sort( this, column, ascending );
}

[VícNežNic]

Heh, taky se mi zdá Zajímavé.

[Michal Kubeček]

Vypadá to na céčkovou rekurzivní implementaci quicksortu, která je otrocky a velmi nešťastným a zoufale neefektivním (hlavně paměťově) způsobem přepsána do C++. Máte samozřejmě pravdu, že by bylo čistší a přehlednější použít jen jednu metodu sort(), ale řekl bych, že to je ve srovnání s paměťovou náročností spíše vedlejší problém.

[Jardík]

Co kdybyste mi věnoval link na nerekurzivní implementaci qicksortu?

[Jardík]

Už jsem ji našel.

[Filip Jirsák]

Stačí návod?

[Michal Kubeček]

Samotná rekurze není problém, problém je v tom, že v každém kroku vytváříte kopii celého pole, které řadíte. Tím dostanete statistickou paměťovou náročnost O(n log n) a maximální dokonce O(n²). Přitom i rekurzivní implementace se dá udělat in-place, tj. přímo na řazeném poli.

[Jardík]

Tak to zkuste napsat líp :). Našel jsem nerekurzivní implementaci, ale je to sice hodně rychlé na řazení datumu, ale asi tak 2x - 3x pomalejší na řazení stringů:

	if( list->count() <= 1 ) return;
	int (*compare)(FileInfo *, FileInfo *, bool);
	switch( column )
	{
		case 0:
			compare = FileInfoList::compare_name;
			break;
		case 1:
			compare = FileInfoList::compare_ext;
			break;
		case 2:
			compare = FileInfoList::compare_size;
			break;
		case 3:
			compare = FileInfoList::compare_date;
			break;
		case 4:
			compare = FileInfoList::compare_attrs;
			break;
		case 5:
			compare = FileInfoList::compare_owner;
			break;
		default:
			compare = FileInfoList::compare_group;
			break;
	}
	#define MAX_LEVELS 1000
	FileInfo *piv;
	int beg[MAX_LEVELS], end[MAX_LEVELS];
	int i=0, L, R, elements = (int)list->count();
	
	beg[0] = 0;
	end[0] = elements;
	while(i>=0)
	{
		L = beg[i];
		R = end[i] - 1;
		if( L < R )
		{
			if( i == MAX_LEVELS - 1 ) return;
			piv = list->at(L);
			while( L < R )
			{
				while(compare(list->at(R),piv,ascending) >= 0 && L<R ) R--;
				if(L<R) list->at(L++) = list->at(R);
				while(compare(list->at(L),piv,ascending) <= 0 && L<R ) L++;
				if(L<R) list->at(R--) = list->at(L);
			}
			list->at(L) = piv;
			beg[i+1] = L+1;
			end[i+1] = end[i];
			end[i++] = L;
		} else {
			i--;
		}
	}

[machr]

a neni to potom tim, ze to nejak nevhodne vybira pivot. Pokud vim, tak je lepsi ho brat z prostredku, protoze pokud ho beres nakraji, tak to nefunguje moc dobre, pokud je to pole uz seradeny (nebo seradeny opacne, podle toho, z kteryho kraje). Tady sem nasel jednu implemtnaci, co bere pivot uprostred intervalu:

template<typename Item>
void qsort(Item* a, int left, int right, int (*less)(Item a, Item b)) {
	int i = left;
	int j = right;
	Item pivot = a[(i+j)/2];
	while(i <= j) {
		while(less(a[i], pivot)) i++;
		while(less(pivot, a[j])) j--;
		if(i < j) {
			Item temp = a[i];
			a[i] = a[j];
			a[j] = temp;
			i++; j--;
		} else
		if(i == j) {
			i++; j--;
		}
	}
	if(left < j) qsort(a, left, j, less);
	if(i < right) qsort(a, i, right, less);
}

less je funkce, ktera prima dva prvky pole a vraci nenulovou hodnotu, pokud je prvni mensi nez druhy (ma byt v poli pred druhym)

upravit to by snad nemel bejt problem...

[Kníže Ignor]

Je úplně jedno odkud bereš pivota, pokud je jeho pozice předem daná a pevná a pokud má každá vstupní posloupnost stejnou pravděpodobnost

[machr]

> a pokud má každá vstupní posloupnost stejnou pravděpodobnost

- to je presne to o cem mluvim podle me ta posloupnost neni naprosto nahodna, ale je pravdepodobny, ze bude uz castecne serazena

[Kníže Ignor]

Proč by měla být? Vždyť máš několik kritérií, podle kterých můžeš třídit (název, čas vytvoření, velikost, ..). Nějaká velká kovariance mezi těmito veličinami se asi nedá očekávat a na disku je to vždy asi uloženo jen podle některé z nich, takže bych to, že to bude v řadě případů už skoro setříděné, moc nepředpokládal.

[Michal Kubeček]

Tak si představte třeba modelovou situaci: v adresáři je několik set (několik tisíc) souborů stejného typu, např. JPEGů. Seřadíte je podle názvu. Pak je seřadíte podle přípony, tu mají všechny stejnou, takže se nezmění nic. A pak je seřadíte opět podle jména. Je to tak zcela vyloučená situace?

Navíc nevím nic o tom, jak jsou data udržována a obnovována, takže jsem raději vynechal naprosto běžné situace typu přidání nebo přejmenování jednoho souboru.

[Kníže Ignor]

Vyloučené to není.

S tím přidáváním souborů - to by byl asi lepší nějaký algoritmus, který je připraven na práci se dvěma setříděnými obecně nestejně velkými posloupnostmi a uměl by je efektivně slít. Quicksort na se mi na to nezdá moc vhodný.

[Josef Kufner]

Nejčastěji je seznam souborů zobrazován seřazen podle jména. Při kopírování to spousta programů veme v setříděném pořadí a seřazeně uloží do filesystému a tím pádem se to pak i seřazeně načte => pravděpodobnost je vysoká. Případy, kdy to bude seřazeno podle něčeho jiného, nejsou tak časté a pokud ano, po prvním zkopírování se to seřadí na filesystému takto a pravděpodobnost bude opět vysoká.

[Kníže Ignor]

Tak to mám teda vyloženě pech. Pokud totiž už používám dvoupanelový správce souborů, tak mám skoro vždy v obou oknech jiný typ řazení

[Josef Kufner]

To jo, já jinak než podle jména neseřazuju. Teda až na výjimky.

[Michal Kubeček]

To je rozhodně podstatný problém, zvlášť v situaci, kdy je poměrně pravděpodobné, že se bude pole opakovaně řadit podle stejného kritéria. Při volbě krajního prvku jako pivota se pak při opakovaném řazení stává algoritmus kvadratickým.

Další (menší) zdroj neefektivity je i v tom, že se používá at() místo operátoru [], čímž se zbytečně pokaždé testují meze.

[Michal Kubeček]

Hlavně bych nepodceňoval autory standardní C++ knihovny a když už ji stejně musím linkovat, použil bych toho, co v ní je hotové.

  bool compare_abc(const FileInfo* a, const FileInfo* b)
  {
     ...
  }

  static bool (*compare_functions[]) = {
    compare_abc,
    compare_def,
    ...
  }

  inline void FileInfoList::sort() {
    sort(begin(), end(), compare_functions[column]);
  }

[Luk]

Moje řeč

[Michal Kubeček]

Oprava:

static bool (*compare_functions[])(const FileInfo* a, const FileInfo* b) = {

[Michal Kubeček]

Oprava opravy :-)

static bool (*compare_functions[])(const FileInfo*, const FileInfo*) = {

[Jardík]

Hezká, ale já prostě potřebuju vědět, jestli se řadí vzestupně či sestupně. Pužít globální proměnnou mi přijde jako prasárna.

[VícNežNic]

Funkce pro řazení o tom dle mého vědět nemusí. Stačí když to ví ta co to pak cpe do modelu -- prostě to udělá obráceně.

[Michal Kubeček]

Na to stačí celkem malá modifikace.

[Michal Kubeček]

Ale spíš už bych to řešil nějak takhle:

class file_comparator {
protected:
  bool ascending;
  virtual bool less(const FileInfo* a, const FileInfo* b) = 0;
public:
  file_comparator(bool asc) : ascending(asc) {}
  virtual ~file_comparator() {}
  bool operator () (const FileInfo* a, const FileInfo* b);
};

bool file_comparator::operator () (const FileInfo* a, const FileInfo* b)
{
  if (b->isDots()) return false;
  if (a->isDots()) return true;
  if (a->isDir() && !b->isDir()) return true;
  if (b->isDir() && !a->isDir()) return false;
  return (ascending ? less(a,b) : less(b,a));
}


class file_comparator_name : public file_comparator {
protected:
  virtual bool less(const FileInfo* a, const FileInfo* b);
public:
  file_comparator_name(bool asc) : file_compararator(asc) {}
  virtual ~file_comparator_name() {}
};

bool file_comparator_name::less(const FileInfo* a, const FileInfo* b)
{
  // tady porovnáme jména
}

// a podobně pro další kritéria


void FileInfoList::sort(FileInfoList::column_t column, bool asc)
{
  file_comparator* cmp;
  switch(column) {
    case col_name:
      cmp = new file_comparator_name(asc); break;
    // ...
    default:
      // cannot happen
      // throw ...;
  }
  std::sort(begin(), end(), cmp);
  delete cmp;
}

(určitě jsou tam chyby, psal jsem to z hlavy a nezkoušel přeložit)

[happy barney]

nie je jednoduchsie implementovat do zoznamu metodu reverse ? v ramci aplikacie sa dokonca moze usetrit jeden zbytocny sort, kedze opacny sort sa vykonava az na druhy klik ...

nevraviac o tom, ze v pripade vektora ci double-linked-list je to operacia urcite menej narocna.

[Michal Kubeček]

Požadavkem bylo, aby se bez ohledu na to, zda se řadí vzestupně nebo sestupně, . a .. vypisovaly vždy na začátku, pak ostatní adresáře a pak teprve ostatní typy souborů. Tím by se i obracení seznamu trochu zkomplikovalo. Kdyby šlo o prosté otočení pořadí, vůbec nejjednodušší by bylo nepřerovnávat nic a pouze ten seznam v opačném pořadí vypisovat…

[happy barney]

v tom pripade mi prijde jednoduchsie . a .. nedavat medzi filelist, ale osetrovat ich mimo (to iste pre vsetky "specialne" subory). To iste by malo platit pre bodkove subory (vypisovat/nevypisovat/vypisovat bez bodky) ci adresar/neadresar (mixed/oddelene).

to by som radsej pouzil nejake filtre (v design pattern terminologii by to boli pravdepodobne dekoratory nad zoznamom), a/alebo miesto komparatora pouzit key-generator (hmm, asi tiez dekoratory, ale nad prvkami zoznami)

priklady key-generatory:
- pre kazdy sortovatelny prvok
- case sensitivity/insensitivity
- ignorovat/neignorovat non-word character na zaciatku retazca
- file extension

[Michal Kubeček]

Nedávat ty "mimořádné" soubory do normálního seznamu není IMHO moc dobrý postup, nemám rád výjimky, mají tendenci se nekontrolovaně množit. Spíš bych byl pro nějaký dodatečný atribut, který by se zohlednil i v algoritmu porovnávání. Podle něj by se pak mohlo provádět i to filtrování.

[happy barney]

preco vynimky? nasleduje pseudokod:

FileList head = FileList->search ('.', '..');
FileList tail = FileList->search (mask)->filter (head);

tail->filter (new OwnerOnlyFilter)->sort (new FileListNameKey);

....

Panel.show (head + tail);

[happy barney]

samozrejme, aj head by bolo mozne prametrizovat.
mozno este stoji za poznamku, ze radsej mat vynimku pre . a .. (kedze su svojim sposobom vynimocne i pre chovanie sa aplikacie), napr .. by sa mali/mohli zobrazit aj v adresari, na ktory ma clovek pravo x, ale nema pravo r.
takisto mi pripada nelogicke bastardit sortovacie funkcie specialnymi vynimkami

[Michal Kubeček]

Tohle se mi moc nelíbí. Buď bych byl pro jeden seznam (a nad ním postavené filtry a řazení) nebo pole několika samostatných seznamů (separátně tříděných a jednotlivě zobrazovaných nebo nezobrazovaných).

[happy barney]

v tom pripade som jednoznacne za to, ze . a .. su extra veci, spravovane panelom, mimo FileList-u.

teraz ma tak napadlo, ze vlastne chyba definicia chovania v pripade rovnosti kriteria (typu primarne podla mtime, potom size, potom reverzne name)

[Michal Kubeček]

No jo, jenže právě tohle jsou věci, kterými je IMHO lepší začít. Protože i když jde zdánlivě o detaily, může to mít podstatný vliv na to, která reprezentace dat bude nejvhodnější.

[Kyosuke]

Jóóó, ty chybějící closures, to je prasárna...

[elviin]

Napsal jsem to, neprekladal. Ale tak nejak bych is predstavoval pouziti stl, ktery to seradi za me, ja jen nadefinuju porovnani - coz uz je. Vyhodu vidim v tom, ze mam moznost vyberu kontejneru i algoritmu porovnani + std::sort je uz hotovej, tzn. ze muzu komponovat do sebe ruzny strategie.

typedef shared_ptr< FileInfo > FileInforPtr;

class RuntimeFileCmp {
public:
    enum cmp_mode {default_mode, size_mode, name_mode, ext_mode, attrs_mode, owner_mode, group_mode, date_mode};
private:
    cmp_mode mode_; //column
    bool ascending_;

    int FileInfoList::compare_size(const FileInforPtr &fi1, const FileInforPtr &fi2) const;
    int FileInfoList::compare_name( const FileInforPtr &fi1, const FileInforPtr &fi2) const;
    int FileInfoList::compare_ext( const FileInforPtr &fi1, const FileInforPtr &fi2) const ;
    int FileInfoList::compare_attrs( const FileInforPtr &fi1, const FileInforPtr &fi2) const;
    int FileInfoList::compare_owner( const FileInforPtr &fi1, const FileInforPtr &fi2) const;
    int FileInfoList::compare_group( const FileInforPtr &fi1, const FileInforPtr &fi2) const;
    int FileInfoList::compare_date( const FileInforPtr &fi1, const FileInforPtr &fi2)const;
public:
    RuntimeFileCmp( cmp_mode m = default_mode, bool ascending = true ) : mode_( m ), ascending_( a ) 
    {
    }
    void setComparisonMode( cmp_mode m = default_mode ){
        mode_ = m;
    }
    cmp_mode getComparisonMode() const {
        return mode_;
    } 
    void setOrderingMode( bool a = true ){
        ascending_ = a;        
    }
    bool getOrderingMode() const {
        return ascending_;        
    }
    bool operator()( const FileInforPtr fi1, const FileInforPtr fi2 ) const
    {
        switch( mode_ )
            {
                    case 0:
                            compareRes = compare_name( fi1, fi2 );
                            break;
                    case 1:
                            compareRes = compare_ext( fi1, fi2);
                            break;
                    case 2:
                            compareRes = compare_size( fi1, fi2 );
                            break;
                    case 3:
                            compareRes = compare_date( fi1, fi2 );
                            break;
                    case 4:
                            compareRes = compare_attrs( fi1, fi2 );
                            break;
                    case 5:
                            compareRes = compare_owner( fi1, fi2);
                            break;
                    default:
                            compareRes = compare_group( fi1, fi2);
                            break;
            }
        return compareRes > 0;
    }
};


typedef std::set< FileInforPtr, RuntimeFileCmp > file_set_t; //kontejner XY

/////////////////////////////////////////////////////////////

//v kodu

RuntimeFileCmp<slo by to udelat i obecne> compareDate(RuntimeFileCmp::date_mode, false);
RuntimeFileCmp compareName(RuntimeFileCmp::name_mode, true);
file_set_t fileSetCompName( comapreName );
file_set_t fileSetCompDate( compareDate );

fileSetCompName a fileSetCompDate se sami seradi, kdyz budu chtit jiny zpusob, tak set priradim jinymu;
nebo pouzit komparator RuntimeFileCmp pro funkci std::sort, tj. data budou ve vektoru a ty vzdy seradim podle 
toho jak vytvorim objekt k razeni, tj. RuntimeFileCmp.

Vse by se navic dalo parametrizovat. Je tu vyhoda oddelenych dat a algoritmu, navic, kdyz uz jsou napsany...

[Michal Kubeček]

Tohle mi nepřipadá úplně šťastné, protože se při porovnávání každých dvou souborů bude zbytečně znovu procházet ten switch. Spíš bych volil řešení využívající polymorfismu, tj. něco podobného jako jsem navrhoval zde.

[elviin]

No videl jsem to reseni, libi se mi, ale ted mi IMHO prijde daleko lepsi udrzovat dejme tomu N std::set[u], kde N je pocet kriterii (ruznych komparatoru). A vzdy kdyz budu potrebovat vypsat data jen pouziju set, ktery radi podle zvoleneho kriteria. Je to staticke reseni, ale rychlejsi nez switch i nez dynamicky bindovani. sety by se vytvorily "na pozadi".

[Michal Kubeček]

Proti téhle části řešení nic nenamítám, nelíbil se mi jen ten detail, že se větvení podle kritéria provádí při každém porovnání dvou souborů znovu. Já vím, je to pár instrukcí, ale člověka, který se učil programovat na PMD-85, nepředěláte… :-) Ono by koneckonců šlo ty dvě myšlenky spojit dohromady, tj. sestavit po změně kritéria seřazený container (jako to děláte vy), ale za pomoci specializovaného komparátoru (jak jsem naznačoval já).

[elviin]

Ono to vyznelo, jako ze smahem odmitam to, co jsi navrhnul, to ne, urcite je to elegantni a ja se taky switchum vyhybam, jak to jen jde. Ale zaroven se snazim vsechno, pokud to zdroje dovolujou vyresit staticky.