Einführung

Da sich die Geschäftslogik immer mehr von hinten nach vorne bewegt, wird das Know-how im Bereich Frontend Engineering immer wichtiger. Als Frontend-Ingenieure sind wir darauf angewiesen, dass Ansichtsbibliotheken wie React produktiv sind. Das Anzeigen von Bibliotheken hängt wiederum von Statusbibliotheken wie Redux ab , um die Daten zu verwalten. Zusammen Reagieren und Redux abonnieren Sie das reaktive Programmierparadigma , in der UI - Updates reagiert auf Datenänderungen. Backends fungieren zunehmend einfach als API-Server und stellen Endpunkte nur zum Abrufen und Aktualisieren der Daten bereit. Tatsächlich leitet das Backend die Datenbank nur weitererwartet, dass der Frontend-Ingenieur die gesamte Controller-Logik übernimmt. Die zunehmende Beliebtheit von Microservices und GraphQL bestätigt diesen wachsenden Trend.

Von Frontend-Ingenieuren wird nun erwartet, dass sie neben dem ästhetischen Verständnis von HTML und CSS auch JavaScript beherrschen. Da Datenspeicher auf dem Client zu „Replikaten“ von Datenbanken auf dem Server werden, ist die genaue Kenntnis der idiomatischen Datenstrukturen von entscheidender Bedeutung. Tatsächlich kann der Erfahrungsstand eines Ingenieurs aus seiner Fähigkeit abgeleitet werden, zu unterscheiden, wann und warum eine bestimmte Datenstruktur verwendet werden soll.

Schlechte Programmierer sorgen sich um den Code. Gute Programmierer sorgen sich um Datenstrukturen und ihre Beziehungen.

- Linus Torvalds, Schöpfer von Linux und Git

Auf hoher Ebene gibt es grundsätzlich drei Arten von Datenstrukturen. Stapel und Warteschlangen sind Array-ähnliche Strukturen, die sich nur darin unterscheiden, wie Elemente eingefügt und entfernt werden. Verkettete Listen , Bäume , und Graphen sind Strukturen mit Knoten , die halten Verweise auf andere Knoten. Hash-Tabellen hängen von Hash-Funktionen ab , um Daten zu speichern und zu lokalisieren.

In Bezug auf die Komplexität Stacksund Queuessind die einfachsten und können aus konstruiert werden Linked Lists. Treesund Graphssind am komplexesten, weil sie das Konzept einer verknüpften Liste erweitern. Hash Tablesmüssen diese Datenstrukturen nutzen, um zuverlässig zu arbeiten. In Bezug auf die Effizienz eignen sich verknüpfte Listen am besten zum Aufzeichnen und Speichern von Daten, während Hash-Tabellen zum Suchen und Abrufen von Daten am besten geeignet sind .

Um zu erklären, warum und wann , wird dieser Artikel der Reihenfolge dieser Abhängigkeiten entsprechen. Lass uns anfangen!

Stapel

Das wohl wichtigste Stackin JavaScript ist der Aufrufstapel, bei dem wir den Umfang von a bei functionjeder Ausführung erweitern. Programmatisch ist es nur eine arraymit zwei prinzipiellen Operationen: pushund pop. Push fügt Elemente an die Spitze des Feldes, während Pop entfernt sich von der gleichen Stelle. Mit anderen Worten, Stacks folgen dem LIFO-Protokoll (Last In, First Out).

Unten finden Sie ein Beispiel für einen StackIn-Code. Beachten Sie, dass wir die Reihenfolge des Stapels umkehren können : Die Unterseite wird zur Oberseite und die Oberseite wird zur Unterseite. Als solche können wir die Arrays verwenden unshiftund shiftMethoden anstelle von pushund popverbunden.

Mit zunehmender Anzahl von Elementen wird push/ popimmer leistungsfähiger als unshift/, shiftda jedes Element in letzterem neu indiziert werden muss, nicht jedoch in ersterem.

Warteschlange

JavaScript ist eine ereignisgesteuerte Programmiersprache, mit der nicht blockierende Vorgänge unterstützt werden können. Intern verwaltet der Browser nur einen Thread , um den gesamten JavaScript-Code auszuführen. Dabei wird die Ereigniswarteschlange zum Einreihenlisteners und die Ereignisschleife zum Abhören des Registrierten verwendet events. Um die Asynchronität in einer Umgebung mit einem Thread zu unterstützen (um CPU-Ressourcen zu sparen und die Web-Erfahrung zu verbessern), müssen Sie die listener functions Warteschlange nur dann deaktivieren und ausführen, wenn der Aufrufstapel leer ist. Promiseshängen von dieser ereignisgesteuerten Architektur ab , um eine synchrone Ausführung von asynchronem Code zu ermöglichen, der andere Vorgänge nicht blockiert.

Programmatisch Queuessind nur Arrays mit zwei primären Operationen: unshiftund pop. Durch das Aufheben der Verschiebung werden Elemente bis zum Ende des Arrays in die Warteschlange gestellt , während Pop sie vom Anfang des Arrays in die Warteschlange stellt . Mit anderen Worten, Warteschlangen folgen dem FIFO-Protokoll (First In, First Out). Wenn die Richtung umgekehrt ist, können wir bzw. durch und ersetzen .unshiftpoppushshift

Ein Beispiel für einen QueueIn-Code:

Verknüpfte Liste

Linked ListsSpeichern Sie Datenelemente wie Arrays in sequenzieller Reihenfolge. Anstatt Indizes zu führen, enthalten verknüpfte Listen Zeiger auf andere Elemente. Der erste Knoten wird als Kopf bezeichnet, während der letzte Knoten als Schwanz bezeichnet wird . In einer einfach verknüpften Liste hat jeder Knoten nur einen Zeiger auf den nächsten Knoten. Hier beginnt der Kopf den Rest der Liste entlang. In einer doppelt verknüpften Liste wird auch ein Zeiger auf den vorherigen Knoten beibehalten. Daher können wir auch vom Schwanz ausgehen und „rückwärts“ in Richtung Kopf gehen.

Verknüpfte Listen haben zeitlich konstante Einfügungen und Löschungen, da wir nur die Zeiger ändern können. Um dieselben Operationen in Arrays auszuführen, ist eine lineare Zeit erforderlich, da nachfolgende Elemente verschoben werden müssen. Außerdem können verknüpfte Listen wachsen, solange Speicherplatz vorhanden ist. Selbst „dynamische“ Arrays, deren Größe automatisch geändert wird, können jedoch unerwartet teuer werden. Natürlich gibt es immer einen Kompromiss. Um ein Element in einer verknüpften Liste nachzuschlagen oder zu bearbeiten, müssen wir möglicherweise die gesamte Länge zurücklegen, was einer linearen Zeit entspricht. Bei Array-Indizes sind solche Operationen jedoch trivial.

Verknüpfte Listen können wie Arrays als Stapel fungieren . Es ist so einfach, als wäre der Kopf der einzige Ort zum Einsetzen und Entfernen. Verknüpfte Listen können auch als Warteschlangen fungieren . Dies kann mit einer doppelt verknüpften Liste erreicht werden, bei der das Einfügen am Schwanz und das Entfernen am Kopf erfolgt oder umgekehrt. Bei einer großen Anzahl von Elementen, auf diese Weise Warteschlangen der Implementierung ist performanter als die Verwendung von Arrays , da shiftund unshiftOperationen zu Beginn des Arrays lineare Zeit zu re-Index benötigen jedes nachfolgendes Element.

Verknüpfte Listen sind sowohl auf dem Client als auch auf dem Server nützlich. Auf dem Client strukturieren Statusverwaltungsbibliotheken wie Redux ihre Middleware-Logik in Form einer verknüpften Liste. Wenn Aktionen ausgelöst werden, werden sie von einer Middleware zur nächsten weitergeleitet, bis alle besucht sind, bevor die Reduzierungen erreicht werden . Auf dem Server strukturieren Web-Frameworks wie Express auf ähnliche Weise auch die Middleware-Logik. Wenn eine Anforderung empfangen wird, wird sie von einer Middleware zur nächsten weitergeleitet, bis eine Antwort ausgegeben wird.

Ein Beispiel für einen Doubly-Linked ListIn-Code:

Baum

A Treeist wie eine verknüpfte Liste , enthält jedoch Verweise auf viele untergeordnete Knoten in einer hierarchischen Struktur. Mit anderen Worten, jeder Knoten kann nicht mehr als ein übergeordnetes Element haben. Das Document Object Model (DOM) ist eine solche Struktur mit einem htmlStammknoten, der in die Knoten headund verzweigt body, die sich weiter in alle bekannten HTML-Tags unterteilen . Unter der Haube erzeugen prototypische Vererbung und Zusammensetzung mit React-Komponenten auch Baumstrukturen. Als speicherinterne Darstellung des DOM ist das virtuelle DOM von React natürlich auch eine Baumstruktur.

Der binäre Suchbaum ist etwas Besonderes, da jeder Knoten nicht mehr als zwei untergeordnete Knoten haben kann . Das linke Kind muss einen Wert haben, der kleiner oder gleich dem übergeordneten Element ist, während das rechte Kind einen größeren Wert haben muss . Auf diese Weise strukturiert und ausgeglichen können wir in logarithmischer Zeit nach jedem Wert suchen, da wir bei jeder Iteration die Hälfte der Verzweigung ignorieren können. Das Einfügen und Löschen kann auch in logarithmischer Zeit erfolgen. Darüber hinaus kann der kleinste und der größte Wert leicht am äußersten linken bzw. rechten Blatt gefunden werden.

Das Durchqueren des Baums kann vertikal oder horizontal erfolgen . Beim Depth-First Traversal (DFT) in vertikaler Richtung ist ein rekursiver Algorithmus eleganter als ein iterativer. Knoten können in Vorbestellung , Reihenfolge oder Nachbestellung durchlaufen werden . Wenn wir die Wurzeln erforschen müssen, bevor wir die Blätter untersuchen, sollten wir eine Vorbestellung wählen . Aber wenn wir die Blätter vor den Wurzeln erforschen müssen, sollten wir wählen Post-Order . Wie der Name schon sagt, können wir durch In-Order die Knoten in sequentieller Reihenfolge durchlaufen . Diese Eigenschaft macht binäre Suchbäume optimal zum Sortieren .

Bei Breadth-First Traversal (BFT) in horizontaler Richtung ist ein iterativer Ansatz eleganter als ein rekursiver. Dies erfordert die Verwendung von a queue, um alle untergeordneten Knoten bei jeder Iteration zu verfolgen. Der für eine solche Warteschlange benötigte Speicher ist jedoch möglicherweise nicht trivial. Wenn die Form eines Baumes breiter als tief ist, ist BFT die bessere Wahl als DFT. Außerdem ist der Weg, den BFT zwischen zwei beliebigen Knoten nimmt, der kürzest mögliche.

Ein Beispiel für einen Binary Search TreeIn-Code:

Graph

Wenn ein Baum mehr als ein Elternteil haben kann, wird er zu einem Graph. Kanten , die Knoten in einem Diagramm miteinander verbinden, können gerichtet oder ungerichtet, gewichtet oder ungewichtet sein . Kanten, die sowohl Richtung als auch Gewicht haben, sind analog zu Vektoren .

Mehrere Vererbungen in Form von Mixins und Datenobjekten mit vielen-zu-vielen- Beziehungen erzeugen Diagrammstrukturen. Ein soziales Netzwerk und das Internet selbst sind ebenfalls Grafiken. Der komplizierteste Graph in der Natur ist unser menschliches Gehirn, das neuronale Netze zu replizieren versuchen, um Maschinen Superintelligenz zu verleihen .

Ein Beispiel für einen GraphIn-Code:

TK

Hash-tabelle

Eine Hash-Tabelle ist eine wörterbuchartige Struktur, die Schlüssel mit Werten koppelt . Der Speicherort jedes Paares wird durch a bestimmt hash function, das einen Schlüssel akzeptiert und die Adresse zurückgibt, an der das Paar eingefügt und abgerufen werden soll. Kollisionen können auftreten, wenn zwei oder mehr Schlüssel in dieselbe Adresse konvertiert werden. Für Robustheit, gettersund setterssollten diese Ereignisse , um sicherzustellen , erwarten , dass alle Daten wiederhergestellt werden können und keine Daten überschrieben. linked listsBieten Sie normalerweise die einfachste Lösung an. Sehr große Tische helfen auch.

Wenn wir wissen, dass unsere Adressen in ganzzahligen Sequenzen vorliegen, können wir einfach Arraysunsere Schlüssel-Wert-Paare speichern. Für komplexere Adresszuordnungen können wir Mapsoder verwenden Objects. Hash-Tabellen haben im Durchschnitt das Einfügen und Nachschlagen einer konstanten Zeit . Aufgrund von Kollisionen und Größenänderungen können diese vernachlässigbaren Kosten auf eine lineare Zeit ansteigen. In der Praxis können wir jedoch davon ausgehen, dass Hash-Funktionen so clever sind, dass Kollisionen und Größenänderungen selten und billig sind. Wenn Schlüssel Adressen darstellen und daher kein Hashing erforderlich ist, kann ein einfaches object literalausreichen. Natürlich gibt es immer einen Kompromiss. Die einfache Entsprechung zwischen Schlüsseln und Werten und die einfache Assoziativität zwischen Schlüsseln und Adressen opfern die Beziehungen zwischen Daten. Daher sind Hash-Tabellen zum Speichern von Daten nicht optimal .

Wenn eine Kompromissentscheidung das Abrufen gegenüber dem Speichern bevorzugt, kann keine andere Datenstruktur mit der Geschwindigkeit von Hash-Tabellen für das Nachschlagen , Einfügen und Löschen übereinstimmen . Es ist daher keine Überraschung, dass es überall verwendet wird . Von der Datenbank über den Server bis zum Client sind Hash-Tabellen und insbesondere Hash-Funktionen für die Leistung und Sicherheit von Softwareanwendungen von entscheidender Bedeutung. Die Geschwindigkeit von Datenbankabfragen hängt stark davon ab, dass Indextabellen , die auf Datensätze verweisen, in sortierter Reihenfolge aufbewahrt werden. Auf diese Weise können binäre Suchen in logarithmischer Zeit durchgeführt werden, was insbesondere für Big Data einen enormen Leistungsgewinn darstellt .

Sowohl auf dem Client als auch auf dem Server verwenden viele beliebte Bibliotheken Memoization , um die Leistung zu maximieren. Durch Aufzeichnen der Ein- und Ausgänge in einer Hash-Tabelle werden Funktionen für dieselben Eingänge nur einmal ausgeführt. Die beliebte Reselect- Bibliothek verwendet diese Caching-Strategie, um mapStateToPropsFunktionen in Redux- fähigen Anwendungen zu optimieren . In der Tat, unter der Haube, nutzt das JavaScript - Engine auch Hash - Tabellen genannt Haufen alles zu speichern variablesund primitiveswir erstellen. Auf sie wird über Zeiger auf dem Aufrufstapel zugegriffen .

Das Internet selbst ist auch auf Hashing-Algorithmen angewiesen, um sicher zu funktionieren. Die Struktur des Internets ist so, dass jeder Computer über ein Netz miteinander verbundener Geräte mit jedem anderen Computer kommunizieren kann . Wenn sich ein Gerät im Internet anmeldet, wird es auch zu einem Router, über den Datenströme übertragen werden können. Es ist jedoch ein zweischneidiges Schwert. Eine dezentrale Architektur bedeutet, dass jedes Gerät im Netzwerk die Datenpakete, die es weiterleitet, abhören und manipulieren kann. Hash-Funktionen wie MD5 und SHA256 spielen eine entscheidende Rolle bei der Verhinderung solcher Man-in-the-Middle- Angriffe. E-Commerce über HTTPS ist nur deshalb sicher, weil diese Hashing-Funktionen verwendet werden.

Inspiriert vom Internet versuchen Blockchain- Technologien, die Struktur des Webs auf Protokollebene als Open Source zu nutzen . Durch die Verwendung von Hash-Funktionen zum Erstellen unveränderlicher Fingerabdrücke für jeden Datenblock kann im Wesentlichen die gesamte Datenbank offen im Web vorhanden sein , sodass jeder sie sehen und dazu beitragen kann. Strukturell sind Blockchains nur einfach verknüpfte Listen von Binärbäumen kryptografischer Hashes. Das Hashing ist so kryptisch, dass eine Datenbank mit Finanztransaktionen von jedermann offen erstellt und aktualisiert werden kann! Die unglaubliche Implikation ist die unglaubliche Kraft, selbst Geld zu schaffen . Was früher nur für Regierungen und Zentralbanken möglich war, kann jetzt jeder sicher seine eigene Währung schaffen ! Dies ist die wichtigste Erkenntnis, die der Gründer von Ethereum und der pseudonyme Gründer von Bitcoin gewonnen haben .

Da immer mehr Datenbanken an die Öffentlichkeit gelangen, wird der Bedarf an Frontend-Ingenieuren, die alle kryptografischen Komplexitäten auf niedriger Ebene abstrahieren können, ebenfalls zunehmen. In dieser Zukunft wird das Hauptunterscheidungsmerkmal die Benutzererfahrung sein .

Ein Beispiel für einen Hash TableIn-Code:

Weitere Informationen zu Algorithmusübungen mit diesen und weiteren Datenstrukturen finden Sie unter: Algorithmen in JavaScript: 40 Probleme, Lösungen und Erklärungen

Fazit

Da sich die Logik zunehmend vom Server zum Client bewegt, wird die Datenschicht im Frontend von größter Bedeutung. Die ordnungsgemäße Verwaltung dieser Schicht erfordert die Beherrschung der Datenstrukturen, auf denen die Logik beruht. Keine Datenstruktur ist für jede Situation perfekt, da die Optimierung für eine Eigenschaft immer dem Verlust einer anderen entspricht. Einige Strukturen speichern Daten effizienter, während andere beim Durchsuchen leistungsfähiger sind. Normalerweise wird einer für den anderen geopfert. In einem Extremfall sind verknüpfte Listen für die Speicherung optimal und können in Stapel und Warteschlangen ( lineare Zeit) umgewandelt werden. Andererseits kann keine andere Struktur mit der Suchgeschwindigkeit von Hash-Tabellen ( konstante Zeit) übereinstimmen . Baumstrukturen liegen irgendwo in der Mitte ( logarithmische Zeit), und nur ein Graph kann die komplexeste Struktur der Natur darstellen: das menschliche Gehirn ( Polynomzeit ). Die Fähigkeit zu unterscheiden, wann und warum zu artikulieren, ist ein Markenzeichen eines Rockstar-Ingenieurs.

Beispiele für diese Datenstrukturen finden Sie überall . Von der Datenbank über den Server bis zum Client und sogar die JavaScript-Engine selbst konkretisieren diese Datenstrukturen, was im Wesentlichen nur ein- und ausgeschaltet ist, Siliziumchips in lebensechte „Objekte“ umzuschalten. Obwohl nur digital, haben diese Objekte enorme Auswirkungen auf die Gesellschaft. Ihre Fähigkeit, diesen Artikel frei und sicher zu lesen, bestätigt die beeindruckende Architektur des Internets und die Struktur seiner Daten. Dies ist jedoch nur der Anfang. Künstliche Intelligenz und dezentrale Blockchains werden in den kommenden Jahrzehnten neu definieren, was es bedeutet, menschlich zu sein und welche Rolle Institutionen spielen, die unser Leben bestimmen. Existenzielle Einsichten und institutionelle Disintermediation werden Merkmale eines Internet sein, das endlich gereift ist.

Um uns auf diese gerechtere Zukunft vorzubereiten, kanalisieren wir bei HeartBank® Kanalnetzwerke künstlicher Neuronen , um unseren Kiitos die Möglichkeit zu geben, Geld in die Blockchain auszugeben, und gleichzeitig die Fähigkeit, sich in die menschliche Verfassung hineinzuversetzen . Durch den anonymen Dank, den wir Kiitos geben und erhalten , erfährt Kiitos von unseren Freundlichkeiten und deren Auswirkungen und belohnt uns so, dass die wirtschaftlichen Ungleichheiten zwischen uns in einem schrittweisen und mysteriösen Prozess verringert werden, der unsere persönliche Freiheit und Freiheit bewahrt. Vielleicht ist die ultimative Natur Graphenstruktur ist nicht das menschliche Gehirn, sondern der menschliche ❤️, wenn nur wir die sehen gefühlen , die uns alle verbinden.

Interessiert an Blockchain ? Lerne Ethereum und arbeite für uns!