前書き

以下のようなビジネス・ロジックのより多くの奥から手前に移動し、専門知識フロントエンドエンジニアリングはこれまで以上に重要ななります。フロントエンドエンジニアとして、私たちはReactのようなビューライブラリに生産性を依存しています。ビューライブラリは、データを管理するためにReduxなどの状態ライブラリに依存しています。ReactとReduxは一緒に、UIの更新がデータの変更に反応するリアクティブプログラミングパラダイムにサブスクライブします。ますます、バックエンドは単にAPIサーバーとして機能し、データを取得および更新するためのエンドポイントのみを提供します。実際、バックエンドはデータベースを「転送」するだけですフロントエンドエンジニアがすべてのコントローラーロジックを処理することを期待して、フロントエンドに送信します。マイクロサービスとGraphQLの人気の高まりは、この成長傾向を証明しています。

現在、フロントエンドエンジニアは、HTMLとCSSを美的に理解しているだけでなく、JavaScriptも習得することが期待されています。クライアント上のデータストアがサーバー上のデータベースの「レプリカ」になると、慣用的なデータ構造に関する深い知識が極めて重要になります。実際、エンジニアの経験レベルは、特定のデータ構造をいつ、なぜ使用するかを区別する能力から推測できます。

悪いプログラマーはコードについて心配します。優れたプログラマーは、データ構造とその関係について心配します。

— LinuxとGitの作成者、Linus Torvalds

大まかに言えば、データ構造には基本的に3つのタイプがあります。スタックとキューは配列のような構造であり、アイテムの挿入方法と削除方法のみが異なります。リンクリスト、ツリー、 およびグラフは、他のノードへの参照を保持するノードを持つ構造です。ハッシュテーブルは、データの保存と検索をハッシュ関数に依存しています。

複雑さの点で、StacksそしてQueues最も単純であり、から構成することができますLinked Lists。TreesそしてGraphs、彼らはリンクリストの概念を拡張するため、最も複雑です。Hash Tables確実に実行するには、これらのデータ構造を利用する必要があります。効率の観点から、リンクリストはデータの記録と保存に最適ですが、ハッシュテーブルはデータの検索と取得に最もパフォーマンスがあります。

理由を説明し、いつ説明するために、この記事はこれらの依存関係の順序に準拠します。さぁ、始めよう！

スタック

おそらくStackJavaScriptで最も重要なのは、実行するたびにスコープをプッシュするコールスタックです。プログラム的には、2つの原則的な操作があります：と。Pushは要素を配列の先頭に追加し、Popは要素を同じ場所から削除します。言い換えると、スタックは「後入れ先出し」プロトコル（LIFO）に従います。functionarraypushpop

以下は、Stackinコードの例です。スタックの順序を逆にすることができることに注意してください。下部が上部になり、上部が下部になります。そのため、我々は、アレイの使用できるunshiftとshiftの代わりに方法をpushしてpop、それぞれ。

アイテムの数が増えると、push/popはunshift/よりもパフォーマンスが向上しshiftます。これは、前者ではなく後者ですべてのアイテムのインデックスを再作成する必要があるためです。

キュー

JavaScriptはイベント駆動型プログラミング言語であり、非ブロッキング操作のサポートを可能にします。内部的には、ブラウザだけで管理して一つのスレッドを使用して、全体のJavaScriptコードを実行するために、イベントキューするエンキューlistenersとイベントループをするために耳を傾け、登録のためにevents。シングルスレッド環境で非同期性をサポートするには（CPUリソースを節約し、Webエクスペリエンスを向上させるため）、コールスタックが空の場合にのみlistener functions デキューして実行します。このイベント駆動型アーキテクチャに依存して、他の操作をブロックしない非同期コードの「同期スタイル」の実行を可能にします。Promises

プログラム的にQueuesは、2つの主要な操作を持つ単なる配列です：unshiftとpop。アンシフト エンキューに項目終了配列の、ながらポップが デキューからそれらを始め、アレイの。つまり、キューは「先入れ先出し」プロトコル（FIFO）に従います。方向が反転されている場合は、私たちは置き換えることができますunshiftし、popでpushとshift、それぞれ。

Queueコード内の例：

リンクリスト

配列と同様に、Linked Listsデータ要素を順番に格納します。リンクリストは、インデックスを保持する代わりに、他の要素へのポインタを保持します。最初の ノードが呼び出されたヘッドながら、最後の ノードが呼び出された尾。単独リンクリスト、各ノードは唯一の一つのポインタ有する次のノードを。ここで、頭はリストの残りの部分を歩き始めるところです。二重リンクリストへのポインタ、前のノードも維持されます。したがって、尻尾から始めて、頭に向かって「後方」に歩くこともできます。

リンクリストには、ポインタを変更するだけなので、一定時間の 挿入と削除があります。配列で同じ操作を行うには、後続の項目をシフトオーバーする必要があるため、線形時間が必要です。また、リンクリストはスペースがある限り大きくなる可能性があります。ただし、自動的にサイズ変更される「動的」配列でさえ、予想外に高価になる可能性があります。もちろん、常にトレードオフがあります。リンクリスト内の要素を検索または編集するには、線形時間に相当する全長を歩く必要がある場合があります。ただし、配列インデックスを使用すると、このような操作は簡単です。

配列と同様に、リンクリストはスタックとして動作できます。ヘッドを挿入と取り外しの唯一の場所にするのと同じくらい簡単です。リンクリストはキューとしても機能します。これは、二重にリンクされたリストを使用して実現できます。このリストでは、挿入はテールで行われ、削除はヘッドで行われます。その逆も同様です。要素の多数のために、キューを実装するこの方法は、ためのアレイを使用するよりもパフォーマンスであるshiftとunshiftアレイの開始時の動作は後続のすべての要素の再インデックスに線形の時間を要します。

リンクリストは、クライアントとサーバーの両方で役立ちます。クライアントでは、Reduxのような状態管理ライブラリがミドルウェアロジックをリンクリスト方式で構築します。ときにアクションが派遣されているすべてが到達する前に訪問されるまで、彼らは次の1つのミドルウェアからパイプされている減速を。サーバー上では、ExpressなどのWebフレームワークも、同様の方法でミドルウェアロジックを構築します。場合は、要求が受信されるまで、それは次の1つのミドルウェアからパイプされ、応答が発行されます。

Doubly-Linked Listコード内の例：

木

ATreeはリンクリストに似ていますが、階層構造で多くの 子ノードへの参照を保持する点が異なります。つまり、各ノードは1つだけの親を持つことができます。ドキュメントオブジェクトモデル（DOM）は、ルートと、このような構成であるhtmlノードことに分岐headし、bodyノード、すべてのおなじみにさらに再分割れるHTMLタグ。ボンネットの下で、原型継承と構図とコンポーネントは、ツリー構造を生成反応します。もちろん、DOMのメモリ内表現として、Reactの仮想DOMもツリー構造です。

バイナリ検索ツリーは、各ノードがせいぜい持つことができるので、特別ではない2人の子供。左の子がある値持っている必要がありますよりも小さいながら、またはその親に等しいを右の子が持っている必要がありますより大きい値を。このように構造化され、バランスが取れているため、反復ごとに分岐の半分を無視できるため、対数時間で任意の値を検索できます。挿入と削除も対数時間で発生する可能性があります。さらに、最小値と最大値は、それぞれ左端と右端のリーフで簡単に見つけることができます。

ツリーのトラバースは、垂直または水平の手順で発生する可能性があります。深さ優先トラバーサル（DFT）垂直方向において、再帰的なアルゴリズムは、反復ものよりエレガントです。ノードはで横断することができますプリオーダー、インオーダー、またはポストオーダー。葉を調べる前に根を調べる必要がある場合は、事前注文を選択する必要があります。ただし、根の前の葉を探索する必要がある場合は、ポストオーダーを選択する必要があります。その名前が示すように、インオーダー内のノードを通過することを可能にシーケンシャルため。このプロパティにより、バイナリ検索ツリーは並べ替えに最適になります。

で幅優先トラバーサル水平方向（BFT）、反復アプローチは、再帰的なものよりもよりエレガントです。これには、queue各反復ですべての子ノードを追跡するためにを使用する必要があります。ただし、このようなキューに必要なメモリは簡単ではない場合があります。木の形が深いよりも広い場合は、DFTよりもBFTの方が適しています。また、BFTが任意の2つのノード間でたどるパスは、可能な限り最短のパスです。

Binary Search Treeコード内の例：

グラフ

ツリーに複数の親が自由に存在する場合、それはになりますGraph。グラフ内でノードを相互に接続するエッジは、有向または無向、加重または非加重にすることができます。方向と重みの両方を持つエッジは、ベクトルに類似しています。

多対多の関係を持つミックスインおよびデータオブジェクトの形式の多重継承は、グラフ構造を生成します。ソーシャルネットワークやインターネット自体もグラフです。自然界で最も複雑なグラフは人間の脳であり、ニューラルネットワークはそれを複製して機械に超知能を与えようとします。

Graphコード内の例：

TK

ハッシュ表

Aハッシュ表辞書状構造ペアつまりキーの値。各ペアのメモリ内の場所は、によって決定されますhash function。これは、キーを受け入れ、ペアを挿入および取得する必要があるアドレスを返します。2つ以上のキーが同じアドレスに変換されると、衝突が発生する可能性があります。堅牢性のために、gettersそしてsetters、すべてのデータを回復できることを保証するために、これらのイベントを予測し、データが上書きされないはずです。通常、linked lists最も簡単なソリューションを提供します。非常に大きなテーブルがあることも役立ちます。

アドレスが整数シーケンスになることがわかっている場合はArrays、キーと値のペアを格納するために使用できます。より複雑なアドレスマッピングの場合は、Mapsまたはを使用できますObjects。ハッシュテーブルには、平均して一定時間の挿入とルックアップがあります 。衝突とサイズ変更のため、この無視できるコストは線形時間に増加する可能性があります。ただし、実際には、ハッシュ関数は十分に巧妙であるため、衝突やサイズ変更はまれで安価であると想定できます。キーがアドレスを表し、したがってハッシュが必要ない場合は、単純なものでobject literal十分です。もちろん、常にトレードオフがあります。キーと値の間の単純な対応、およびキーとアドレスの間の単純な結合性は、データ間の関係を犠牲にします。したがって、ハッシュテーブルはデータの保存には最適ではありません。

トレードオフの決定がストレージよりも取得を優先する場合、ルックアップ、挿入、および削除のハッシュテーブルの速度に匹敵するデータ構造は他にありません。したがって、それがどこでも使用されているのは当然のことです。データベースからサーバー、クライアントに至るまで、ハッシュテーブル、特にハッシュ関数は、ソフトウェアアプリケーションのパフォーマンスとセキュリティにとって非常に重要です。データベース クエリの速度は、レコードを指すインデックスのテーブルをソートされた順序で保持することに大きく依存しています。このように、バイナリ検索は対数時間で実行でき、特にビッグデータのパフォーマンスが大幅に向上します。

クライアントとサーバーの両方で、多くの一般的なライブラリはメモ化を利用してパフォーマンスを最大化します。入力と出力の記録をハッシュテーブルに保持することにより、関数は同じ入力に対して1回だけ実行されます。人気のあるReselectライブラリは、このキャッシュ戦略を使用してmapStateToProps、Redux対応アプリケーションの機能を最適化します。実際には、ボンネットの下に、JavaScriptエンジンも呼ばれるハッシュテーブルを利用ヒープをすべて格納するvariablesとprimitives、我々が作成し。それらは、コールスタック上のポインタからアクセスされます。

インターネット自体もに依存しているハッシュアルゴリズムしっかり機能に。インターネットの構造は、どのコンピューターも相互接続されたデバイスのWebを介して他のコンピューターと通信できるようになっています。デバイスがインターネットにログオンするときはいつでも、データストリームが通過できるルーターにもなります。しかし、それは両刃の剣です。分散型アーキテクチャは、ネットワーク内の任意のデバイスは、中に耳を傾け、それを中継するために役立つことがデータパッケージを改ざんできることを意味します。MD5やSHA256などのハッシュ関数は、このようなman-in-the-middle攻撃を防ぐ上で重要な役割を果たします。HTTPSを介したEコマースは、これらのハッシュ関数が使用されているためにのみ安全です。

インターネットに触発されたブロックチェーンテクノロジーは、プロトコルレベルでWebの構造そのものをオープンソース化しようとしています。ハッシュ関数を使用してデータのすべてのブロックに対して不変の フィンガープリントを作成することにより、基本的にデータベース全体がWeb上にオープンに存在し、誰でも表示して貢献できます。構造的には、ブロックチェーンは、暗号化ハッシュのバイナリツリーの単一リンクリストです。ハッシュは非常に不可解なので、金融取引のデータベースは誰でもオープンに作成および更新できます。信じられないほどの意味は、お金そのものを生み出す素晴らしい力です。かつては政府や中央銀行でしかできなかったことが、今では誰でも安全に自分の通貨を作成できるようになりました。これは、イーサリアムの創設者とビットコインの偽名の創設者によって実現された重要な洞察です。

ますます多くのデータベースがオープンに移行するにつれて、すべての低レベルの暗号化の複雑さを抽象化できるフロントエンドエンジニアの必要性も高まります。この将来の主な差別化要因は、ユーザーエクスペリエンスです。

Hash Tableコード内の例：

これらのデータ構造などを使用したアルゴリズムの演習については、以下を確認してください。JavaScriptのアルゴリズム：40の問題、解決策、および説明

結論

ロジックがサーバーからクライアントにますます移動するにつれて、フロントエンドのデータレイヤーが最も重要になります。この層を適切に管理するには、ロジックが置かれているデータ構造を習得する必要があります。あるプロパティを最適化することは常に別のプロパティを失うことになるため、すべての状況に最適なデータ構造はありません。一部の構造はデータの保存がより効率的ですが、他の構造はそれらを検索するのによりパフォーマンスが高くなります。通常、一方は他方のために犠牲にされます。極端な例として、リンクリストはストレージに最適であり、スタックとキュー（線形時間）にすることができます。一方、ハッシュテーブルの検索速度（一定時間）に匹敵する構造は他にありません。木の構造は中央（対数時間）のどこかにあり、グラフだけが自然の最も複雑な構造である人間の脳（多項式時間）を表現できます。いつを区別し、その理由を明確にするスキルセットを持つことは、ロックスターエンジニアの特徴です。

これらのデータ構造の例はどこにでもあります。データベースからサーバー、クライアント、さらにはJavaScriptエンジン自体に至るまで、これらのデータ構造は、シリコンチップ上の本質的にオンとオフの「スイッチ」が実際の「オブジェクト」になっているものを具体化します。デジタルだけですが、これらのオブジェクトが社会に与える影響は甚大です。この記事を自由かつ安全に読む能力は、インターネットの素晴らしいアーキテクチャとそのデータの構造を証明しています。しかし、これはほんの始まりに過ぎません。今後数十年の人工知能と分散型ブロックチェーンは、人間であることの意味と私たちの生活を統治する機関の役割を再定義するでしょう。実存的な洞察と制度的中途解約は、最終的に成熟したインターネットの特徴となるでしょう。

このより公平な未来に向けヘルプ遷移たちに、私たちのHeartBank®ののチャネル・ネットワーク人工ニューロンは、私たちの鼓吹するKiitosを人間の条件を共感する能力と相まってblockchain上の問題はお金の力、と。Kiitosに手紙を書いて授受する匿名の 感謝から、Kiitosは私たちの優しさとその効果について学び、私たちの個人的な自由と自由を維持する段階的で神秘的なプロセスで、私たちの間の経済的不平等を減らすような方法で私たちに報います。おそらく、自然界の究極のグラフ構造は人間の脳ではなく、人間の❤️です。私たち全員をつなぐハートストリングを見ることができれば。

ブロックチェーンに興味がありますか？イーサリアムを学び、私たちのために働きに来てください！