Vyhledávání IV. – Tabulky s rozptýlenými položkami
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
Reklama
Reklama

Vyhledávání IV. – Tabulky s rozptýlenými položkamiVyhledávání IV. – Tabulky s rozptýlenými položkami

 

Vyhledávání IV. – Tabulky s rozptýlenými položkami

Google       Google       17. 4. 2006       16 572×

  • Tabulky s přímým přístupem
  • Mapovací funkce
  • Princip tabulek s rozptýlenými položkami
  • TRP s explicitně zřetězenými synonymy
  • TRP s implicitně zřetězenými synonymy
  • TRP s lineárním vyhledáváním
  • TRP s kvadratickým vyhledáváním
  • TRP s dvojí rozptylovací funkcí
  • Brentova varianta
  • Operace DELETE v TRP
  • Hodnocení vyhledávání v tabulkách s rozptýlenými pložkami

Reklama
Reklama

4.1. Tabulky s přímým přístupem

Je-li známa množina všech klíčů K={K1, … Kn}, které se budou vkládat do vyhledávací tabulky, a je-li možné nalézt jedno-jednoznačnou mapovací funkci f(Ki) = i (i = 1, 2, … n) pro všechny prvky množiny K, je možné vytvořit tabulku s přímým přístupem. Tuto tabulku tvoří pole, v němž položka s klíčem Ki bude uložena na indexu u daného pole.

Nechť jsou dány tyto typy:

		TYPPOLOZKY = record
				     DATA:TYPDATA;
				     KLIC:TYPKLIC;
				     OBSAZEN:Boolean;
				  end;
		TYPTABULKY = array [1..n] of TYPPOLOZKY;
	a proměnné
		TAB:TYPTABULKY;  K:TYPKLIC;  DATAPOLOZKY:TYPDATA;

Pak operace INITTAB ustaví složku OBSAZEN u všech položek pole na hodnotu false. Algoritmus operace INSERT bude mít jednoduchý tvar:


	procedure INSERTTAB (var TAB:TYPTABULKY; K:TYPKLIC; DATAPOLOZKY:TYPDATA);
	begin
		TAB[f(k)].DATA := DATAPOLOZKY;
		TAB[f(k)].KLIC := K;	{ tato operace není při jedno-jednoznačnosti funkce f() nutná }
		TAB[f(k)].OBSAZEN := true;
	end;

Operace SEARCHTAB ustaví svou hodnotu na základě složky OBSAZEN:


	function SEARCHTAB (var TAB:TYPTABULKY; K:TYPKLIC):Boolean;
	begin
		SEARCHTAB := TAB[f(k)].OBSAZEN;
	end;

Operace DELETETAB vyřadí prvek s klíčem K tímto příkazem:


	procedure DELETETAB (var TAB:TYPTABULKA; K:TYPKLIC);
	begin
		TAB[f(k)].OBSAZEN := false;
	end;

Obtíž s využitím jinak vysoce účinné tabulky s přímým přístupem spočívá v obtížném nalezení vhodné mapovací funkce f. V praxi se tato potíž někdy obchází používáním numerických klíčů pro identifikaci položek. Takové klíče dobře známe pod názvy „pořadové“ nebo „evidenční číslo“. V řadě případů je však tento manévr neúčinný, protože je nutné pracovat s textovým (nejčastěji sugestivním) tvarem klíče. Typickým příkladem takového případu je manipulace překladače s identifikátory, které tvoří uživatel programovacího jazyka při tvorbě svých programů.

4.2. Mapovací funkce

Jak nalézt vhodnou mapovací funkci pro danou množinu klíčů? Pro 31 různých prvků, které se mají zobrazit do 41 prvkové množiny existuje 4131 (tj. cca 1050) možných mapovacích funkcí. Přitom pouze (41!/31!) z nich dává odlišné hodnoty pro různé klíče. (tzn., že funkce je jedno-jednoznačná). To znamená, že poměr vhodných funkcí ke všem možným funkcím je asi 1:107. Jedno-jednoznačné funkce jsou tedy velmi řídkým jevem.

V dalších úvahách budeme hledat takovou mapovací funkci, která klíče z dané předpokládané množiny klíčů „rozptýlí“ v dané tabulce, aniž budeme trvat na jedno-jednoznačnosti funkce. Klíče, které mají stejnou hodnotu mapovací funkce, budeme nazývat synonyma. Dojde-li k pokusu umístit novou položku na místo, které je již obsazeno, budeme situaci nazývat kolize. Mapovací funkci používané k rozptýlení položek v tabulce budeme říkat rozptylovací funkce (angl. hash-function, říká se jí také hashovací či hašovací funkce).

Předpokládejme, že máme k dispozici celočíselnou funkci Num(K), která z libovolného typu klíče získá celé kladné číslo. Je-li klíč textovým řetězcem, může se využít jeho binárního obrazu (v Pascalu budeme pracovat např. s funkcí ord). Právě volba funkce Num nejvíce ovlivní počet synonym a množství kolizí v tabulce. Pro volbu této funkce však nelze stanovit obecně platná pravidla. Volba musí vycházet z konkrétních vlastností množiny klíčů. Bude-li funkce Num odvozovat svou hodnotu např. z prvního znaku textového klíče, pak všechny identifikátory (použité jako klíče) se stejným písmenem na začátku, budou synonyma. Protože všechna písmena nemají rovnoměrný výskyt jako první znaky identifikátorů, bude u některých znaků docházet k častějším klizím.

Na dobrou rozptylovací funkci se kladou dva základní požadavky:

  • výpočet rozptylovací funkce musí být dostatečně rychlý
  • rozptylovací funkce má vytvářet co nejméně kolizí

Je zřejmé, že tyto požadavky jsou většinou protichůdné.

Nechť rozptylovací funkce R(K) = h(Num(K)), kde funkce h zajistí transformaci (mapování) libovolného celého kladného čísla (získaného funkcí Num) do intervalu daného rozsahem indexu pole, kterým implementujeme tabulku. Tímto intervalem bude nejčastěji 0..MAX nebo 1..MAX.

Poměrně úspěšné rozptylovací funkce h jsou založeny na vlastnostech celočíselného dělení, a to především operace modulo. Např.


		h(K) = K mod (MAX + 1)

získá hodnoty z intervalu 0..MAX a funkce


		h(K) = K mod MAX + 1		z intervalu 1..MAX

Úspěšnost zvolené funkce však může záviset také na volbě velikosti tabulky (MAX). Pro funkci h(K) = K mod MAX jsou některé hodnoty MAX nevhodné. Jsou to např. hodnoty MAX = rl ± c, kde l a c jsou malá celá čísla a r je řád použitého alfanumerického kódu (např. 64, 128, 256 apod.).

4.3. Princip tabulek s rozptýlenými položkami

Princip vyhledávání v tabulkách s rozptýlenými položkami (dále jen TRP) je velmi podobný principu vyhledávání v indexsekvenčním souboru. Pomocí rozptylovací funkce se získá index pole, na něž se uloží (od něj se vyhledává) položka s daným klíčem. Obsahuje-li tabulka synonyma vzhledem k danému indexu (více různých klíčů mělo shodnou hodnotu rozptylovací), pak na daném indexu začíná lineární seznam synonym, v němž se vyhledává položka s daným klíčem. Vyhledávání v TRP bude účinné tehdy, jestliže počet seznamů synonym bude co největší a jejich délka bude co nejkratší.

Podle způsobu, jakým se realizuje lineární seznam synonym, se rozdělují nejznámější metody implementace TRP do dvou skupin:

  • Tabulky s explicitně zřetězenými synonymy
  • Tabulky s implicitně zřetězenými synonymy (této skupině se také říká „tabulky s otevřeným adresováním položek“)

Explicitním zřetězením se rozumí, že každý prvek seznamu obsahuje ukazatel na následníka v seznamu. Implicitním zřetězením se rozumí, že z adresy (indexu) každého prvku seznamu se může určit adresa (index) následujícího prvku.

4.4. TRP s explicitně zřetězenými synonymy

Základem TRP je pole. Na i-tém prvku pole je začátek lineárního seznamu všech položek se synonymními klíči, pro které platí R(K) = i. TRP s explicitně zřetězenými seznamy můžeme principiálně rozdělit podle způsobu, kterým se přiděluje paměťový prostor položkám seznamu.

  • Pole obsahuje pouze ukazatele na jednotlivé seznamy synonym
  • Pole obsahuje položky seznamu. Synonyma se ukládají do „oblasti přeplnění“. Kolidující položka v tabulce je zřetězena se seznamem synonym umístěným v oblasti přeplnění.

Oblast přeplnění může být organizována různými způsoby:

  • Oblast přeplnění budou vytvářet paměťové místa získaná mechanismem dynamického přidělování paměti (new)
  • Oblast přeplnění tvoří zvláštní pole (v některých případech to může být „horní“ část pole, jehož „spodní“ část je použita jako základní pole TRP)
  • Oblast přeplnění se překrývá se základním polem TRP

Jako první si ukážeme implementaci typu A, v níž jsou všechny prvky tabulky obsaženy v „oblasti přeplnění“ realizované podle způsobu A. (V tom případě nemá vlastně smysl hovořit o oblasti přeplnění, protože jsou v ní uloženy všechny prvky.)

Nechť jsou dány tyto typy:


	TYPUK = ^TYPPOLOZKY;
	TYPPOLOZKY = record
			     DATA:TYPDATA;
			     KLIC:TYPKLIC;
			     DALSI:TYPUK;
			  end;
	TYPTAB = array [1..MAX] of TYPUK;

Operace INIT nastaví všechny ukazatele tabulky TAB na hodnotu null.


	procedura INIT (var TAB:TYPTAB);
	var I:POSINT;
	begin
	   for I:=1 to MAX do TAB[I[:=nil
	end;

Operace SEARCH bude mít tvar Booleovské funkce:


function SEARCH (TAB:TYPTAB; K:TYPKLIC):Boolean;
var I:POSINT;
      POMUK:TYPUK;
begin	I := R(K);
	POMUK := TAB[I];
	SEARCH := false;
	if POMUK <> nil then begin while (POMUK^.DALSI <> nil) and 
   (POMUK^.KLIC<> K) do POMUK:=POMUK^.DALSI;
					      SEARCH:=POMUK^.KLIC=K
				         end
	end; { procedury SEARCH }

Operace INSERT buď vloží do tabulky novou položku (bylo-li vyhledání daného klíče neúspěšné), nebo přepíše (aktualizuje) datovou složku položky s vyhledaným klíčem. Uvedený algoritmus vkládá nový prvek na začátek seznamu synonym.


	procedure INSERT (var TAB:TYPTAB; K:TYPKLIC; DATAPOLOZKY:TYPDATA);
	var I:POSINT;
	      POMUK:TYPUK;
	      NASEL:Boolean;
	begin
		I:=R(K);
		POMUK := TAB[I];
		if POMUK <> nil
		then { seznam synonym je neprázdný; prohledá se }
		   begin while (POMUK^.DALSI <> nil) and (POMUK^.KLIC <> K) do
				POMUK := POMUK^.DALSI;
			NASEL := POMUK^.KLIC = K;
		   end;
		if NASEL then POMUK^.DATA := DATAPOLOZKY; { Přepis datové složky }
			  else begin { Nová položka se zařadí na začátek seznamu synonym }
				new (POMUK);
				POMUK^.DALSI := TAB[I];
				TAB[I] := POMUK;
				POMUK^.KLIC := K;
				POMUK^.DATA := DATAPOLOZKY;
			         end
	end; { procedury INSERT }

Operace DELETE je podobná operaci DELETE nad lineárním seznamem.

Dále je uveden algoritmus, v němž se oblast přeplnění překrývá se základním polem. Není-li při vkládání nového prvku volné místo na indexu získaném rozptylovací funkcí R, vyhledá se v poli tabulky první volný prvek (pro usnadnění vyhledávání se používá pomocný ukazatel ukazující na poslední volný prvek), naplní se daty a připojí se k seznamu synonym. Parametr ERROR oznamuje, že novou položku nelze vložit, protože je tabulka plná.

Nechť jsou dány tyto typy:


	TYPPOLOZKY = record
			     KLIC:TYPKLIC;
			     DATA:TYPDATA;
			     VOLNY:Boolean;
			     DALSI:0..MAX;
			  end;
	TYPTAB:array [1..MAX] of TYPPOLOZKY;

Operace inicializace bude ustavovat pole volných prvků a nastavovat pomocný ukazatel RR.


	procedure INIT (var TAB:TYPTAB; var RR:POSINT);
	var I:POSINT;
	begin
	   fori I:=1 to MAX do TAB[I].VOLNY := true;
	   RR := MAX;
	end;	{ procedury INIT }

Protože mechanismus vyhledávání je obsažen v operaci INSERT, nebudeme uvádět samostatnou operaci SEARCH. Operace INSERT podle uvedeného Knuthova algoritmu bude mít následující tvar:


	procedure INSERT (var TAB:TYPTAB; K:TYPKLIC; DATAPOLOZKY:TYPDATA;
			       var RR:POSINT; var ERROR:Boolean);
	var I:POSINT;
	     JESTE, NASEL:Boolean;
	begin
	    I := R(K);	{ Rozptylovací funkce poskytuje hodnoty z intervalu 1..MAX }
	    ERROR := false; NASEL := false;	{ Inicializace Booleovských proměnných }
	    if not TAB[I].VOLNY
then begin	{ prvek není volný, hledej v lineárním seznamu }
   JESTE := TAB[I].KLIC <> K	{ Inicializace řídící proměnné cyklu }
		   while JESTE do begin
		      I := TAB[I].DALSI;	{ Index následníka }
		      if I = 0 then JESTE := false	{ Konec seznamu }
			    else JESTE := TAB[I].KLIC <> K;
		   end;
		   if I = 0 then begin NASEL := true;
				      TAB[I].DATA := DATAPOLOZKY	{ Přepis při nalezení }
			         end;
		   if not NASEL then begin  { Vyhledej místo pro vkládanou položku }
		      while (RR = 0) and (not TAB[RR].VOLNY) do RR:=RR-1;
		      ERROR := RR = 0;
		      if not ERROR then begin
			TAB[I].DALSI := RR;	{ připojení k seznamu }
			I := RR		{ příprava pro naplnění }
		      end
		end;
	    if (not NASEL) and (not ERROR) then begin	{ naplnění složek vkládané položky }
		TAB[I].KLIC := K;
		TAB[I].DALSI := 0;
		TAB[I].DATA := DATAPOLOZKY;
		TAB[I].VOLNY := false;
	    end
	end;	{ procedury INSERT }

4.5. TRP s implicitně zřetězenými synonymy

TRP s implicitně zřetězenými synonymy jsou implementovány jedním polem, které plní jak funkci základního pole (do něhož míří index získaný rozptylovací funkcí), tak oblasti přeplnění. Index následníka v seznamu synonym je dán součtem indexu předchůdce a přírůstku INC. Podle vlastnosti přírůstku dělíme metody s implicitně zřetězenými synonymy takto:

  • Lineární vyhledávání (INC je konstantní; nejčatěji INC := 1)
  • Kvadratické vyhledávání (INC lineárně vzrůstá; nejčastěji INC := INC + 1)
  • Metoda dvou rozptylovacích funkcí (INC je konstantní, ale získá se druhou rozptylovací funkcí (INC := R2(K)

4.5.1. TRP s lineárním vyhledáváním

Vyhledávání v této tabulce postupuje podle pravidel:

  • Rozptylovací funkce určí index prvního přístupu do pole tabulky
  • Od této pozice se zahájí vyhledávání v sekvenčně umístěném seznamu v poli. Vyhledávání končí úspěšně při nalezení položky s vyhledávaným klíčem, nebo neúspěšně, dojde-li se k prvnímu neobsazenému prvku pole. S polem se pracuje jako s kruhovým seznamem.

Pro zajištění konečnosti neúspěšného vyhledávání se musí zachovat alespoň jedna zarážka ve formě neobsazeného prvku pole. Nejčastěji se to dělá pomocnou proměnnou POCET, která udává počet prvků v tabulce. Je-li POCET právě o 1 menší, než je maximální kapacita, je tabulka zaplněna. (Jinou možností konečnosti vyhledávání je test na shodu s výchozím indexem).

Nechť jsou dány typy:


	TYPPOLOZKY = record
			     KLIC:TYPKLIC;
			     DATA:TYPDATA;
			     OBSAZENY:Boolean;
			  end;
	TYPTAB = array [0..MAX] of TYPPOLOZKY;

Operace INIT a INSERT nad TRP s lineárním vyhledáváním budou mít tvar:


procedure INIT (var TAB:TYPTAB; var POCET:POSINT);
var I:POSINT;
begin
    for I := 0 to MAX do TAB[I].OBSAZENY := false;
    POCET := 0
end

	procedure INSERT (var TAB:TYPTAB; K:TYPKLIC; DATAPOLOZKY:TYPDATA;
			       var POCET:POSINT);
	var INC, I:POSINT;
	begin
		I := R(K);	{ R(K) je v intervalu 0..MAX }
		INC := 1;
		while TAB[I].OBSAZENY and (TAB[I].KLIC <> K) do I:=(I+INC) mod (MAX+1);
		if TAB[I].KLIC = K then TAB[I].DATA:=DATAPOLOZKY	{ Našel, přepisuje }
				   else begin	{ Vkládá }
					TAB[I].KLIC := K;
					TAB[I].DATA := DATAPOLOZKY;
					TAB[I].OBSAZENY := true;
					POCET := POCET + 1;
				   end
	end;	{ procedury INSERT }

4.5.2. TRP s kvadratickým vyhledáváním

U TRP s lineárním vyhledáváním je častý případ, který se projevuje vytvářením shluků obsazených prvků pole, vznikajících nejčastěji tehdy, je-li přírůstek INC = 1 a jsou-li indexy několika skupin synonym dosti blízké. Situaci lze zlepšit změnou hodnoty INC na hodnotu větší než 1. Hodnota INC však nesmí být dělitelem délky základního pole (aby se zajistil průchod všemi prvky pole).

Jiný významný způsob zabránění vzniku shluků spočívá v kvadratickém vyhledávání. To znamená, že hodnoty indexu po sobě jdoucích prvků vytvářejí kvadratickou funkci. Je-li I0=R(K), pak Il=(I0+l2) mod MAX. Přitom platí Il+1=Il+INCl a INCl+1=INCl+2. Je-li I0=1, pak se při průchodu postupně projde indexy 1, 2, 5, 10, 17, 26, 37 …. Je-li MAX prvočíslo, pak se při neúspěšném vyhledávání v nejhorším případě projde polovinou prvků pole a průchod končí při INC = MAX.


	Další metota postupně prochází indexy
		I0 = R(K)
		I = (I0+0.5*l + 0.5*l2) mod MAX
	přičemž platí	Il+1=Il+INCl
			INCl+1=INCl+1

Je-li I0=1, pak se při průchodu postupně projde indexy 1, 2, 4, 7, 11, 16, 22 …. Pro tuto metodu musí mít MAX hodnotu prvočísla ve tvaru 4n+3 (např. 991).

Nechť je dán typ:

TYPTAB = array [1..PRVOCISLO] of TYPPOLOZKY

kde PRVOCISLO=4K+3 pro celé kladné K (např. 991) a TYPPOLOZKY je shodný s typem z předchozího odstavce. Pak operace INIT a INSERT budou mít tento tvar:


	procedure INIT (var TAB:TYPTAB);
	var I:POSINT;
	begin
	    for I:=1 to PRVOCISLO do TAB[I].OBSAZENY := false;
	end;


 
	procedure INSERT (var TAB:TYPTAB; K:TYPKLIC; DATAPOLOZKY:TYPDATA;
			       var ERROR:Boolean);
	var I, INC:POSINT;
	    KONEC, VLOZIL:Boolean;
	begin
	    INC := 1;	{ * }
	    I:=R(K);	{ R(K) je z intervalu 1..PRVOCISLO }
	    VLOZIL := false;
	    repeat 
KONEC := false;
		if not TAB[I].OBSAZENY then begin	{ Našel volný prvek, vkládá a končí }
			TAB[I].KLIC := K;
			TAB[I].DATA := DATAPOLOZKY;
			TAB[I].OBSAZENY := true;
			KONEC := true; VLOZIL := true;
		end
		else begin	{ Prvek není volný }
			if TAB[I].KLIC = K then begin	{ Našel shodu, přepisuje }
			    TAB[I].DATA := DATAPOLOZKY;
			    KONEC := true
			end
			else begin 	{ Připrav index dalšího prvku }
			    I := I + INC;	{ * }
			    if I>PRVOCISLO then I:=I-PRVOCISLO;
			    INC:=INC+1;
			    if INC >= (PRVOCISLO div 2)	{ * }
				then begin
				    KONEC:=true; ERROR := true;
				end
			end
		end
	    until KONEC
	end { procedury INSERT }				

Skutečnost, že algoritmus prochází v nejhorším případě jen polovinu prvků tabulky, neubírá metodě na účinnosti. Přesto lze jednoduchou úpravou algoritmus zlepšit tak, aby byla pro každý klíč dostupná celá tabulka. Tato úprava se nazývá „Full Table Quadratic Searching“ – tedy kvadratické vyhledávání v plné TRP. Úprava spočívá ve třech změnách na místech v programu označených { * }.


	Místo	INC := 1	se uvede	INC := - PRVOCISLO
	místo	I := I + INC	se uvede	I := I + abs(INC)
	místo	if INC>=(PRVOCISLO div 2)
				se uvede	if INC >= PRVOCISLO

4.5.3. TRP s dvojí rozptylovací funkcí

Odstranění shluků v TRP se může dosáhnout také s přírůstkem INC, který je sice konstantní, ale jeho hodnota se získá druhou rozptylovací funkcí z klíče K. Zatímco první rozptylovací funkce R(K) dává hodnotu z intervalu 0..MAX, druhá rozptylovací funkce Q(K) musí mít hodnotu z intervalu 1..MAX takovou, která není dělitelem čísla MAX+1. (Bude-li MAX+1 prvočíslo, pak to může být každé číslo z daného intervalu; bude-li (MAX+1)=2m, pak to může být každé liché číslo z intervalu 1..(2m-1) ).

Nechť je dán typ:


		TYPTAB = array [0..MAX] of TYPPOLOZKY;	{ MAX+1 je prvočíslo }

Operace INIT a INSERT pak budou mít následující tvar:


	procedure INIT (var TAB:TYPTAB; var POCET:POSINT);
	var I:POSINT;
	begin
	    for I:=) to MAX do TAB[I].OBSAZENY := false;
	    POCET := 0;
	end;

	procedure INSERT (var TAB:TYPTAB; K:TYPKLIC; DATAPOLOZKY:TYPDATA;
			       var POCET:POSINT; var ERROR:Boolean);
	var I, INC:POSINT;
	      NASEL, KONEC:Boolean;
	begin
	    ERROR := false;
	    NASEL := false;
	    I := R(K);	{ Funkce dává hodnotu z intervalu 0..MAX }
	    if TAB[I].OBSAZENY then { Prvek není volný }
		if TAB[I].KLIC = K 
  then NASEL := true	{ Našel shodu }
		  else begin	{ Hledej v seznamu }
			INC := Q(K);	{ Funkce dává hodnotu z intervalu 1..MAX }
			repeat
			    KONEC := false;
			    I := I + INC;
			    if I > MAX then I := I – MAX – 1;
			    if not TAB[I].OBSAZEN 
then KONEC := true	{ Našel volný, končí }
				else if TAB[I].KLIC = K then begin  { Našel shodu, končí }
								KONEC := true; NASEL := true;
							       end
			until KONEC;
		end;
	    if NASEL then TAB[I].DATA := DATAPOLOZKY	{ Přepisuje nalezenou položku }
		       else if POCET = MAX then ERROR := true
					    else begin	{ Vkládá novou položku }
						  POCET := POCET + 1;
						  TAB[I].DATA := DATAPOLOZKY;
						  TAB[I].KLIC := K;
						  TAB[I].OBSAZENY := true
						end
	end;	{ procedury INSERT }

4.5.4. Brentova varianta

Brentova varianta vychází z metody dvou rozptylovacích funkcí a předpokládá, že úspěšné vyhledávání je častější než neúspěšné vyhledání a následným vkládáním nového prvku. Algoritmus vkládání je složitější, ale má za důsledek zkrácení úspěšného vyhledávání. Metoda používá dvou rozptylovacích funkci R a Q stejných jako v předcházející metodě.

Popis Brenotvy varianty najdete v literatuře.

4.6. Operace DELETE v TRP

U jednotlivých metod TRP byly uvedeny většinou pouze operace INIT a INSERT. Z operace INSERT kze snadno odvodit algoritmus operací SEARCH a READ. Poněkud složitější je to s operací DELETE. V metodách s explicitním zřetězením lze vyřazovaný prvek vyloučit na principu operace DELETE v jednosměrném zřetězeném seznamu (u Knuthovy varianty by se měl aktualizovat pomocný ukazatel RR).

U TRP s implicitním zřetězením je jedinou praktickou možností „zaslepení“ vylučované položky. Nastavením složky OBSAZENY na hodnotu false by se totiž porušilo implicitní zřetězení mezi přechůdcem a následníkem vyřazovaného prvku. Zaslepení však vyžaduje indikaci zaslepeného prvku. Místo složky OBSAZENY lze definovat např. složku STAV:(VOLNY, OBSAZENY, SLEPY). Operaci INSERT lze pak upravit tak, že si při vyhledávání pamatuje index první slepé položky v procházeném seznamu a na tento index pak vloží novou položku v případě neúspěšného vyhledání.

4.7. Hodnocení vyhledávání v tabulkách s rozptýlenými pložkami

U tabulek, které jsou celé implementované polem, hraje nejdůležitější roli pro hodnocení délky vyhledávání koeficient zaplnění tabulky a=POCET/MAX (poměr počtu prvků v tabulce k maximálnímu možnému počtu).

Analýza jednotlivých metod není jednoduchá a analytické vyjádření průměrné doby úspěšného a neúspěšného vyhledávání mají podobu vztahů jen zřídka použitelných v praxi.

Metoda lineárního vyhledávání potřebuje větší počet porovnání než ostatní metody, ale její výhodou je jednoduchost. Uvážíme-li, že při 90% zaplnění potřebuje pro úspěšné vyhledání v průměru méně než 5,5 porovnání, lze říci, že metoda je užitečná. Pro vložení nové položky po neúspěšném vyhledání však potřebuje při tomto zaplnění v průměru 50,5 porovnání.

Metody s explicitním zřetězením jsou ekonomické s ohledem na počet porovnání, ale jejich nevýhodou je to, že pro řetězící ukazatele potřebují více paměti. Jsou-li položky paměti krátké, může se ukázat, že je výhodnější větší tabulka s implicitním zřetězením než menší tabulka s explicitním zřetězením.

Z uvedených metod se jeví nejúčinnější Brentova varianta, která umožňuje úspěšné vyhledání v zaplněné tabulce s průměrem 2,5 porovnání. Neúspěšné vyhledávání s vložením nové položky je však pomalé a vyžaduje cca 0,5*N porovnání.

Ze srovnání s jinými vyhledávacími metodami vyplývá, že tabulky s rozptýlenými položkami jsou rychlejší než binární vyhledávání, zejména pro větší N. Binární vyhledávání je přitom vhodné jen pro statické tabulky. Tabulky s rozptýlenými položkami jsou rychlejší než vyhledávání ve stromech, je-li počet prvků řádově vyšší než 100.

Literatura

[1] skriptum PROGRAMOVACÍ TECHNIKY – Doc. Ing. Jan Honzík a kolektiv

Zdroj: Petr Pindur – vyhledávání

×Odeslání článku na tvůj Kindle

Zadej svůj Kindle e-mail a my ti pošleme článek na tvůj Kindle.
Musíš mít povolený příjem obsahu do svého Kindle z naší e-mailové adresy kindle@programujte.com.

E-mailová adresa (např. novak@kindle.com):

TIP: Pokud chceš dostávat naše články každé ráno do svého Kindle, koukni do sekce Články do Kindle.

Hlasování bylo ukončeno    
0 hlasů
Google
(fotka) Lukáš ChurýLukáš je šéfredaktorem Programujte, vyvíjí webové aplikace, fascinuje ho umělá inteligence a je lektorem na FI MUNI, kde učí navrhovat studenty GUI. Poslední dobou se snaží posunout Laser Game o stupeň výše a vyvíjí pro něj nové herní aplikace a elektroniku.
Web     Twitter     Facebook     LinkedIn    

Nové články

Obrázek ke článku NEWTON Media prohledá 200  milionů mediálních zpráv během sekund díky Cisco UCS

NEWTON Media prohledá 200 milionů mediálních zpráv během sekund díky Cisco UCS

Česká společnost NEWTON Media provozuje největší archiv mediálních zpráv ve střední a východní Evropě. Mezi její zákazníky patří například ministerstva, evropské instituce nebo komerční firmy z nejrůznějších oborů. NEWTON Media rozesílá svým zákazníkům každý den monitoring médií podle nastavených klíčových slov a nabízí online službu, kde lze vyhledat mediální výstupy v plném znění od roku 1996.

Reklama
Reklama
Obrázek ke článku Delphi 10.1.2 (Berlin Update 2) – na co se můžeme těšit

Delphi 10.1.2 (Berlin Update 2) – na co se můžeme těšit

Touto roční dobou, kdy je zem pokrytá barevným listím a prsty křehnou v mrazivých ránech, se obvykle těšíme na zbrusu novou verzi RAD Studia. Letos si však ale budeme muset počkat na Godzillu a Linux až do jara. Vezměme tedy za vděk alespoň updatem 2 a jelikož dle vyjádření pánů z Embarcadero se budou nové věci objevovat průběžně, pojďme se na to tedy podívat.

Obrázek ke článku Konference: Moderní datová centra pro byznys dneška se koná už 24. 11.

Konference: Moderní datová centra pro byznys dneška se koná už 24. 11.

Stále rostoucí zájem o cloudové služby i maximální důraz na pružnost, spolehlivost a bezpečnost IT vedou k výrazným inovacím v datových centrech. V infrastruktuře datových center hraje stále významnější roli software a stále častěji se lze setkat s hybridními přístupy k jejich budování i provozu.

Obrázek ke článku Konference: Mobilní technologie mají velký potenciál pro byznys

Konference: Mobilní technologie mají velký potenciál pro byznys

Firmy by se podle analytiků společnosti Gartner měly  rychle přizpůsobit skutečnosti, že mobilní technologie už zdaleka nejsou horkou novinkou, ale standardní součástí byznysu. I přesto - nebo možná právě proto - tu nabízejí velký potenciál. Kde tedy jsou ty největší příležitosti? I tomu se bude věnovat již čtvrtý ročník úspěšné konference Mobilní řešení pro business.

Reklama autora

loadingtransparent (function() { var po = document.createElement('script'); po.type = 'text/javascript'; po.async = true; po.src = 'https://apis.google.com/js/plusone.js'; var s = document.getElementsByTagName('script')[0]; s.parentNode.insertBefore(po, s); })();
Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032016 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý