Optimalizace spojového seznamu – Pascal – Fórum – Programujte.com
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
Reklama
Reklama

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

 

Hledá se programátor! Plat 1 800 € + bonusy (firma Boxmol.com)
Wimby0
Duch
18. 10. 2008   #1
-
0
-

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;


Položek není mnoho (kolem 500-5000), ale jsou velice často hledány právě podle názvu, takže je kolikrát nutné projet celý seznam...

Napadlo mě, že bych mohl udělat strom, který by se řadil v závislosti na názvu větví:

strom = record

nazev : string;
cislo : dword;
vlevo : ^strom;
vpravo : ^strom;
end;


Napřed by se podle názvu vypočítalo číslo (a = 1, b = 2, c = 3 ... => 'ahoj' = 1 + 8 + 15 + 10 => cislo := 34) a pokud by číslo bylo menší než číslo v kořenu stromu, pak by se hledalo vlevo a pokud by bylo větší, tak by se hledalo vpravo... Bohužel spousta slov může tvořit stejné číslo... a pak to má ještě jednu nevýhodu, a to že pokud jako první bude nějaký slovo s vysokým číslem, pak to bude stejný jako spojovej seznam, protože všechny slova budou vlevo...

Nevíte někdo nějakej lepší způsob jak zrychlit hledání?

Nahlásit jako SPAM
IP: 83.208.196.–
Reklama
Reklama
KIIV+42
God of flame
18. 10. 2008   #2
-
0
-

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

Nahlásit jako SPAM
IP: 80.250.27.–
Program vždy dělá to co naprogramujete, ne to co chcete...
Wimby0
Duch
18. 10. 2008   #3
-
0
-

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...

Nahlásit jako SPAM
IP: 83.208.196.–
KIIV+42
God of flame
18. 10. 2008   #4
-
0
-

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...

Nahlásit jako SPAM
IP: 80.250.27.–
Program vždy dělá to co naprogramujete, ne to co chcete...
Osiris0
Stálý člen
18. 10. 2008   #5
-
0
-

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

Nahlásit jako SPAM
IP: 85.70.130.–
Wimby0
Duch
18. 10. 2008   #6
-
0
-

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á.

Nahlásit jako SPAM
IP: 83.208.196.–
Wimby0
Duch
18. 10. 2008   #7
-
0
-

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;


Potřeboval bych něco jako MD5, který by mi udělalo z "jmena" unikátní číslo, takže bych pak měl strom:

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;


Nebo nějakou proceduru, která by porovnala dva řetězce a rozhodla by (pokaždý stejně) jestli to patří doprava nebo doleva nebo jestli se rovnají...

Do hashů se mi moc pouštět nechce... :-)

Nahlásit jako SPAM
IP: 83.208.196.–
Osiris0
Stálý člen
18. 10. 2008   #8
-
0
-

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.

Nahlásit jako SPAM
IP: 85.70.130.–
Wimby0
Duch
18. 10. 2008   #9
-
0
-

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;

Nahlásit jako SPAM
IP: 83.208.196.–
Osiris0
Stálý člen
18. 10. 2008   #10
-
0
-

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).

Nahlásit jako SPAM
IP: 85.70.130.–
Laaca0
Stálý člen
19. 10. 2008   #11
-
0
-

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;


4) A jestli ho intenzivně měníš, ale málo kdy z něho čteš, tak je lepší nechat ho netříděný.

Nahlásit jako SPAM
IP: 195.113.79.–
DOS-u-akbar
Laaca0
Stálý člen
19. 10. 2008   #12
-
0
-

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.

Nahlásit jako SPAM
IP: 195.113.79.–
DOS-u-akbar
Wimby0
Duch
19. 10. 2008   #13
-
0
-

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

Nahlásit jako SPAM
IP: 83.208.196.–
Laaca0
Stálý člen
19. 10. 2008   #14
-
0
-

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ě.

Nahlásit jako SPAM
IP: 195.113.79.–
DOS-u-akbar
Osiris0
Stálý člen
19. 10. 2008   #15
-
0
-

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

Nahlásit jako SPAM
IP: 85.70.130.–
Wimby0
Duch
19. 10. 2008   #16
-
0
-

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ů :-)

Nahlásit jako SPAM
IP: 83.208.196.–
Mircosoft+1
Věrný člen
20. 10. 2008   #17
-
0
-

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ěť.

Nahlásit jako SPAM
IP: 147.32.161.–
Chceš-li lepší odpověď, polož lepší otázku.
Moje stránka.
Laaca0
Stálý člen
20. 10. 2008   #18
-
0
-

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ů.

Nahlásit jako SPAM
IP: 81.0.253.–
DOS-u-akbar
Wimby0
Duch
20. 10. 2008   #19
-
0
-

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;


to by to pak vypadalo nějak takhle?

seznam = record

uzel : ^uzel;
dalsi : seznam;
end;

uzel = record
pismeno : char;
seznamSymbolu : ^seznam;
symbol : ^symbol;
end;


přičemž by to začínalo řekněme uzlem s písmenem 'A', kterej by odkazoval pomocí seznamu symbolu na všechny uzle začínající písmenem A a nějak pokračující a pokud by se vyskytnul symbol s názvem 'A', tak by se přidal do uzle pod položku 'symbol'?

Je fakt, že tohle by se docela mohlo vyplatit, protože už sem mnohokrát viděl symboly začínající stejně, například Read, Get nebo Put... ale zajímalo by mě jestli je to potom rychlejší než binární strom a okolik víc paměti to veme... :-)

Nahlásit jako SPAM
IP: 83.208.196.–
Mircosoft+1
Věrný člen
20. 10. 2008   #20
-
0
-

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;

O kolik to bude rychlejší? Na každé slovo je potřeba přesně tolik přechodů od jednoho uzlu k dalšímu, kolik je v tom slově znaků. U binárního stromu je to různé a závisí to na celkovém počtu uzlů ve stromu.

Nahlásit jako SPAM
IP: 89.176.249.–
Chceš-li lepší odpověď, polož lepší otázku.
Moje stránka.
Laaca0
Stálý člen
21. 10. 2008   #21
-
0
-

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)

Nahlásit jako SPAM
IP: 81.0.253.–
DOS-u-akbar
Zjistit počet nových příspěvků

Přidej příspěvek

Toto téma je starší jak čtvrt roku – přidej svůj příspěvek jen tehdy, máš-li k tématu opravdu co říct!

Ano, opravdu chci reagovat → zobrazí formulář pro přidání příspěvku

×Vložení zdrojáku

×Vložení obrázku

Vložit URL obrázku Vybrat obrázek na disku
Vlož URL adresu obrázku:
Klikni a vyber obrázek z počítače:

×Vložení videa

Aktuálně jsou podporována videa ze serverů YouTube, Vimeo a Dailymotion.
×
 
Podporujeme Gravatara.
Zadej URL adresu Avatara (40 x 40 px) nebo emailovou adresu pro použití Gravatara.
Email nikam neukládáme, po získání Gravatara je zahozen.
-
Pravidla pro psaní příspěvků, používej diakritiku. ENTER pro nový odstavec, SHIFT + ENTER pro nový řádek.
Sledovat nové příspěvky (pouze pro přihlášené)
Sleduj vlákno a v případě přidání nového příspěvku o tom budeš vědět mezi prvními.
Reaguješ na příspěvek:

Uživatelé prohlížející si toto vlákno

Uživatelé on-line: 0 registrovaných, 6 hostů

Podobná vlákna

Mazání ze spojového seznamu — založil Martin Pomichálek

Výpis spojového seznamu — založil MaxDJs

Optimalizace — založil Kowalsky95

Moderátoři diskuze

 

Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032016 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý