Optimalizace spojového seznamu – Pascal – Fórum – Programujte.com

Ahoj,

Nevíte jakym způsobem by šlo urychlit procházení spojového seznamu kde závisí na názvu položky?
příklad:

polozka = record

  nazev : string;

  dalsi : ^polozka;

end;

strom = record

  nazev : string;

  cislo : dword;

  vlevo : ^strom;

  vpravo : ^strom;

end;

no ono se blbe radi podle nazvu...
lepsi je udelat si pole nejakejch jednoduchejch hashu... kdyz zvolis dobrou hashovaci funkci tak se ti to rozlozi pekne do tech hodnot a u kazdy z nich budes mit uz ten spojovej seznam... akorat tam bude jen par polozek

Jenže pro hash musim znát počet prvků ne? A to já nevim, může jich bejt 100, může jich bejt 500, může jich bejt ale i třeba 2 000 000...

hash se pocita z toho klicovyho slova... klidne si muzes propocitat na pouhejch 256 hashu... jediny co to chce je aby kolize byly rovnomerne rozlozene... tj abys to nemel nakonec snadnejsi fakt tim jednim spojovym seznamem
nebo si udelat index... ale s indexama sem nedelal takze nevim...

To Wimby : Udělej si AVL či červenočerný strom založený na lexikografickém uspořádání těch stringů.

Jo, ty stromy sou mi jasný, ale jak mam udělat to lexikografický uspořádání? Nejlepší by bylo, aby pro každej název šlo udělat nějaký unikátní číslo, který bych porovnával jenom jestli je větší, menší nebo se rovná.

teď to vypadá asi takhle:

type

  pSeznam = ^tSeznam;

  tSeznam = record

    jmeno : string;

    dalsi : pSeznam;

  end;



function Hledej(polozka : pSeznam; jmeno : string) : pSeznam;

begin

  while assigned(polozka) do begin

    if polozka^.jmeno = jmeno then begin

      Hledej := polozka;

      exit;

    end;

    polozka := polozka^.dalsi;

  end;

  Hledej := nil;

end;

type

  pStrom = ^tStrom;

  tStrom = record

    jmeno : string;

    cislo : dword;

    vlevo : pStrom;

    vpravo : pStrom;

  end;





function VypocitejCisloPodleJmena(jmeno) : dword;

{...}



function Hledej(vetev : pStrom; jmeno : string; cislo : dword) : pStrom;

begin

  while assigned(vetev) do begin

    if vetev^.cislo = cislo then begin

      Hledej := vetev;

      exit;

    end else if cislo < vetev^.cislo then

      vetev := vetev^.vlevo

    else

      vetev := vetev^.vpravo;

  end;

  Hledej := nil;

end;

To Wimby : No to je přece velmi jednoduché. Víš, jak vypadá seřazení slov podle abecedy?

Příklad: Adéla < Bětka < Budulínek < Cecílie < Delfín...

Co je na tom k nepochopení? Pokud chceš dělat hashe, tak to nedělej jako stromy, ale jako hašovací tabulky. Nepoužívej MD5, protože je tak pomalá, že ti to rychlejc projde ten strom.

To je fakt, na to sem nějak zapomněl :-D

čili to bude vypadat nějak takhle:

type

  pStrom = ^tStrom;

  tStrom = record

    jmeno : string;

    vlevo : pStrom;

    vpravo : pStrom;

  end;





function PorovnejJmena(jmeno1,jmeno2) : shortint;

var

  i : byte;

begin

  for i := 1 to length(jmeno) do

    if ord(jmeno1[i]) < ord(jmeno2[i]) then begin

      PorovnejJmena := 1;

      exit;

    end else if ord(jmeno1[i]) > ord(jmeno2[i]) then begin

      PorovnejJmena := -1;

      exit;

    end;

  if length(jmeno1) = length(jmeno2) then

    PorovnejJmena := 0

  else

    PorovnejJmena := 1;

end;



function Hledej(vetev : pStrom; jmeno : string) : pStrom;

var

  cislo : shortint;

begin

  while assigned(vetev) do begin

    cislo := PorovnejJmena(vetev^.jmeno,jmeno);

    if cislo = 0 then begin

      Hledej := vetev;

      exit;

    end else if cislo < 0 then

      vetev := vetev^.vlevo

    else

      vetev := vetev^.vpravo;

  end;

  Hledej := nil;

end;

To Wimby : Ano, ale až budeš programovat insert a delete, nezapomeň na vyvažování (stále hrozí, že ti tam někdo zadá uspořádanou posloupnost).

Já bych se rozhodoval podle toho, jak často bys měnil prvky v seznamu - tedy jak často bys je přidával a ubíral.

1) Jestli je to tak, že na začátku programu vytvoříš spojový seznam a potom ho už neměníš a jenom z něho čteš, tak bych ho převedl na obyčejné setříděné pole.

2) Jestli ho intenzívně měníš, tak je nejlepší řešení binární strom. Na hashování bych se být tebou vybodnul - uvědom si, že MD5 hash má 16 bajtů, kdežto ty zas tak často nebudeš řešit případ, kdy by se odlišnost v řetězcích projevovala až na 17. znaku či dále. Pro porovnávání řetězců ani není nutné psát funkce pro převod na číslo; klidně můžeš napsat: if S1>S2 then ...

3) Jestli ho měníš jenom občas, tak můžeš buďto zase použít binární strom nebo se můžeš pokusit o tabulku odkazů uvnitř spojového seznamu. Struktura by potom vypadala takto:

polozka = record

   nazev:string;

   dalsi:^polozka;

   vestsi,mensi:^polozka;

   end;

Aha, opožděně mi došlo, k čemu by ty hashe mohly bejt dobrý - jako obrana proti tomu, aby ti nevznikl nevyvážený strom. No... Ale i tak si myslím, že by bylo lepší obejít se bez nich.

Jj, hashe dělat nebudu...

To Laaca : Je to něco mezi 1) a 2) :-)
Je to na strukturu symbolů v kompileru. Na začátku vkládám přibližně 50 údajů-identifikátorů (standatdní názvy typů, funkcí, operátorů, konstant a proměnných) a pokaždé když při kompilaci kódu narazim na identifikátor, tak se hledá, jestli náhodou už neexistuje. Ovšem od těch identifikátorů očekávám, že v tom seznamu nejsou, proto se musí, podle mě zbytečně, projíždět celej spojovej seznam a to pokaždý, když se narazí na identifikátor... je to sice prkotina, ale už mam kompiler "skoro" hotovej, tak se koukám, co by tam šlo zrychlit :-)
A taky chci mít úpravy co nejsnazší, abych nemusel přepisovat celej kompiler :-)
Jo a ještě co se týče toho seznamu identifikátorů, tak ten se maže naráz na konci kompilace...

Napadla mě ještě jedna věc, menuje se to myslim přeskokovej seznam a vypadá to nějak takhle:

4---------------8---------------nil
2-------4-------6-------8---nil
1---2---3---4---5---6---7---8---9---nil

Kde když budu chtít 8, tak jí budu mít na dva kroky, ale nevim pořádně jak to udělat a taky mi přijde, že ty stromy budou rychlejší a zaberou míň paměti

No, přeskokový seznam mi příjde složitý na naprogramování. Potíž je, že s každou modifikací toho hlavního seznamu bys musel synchronizovaně měnit i přeskoky. To už mi příjde schůdnější přidat do spojového seznamu odkazy na abecedně vyšší a abecedně nižší prvek.

Spíš bych ti ale radil se v první fázi na třídění spojového seznamu vykašlat, napsat první neoptimalizovanou verzi kompilátoru a eventuálně se k tomu vrátit až později, kdy budeš program optimalizovat na rychlost.
Můžeš třeba zjistit, že pro normální programy bude i zcela neoptimalizovaný překladač na dnešních průměrných počítačích rychlý zcela dostatečně.

To Wimby : Nejrychlejší v tomhle případě bude hašovací tabulka.

To Laaca : Asi na to teda kašlu... ale pořád na to musim myslet, že je tam něco, co vim že by nějak šlo zrychlit a nedává mi to spát :-)
Taky nechci dělat dvě verze kompileru, ale jednu pořádnou :-)
Ale nechám to teda na poslední fázi... což stejně už bude brzy :-) a pak teda asi udělám normální binární vyhledávací strom a po každym insertu ho převážim, to bude rychlejší než spojový seznam a bude to delší jenom o pár desítek řádků :-)

Ještě mě napadá taková menší příšernost. Identifikátory by se uložily do stromu; každý uzel by se mohl větvit do tolika větví, kolik je symbolů, ze kterých můžou být identifikátory sestavené. Takže mám třeba slovo 'END'. Začnu na kořeni stromu, skočím podle ukazatele na indexu 'E', v dalším uzlu podle 'N' atd.. Když se dostanu na nil dřív než projdu celé slovo, tak zřejmě neexistuje (a hned ho tam můžu přidat).
Výhoda: vysoká rychlost, jednoduché vkládání.
Nevýhoda: velké nároky na paměť.

Jo, to, co popisuješ, se nazývá slovníková struktura a skutečně se používá pro uchovánání slovníků. Používají ji třeba našeptávače nebo automatické korektory překlepů.

To Mircosoft : To neni špatnej nápad :-)
Akorát nevim jak by se to dalo udělat...

teď ta struktura symbolů vypadá přibližně nějak takhle:

symbol = record

  jmeno : string;

  dalsi : ^symbol;

  {...}

  case typ : (konstanta,promenna,typ{...}) of

    konstanta : (definiceKonstanty : ^definice;

      hodnotaKonstanty : hodnota);

    promenna : (definicePromenne : ^definice;

      typPromenne : typyPromennych);

    typ : (definiceTypu : ^definice);

    {...}

  end;

seznam = record

  uzel : ^uzel;

  dalsi : seznam;

end;



uzel = record

  pismeno : char;

  seznamSymbolu : ^seznam;

  symbol : ^symbol;

end;

Zhruba takhle:

type uzel = record

            ...písmeno není třeba ukládat, protože jestli se sem dostaneme, přesně víme, kde jsme...

            naslednici:array['A'..'Z'] of ^uzel; ...plus čísla a podtržítko...

            end;

V knihkupectvích bývá kniha od Piotra Wróblewského Algoritmy - datové struktury a programovací techniky
Doporučuju přečíst si kapitolu Datové struktury a speciálně oddíl Univerzální slovníková struktura (od stránky 147)