Konstantní složitost u jednosměrného spojového seznamu

24.10.2010 23:03 | Přečteno: 2378× | Linux a další věci co má společného s IT

Tak už jsem dlouho nenapsal žádný blog, tak jsem se rozhodl, že spojím užitečné se zábavou. Takže jelikož jsem v poslední době byl někým žádán abych mu poskytl svůj program pro názorný výpočet determinantu (Python a PyQt vše je v dokumentaci), tak ho vložím i sem. Třeba se to taky někomu bude hodit. Dál se pokusím najít Salxeso (pexeso psané v Javě, samozřejmě psané jako semestrálka, takže to není žádný zázrak) do kterého mi tady někdo taky dělal hrací karty.

A teď se konečně dostáváme k věcem, na které jsem se zdejších odborníků chtěl zeptat, zda jsou vůbec proveditelné. Takže dostali jsme za úkol na C/C++ abychom napsali spojoví seznam. Na tom není nic těžkého podmínky byly jasně stanoveny, aby byl jednosměrný a aby obsahoval určité metody a to konkrétně: head(), first(), last(), isEmpty(), popFront(), pushFront(SItem), pushBack(SItem), insertAfter(SHandle *, SItem), concat(SList *), makeEmpty,moveAfter(SHandle *,SHandle *), moveToFront(SHandle *), moveToBack(SHandle *), remove(SHandle *). Na tom by nebylo nic složitého, ale máme další podmínku a to aby tyto metody měli konstantní časovou složitost, ale zde již narážím. Skoro všechny metody lze udělat s konstantní časovou složitostí ale pouze s dvousměrným seznamem (alespoň se tak domnívám). Konkrétně mi jde o tyto metody: insertAfter(SHandle *, SItem), makeEmpty, moveAfter(SHandle *,SHandle *), moveToFront(SHandle *), moveToBack(SHandle *), remove(SHandle *). U těchto metod totiž potřebujeme vědět předchůdce objektu (prvku) a jedinou možností, která mě napadá je si celý seznam projít a nalézt hledaného předchůdce, tudíž se dostáváme na časovou složitost algoritmu O(n). Navíc třeba metoda makeEmpty, která má celý spojoví seznam zahodit nelze v C++ realizovat, pokud používáme dynamické přidělování paměti, protože by nám objekty zůstali vyset v paměti, ale nevím jestli se i tohle počítá do časové složitosti toho algoritmu, ale řekl bych, že ano.

Tak co jaký názor na to mát? Myslíte si někdo, že to půjde, nebo je to pouze špatně zadané? Nebo jsem úplný blbec (to jsem )?

       

Komentáře

[Saljack]

Příloha:

• Madet.zip (392871 bytů)

Tady je ten program pro názorný výpočet determinantu.

[Saljack]

Příloha:

• Salxeso.jar (183983 bytů)

A tady Salxeso nevím co je to za verzi, takže tam něco nemusí jít ale snad by to měla být ta poslední. Spuštění klasicky "java -jar salxeso.jar"

[Martin Tůma]

IMHO se ty operace dají udělat i s jednosměrně zřetězeným seznamem v konstantním čase, jenom to neni zrovna obvyklé řešení (to s "přesměrovánim" ukazatelů).

Operaci vyjmout prvek lze totiž udělat i tak, že si zapamatuješ "obsah" prvku a ten nahradíš "obsahem" jeho následníka (včetně ukazatele na následující prvek).

[Saljack]

Jo tohle mě nenapadlo tak by to šlo.

[Saljack]

Otázkou je, jestli tohle je zrovna dobré řešení a není náhodou celkem zbytečné. Nebude to už moc obecné, protože budu muset mít něco co ten objekt bude kopírovat a příjde mi to celkem zbytečné.

[Saljack]

Tak je to dobré řešení , protože tam mám ukazatele na ty prvky, takže je stačí jenom prohodit a nemusím nic kopírovat. Takže dík.

[xxx]

Tak to jsem zvedavej jak. Ja totiz myslim, ze u toho jednosmerneho seznamu je hlavni problem se tim, abys nasel nejaky prvek, ze se nedostanes pod O(n). Abych to zjednodusil, predpokladejme obyceny jednosmerny spojovy seznam o N prvcich. Chci vratit N-1 prvek (to kdyby snad chtel mit nekdo pointr na last). Jak to udelat v N-1 krocich?

[xxx]

Ha tak stara felacka struktura Tumic mi poradila, ze treba u insertAfter mam ptr na prvek za ktery chci vkladat, tak jako bych nic nerek.

[kralyk z abclinuxu]

jej, tak jsem byl pomalejší...

[Martin Doucha]

Tohle má dva háčky:

1) Bude to za konstantu jen za předpokladu, že kopírování datové položky je za konstantu. To obecně nemusí platit.

2) Nepůjde smazat poslední prvek. I kdyby typ datové položky měl nějakou speciální "prázdnou" hodnotu, nebude jak správně aktualizovat ukazatel na konec seznamu, který je potřeba pro jiné operace.

Jediná věc, která mě napadá, je předávat trhacím operacím seznam s hlavou, tedy předka skutečně trhané položky. Pak to fungovat bude.

[Saljack]

1) Řešit nemusím, protože mám ty prvky jako ukazatele, tak je pouze nahradím. 2) To je pravda a celý se mi to asi zbořilo jak hromádka z karet.

[Martin Tůma]

2) Nepůjde smazat poslední prvek. I kdyby typ datové položky měl nějakou speciální "prázdnou" hodnotu, nebude jak správně aktualizovat ukazatel na konec seznamu, který je potřeba pro jiné operace.

Místo ukazatele na poslední prvek seznamu můžeš udržovat ukazatel na předposlední prvek.

[Saljack]

Ale to nic nevyřeší, protože pak nebudeš mít zase ten ukazatel na ten předposlední, takže jsi v pytli .

[Martin Tůma]

?! Ukazatel na předposlední prvek si právě budeš pamatovat. A jestli si myslel "poslední" místo "předposlední", tak k tomu se z předposledního lehce dostaneš v konstantnim čase...

[Saljack]

No to sice jo, ale co když budeš potřebovat odebrat 2x za sebou poslední prvek, v tomto případě už nemůžeš zjistit ten předposlední prvek.

[Martin Tůma]

Máš pravdu, teorie s předposlednim prvkem je blbost. Nicméně by to mělo jít udělat přes "fixní" poslední prvek seznamu. Tzn. poslední prvek seznamu by byl "speciální" prvek, který by se nikdy nemazal.

[Saljack]

To ale taky nejde, protože já potřebuju vracet i ten poslední prvek a tím pádem bych musel ten seznam projít.

[Martin Tůma]

Myslim to tak, že ten poslední prvek nebude navenek součástí seznamu. Seznam prostě pro N "uživatelskejch" prvků bude mít interně N + 1 prvků.

[Martin Doucha]

Máš dvě možnosti. Buď ukazatel na poslední prvek v hlavičce seznamu ukazuje na prvek N+1, a pak je k ničemu, nebo ukazuje na prvek N, ale pak ho neumíš opravit při mazání prvku N.

[Saljack]

Takže to takhle nejde, můžete to ještě někdo porvrdit ať dneska nejsem za vola, když se ho na to budu ptát.

[Martin Doucha]

Ono to jde, ale prostě musíš jako parametr dostávat ukazatele na předka a ne přímo na mazaný prvek.

[Saljack]

Jenže toho předka musíš někde nalézt a ten lze nalézt jenom za pomocí toho, že projdu celý seznam a to je opět lineární složitost, takže jsi stejně kde jsem akorát si problém rozložil na dva.

[Martin Doucha]

Jasně, ale o tuhle lineární složitost už se nemusíš starat, protože jí musí zaplatit ten, kdo ty operace volá. Obecně platí, že když máš operace insert, delete a findMin, tak všechny za konstantu mít nemůžeš (ani amortizovanou), aspoň jedna z nich musí mít složitost aspoň log(n).

[Saljack]

Jako šlo by to, ale bude to celkem divný, hlavně třeba u mazání dostávat předchůdce mazaného prvku je celkem blbost .

[Saljack]

Je pravda, že tohle v zadání není

[Gilhad]

No, urcite jde vymyslet priklad, kdy vysledek nejakeho vypoctu bude "tady je prvek, nastav ho takhle a ten za nim smaz" :)

