Einige Unternehmen befragen Online-Schreibcodes. Es ist erforderlich, um das Olympiadenproblem für Geschwindigkeit zu lösen. Unter solchen Umständen bleibt keine Zeit, um die Details der Implementierung von Datenstrukturen zu sehen - Sie müssen die Idee sofort umsetzen. Kurse zu Algorithmen und Datenstrukturen bieten jedoch Beispiele in Pseudocode oder C ++. Weitere Referenzlösungen für Probleme werden häufig in C ++ geschrieben. Als ich mich auf ein Interview vorbereitete, machte ich eine Krippe mit Bibliotheken - Analoga von STL-Containern, um keine kostbare Zeit mit der Suche zu verschwenden.
Beginnen wir mit dem Offensichtlichen.
Dynamisches kontinuierliches Array
Analoger
std::vector .
Unterstützt den Zugriff auf ein Element per Index für eine konstante Zeit von mehreren Prozessorzyklen. Sie können die Kapazität erhöhen oder verringern. Dies ist das eingebaute Slice:
vector := []int{}
Praktischerweise sind grundlegende Konzepte in die Sprache eingebaut.
Analog zu
std::stack .
Ein geordneter Satz, in dem neue Elemente hinzugefügt und vorhandene gelöscht werden, erfolgt von einem Ende aus. Das zuletzt platzierte Element (last-in, first-out - LIFO) wird zuerst vom Stapel entfernt. Dies ist wieder eine ummauerte Scheibe. Snippets werden von Projekt zu Projekt kopiert:
Die Slice-Operation weist keinen neuen Speicher zu.
Analog zu
std::queue und
std::deque .
Warteschlangen implementieren Abruf- und Additionsoperationen für Start und Ende in konstanter Zeit. Das zuerst platzierte Element (First-In, First-Out - FIFO) wird zuerst aus der Warteschlange gelöscht. Ein gepufferter Kanal ist eine Warteschlange in einem Ringpuffer. Sie können ihn verwenden, wenn Leser und Schreiber unterschiedliche Goroutinen sind. In der Standardbibliothek gibt es jedoch keine separate Warteschlangenimplementierung. Die
Awesome-Go- Liste weist die Bibliothek
https://github.com/gammazero/deque an .
import "github.com/gammazero/deque"
Laufende Operationen:
func (q *Deque) PushBack(elem interface{}) func (q *Deque) PushFront(elem interface{}) func (q *Deque) PopBack() interface{} func (q *Deque) PopFront() interface{} func (q *Deque) Back() interface{} func (q *Deque) Front() interface{} func (q *Deque) At(i int) interface{}
Doppelt verknüpfte Liste
Analog zu
std::list .
Es besteht aus Elementen, die zusätzlich zu ihren eigenen Daten Links zum nächsten und vorherigen Listenelement enthalten. Es befindet sich in der Standardbibliothek:
import "container/list"
Wie erwartet unterstützt es Einfügevorgänge (am Anfang, am Ende, vor und nach dem Element, an das der Zeiger übergeben wird) und das Löschen.
func (l *List) PushBack(v interface{}) *Element func (l *List) PushFront(v interface{}) *Element func (l *List) InsertAfter(v interface{}, mark *Element) *Element func (l *List) InsertBefore(v interface{}, mark *Element) *Element func (l *List) Remove(e *Element) interface{}
Go bietet keine spezifische Syntax für Iteratoren. Daher kann das nächste / vorherige Element von einem Zeiger auf einen beliebigen Knoten erhalten werden. Diese Methoden werden nach dem Hinzufügen / Entfernen eines Elements zur Liste nicht ohne Überraschungen schlecht.
func (e *Element) Next() *Element func (e *Element) Prev() *Element
Prioritätswarteschlange
Analoge
std::priority_queueErmöglicht es Ihnen, Elemente in beliebiger Reihenfolge zu stapeln und jederzeit die höchste Priorität der verbleibenden zu erhalten. Es wird zum Beispiel in dem Algorithmus zum Erstellen eines minimalen Spannbaums verwendet, wenn der Algorithmus im nächsten Schritt die kürzeste Kante von allen auswählt, beginnend an den Scheitelpunkten, die bereits an einem Ende abgedeckt sind.
Die Standardbibliothek verfügt über einen Adapter, der jeden sortierbaren Container (der
sort.Interface implementiert) in eine Prioritätswarteschlange
sort.Interface .
import "container/heap"
Dies ist ein klassischer
binärer Heap . Implementiert das Einfügen und Löschen in O (log n).
func Pop(h Interface) interface{} func Push(h Interface, x interface{}) func Remove(h Interface, i int) interface{}
Es ist ein Wörterbuch und ein assoziatives Array.
Analoge
std::unordered_map .
Ermöglicht das Hinzufügen eines Schlüsselwerts, das Löschen des Werts nach Schlüssel und das Überprüfen des Vorhandenseins eines Elements für O (1) im Durchschnitt. Offensichtlich ist die Karte in die Sprache eingebaut:
unorderedMap := make(map[string]int)
Das Ergebnis von make (map) ist ein Zeiger, und die Funktionsweise unterscheidet sich geringfügig von Standardcontainern:
"Runtime / map" kümmert sich im Gegensatz zu std :: unordered_map um den Programmierer - es ist sicher, Werte während der Iteration zu löschen.
Viele
Analoges
std::unordered_set .
Fast das gleiche wie eine Hash-Tabelle, jedoch ohne den Wert zu speichern.
Wenn wir nur eine schnelle Eingabeprüfung benötigen, können wir die integrierte Karte wieder verwenden. Es muss nur ein leerer Wert angegeben werden, um anzuzeigen, dass nur der Schlüssel wichtig ist.
var m = make(map[string]struct{}) m["!"] = struct{}{} _, ok := m["!"]
Diese Implementierung unterstützt jedoch keine komplexen Operatoren. Um den Unterschied zur Box zusammenzuführen, zu überschneiden, benötigen Sie Bibliotheken von Drittanbietern. Am häufigsten verwendet, gemessen an der Anzahl der Sterne:
https://github.com/deckarep/golang-set import "github.com/deckarep/golang-set"
Der am meisten benötigte Teil der
API :
Add(i interface{}) bool Remove(i interface{}) Cardinality() int
Setze int
Im experimentellen Teil der Standardbibliothek gibt es eine optimierte Menge int, die jedes Bit speichert.
import "golang.org/x/tools/container/intsets"
Es unterstützt auch Vereinigung, Schnittmenge, Differenz von Mengen.
Analoge
std::set und
std::map .
Es mag wie ein Anfänger erscheinen, der schlechte Analoga von Hash-Tabellen hat:
Unterstützt auch das Hinzufügen, Entfernen und Überprüfen auf Vorkommen, jedoch über O (log n) hinaus.
Bäume speichern Knoten jedoch nach Schlüssel sortiert.
Die Standard-Go-Bibliothek enthält keine Bäume. Ein
Repository mit AVL-, Rot-Schwarz- und B-Bäumen ist weit verbreitet.
import "github.com/emirpasic/gods/trees/avltree"
Am häufigsten verwendete
API- Methoden:
func (tree *Tree) Get(key interface{}) (value interface{}, found bool) func (tree *Tree) Put(key interface{}, value interface{}) func (tree *Tree) Remove(key interface{}) func (tree *Tree) Size() int func (tree *Tree) Keys() []interface{} func (tree *Tree) Values() []interface{} func (tree *Tree) Left() *Node func (tree *Tree) Right() *Node
Es gibt zwei besonders wichtige Baummethoden:
func (tree *Tree) Ceiling(key interface{}) (ceiling *Node, found bool)
Gibt das kleinste vorhandene Element zurück, das größer als der Schlüssel ist.
func (tree *Tree) Floor(key interface{}) (floor *Node, found bool)
Gibt das größte vorhandene Element weniger als einen Schlüssel zurück.
Die Aufgaben hierfür finden sich relativ häufig in Interviews. Im wirklichen Leben wird es in Datenbankindizes verwendet:
select x from table where x <= $1 limit 1;
Wenn es einen Index gibt, funktioniert er für O (log n), für 1 Suche nach dem Rand im B-Baum.
Diese Datenstruktur in stl ist es jedoch nicht.
Wie bei einer Hash-Tabelle können Sie überprüfen, ob ein Element zu einer Menge gehört. Der Filter speichert jedoch beim Hinzufügen keine Schlüssel und benötigt konstant viel Speicher. Es ist möglich, eine falsch positive Antwort zu erhalten (es gibt kein Element in der Menge, aber die Datenstruktur meldet dies), aber nicht falsch negativ. Es wird als Filter verwendet, um fast alle nicht vorhandenen Schlüssel schnell abzuschneiden und so teurere Überprüfungen zu sparen, z. B. das Lesen von einer Festplatte oder das Anfordern einer Anforderung an die Datenbank.
Es gibt eine Drittanbieter-Bibliothek:
https://github.com/willf/bloom import "github.com/willf/bloom"
Nicht so oft verwendet, können Sie einen Blick auf die
API werfen .
In der Standard-C ++ - Bibliothek gibt es so etwas nicht.
Probabilistische Datenstruktur. Mit einem kleinen Fehler (≈ 0,4%) wird die Anzahl der eindeutigen Elemente berücksichtigt, ohne die Schlüssel selbst zu speichern. Es bietet enorme Speichereinsparungen. Wenn es darum geht, die Anzahl der Besucher oder Anfragen schnell zu berechnen, ist HyperLogLog ideal.
Die beliebteste Bibliothek dafür jetzt.
https://github.com/axiomhq/hyperloglog import "github.com/axiomhq/hyperloglog"
Sortierungen
Analoge
std::sort und
std::stable_sort .
Aus Verbrauchersicht gibt es nur zwei grundsätzlich unterschiedliche Typen:
Stabil (ändern Sie nicht die Reihenfolge der gleichen Elemente [[4, 0], [1, 2], [1, 1], [5, 6]] -> [[1, 2], [1, 1], [4 , 0], [5, 6]])
und nicht stabil, garantiert nicht die Konsistenz der verbleibenden Felder.
Beide befinden sich in der Standardbibliothek:
func Sort(data Interface)
Dies ist eine instabile Hoar-QuickSort-Implementierung. Für Abschnitte mit einer Länge <12 wird jedoch die Heap-Sortierung als Optimierung verwendet.
func Stable(data Interface)
Im Inneren handelt es sich um eine Zusammenführungssortierung. Aus Effizienzgründen wird jedoch eine Einfügungssortierung verwendet, wenn der rekursive Algorithmus Blöcke mit weniger als 20 Elementen erreicht.
Dies sind die klassischen Algorithmen, die für O (n log n) arbeiten.
Wenn Sie es lesen, herzlichen Glückwunsch. Die Kenntnis bestimmter APIs hilft bei der Lösung von Testproblemen. (Wenn Sie mit etwas gearbeitet haben und die besten Alternativen kennen - schreiben Sie in die Kommentare.