Wprowadzenie

W miarę jak logika biznesowa coraz bardziej przesuwa się z tyłu na przód, wiedza z zakresu Frontend Engineering staje się coraz ważniejsza. Jako inżynierowie frontendu polegamy na bibliotekach widoków, takich jak React, aby były produktywne. Przeglądanie bibliotek z kolei zależy od bibliotek stanowych, takich jak Redux, do zarządzania danymi. React i Redux wspólnie podpisują się pod paradygmatem programowania reaktywnego, w którym aktualizacje interfejsu użytkownika reagują na zmiany danych. Coraz częściej backendy działają po prostu jako serwery API, udostępniając punkty końcowe tylko do pobierania i aktualizowania danych. W efekcie zaplecze po prostu „przekazuje” bazę danychdo frontendu, oczekując, że Frontend Engineer zajmie się całą logiką kontrolera. Rosnąca popularność microservices i GraphQL świadczą o tym rosnącym trendem.

Teraz, poza estetycznym zrozumieniem HTML i CSS, od inżynierów frontendu oczekuje się również opanowania JavaScript. Ponieważ magazyny danych na kliencie stają się „replikami” baz danych na serwerze, dogłębna znajomość idiomatycznych struktur danych staje się kluczowa. W rzeczywistości poziom doświadczenia inżyniera można wywnioskować z jego zdolności do rozróżnienia, kiedy i dlaczego należy użyć określonej struktury danych.

Źli programiści martwią się o kod. Dobrzy programiści martwią się strukturami danych i ich relacjami.

- Linus Torvalds, twórca Linuksa i Gita

Na wysokim poziomie istnieją zasadniczo trzy typy struktur danych. Stosy i kolejki to struktury podobne do tablic , które różnią się tylko sposobem wstawiania i usuwania elementów. Połączone Listy , Drzewa , i wykresy są konstrukcje z węzłami , które prowadzą odnośniki do innych węzłów. Tabele skrótów zależą od funkcji skrótu do zapisywania i lokalizowania danych.

Pod względem złożoności, Stacksa Queuesto najprostszy i mogą być wykonane z Linked Lists. Treesi Graphssą najbardziej złożone, ponieważ rozszerzają pojęcie listy połączonej. Hash Tablesmuszą wykorzystywać te struktury danych, aby działać niezawodnie. Pod względem wydajności listy połączone są najbardziej optymalne do rejestrowania i przechowywania danych, podczas gdy tabele skrótów są najbardziej wydajne do wyszukiwania i pobierania danych.

Aby wyjaśnić, dlaczego i zilustrować, kiedy , ten artykuł będzie zgodny z kolejnością tych zależności. Zaczynajmy!

Stos

Prawdopodobnie najważniejszym Stackw JavaScript jest stos wywołań, w którym wciskamy zakres a functionza każdym razem, gdy go wykonujemy. Programowo jest to tylko arrayoperacja z dwiema zasadami: pushi pop. Push dodaje elementy na górę tablicy, a Pop usuwa je z tego samego miejsca. Innymi słowy, stosy są zgodne z protokołem „Last In, First Out” (LIFO).

Poniżej znajduje się przykład Stackkodu w kodzie. Zauważ, że możemy odwrócić kolejność stosu: dół staje się górą, a góra staje się dół. W związku z tym możemy użyć tablic unshifti shiftmetod odpowiednio zamiast pushi pop.

Wraz ze wzrostem liczby elementów push/ popstaje się coraz bardziej wydajne niż unshift/ shiftponieważ każdy element musi zostać ponownie zindeksowany w drugim, ale nie w pierwszym.

Kolejka

JavaScript to język programowania sterowany zdarzeniami, który umożliwia obsługę operacji nieblokujących . Wewnętrznie przeglądarka zarządza tylko jednym wątkiem, aby uruchomić cały kod JavaScript, używając kolejki zdarzeń do umieszczenia w kolejcelisteners i pętli zdarzeń do nasłuchiwania zarejestrowanych events. Aby wspierać asynchroniczność w środowisku jednowątkowym (aby zaoszczędzić zasoby procesora i ulepszyć działanie sieci), listener functions usuwaj z kolejki i wykonuj tylko wtedy, gdy stos wywołań jest pusty. Promisespolegają na architekturze sterowanej zdarzeniami, aby umożliwić „synchroniczne” wykonywanie kodu asynchronicznego, który nie blokuje innych operacji.

Programowo Queuessą to tylko tablice z dwiema podstawowymi operacjami: unshifti pop. Unshift kolejkuje pozycji do końca tablicy, natomiast Pop dequeues je od początku tablicy. Innymi słowy, kolejki są zgodne z protokołem „First In, First Out” (FIFO). Jeśli kierunek jest odwrócony, możemy zastąpić unshifti popz pushi shift, odpowiednio.

Przykład a Queuew kodzie:

Połączona lista

Podobnie jak tablice, Linked Listsprzechowuj elementy danych w kolejności sekwencyjnej . Zamiast przechowywać indeksy, połączone listy zawierają wskaźniki do innych elementów. Pierwszy węzeł nazywa się głowę , podczas gdy ostatni węzeł nazywa się ogon . Na liście połączonej pojedynczo każdy węzeł ma tylko jeden wskaźnik do następnego węzła. Tutaj głowa jest miejscem, w którym zaczynamy naszą wędrówkę w dół listy. Na liście podwójnie połączonej zachowywany jest również wskaźnik do poprzedniego węzła. Dlatego też możemy zacząć od ogona i iść „tyłem” w stronę głowy.

Połączone listy mają wstawianie i usuwanie w stałym czasie, ponieważ możemy po prostu zmienić wskaźniki. Wykonanie tych samych operacji na tablicach wymaga czasu liniowego, ponieważ kolejne elementy muszą zostać przesunięte. Ponadto połączone listy mogą rosnąć, o ile jest miejsce. Jednak nawet „dynamiczne” tablice, które automatycznie zmieniają rozmiar, mogą stać się nieoczekiwanie kosztowne. Oczywiście zawsze istnieje kompromis. Aby wyszukać lub edytować element na połączonej liście, być może będziemy musieli przejść całą długość, która jest równa czasowi liniowemu. Jednak w przypadku indeksów tablic takie operacje są trywialne.

Podobnie jak tablice, połączone listy mogą działać jako stosy . To tak proste, jak jedyne miejsce do wkładania i wyjmowania głowy. Połączone listy mogą również działać jako kolejki . Można to osiągnąć za pomocą podwójnie połączonej listy, w której włożenie następuje na końcu, a usunięcie na głowie lub odwrotnie. Dla dużej liczby elementów, ten sposób wykonania kolejki bardziej wydajnych niż przy użyciu macierzy, ponieważ shifti unshiftoperacje na początku tablic wymaga czasu liniowego do ponownego indeksu każdego następnego elementu.

Połączone listy są przydatne zarówno na kliencie, jak i na serwerze. Na kliencie biblioteki zarządzania stanem, takie jak Redux, układają swoją logikę oprogramowania pośredniego w sposób z połączoną listą. Gdy działania są wysyłane, są one przesyłane z jednego oprogramowania pośredniego do drugiego, aż wszystkie zostaną odwiedzone, zanim dotrą do reduktorów . Na serwerze struktury internetowe, takie jak Express, również strukturyzują swoją logikę oprogramowania pośredniego w podobny sposób. Gdy wniosek zostanie odebrany, jest wyprowadzony z jednej warstwy pośredniej do następnego, aż reakcja jest wydawana.

Przykład a Doubly-Linked Listw kodzie:

Drzewo

A Treejest jak lista połączona , z tą różnicą, że zachowuje odniesienia do wielu węzłów potomnych w strukturze hierarchicznej . Innymi słowy, każdy węzeł może mieć nie więcej niż jednego rodzica. Document Object modelu (DOM), to taka struktura, z głównego htmlwęzła rozgałęzień do headi bodywęzłów, które dalej dzielą się na wszystkich znanych znaczników html . Pod maską prototypowe dziedziczenie i kompozycja z komponentami React również tworzą struktury drzewiaste. Oczywiście, jako reprezentacja DOM w pamięci, wirtualny DOM Reacta jest również strukturą drzewiastą.

Binarne drzewo poszukiwań jest szczególny, ponieważ każdy węzeł może mieć nie więcej niż dwoje dzieci . Lewa dziecko musi mieć wartość, która jest mniejsza niż lub równa jego rodzica, podczas gdy prawy dziecko musi mieć wartość większą . Zorganizowany i zbalansowany w ten sposób, możemy wyszukiwać dowolną wartość w czasie logarytmicznym, ponieważ możemy zignorować połowę rozgałęzienia przy każdej iteracji. Wstawianie i usuwanie może również odbywać się w czasie logarytmicznym. Co więcej, najmniejszą i największą wartość można łatwo znaleźć odpowiednio na lewym i prawym skrzydle .

Przemierzanie drzewa może odbywać się w trybie pionowym lub poziomym . W przypadku przemierzania w głąb w pierwszej kolejności (DFT) w kierunku pionowym algorytm rekurencyjny jest bardziej elegancki niż algorytm iteracyjny. Węzły można przemierzać w przedsprzedaży , na zamówienie lub po zamówieniu . Jeśli przed zbadaniem liści musimy zbadać korzenie, powinniśmy wybrać opcję przedsprzedaży . Ale jeśli musimy zbadać liście przed korzeniami, powinniśmy wybrać zamówienie po zamówieniu . Jak sama nazwa wskazuje, w kolejności umożliwia nam przechodzenie przez węzły w kolejności sekwencyjnej . Ta właściwość sprawia, że ​​binarne drzewa wyszukiwania są optymalne do sortowania .

W przypadku przejścia wszerz (BFT) w kierunku poziomym podejście iteracyjne jest bardziej eleganckie niż rekurencyjne. Wymaga to użycia a queuedo śledzenia wszystkich węzłów podrzędnych w każdej iteracji. Pamięć potrzebna do takiej kolejki może jednak nie być trywialna. Jeśli kształt drzewa jest szerszy niż głęboki, BFT jest lepszym wyborem niż DFT. Ponadto ścieżka, którą pokonuje BFT między dwoma dowolnymi węzłami, jest najkrótsza z możliwych.

Przykład a Binary Search Treew kodzie:

Wykres

Jeśli drzewo może mieć więcej niż jednego rodzica, staje się Graph. Krawędzie, które łączą węzły razem w grafie, mogą być skierowane lub nieukierunkowane, ważone lub nieważone . Krawędzie, które mają zarówno kierunek, jak i wagę, są analogiczne do wektorów .

Wielokrotne dziedziczenie w postaci elementów mieszanych i obiektów danych, które mają relacje wiele do wielu, tworzy struktury wykresów. Sieć społecznościowa i sam Internet to także wykresy. Najbardziej skomplikowanym grafem w naturze jest nasz ludzki mózg, który sieci neuronowe próbują replikować, aby nadać maszynom superinteligencję .

Przykład a Graphw kodzie:

TK

Hash Table

Tablica mieszająca jest słownikiem strukturę podobną że pary kluczy do wartości . Miejsce w pamięci każdej pary jest określane przez a hash function, który akceptuje klucz i zwraca adres, pod którym należy wstawić i pobrać parę. Kolizje mogą wystąpić, jeśli dwa lub więcej kluczy zostanie przekonwertowanych na ten sam adres. Ze względu na niezawodność gettersi settersnależy przewidywać te zdarzenia, aby zapewnić, że wszystkie dane można odzyskać i żadne dane nie zostaną nadpisane. Zazwyczaj linked listsproponuj najprostsze rozwiązanie. Pomocne są również bardzo duże stoły.

