Original title: Praktická efektivita kontejnerů
Translated title: Practical Efficiency of Containers
Authors: Halámka, Jan ; Letko, Zdeněk (referee) ; Holík, Lukáš (advisor)
Document type: Bachelor's theses
Year: 2015
Language: cze
Publisher: Vysoké učení technické v Brně. Fakulta informačních technologií
Abstract: [cze] [eng]
Práce se zabývá teoretickým a praktickým porovnáním následujících kontejnerů: vector, deque, list, hash table, avl-tree, red black tree, splay tree, sg-tree, treap, B-tree, binomiální halda, fibonacciho halda, rope, skiplist při práci s množinami. U každé z nich jsou v práci zmíněny jejich asymptotické třídy složitosti, amortizované složitosti a složitosti v průměrném případě. U každé struktury je rovněž zmíněn způsob jakým se dá implementovat a jak vypadá v paměti počítače. Pro porovnání byla v práci rovněž navržena a implementována sada testů jejíž výsledky jsou k dispozici. This thesis is about theorethical and practical comparrison of following data containers: vector, deque, list, hash table, avl-tree, rb-tree, splay-tree, sg-tree, treap, B-tree, binomial heap, fibonacci heap, rope and skiplist while implementing sets. Asymptotic, amortized and average-case complexity for each of those structures are noted, as well as details about their implementation and description of how are they stored in computer memory. There was also created a set of tests for comparrison purposes, its results are also part of this paper.
Keywords: avl-tree; b-tree; binomial heap; container; data structure; deque; hash table; list; rb-tree; rope; scapegoat; sg-tree; skip list; splay-tree; treap; vector; binomiální halda; datová struktura; fibonacciho halda; kontejner; strom; vektor

Institution: Brno University of Technology (web)
Document availability information: Fulltext is available in the Brno University of Technology Digital Library.
Original record: http://hdl.handle.net/11012/52444

Permalink: http://www.nusl.cz/ntk/nusl-235120


The record appears in these collections:
Universities and colleges > Public universities > Brno University of Technology
Academic theses (ETDs) > Bachelor's theses