I kurserne Algoritmer og Datastrukturer 1 og Algoritmer og Datastrukturer 2 (dADS1 og dADS2) gennemgås en del algoritmer og datastrukturer, der forekommer i adskillige standard biblioteker i f.eks. Java og C++. Fokus for kurserne er ikke at gennemgå de forskellige implementationer i disse biblioteker, men at gennemgå de bagvedliggende algoritmer og datastrukturer og disses asymptotiske teoretiske køretider.
På denne side forsøges at give et lille overblik over hvordan de i kurserne gennemgåede algoritmer og datastrukturer forekommer i standard bibliotekerne for Java og C++. Overblikket er på ingen måder tænkt som værende udtømmende, men mere som en dokumentation for fagenes relevans. At omsætte en algoritme eller en datastruktur fra teori til at være en del af et effektivt og generelt anvendeligt bibliotek er en ikke triviel opgave — og er uden for disse kursers rammer (f.eks. skal man også overveje sprog specifikke standarder for template og klasse definitioner, effektivitetsoptimeringer, hardware specifikke optimeringer, håndtering af alle specialtilfælde, numerisk stabilitet, exception håndtering, systematisk testning — for blot at nævne nogen af de aspekter man også skal inddrage).
I C++ findes en del af algoritmerne og datastrukturerne i sprogets "Standard Template Library" (STL), andre findes i det meget anvendte Boost bibliotek (www.boost.org). En del af Boost biblioteket forventes med tiden at overgå til STL ved revisionerne af C++ sproget. Et C++ bibliotek med fokus på mere komplekse algoritmer er LEDA biblioteket ("Library of Efficient Data types and Algorithms"), oprindeligt udviklet ved Max-Planck-Instituttet for datalogi i Saarbrücken, Tyskland. For streng algoritmer findes der ikke helt så autoritære biblioteker, men f.eks. SeqAn biblioteket for (biologisk) sekvensanalyse indeholder en del strengalgoritmer.
I Java findes der en del af algoritmerne i standard Java klasse biblioteket (JCL). For mere komplekse algoritmer findes der ikke helt så autoritære biblioteker for Java som for C++. For grafalgoritmer findes der f.eks. bibliotekerne JGraphT og JUNG ("Java Universal Network/Graph Framework"), men disse er blot to blandt mange biblioteker.
| Course | Algoritme / Datastruktur | Java | C++ |
|---|---|---|---|
| dADS1 | Binær søgning | java.util.Arrays.binarySearch java.util.Collections.binarySearch | std::binary_search std::lower_bound std::upper_bound |
| Fletning (af to sorterede lister) | std::merge | ||
| Flettesortering | java.util.Collections.sort java.util.Arrays.sort (arrays med objekter, dvs. langsomme sammenligninger) | ||
| Prioritetskø | java.util.PriorityQueue | std::priority_queue | |
| Build-heap algoritme | std::make_heap | ||
| Heap-sort | std::sort_heap | ||
| QuickSort | java.util.Arrays.sort (arrays med char, byte, int, long, float, double) | std::sort (GCC bruger IntroSort, en kombination af QuickSort og HeapSort) | |
| Partition | std::partition | ||
| Select/Median | std::nth_element | ||
| Liste | java.util.LinkedList | std::list | |
| Forlængbar array | java.util.ArrayList | std::vector | |
| Stak | java.util.Stack | std::stack | |
| Kø | java.util.Queue java.util.LinkedList java.util.ArrayDeque | std::queue | |
| Dobbelt endet kø (deque) | java.util.Deque java.util.LinkedList java.util.ArrayDeque | std::deque | |
| Rød-sorte træer | java.util.TreeMap java.util.TreeSet | std::map std::set | |
| Union-find datastruktur | org.jgrapht.alg.util.UnionFind | boost::disjoint_sets | |
| Hashing | java.util.HashSet java.util.HashMap (I Java skal alle objekter have en hashværdi java.lang.Object.hashCode) | std::unordered_set std::unordered_map std::hash | |
| dADS2 | Bredde først søgning (BFS) | org.jgrapht.traverse.BreadthFirstIterator | boost::breadth_first_search |
| Dybde først søgning (DFS) | org.jgrapht.traverse.DepthFirstIterator | boost::depth_first_search | |
| Topologisk sortering | org.jgrapht.alg.CycleDetector org.jgrapht.traverse.TopologicalOrderIterator | boost::topological_sort | |
| Stærke sammenhængskomponenter | org.jgrapht.alg.StrongConnectivityInspector | boost::strong_components | |
| Korteste veje: Dijkstra's algoritme | org.jgrapht.alg.DijkstraShortestPath | boost::dijkstra_shortest_paths | |
| Korteste veje: Bellman-Ford's algoritme | org.jgrapht.alg.BellmanFordShortestPath | boost::bellman_ford_shortest_paths | |
| Korteste veje: Floyd-Warshall's algoritme | org.jgrapht.alg.FloydWarshallShortestPaths | boost::floyd_warshall_all_pairs_shortest_paths | |
| Minimum udspændende træ: Prim's algoritme | edu.uci.ics.jung.algorithms.shortestpath.PrimMinimumSpanningTree | boost::prim_minimum_spanning_tree | |
| Minimum udspændende træ: Kruskal's algoritme | org.jgrapht.alg.KruskalMinimumSpanningTree | boost::kruskal_minimum_spanning_tree | |
| Maksimale strømninger: Edmonds-Karp's algoritme | org.jgrapht.alg.EdmondsKarpMaximumFlow | boost::edmonds_karp_max_flow | |
| Mønstergenkendelse: Knuth-Morris-Pratt's algoritme | boost::algorithm::knuth_morris_pratt | ||
| Længste voksende delsekvens | seqan::longestIncreasingSubsequence | ||
| Længste fælles delsekvens | seqan::longestCommonSubsequence | ||
| Suffix arrays | seqan::createSuffixArray |
Send en email hvis du har forslag til rettelser eller tilføjelser til ovenstående tabel.