Was sind einige weniger bekannte Datenstrukturen und Algorithmen, die man kennen sollte?

Question

Kürzlich stieß ich auf die SkipList-Datenstruktur. Es hat mir wirklich geholfen, ein ansonsten schwer zu lösendes Problem zu lösen. Ich habe versucht, es mit Balanced Binary Tree zu lösen, aber es wurde sehr komplex, da der Baum immer ausgewogen sein muss und ich wollte wissen, dass nicht nur ein bestimmter Wert existiert, sondern Werte in einem bestimmten Bereich. SkipList hat mir geholfen, dieses Problem effektiv zu lösen.

Ich frage mich, welche anderen Datenstrukturen ich wissen muss? Ich weiß über - Array, Liste, Stack, Warteschlange, Linked List, Hashtable, Baum und seine verschiedenen Formen wie B-Baum, Trie usw. Möchten Sie wissen, ob Sie eine andere Datenstruktur/Konzept interessant sowie nützlich finden in ein regelmäßiger Entwicklungszyklus.

Answer 1

Sie haben keine Graphen erwähnt, die sehr mächtig sind, und wenn Sie nichts über sie wissen, sollten Sie sie unbedingt lesen. Suchen Sie den Dijkstra-Algorithmus und den A * -Suchalgorithmus sowie die allgemeine Tiefensuche und die erste Breitensuche.

Sie haben auch Heaps ausgelassen, die oft als zugrunde liegende Struktur für eine Prioritätswarteschlange verwendet werden. Binäre Heaps sind die einfachsten, aber Sie können auch in Min-Max-Median-Heaps, Binomial-Heaps (schnelle Zusammenführungen) und Fibonacci-Heaps (Schnell-Verkleinerungs-Schlüssel - nützlich für einige Graphalgorithmen) suchen.

Weitere interessante Datenstrukturen sind Patricia-Versuche, die platzsparende Versuche sind (auf Teilstrings anstelle von Zeichen getastet), Splay-Bäume, die ausgeglichen sind und so programmiert werden können, dass sie persistent sind. Überprüfen Sie auch Bloom-Filter, bei denen es sich um eine probabilistische Datenstruktur handelt, mit der Sie feststellen können, ob ein Element Mitglied eines Sets ist. Es kann falsch positive, aber nicht falsch negative Ergebnisse haben und ist raum- und zeiteffizient.

Schließlich können Sie die funktionale Route gehen und in unveränderliche und persistente Datenstrukturen suchen. Viele davon sind nur funktionale Versionen von Datenstrukturen, die Sie bereits kennen. Wenn Sie daran interessiert sind, dann empfehle ich Okasaki's rein funktionalen Datenstrukturen.

Answer 2

Sie haben beide "Liste" und "Verknüpfte Liste", und es ist überhaupt nicht klar, welchen Unterschied (wenn überhaupt) Sie zwischen den beiden beabsichtigen. Wie auch immer, eine offensichtliche Struktur, die Sie übersprungen haben, ist der Heap (den Sie vielleicht als eine Art Baum klassifizieren würden, aber das ist bestenfalls unsicher). Letztendlich sind Bäume eine Teilmenge von Graphen. Wenn Sie also keine Graphen (im Allgemeinen) studiert haben, ist dies wahrscheinlich ein Bereich, den Sie erforschen sollten.

Ich würde anmerken, dass keines von diesen besonders "neu" ist - sie sind alle seit Jahrzehnten bekannt. Die meisten dieser wirklich allgemeinen Strukturen sind schon länger bekannt. In jüngerer Zeit entdeckte Entdeckungen neigen dazu, sich auf spezifischere Themenbereiche zu beziehen.