Výběr správné datové struktury může zefektivnit váš program. Zde je průvodce, který vám pomůže se správným výběrem.

Výběr nejlepší datové struktury pro vaše cíle může být náročný s více dostupnými možnostmi. Při výběru datové struktury zvažte data, se kterými budete pracovat, operace, které mají být s daty provedeny, a prostředí, ve kterém se bude vaše aplikace spouštět.

Pochopte svá data

Před výběrem datové struktury je životně důležité porozumět datům, se kterými budete pracovat. Společné datové struktury které pracují s různými datovými typy, zahrnují pole, propojené seznamy, stromy, grafy a hashovací tabulky.

Například, když potřebujete náhodně přistupovat k prvkům z vašich dat, pole mohou být nejlepší volbou. V případě, že neustále potřebujete přidávat nebo odstraňovat prvky ze seznamu a velikost seznamu se také může měnit, mohou být propojené seznamy obzvláště užitečné.

Když potřebujete efektivně ukládat více úrovní dat, jako jsou struktury záznamů, a provádět operace, jako je vyhledávání a třídění, pak jsou stromy užitečné.

instagram viewer

Když potřebujete popsat interakce mezi entitami, jako jsou ty v sociálních sítích, a provádět operace, jako je nejkratší cesta a konektivita, pak jsou preferovány grafy. Hash tabulky jsou užitečné pro rychlé vyhledávání klíčů.

Zvažte operace, které mají být provedeny na datech

Při výběru datové struktury musíte také zvážit operace, které se mají s daty provést. Různé datové struktury optimalizují četné akce, jako je třídění, vyhledávání, vkládání a mazání.

Například propojené seznamy jsou lepší pro akce, jako je vkládání a mazání, ale binární stromy jsou nejlepší pro vyhledávání a třídění. Hašovací tabulka může být nejlepší volbou, pokud vaše aplikace vyžaduje současné vkládání a vyhledávání.

Vyhodnoťte životní prostředí

Při zvažování datové struktury musíte vyhodnotit prostředí, ve kterém bude aplikace běžet. Prostředí ovlivňuje, jak dobře a jak rychle jsou dostupné datové struktury.

Při hodnocení vašeho aktuálního stavu zvažte následující faktory:

  1. Procesní výkon: Vyberte datové struktury pro své aplikace, které dobře fungují na počítačích s malým výpočetním výkonem při běhu na platformě. Například jednodušší datové struktury, jako jsou pole, by mohly být vhodnější než stromy nebo grafy.
  2. Konkurence: Měli byste zvolit datovou strukturu bezpečnou pro vlákna, která zvládne simultánní přístup bez poškození dat; pokud vaše aplikace běží v souběžném prostředí, kde více vláken nebo procesů přistupuje k datové struktuře současně. V tomto případě jsou datové struktury bez zámku jako ConcurrentLinkedQueue a ConcurrentHashMap může být vhodnější než tradiční, jako je ArrayListand HashMap.
  3. Latence sítě: Pokud vaše aplikace vyžaduje přenos dat po síti, musíte při rozhodování o nejlepší datové struktuře zvážit latenci sítě. V takových situacích může použití datové struktury, která omezuje síťová volání nebo snižuje objem přenosu dat, pomoci zlepšit provádění.

Společné datové struktury a jejich případy použití

Zde je shrnutí několika populárních datových struktur a jejich použití.

  1. Pole: Toto je jednoduchá a efektivní datová struktura, která může obsahovat řadu prvků stejného datového typu s pevnou velikostí. Aby správně fungovaly, potřebují rychlý a přímý přístup ke konkrétním objektům prostřednictvím indexu.
  2. Propojené seznamy: Propojené seznamy se skládají z uzlů, které obsahují prvek a odkaz na další uzel a/nebo předchozí uzel. Propojené seznamy jsou díky svým efektivním operacím nejvhodnější v situacích vyžadujících časté vkládání nebo mazání prvků. Přístup k jednotlivým prvkům podle indexu v propojených seznamech je však ve srovnání s poli pomalejší.
  3. Fronty a zásobníky: Zásobníky dodržují pravidlo LIFO (Last-In-First-Out), kde poslední vložená položka je první odebraná položka. Fronty se řídí principem First-In-First-Out (FIFO). kde první přidaný prvek je zároveň prvním odstraněným prvkem.
  4. Hash tabulky: Hashovací tabulky jsou formou datové struktury, která obsahuje páry klíč–hodnota. Nejlepším řešením je použít hashovací tabulky, když je počet komponent nepředvídatelný a potřebujete rychlý přístup k hodnotám pomocí klíče.
  5. Stromy: Stromy jsou hierarchické datové struktury, které mohou ukládat skupinu prvků v hierarchii. Nejlepší využití pro binární vyhledávací stromy jsou v hierarchických datových strukturách, kde vztahy mezi datovými položkami mohou představovat stromovou strukturu.

Výběr správné datové struktury

Před výběrem datové struktury zvažte data, povinnosti a prostředí vaší aplikace. Při výběru myslete na následující prvky:

  1. Časová složitost: Výkon vaší aplikace může být významně ovlivněn časovou složitostí vaší datové struktury. Pokud vaše aplikace vyžaduje časté operace vyhledávání nebo načítání, použijte datovou strukturu se sníženou časovou složitostí, jako je hash tabulka.
  2. Vesmírná složitost: Dalším důležitým aspektem je prostorová složitost datové struktury. Pokud je vaše aplikace náročná na paměť, zvolte datovou strukturu s menší prostorovou složitostí, například pole. Pokud se nejedná o prostor, můžete použít datovou strukturu s větší prostorovou složitostí, jako je strom.
  3. Číst vs. Operace zápisu: Pokud vaše aplikace využívá mnoho operací zápisu, vyberte datovou strukturu s rychlejším výkonem vkládání, jako je hash tabulka. Pokud vaše aplikace vyžaduje mnoho operací čtení, vyberte datovou strukturu s vyšší rychlostí vyhledávání, jako je binární vyhledávací strom.
  4. Typ dat: Data, se kterými pracujete, mohou také ovlivnit vámi vybranou datovou strukturu. Pokud jsou vaše data hierarchická, můžete například použít stromovou strukturu dat. Pokud máte jednoduchá data, ke kterým je třeba přistupovat náhodně, může být nejlepší volbou výběr datové struktury založené na poli.
  5. Dostupné knihovny: Zvažte knihovny, které jsou snadno dostupné pro datovou strukturu, o které uvažujete. Spouštění a údržba by mohla být snazší, pokud má váš programovací jazyk vestavěné knihovny pro určitou datovou strukturu.

Následující příklad Pythonu ukazuje, jak vybrat nejlepší datovou strukturu pro konkrétní případ použití.

Zvažte případ, kdy vyvíjíte aplikaci systému souborů, která musí ukládat a načítat soubory v hierarchii. Musíte zvolit datovou strukturu, která dokáže efektivně reprezentovat tuto hierarchickou strukturu a rychle provádět operace, jako je vyhledávání, vkládání a mazání.

Mohlo by být dobrým nápadem použít stromovou datovou strukturu, jako je binární vyhledávání nebo B-strom. Pokud je počet položek v každém adresáři relativně malý a strom není příliš hluboký, binární vyhledávací strom by fungoval dobře. Pro větší počet souborů a hlubší adresářové struktury by byl vhodnější B-strom.

Níže je uveden příklad binárního vyhledávacího stromu v Pythonu.

třídaUzel:
def__init__(já, hodnota):
 vlastní.hodnota = hodnota
 self.left_child = Žádný
 self.right_child = Žádný


třídaBinarySearchTree:


def__init__(já):
 self.kořen = Žádný
defvložit(já, hodnota):


-li sebe.kořen jeŽádný:
 self.root = Uzel (hodnota)


jiný:
 self._insert (hodnota, self.root) 
def_vložit(vlastní, hodnota, aktuální_uzel):


-li hodnota < aktuální_uzel.hodnota:
-li aktuální_uzel.left_child jeŽádný:
 current_node.left_child = Uzel (hodnota)


jiný:
 self._insert (hodnota, aktuální_uzel.left_child)
elif hodnota > aktuální_uzel.hodnota:
-li aktuální_uzel.right_child jeŽádný:
 current_node.right_child = Uzel (hodnota)
jiný:
 self._insert (value, current_uzel.right_child)


jiný:
 tisk("Hodnota již ve stromu existuje.")
defVyhledávání(já, hodnota):
-li sebe.kořen jeneŽádný:
vrátit se self._search (value, self.root)


jiný:
vrátit seNepravdivé
def_Vyhledávání(vlastní, hodnota, aktuální_uzel):


-li hodnota == aktuální_uzel.hodnota:
vrátit seSkutečný


elif hodnota < aktuální_uzel.hodnota a aktuální_uzel.left_child jeneŽádný:
vrátit se self._search (hodnota, aktuální_uzel.left_child)


elif hodnota > aktuální_uzel.hodnota a aktuální_uzel.right_child jeneŽádný:
vrátit se self._search (value, current_node.right_child)
jiný:
vrátit seNepravdivé

V této implementaci vytvoříte dvě třídy: a BinarySearchTree třída, která spravuje operace vkládání a vyhledávání a a Uzel třída, která symbolizuje uzel ve stromu binárního vyhledávání.

Zatímco metoda insert vloží nový uzel na příslušné místo ve stromu v závislosti na jeho hodnotě, metoda vyhledávání hledá uzel se zadanou hodnotou. Časová složitost obou operací ve vyváženém stromu je O(log n).

Vyberte optimální datovou strukturu

Rychlost a přizpůsobivost vaší aplikace lze výrazně zlepšit zvolenou datovou strukturou. Zohlednění vašich dat, vašich operací a vašeho prostředí vám může pomoci s výběrem nejlepší datové struktury.

Důležité jsou úvahy jako časová složitost, prostorová složitost, operace čtení versus zápis, souběžnost, datový typ a dostupnost knihovny.

Posouzením váhy každé součásti byste měli vybrat datovou strukturu, která vyhovuje potřebám vaší aplikace.