A navic, pokud se jedna o zadani ukolu do skoly, tak neni tak kriticky dulezite resit, k cemu by se to pouzivalo, pokud by se to snad nekdy pouzilo, ale je potreba resit jak to udelat, abych dodrzel zadani a ziskal pozadovany vysledek.

(Ac to zni absurdne, tak pokud je pozadovana pouze konstantni casova narocnost, ale nikoli efektivita, tak by kazde to vloani mohlo jako vedlejsa spocist pi na tisic cisel a vysledek zahodit. Porad by to bylo konstatni v case, i kdyz absolutne neefektivni, cili zadani by to stejne doslovne splnilo. Takze pokud neni v zadani i hlavicka funkce, tak je teoreticky mozne si ji navrhnout tak, aby obsahovala pointer na predchozi prvek a osetrit specialni pripad zacatku seznamu.)

[petris]

Vzhledem k tomu, ze v zadani nebyla konstantni operace next(), tak si muzes udelat ty ukazatele opacne. Pak jsou vsechny operace az na next a vymazani celeho seznamu konstantni.

[Saljack]

next musí mít taky konstantní složitost.

[kralyk z abclinuxu]

insertAfter(SHandle *, SItem), makeEmpty, moveAfter(SHandle *,SHandle *), moveToFront(SHandle *), moveToBack(SHandle *), remove(SHandle *). U těchto metod totiž potřebujeme vědět předchůdce objektu (prvku)

Předpokládám, že předchůdce je právě ten první parametr. Čili hledat ho nepotřebuješ: insertAfter(SHandle *item, SItem) {item->next = /*novej prvek*/;}
moveToFront je jednoduché.
A remove konstatně moc nejde, leda že bys hodnotu následujícího překopíroval do toho k odebrání, napojil ten následující za následujícím a uvolnil následující.
moveToBack a moveAfter imho konstatně nepůjdou.
makeEmpty nevím co znamená, ale jestli to zahrnuje uvolňování paměti všech, konstatní složitost to určitě mít nebude...

[kralyk z abclinuxu]

Počkat, moveToFront vlastně jednoduché není, ledaže bys zase přehazoval hodnoty, což by se týkalo všech move* a pak by to bylo konstatní.

Jinak můžeš se mrknout sem, složitost tam je popsaná..

[Saljack]

To moveToFront je jednoduché, protože máš prvek, který je jako první (head) ale není součástí seznamu (tak to bylo v zadání). Jenže když ten prvek posuneš musíš ho z jeho pozice odebrat a musíš nějak udělat aby ten předcházející prvek odkazoval na ten další a to problém je, ale jde to řešit jak již někdo napsal výše tím, že se ten další prvek nakopíruje na místo prvku, který chci přesunout.

[kralyk z abclinuxu]

že se ten další prvek nakopíruje na místo prvku, který chci přesunout.

Jj, tak jsem to myslel. Dalo by se to udělat tak, že bys ty hodnoty do toho seznamu nevkládal přímo, ale přes pointer - "kopírování" by pak bylo jednoduchý. Ono s nějakým nasazením třeba templatů nebo něčeho by to v podstatě takhle dopadlo tak jako tak...

[Saljack]

No oni naštěstí ty pointry (na ty objekty) jsou v zadání takže jsem to měl už připravené jenom jsem to upravil .

[Saljack]

Ale to makeEmpty konstantně nejde

[Martin Tůma]

Taky to jde, když pro seznam použiješ jeden "buffer" (kterej budeš třeba exponenciálně zvětšovat) a nebudeš alokovat paměť pro každý prvek zvlášť.

[Saljack]

Ale tím už bych neměl konstantní třeba přidání prvku ne?

[Martin Doucha]

Bude to amortizovaně konstantní. Jeden insert sice může způsobit kopii celého pole, ale při exponenciálním zvětšování počtu položek bude nasčítaný počet zkopírování jedné položky ku počtu položek celkem konstanta.

[Saljack]

Otázkou je, jestli amortizovaně konstantní je také konstantní u tohle si právě nejsem jistý.

[Martin Tůma]

Správnou odpověď ti dá asi jenom zadavatel, tedy cvičící. Já bych to tipoval, že operace smazat seznam konstantní bejt nemusí, jenom to neni v zadání explicitně napsaný. V nejhoršim případě můžeš prostě jenom "vynulovat" ukazatel na začátek seznamu a argumentovat tim, že o uvolňování paměti se v zadání nic nepíše .

[Saljack]

No tak já tam to uvolnění nechám, s tím, že ten algoritmus bude mít konstantní složitost pokud ho vezmeme jako jazykově nezávislý .

[Grunt]

IMHO si zase cvičící/zadávající představuje, že ta metoda/funkce nacpe do nějakého pracovního registru nebo proměnné místo pointeru na začátek či libovolný prvek seznamu hodnotu NULL, čímž se ztratí jakákoliv reference na celý seznam a o zbytek se postará Garbage collector (jeho režije už se asi těžko nějak spojovat s programem samotným a většinou stejně to místo nevratí, ale označí ho za volné a bude použito pro další alokace v rámci frameworku, takže krom nějakého blbého papírování celkový propálený čas null komma null). Teda to by aspoň platilo pro C++. V céčku už by to bylo horší. Asi by to chtělo něco ve smyslu flagů pro každý prvek a určit jestli je prvek ještě k něčemu a nebo už k ničemu a dá se použít při dalším vkládání (nebudeš muset zbytečně alokovat, ale můžeš prvek rovnou požít a data v něm jen přepsat). No do realokace a zvětšovaní/zmenšovaní spojitého bufferu bych se určitě nepouštěl. To je blbost. Přijdeš tím skoro o všechny výhody spojovaného seznamu. To už z toho potom radši udělat nějaké chytřejší pole, čímž tu konstantní složitost zajistíš téměř určitě.

[Grunt]

a nebo si ten Garbage collector můžeš implementovat sám. Udělat ještě jeden seznam prvky alokované, ale jinak úplně na h*vn*, v případě že budeš chtít alokovat, tak můžeš mrknout do toho druhého seznamu a prvky už alokované jen znova přidělíš a ještě si do toho napíšeš nějakou čistící rutinu, která po nějaké časové periodě mrkne do toho druhého seznamu a pokud v něm bude nějaký prvek, tak ho podle pointerů projede a celý uvolní. U procedur z vnějšího rozhraní dodržíš zadání a jak se to dělá uvnitř už nikoho nemusí zajímat.

[Martin Doucha]

No, mazání seznamu po jednotlivých prvcích se dá spáchat i tak, že se ten seznam hodí do pomocného pointeru a při libovolné jiné operaci se z pomocného pointeru smaže nějaký konstantní počet prvků. Celkově tak nekonstantní složitost může mít jedině destruktor kontejneru, který musí zbytek uklidit najednou.

[Saljack]

To by šlo ale je to celkem prasárna

[Josef Kufner]

Té kopii se dá vyhnout. Viz Qt Container Classes

[Martin Doucha]

Tahle technika je ale podvod, spoléhá na to, že log(n) je konstanta.

[Josef Kufner]

Naopak, ono to z toho tu (malou) konstantu dělá.

[Kvakor]

Ale to makeEmpty konstantně nejde

Jde, ale ne standardní alokaci paměti. Je třeba použít jiný typ alokace, tj. buď si jí dělat osobně (např. přes mmap()), nebo použít nějaký hiearchický alokator, jako třeba obstack nebo talloc. Když pak chcete zahodit celý seznam, tak stačí jen zrušit kontajner, ve kterém jsou jednolivé objekty alokovány.

[Martin Mareš]

Spoléháte ovšem na to, že mmap() má konstantní časovou složitost, což (1) Vám nikdo neslibuje, (2) není pravda.

[Kvakor]

V praxi se mmap()uje /dev/zero, což je metoda, jakou používají používají i standardní knihovny (vedle brk()/sbrk()). Za optimálních podmínek je odmapování otázka jediného volání jádra, takže v praxi nemá uživatelský program stejně žádnou rychlejší metodu, jak navrátit paměť operačnímu systému.

V moderních OS je dokonce možné ještě dále snížit režii jádra použitím stránek větších než 4KB (běžně 1MB, u nejnovějších procesorů až 1GB), což má i kladný vliv na rychlost přístupu k této paměti (lepší využitím TBL cache). V ultimativním případě se dá celá komplikovaná struktura uvolnit v čase velmi blízkém O(1), tedy pokud se do takovéto olbřímí stránky vejde celá.

Bohužel opravdu konstantí časová složitost opravdu zajistit nejde, ale dá se jí dost přiblížit zamknutím stránek v paměti a naplánování se jako realtime proces. Jenže pravé realtimové procesy stejně většinou nepoužívají klasickou dynamickou alokaci, buď mají všechny struktury statické, nebo přidělují bloky pevné velikosti.

[Martin Mareš]

Režie mmap() zdaleka nezávisí jenom na stránkách, ale (zrovna v případě Linuxu, jiné systémy na tom jsou podobně) i na režii VMA-listů, které mají logaritmickou složitost vzhledem k počtu prvků – jsou to ve skutečnosti vyhledávací stromy, protože je potřeba umět pro nový blok paměti najít volné místo v adresním prostoru. Zamykání stránek od toho nepomůže.

[rastos]

Operácie nad jednosmerne zreťazeným zoznamom nemajú konštantnú zložitosť, pretože ak chceš nájsť N-tý prvok, potrebuješ aspoň N posunutí. Čo ti bráni posúvať sa po tom zozname ďalej, aj keď si už našiel N-tý prvok? Nerob program optimálny. Rob program, ktorý vyhovuje zadaniu.

[Saljack]

To s tou konstantní složitostí je právě součástí zadaní. Přesněji:

Implementujte třídy SHandle, SItem a SList, reprezentující prvky jednosměrně zřetězeného seznamu. SList - samotný spojový seznam, SHandle - ukazatel na SItem, SItem - prvek seznamu Implementujte operace pro SList head(), first(), last(), isEmpty(), popFront(), pushFront(SItem), pushBack(SItem), insertAfter(SHandle *, SItem), concat(SList *), makeEmpty,moveAfter(SHandle *,SHandle *), moveToFront(SHandle *), moveToBack(SHandle *), remove(SHandle *) s konstantní složitostí a findNext(SItem *, SHandle *) se složitostí O(n).

[rastos]

Ešte raz: zadanie hovorí, že zložitosť má byť konštatná. Nehovorí, že algoritmus má byť rýchly (optimálny). Porovnaj nasledovné:

found=false;

for (c=str;*c; c++)
  if (*c=='a')
  {
     found=true;
 
  }
for (c=str;*c;c++)
  if (*c=='a')
  {
     found=true;
     break;
   }
printf("found %d\n",found);

[Saljack]

Ale tohle je lineární složitost O(n).

[qk_]

Tak samozrejme ze to jde. jde jen o vhodnou strukturu :) A kdyz mas to jako ukol tak by sis to mel sam vymyslet.

Ale tak par rad. mit v spojaku data je blby kvuli jejich kopirovani, takze je lepsi tam mit spojak co ma kazdy prvek dva ukazatela data a next. Celej spojak by mel tyto dalsi udaje: prvni prvek specialni posledni prvek, kterej je koncovej

a ted metody kde nevis: insertAfter(SHandle *, SItem), to mi prijde jednoduche vlozeni do seznamu, kde je problem?

makeEmpty pokud pouzivas komulovanou slozitost tak neni problem. Obecne pokud chces uvolnovat data, tak se to problem.

moveAfter(SHandle *,SHandle *) operave remove + insert after obe konstantni (dle zadani)

moveToFront(SHandle *) to samy co vys - slozeni dvou konstantnich ( dat neco dopredu je v pohode)

moveToBack(SHandle *) remove + vyuzijes specialni psoledni prvek tak jak je definovan

remove(SHandle *) jak uz nekdo psal vyse, zkopirujes dva ukazatele nasledovnika do prvku, tim zustane predkovi validni ukazatel pokud odstranujes posledni prvek (posledni nespecialni). Tak na zacatku to snadno zdetekujes pres porovnani a udelas specialni prvek z toho odstranovanyho a odalokujes ten specialni ( tedy

if next == end
  free (end);
  end = this;
end;

to ti zaruci, ze spojak stale ukazuje spravne.

[Saljack]

Tohle právě nejde, protože já potřebuj vědět pokaždé, který prvek je poslední a to pokud odeberu poslední prvek prostě nevím. Musím celý seznam znovu projít až na konec a tím už to není konstantní. Proto nejde odebírat (přesouvat) ty prvky konstantně. A jestli jsem to správně pochopil, tak to co jsi popsal s tím speciálním posledním prvkem vůbec nic neřeší a je to stejně lineární.

[qk_]

neni, vzdy vys, ze posledni prvek je ten specialni.

Tedy kdyz odeberes posledni normalni, tak specialni ma novou adresu stejnou mel ten posledni normalni ( trik je v tom, ze zachovavas adresu prechudce ).

Ukaz mi operaci, kdy potrebujes znovu projit seznam a ja ti reknu, jak to udelat bez toho.

[Saljack]

Vrátit poslední prvek, po odebrání posledního "normálního".

[qk_]

Jestli chapu co chces (tedy vratit jen data po remove, protoze PopLast tam nevidim), tak tenhle kod to dela

def remove (link)
  if link.next == List.last
    data = link.data
    List.last = link
  else
    #normalni remove
  end
  return data
end

[qk_]

Ha, tak uz asi vidim tu problematickou metodu...je fakt, ze metoda last nevrati to co clovek ceka, ale bez ni by to fungovalo :)

[Saljack]

To jo ale ta last by zase nebyla konstantní to je prostě začarovaný kruh

[Andrej]

To přece není až tak složité. Trik je v rozdílu mezi SHandle a SItem.

SHandle je datová struktura pro uživatele transparentní; je to nějaký pointer do seznamu, s nímž uživatel nebude nic provádět, jen ho může podstrčit tomu API. (Tedy obdoba C++ iterátoru.) Takové věci se většinou ve veřejných headerech nechávají jako incomplete type, aby se je nikdo nesnažil nějak „instanciovat“ nebo kopírovat. (Ale to není podstatné.)

No a když mám přímo pointer na prvek toho seznamu, je implementace insertAfter(SHandle *, SItem) v O(1) triviální.

Pro jednoduchost (a odstranění zbytečných ifů) je dobré mít v seznamu vždy alespoň jeden prvek, tedy jakousi hlavu, která v případě prázdného seznamu bude ukazovat sama na sebe. Implementaci to výrazně zjednoduší. A co je ještě důležitější — umožní to navíc implementaci insertBefore(SHandle *, SItem) v O(1). Struktura SHandle jednoduše nebude ukazovat přímo na referencovaný prvek seznamu, ale na jeho předchůdce. Implementace insertBefore() i insertAfter() v O(1) je pak snadná.

Ještě jednou základní pointa:

• insertAfter(SItem where, SItem newItem) lze u seznamu provést pouze v O(n).
• insertAfter(SHandle * where, SItem newItem) lze provést v O(1).
• Pro oba typy insertBefore() platí totéž.

[Andrej]

Zapomněl jsem to explicitně napsat, ale požadované moveAfter(), moveBefore(), moveToBack() či moveToFront() se vyřeší obdobným způsobem. Když potřebuješ znát předchůce, ukazuj prostě pomocí SHandle * na předchůce a ne přímo na referencovaný prvek.

[Saljack]

Tohle ale vůbec nic neřeší, protože když budu potřebovat zjistit následníka toho prvku tak jsem opět na lineární složitosti.

[Gilhad]

Jak neresi? Mam-li prvek, tak jeho nasledovnik je prvek->next coz je konstantni nactenihodnoty. Nic vic.

[Saljack]

Já jsem to špatně asi pochopil. Myslím si, že jsi měl na mysli, že těm funkcím budu dávat toho předchůdce prvku, který budu chtít přesunout (odebrat). Je to tak? V tomhle případě to jde a asi to tak udělám i když se mi to zdá celkem jako blbost.

[Xerces]

A co to naprogramovat tak jak potrebujes a tu konstantni casovou slozitost zajistit nejakym wait cyklem. Teda ze by sis urcil nejakou dostatecne velkou casovou konstantu, potom spustil ten tvuj algoritmus a spocital cas behu a po zbytek bys sleepoval

[David Watzke]

Stačilo říct: použij the Microsoft way.