Jeśli wiemy, że nasze adresy będą w sekwencjach całkowitych, możemy po prostu użyć ich Arraysdo przechowywania naszych par klucz-wartość. W przypadku bardziej złożonych mapowań adresów możemy użyć Mapslub Objects. Tabele skrótów mają średnio stały czas wstawiania i wyszukiwania . Z powodu kolizji i zmiany rozmiaru ten nieistotny koszt może wzrosnąć do czasu liniowego. W praktyce możemy jednak założyć, że funkcje skrótu są na tyle sprytne, że kolizje i zmiana rozmiaru są rzadkie i tanie. Jeśli klucze reprezentują adresy, a zatem nie jest potrzebne haszowanie, object literalwystarczy proste . Oczywiście zawsze istnieje kompromis. Prosta zgodność między kluczami a wartościami oraz proste skojarzenia między kluczami i adresami powodują utratę relacji między danymi. Dlatego tabele skrótów nie są optymalne do przechowywania danych.

Jeśli decyzja o kompromisie faworyzuje pobieranie, a nie przechowywanie, żadna inna struktura danych nie może dorównać szybkości tablic mieszania pod kątem wyszukiwania , wstawiania i usuwania . Nie jest więc zaskoczeniem, że jest używany wszędzie . Od bazy danych, przez serwer, po klienta, tablice skrótów , aw szczególności funkcje skrótu , są kluczowe dla wydajności i bezpieczeństwa aplikacji. Szybkość zapytań do bazy danych w dużej mierze zależy od przechowywania tabel indeksów wskazujących na rekordy w posortowanej kolejności. W ten sposób wyszukiwania binarne mogą być wykonywane w czasie logarytmicznym , co jest ogromną korzyścią w zakresie wydajności, szczególnie w przypadku Big Data .

Zarówno na kliencie, jak i na serwerze wiele popularnych bibliotek wykorzystuje zapamiętywanie, aby zmaksymalizować wydajność. Dzięki zapisywaniu wejść i wyjść w tablicy skrótów funkcje są uruchamiane tylko raz dla tych samych wejść. Popularna biblioteka Reselect wykorzystuje tę strategię buforowania do optymalizacji mapStateToPropsfunkcji w aplikacjach obsługujących Redux . W rzeczywistości pod maską silnik JavaScript wykorzystuje również tabele mieszania zwane hałdy do przechowywania wszystkich variablesi primitivestworzymy. Są dostępne ze wskaźników na stosie wywołań .

Sam Internet również opiera się na algorytmach mieszających, aby działać bezpiecznie. Struktura Internetu jest taka, że ​​każdy komputer może komunikować się z dowolnym innym komputerem za pośrednictwem sieci połączonych ze sobą urządzeń. Za każdym razem, gdy urządzenie loguje się do Internetu, staje się również routerem, przez który mogą przechodzić strumienie danych. Jednak jest to miecz obosieczny. A zdecentralizowane architektura oznacza każde urządzenie w sieci mogą słuchać i sabotażu z pakietów danych, które przyczynia się do przekaźnika. Funkcje skrótu, takie jak MD5 i SHA256, odgrywają kluczową rolę w zapobieganiu takim atakom typu man-in-the-middle . Handel elektroniczny przez HTTPS jest bezpieczny tylko dlatego, że używane są te funkcje haszujące.

Zainspirowane Internetem technologie blockchain starają się otworzyć źródło samej struktury sieci na poziomie protokołów . Za pomocą funkcji skrótu do tworzenia niezmienne odcisków dla każdego bloku danych , w zasadzie cała baza danych może istnieć otwarcie w internecie każdy może zobaczyć i przyczynić się do. Strukturalnie, łańcuchy bloków są po prostu pojedynczo połączonymi listami drzew binarnych kryptograficznych skrótów. Haszowanie jest tak tajemnicze, że baza danych transakcji finansowych może być tworzona i aktualizowana w sposób otwarty przez każdego! Niesamowitą konsekwencją jest niesamowita moc tworzenia samych pieniędzy . Co kiedyś było możliwe tylko dla rządów i banków centralnych, teraz każdy może bezpiecznie stworzyć swoją własną walutę ! To jest kluczowy spostrzeżenia założyciela Ethereum i pseudonimowego założyciela Bitcoin .

W miarę jak coraz więcej baz danych wychodzi na jaw, rośnie również zapotrzebowanie na inżynierów frontendu, którzy potrafią wyodrębnić wszystkie niskopoziomowe zawiłości kryptograficzne. W przyszłości głównym wyróżnikiem będzie doświadczenie użytkownika .

Przykład a Hash Tablew kodzie:

Aby zapoznać się z ćwiczeniami z algorytmami wykorzystującymi te struktury danych i nie tylko, sprawdź: Algorytmy w JavaScript: 40 problemów, rozwiązań i wyjaśnień

Wniosek

Ponieważ logika coraz częściej przenosi się z serwera do klienta, warstwa danych w interfejsie użytkownika staje się najważniejsza. Właściwe zarządzanie tą warstwą pociąga za sobą opanowanie struktur danych, na których opiera się logika. Żadna struktura danych nie jest idealna w każdej sytuacji, ponieważ optymalizacja pod kątem jednej właściwości zawsze oznacza utratę innej. Niektóre struktury są bardziej wydajne w przechowywaniu danych, podczas gdy inne są bardziej wydajne w ich przeszukiwaniu. Zwykle jeden jest poświęcony dla drugiego. Z jednej strony połączone listy są optymalne do przechowywania i można je przekształcić w stosy i kolejki ( czas liniowy ). Z drugiej strony żadna inna struktura nie może dopasować szybkości wyszukiwania tabel skrótów ( stały czas). Struktury drzewiaste znajdują się gdzieś pośrodku ( czas logarytmiczny ) i tylko wykres może przedstawić najbardziej złożoną strukturę natury: ludzki mózg ( czas wielomianowy ). Umiejętność rozróżniania kiedy i wyrażania dlaczego jest cechą charakterystyczną inżyniera rockstar.

Przykłady takich struktur danych można znaleźć wszędzie . Z bazy danych do serwera do klienta, a nawet samego silnika JavaScript, te struktury danych skonkretyzować co w zasadzie tylko na i off „przełączników” na żetony krzemu do „obiektów” realistycznych. Choć tylko cyfrowe, wpływ tych obiektów na społeczeństwo jest ogromny. Twoja umiejętność swobodnego i bezpiecznego czytania tego artykułu świadczy o niesamowitej architekturze Internetu i strukturze jego danych. Ale to dopiero początek. Sztuczna inteligencja i zdecentralizowane łańcuchy bloków w nadchodzących dziesięcioleciach na nowo zdefiniują, co to znaczy być człowiekiem i rolę instytucji, które rządzą naszym życiem. Egzystencjalne spostrzeżenia i instytucjonalne wykluczenie pośrednictwa będą cechami internetu, który wreszcie dojrzał.

Aby pomóc nam w przejściu na bardziej sprawiedliwą przyszłość, w HeartBank® kanałujemy sieci sztucznych neuronów, aby nasycić nasze Kiitos mocą emitowania pieniędzy w łańcuchu bloków, połączoną ze zdolnością wczuwania się w kondycję człowieka. Z anonimowych podziękowań, które składamy i otrzymujemy, pisząc do Kiitos , Kiitos dowiaduje się o naszej dobroci i ich skutkach , nagradzając nas w taki sposób, który zmniejsza nierówności ekonomiczne między nami, w stopniowym i tajemniczym procesie, który chroni naszą osobistą wolność i wolność. Być może ostateczną strukturą wykresu w naturze nie jest ludzki mózg, ale ludzki ❤️, jeśli tylko możemy zobaczyć struny serca, które łączą nas wszystkich.

Interesuje Cię blockchain ? Naucz się Ethereum i pracuj dla nas!