テクノロジー企業で働いていたときに使用したデータ構造とアルゴリズム

日常業務でデータ構造とアルゴリズムを使用していますか？アルゴリズムを現実とあまり関係のないものだと考える人が増えていることに気づきました。ハイテク企業は、自分たちの気まぐれでインタビューに興味を持っています。多くの人々は、アルゴリズムの問​​題は現在の研究とはほとんど関係のない理論の分野からのものであると不平を言います。 Homebrewの作者であるMaxHowellがGoogleのインタビューで彼に何が起こったのかをツイートした後、この見方は間違いなく広がりました。Google：



エンジニアの90％があなたが書いたプログラム（Homebrew）を使用していますが、あなたはボード上のバイナリツリーを反転できないので、さようなら。



バイナリツリーを反転する必要はありませんでしたが、Skype / Microsoft、Skyscanner、Uberで働いていたときに、日常業務でデータ構造とアルゴリズムを実際に使用した例に出くわしました。これには、データ構造とアルゴリズムの詳細に基づくコーディングと意思決定が含まれていました。しかし、私はほとんどの場合、特定のシステムがどのように作成されたか、そしてなぜそれらがそのように作成されたかを理解するために、関連する知識を使用しました。関連する概念の知識により、これらの概念が使用されているシステムのアーキテクチャと実装を理解しやすくなります。







この記事では、ツリーやグラフなどのデータ構造やさまざまなアルゴリズムが実際のプロジェクトで使用されている状況についての話を含めました。ここで、データ構造とアルゴリズムの基本的な知識は、インタビューだけに必要な役に立たない理論ではなく、急成長している革新的なテクノロジー企業で働く誰かが本当に必要とする可能性が非常に高いことを読者に示したいと思います。



ここではごく少数のアルゴリズムについて説明しますが、データ構造に関する限り、ここではそれらのほとんどすべてに触れます。私がアルゴリズムを強調しすぎて、練習に触れておらず、赤黒の木やAVLの木のようなエキゾチックなデータ構造をターゲットにしているようなインタビューの質問のファンではないことは、誰にとっても当然のことです。私はインタビューでそのような質問をしたことがなく、質問もしません。この記事の最後に、そのようなインタビューについての私の考えを共有します。しかし、上記にもかかわらず、基礎となるデータ構造の知識は計り知れない価値があります。この知識により、特定の実際的な問題を解決するために必要なものを正確に選択できます。



次に、実際のデータ構造とアルゴリズムの使用例に移りましょう。

ツリーとツリートラバーサル：Skype、Uber、UIフレームワーク

Xbox One用のSkypeを開発していたとき、必要なライブラリがない純粋なXboxOS用にコードを作成する必要がありました。このプラットフォーム用の最初の本格的なアプリケーションの1つを開発しました。タッチスクリーンと音声コマンドの両方を使用して操作できるアプリケーションナビゲーションシステムが必要でした。



基本的なWinJSベースのナビゲーションフレームワークを作成しました。これを行うには、DOMのようなグラフを維持する必要がありました。これは、ユーザーが対話できる要素の観察を整理するために必要でした。このような要素を見つけるために、DOMトラバーサルを実行しました。これは、ツリートラバーサル、つまりDOM要素の既存の構造に要約されます。これは、BFSまたはDFSの典型的な例です（幅優先検索または深度優先検索-幅優先検索または深度優先検索）。



Web開発を行っている場合、これは、ツリー構造、つまりDOMをすでに使用していることを意味します。すべてのDOMノードは子ノードを持つことができます。ブラウザは、DOMツリーをトラバースした後、画面にノードを表示します。特定の要素を見つける必要がある場合は、組み込みのDOMメソッドを使用してこの問題を解決できます。たとえば、getElementByIdメソッド。別の方法は、ノードをトラバースして必要なものを見つけるための独自のBFSまたはDFSソリューションを開発することです。たとえば、ここでは同様のことが行われます。



UI要素をレンダリングする多くのフレームワークは、その深さでツリー構造を使用します。そのため、Reactは仮想DOMをサポートし、スマートな調整アルゴリズムを使用します（比較）。これにより、インターフェイスの変更された部分のみが再レンダリングされるため、高いパフォーマンスを実現できます。このプロセスの可視化は、ここで見つけることができます。 モバイルアーキテクチャUberでは、RIB



、木も使用されます。これにより、このアーキテクチャは、要素の階層構造を表示する他のほとんどのUIフレームワークと同様になります。 RIBアーキテクチャは、状態管理の目的でRIBツリーを維持します。 RIBをアタッチしたり、RIBからデタッチしたりすると、レンダリングが制御されます。 RIBを操作しているときに、RIBが既存の階層に適合するかどうかを理解するためにスケッチを行い、問題のRIBに可視要素を含める必要があるかどうかについて話し合うことがありました。つまり、この構造がインターフェイスの視覚的表現の形成に関与するのか、それとも状態管理にのみ使用されるのかについて話し合いました。





RIBを使用する場合の状態遷移。あなたは、ここでのRIBの詳細を見つけることができます。



あなたは、階層的な要素をレンダリングするツリー構造は通常、それらを横断して訪問した要素をレンダリング、このために使用されていることに注意する必要がある場合。私はこのアプローチを採用する多くの内部ツールに出くわしました。このようなツールの例は、Uberのモバイルプラットフォームチームによって作成されたRIBレンダラーです。ここで、このトピックに関する話。

加重グラフと最短パスファインダー：Skyscanner

Skyscannerは、航空券のお買い得情報を見つけることを目的としたプロジェクトです。そのような提案の検索は、世界に存在するすべてのルートを表示および分析し、それらを組み合わせることによって実行されます。航空会社は次のフライトの待機時間を独自に計算するため、このタスクの本質は、検索ロボットによる自動データ収集に関連しており、このすべてのデータをキャッシュすることには関連していません。しかし、いくつかの都市を訪問する旅行を計画する可能性は、最短の道を見つけるという仕事に帰着します。



複数都市の旅行計画は、Skyscannerが実装するのに長い時間がかかった可能性の1つでした。同時に、主に開発中のシステム自体に関連する問題。この種の最良の取引は、DijkstraやA *などの最短パスアルゴリズムを使用して見つけられます。飛行ルートは、有向グラフの形式で表示されます。その各エッジには、チケット価格の形式で重みが割り当てられます。最適なルートを検索する場合、2つの都市間の最も安いルートを見つけるには、変更されたA *アルゴリズムの実装を使用します。航空券の選択と最短ルートの検索のトピックに興味がある場合は、 BFSを使用してそのような問題を解決するための良い記事があります。



ただし、Skyscannerの場合、問題を解決するためにどのアルゴリズムが使用されたかは特に重要ではありませんでした。キャッシング、検索ロボットの使用、さまざまなサイトでの作業の整理-これらはすべて、アルゴリズムを選択するよりもはるかに困難でした。しかし同時に、最短経路を見つけるという問題のさまざまなバリエーションが、多くの異なる旅行計画会社で発生し、そのような旅行のコストを最適化します。当然のことながら、このトピックはSkyscannerでも舞台裏の話の主題となっています。

並べ替え：Skype（またはそのようなもの）

ソートアルゴリズムを自分で実装したり、その構造の複雑さを深く研究したりする理由はめったにありませんでした。しかし、それにもかかわらず、バブルソート、挿入ソート、マージソート、選択ソートから、最も複雑なアルゴリズムであるクイックソートまで、このようなアルゴリズムがどのように機能するかを理解するのは興味深いことでした。特にライブラリの一部であるソート関数を作成する必要がない場合は、このようなアルゴリズムを実装する必要はめったにないことがわかりました。



しかし、Skypeでは、ソートアルゴリズムの知識を実際に使用する必要がありました。プログラマーの1人が、連絡先を表示するために挿入による並べ替えを実装することにしました。 2013年、Skypeがオンラインだったとき、連絡先はバッチでダウンロードされました。それらをすべてダウンロードするのに少し時間がかかりました。その結果、そのプログラマーは、挿入ソートを使用して名前でソートされた連絡先のリストを作成する方がよいと考えました。すでに実装されているものを使用しない理由を考えながら、このアルゴリズムについて多くのことを議論しました。その結果、アルゴリズムの実装を適切にテストし、そのパフォーマンスを確認するのに最も時間がかかりました。個人的には、このアルゴリズムの独自の実装を作成することにあまり意味がありませんでした。しかし、その後、プロジェクトはそのような段階にありましたそんなことをする時間があったところ。



もちろん、効率的な並べ替えがプロジェクトで非常に重要な役割を果たす実際の状況があります。また、開発者がデータの機能に基づいて独自に最適なアルゴリズムを選択できる場合、これによりソリューションのパフォーマンスが著しく向上する可能性があります。挿入ソートは、リアルタイムでどこかに送信された大きなデータセットを操作し、このデータをすぐに視覚化する場合に非常に役立ちます。マージソートは、異なるノードに格納されている大量のデータを処理する場合の分割および征服アプローチに適しています。私はそのようなシステムを使ったことがないので、今のところ、ソートアルゴリズムは日常業務での使用が制限されているものとして考え続けています。それは本当です、さまざまな並べ替えアルゴリズムがどのように機能するかを理解することの重要性についてではありません。

ハッシュテーブルとハッシュ：どこでも

私が定期的に使用するデータ構造はハッシュテーブルです。これにはハッシュ関数も含まれます。これは、特定のエンティティの数のカウント、重複の検出、キャッシュから、分散システムで使用されるシャーディングなどのシナリオまで、さまざまなタスクを解決するために使用できる非常に便利なツールです。ハッシュテーブルは、配列の後、プログラミングで最も一般的なデータ構造です。私はそれを無数の状況で使用しました。ほぼすべてのプログラミング言語に存在し、必要に応じて、自分で簡単に実装できます。

スタックとキュー：時々

スタックは、スタックトレースをサポートする言語で記述されたコードをデバッグしたことのある人なら誰でも知っているデータ構造です。スタックをデータ構造として説明すると、作業の過程で、それを解決するために必要ないくつかの問題が発生しました。ただし、コードのパフォーマンスをデバッグおよびプロファイリングするときに、スタックを正しく知ることができたことに注意してください。スタックは、DFSを実行するときに使用するデータ構造の自然な選択でもあります。



キューを使用する必要はめったにありませんでしたが、さまざまなプロジェクトのコードベースでキューに頻繁に遭遇しました。何かがキューに入れられ、そこから何かが取得されたとしましょう。通常、キューは幅優先のツリートラバーサルを実装するために使用され、このタスクに最適です。キューは、他の多くの状況でも使用できます。ある日、最短のジョブが最初に実行されたときに、heapqPythonモジュールによって実装された優先度キューの適切な使用例を見つけたジョブスケジューリングコードに出くわしました。

暗号化アルゴリズム：Uber

ユーザーがモバイルアプリまたはWebアプリに入力する重要なデータは、ネットワーク経由で送信する前に暗号化する必要があります。そして、必要な場所でのみ復号化します。このような作業スキームを整理するには、アプリケーションのクライアント部分とサーバー部分に暗号化アルゴリズムの実装が存在する必要があります。



暗号化アルゴリズムを理解することは非常に興味深いことです。同時に、特定の問題を解決するための独自のアルゴリズムを提供するべきではありません。これは、プログラマーが考えることができる最悪のアイデアの1つです。代わりに、既存の十分に文書化された標準を採用し、それぞれのフレームワークのネイティブプリミティブを使用します。通常、AESは、暗号化ソリューションを実装するときに選択される標準として機能します。..。米国で分類された情報を暗号化するために使用するのに十分な安全性があります。プロトコルに対する既知の動作中の攻撃はありません。 AES-192およびAES-256は通常、ほとんどの実用的なタスクに対して非常に信頼性があります。



Uberに来たとき、モバイル暗号化システムとWebアプリケーションの暗号化システムはすでに実装されていて、上記のメカニズムに基づいていたので、AES（Advanced Encryption Standard）、HMAC（Hashed Message Authentication Codes）の詳細を調べる言い訳がありました。 、RSAアルゴリズムなどについて。暗号化で使用される一連のアクションの暗号化強度がどのように証明されるかを理解することも興味深いものでした。たとえば、添付データを使用した認証済み暗号化について説明すると、encrypt-and-MAC、MAC-then-encrypt、encrypt-then-MACモードを分析すると、そのうちの1つだけの暗号化強度を証明できますが、これはその意味ではありません。残りは暗号的に安全ではありません。



完全に新しい暗号化フレームワークを実装しない限り、暗号化プリミティブを自分で実装する必要はほとんどありません。ただし、使用するプリミティブとそれらを組み合わせる方法を決定する必要がある場合があります。特定のシステムがデータ暗号化に特定のアプローチを使用する理由を理解するために、暗号化アルゴリズムの分野の知識が必要になる場合もあります。

決定ツリー：Uber

プロジェクトの1つに取り組んでいる間、モバイルアプリケーションに複雑なビジネスロジックを実装する必要がありました。つまり、半ダースのルールに基づいて、いくつかの画面の1つを表示する必要がありました。テストシーケンスの結果とユーザーの好みを考慮に入れる必要があるため、これらのルールは非常に複雑でした。



この問題の解決を始めたプログラマーは、最初にこれらすべてのルールをif-elseステートメントの形式で表現しようとしました。その結果、コードが非常に混乱しました。その結果、決定ツリーを使用することが決定されました。彼の助けを借りて、必要なすべてのチェックを簡単に実行できました。実装は比較的簡単でした。また、必要に応じて問題なく交換できます。条件チェックがそのエッジで実行されるように、決定ツリーの独自の実装を作成する必要がありました。このツリーに必要なのはこれだけです。別のアプローチをとることでツリーの実装に費やす時間を節約できたかもしれませんが、チームは特定のツリーを維持する方が簡単であると判断し、作業に取り掛かりました。このツリーは次のようになります。エッジは条件をチェックした結果を表し（これらはバイナリ結果、または値の範囲で表された結果です）、ツリーのリーフノードはナビゲートする必要のある画面を示します。





, , .



SubmitQueueと呼ばれるUberのモバイルアプリのビルドシステムも決定ツリーを使用しましたが、動的に生成されました。開発者エクスペリエンスチームは、数百のソースブランチとターゲットブランチを毎日マージするという難しい問題に取り組む必要がありました。同時に、各アセンブリの完了には約30分かかりました。これには、コンパイル、ユニットテストと統合テストの実行、およびインターフェイステストが含まれます。アセンブリの並列化は十分な解決策ではありませんでした。異なるアセンブリで変更が重複することが多く、マージの競合が発生したためです。実際には、これは、プログラマーが2〜3時間待って、リベースし、マージプロセスを再開しなければならない場合があることを意味し、今回は競合に直面しないことを期待していました。



Developer Experienceチームは革新的なアプローチを採用して、マージの競合を予測し、それに応じてアセンブリをキューに入れました。これは、特別なバイナリ決定ツリー（推測ツリー）を使用して行われました。





SubmitQueueは、予測された確率で注釈が付けられたエッジを持つバイナリ決定ツリーを使用します。このアプローチにより、並列で実行できるアセンブリのセットを決定できます。これは、タスクの受信と実行の間の時間を短縮し、システムのスループットを向上させるために行われます。この場合、完全にテストされ実行可能なコードのみがマスターブランチに入る必要があります。



このシステムを作成した開発者エクスペリエンスチームは、それに関する優れた資料を作成しました。しかし、ここに-同じトピックに関する別の記事。このシステムの実装の結果、以前よりもはるかに高速なプロジェクトアセンブリシステムが作成されました。これにより、プロジェクトのビルド時間を最適化し、何百人ものモバイルプログラマーの生活を楽にすることができました。

六角形のグリッド、階層インデックス：Uber

これが私がここで話したい最後のプロジェクトです。それは完全に1つの特定のデータ構造に基づいていました。それをすることで、このデータ構造について学びました。階層インデックスを持つ六角形のグリッドについて話しています。



Uberで最も困難で興味深い問題の1つは、旅費の最適化とパートナー間の注文の分配でした。旅行の料金は動的に変化する可能性があり、ドライバーは常に移動しています。 UberのエンジニアがH3グリッドシステムを作成しました。さまざまな規模の都市全体のデータを視覚化および分析するように設計されています。上記の問題を解決するために使用されるデータ構造は、階層インデックスを持つ六角形のグリッドです。データを視覚化するために、いくつかの専用の内部ツールが使用されます。





マップを六角形のセルに分割する 



このデータ構造には、独自のインデックスシステム、トラバーサル、グリッドの個々の領域の独自の定義、独自の機能があります。これらすべての詳細な説明は、対応するAPIのドキュメントに記載されています。 H3の詳細についてはこちらをご覧ください。これがソースコードです。ここでは、このシステムが作成された方法と理由についてのストーリーを見つけることができます。



このシステムの経験から、非常に具体的な問題を解決するときに、独自の特殊なデータ構造を作成することが理にかなっているという事実を感じることができました。異なるレベルの各結果データフラグメントとの比較でマップフラグメントへの分割を考慮しない場合、六角形グリッドを適用できるソリューションの問題はほとんどありません。ただし、他の場合と同様に、他のデータ構造に精通している場合は、これをはるかに理解しやすくなります。また、六角形のグリッドを扱ったことがある人にとっては、そのようなグリッドを使用して解決される問題と同様の問題を解決するように設計された新しいデータ構造を作成する方が簡単です。

インタビューにおけるデータ構造とアルゴリズム

上記では、さまざまな企業で長い間働いていたときに遭遇したデータ構造とアルゴリズムについて説明しました。記事の冒頭で述べたMaxHowellによるツイートに戻ることを提案します。そこでマックスは、Googleのインタビューで、ボード上のバイナリツリーを反転するように求められたと不満を漏らしました。彼はしませんでした。彼はドアを見せられた。この状況では、私はマックスの側にいます。



人気のあるアルゴリズムがどのように機能するか、またはエキゾチックなデータ構造がどのように機能するかを知ることは、ハイテク企業で働くために必要な種類の知識ではないと思います。アルゴリズムが何であるかを知る必要があります。たとえば、「貪欲」の原則に取り組むなど、単純なアルゴリズムを独自に考え出すことができる必要があります。また、ハッシュテーブル、キュー、スタックなどの最も一般的なデータ構造についての知識も必要です。しかし、DijkstraのアルゴリズムやA *のような非常に具体的なもの、またはさらに複雑なものは、暗記する必要のあるものではありません。これらのアルゴリズムが本当に必要な場合は、それらの参考資料を簡単に見つけることができます。たとえば、ソートアルゴリズムとは関係のないアルゴリズムについて話す場合、私は通常、それらを一般的な用語で理解し、その本質を理解しようとしました。同じことが、赤黒の木やAVLの木のようなエキゾチックなデータ構造にも当てはまります。私はそれらを使用する必要はありませんでした。そして、必要に応じて、適切な出版物に頼ることで、いつでもそれらについての知識を更新することができました。私が言ったように、インタビューするとき、私はそのような質問をすることは決してなく、彼らに尋ねるつもりもありません。



私はプログラミングに関連する実際的な問題に賛成です。解決には、アルゴリズムの「ブルートフォース」や「貪欲」なバリエーションの方法から、より高度なアルゴリズムのアイデアまで、さまざまなアプローチを適用できます。たとえば、このようなテキストの配置タスクを実行してもまったく問題ないと思います。たとえば、Windows Phoneでテキストをレンダリングするためのコンポーネントを作成するときに、この問題を解決する必要がありました。この問題は、トリッキーなデータ構造に頼ることなく、配列といくつかのif-elseステートメントを使用するだけで解決できます。



実際、多くのチームや企業は、アルゴリズムの問​​題の重要性を誇張しています。アルゴリズムの質問の魅力を理解しています。短時間で応募者を評価でき、やり直しも簡単です。つまり、誰かに聞いた質問が公開されても、特別な問題は発生しません。アルゴリズムの質問は、多数の申請者の試験を整理するのに適しています。たとえば、100を超える質問のプールを作成し、それらを応募者にランダムに配布できます。動的プログラミングとエキゾチックなデータ構造に関する質問はますます一般的になっています。特にシリコンバレーで。これらの質問は、企業が強力なプログラマーを雇うのに役立ちます。しかし、これらの同じ質問は、ビジネスで成功した人々への会社の道を閉じることができます、アルゴリズムの深い知識が必要ない場合。



生まれてから複雑なアルゴリズムに精通している人だけを雇っている会社の場合は、これらが必要な人かどうかを慎重に検討することをお勧めします。たとえば、Skyscanner（ロンドン）とUber（アムステルダム）で、トリッキーなアルゴリズムの質問をせずに素晴らしいチームを雇いました。私は自分自身を最も一般的なデータ構造に限定し、問題解決に関連するインタビュー対象者の能力をテストしました。つまり、彼らは一般的なデータ構造について知り、直面している問題を解決するための簡単なアルゴリズムを考え出すことができる必要がありました。データ構造とアルゴリズムは単なるツールです。

結論：データ構造とアルゴリズムはツールです

ダイナミックで革新的なテクノロジー企業で働いている場合、おそらくこの企業の製品のコードにさまざまなデータ構造とアルゴリズムの実装に遭遇するでしょう。まったく新しいものを開発している場合は、直面している問題の解決を容易にするデータ構造を探す必要があります。このような状況では、正しい選択を行うために、アルゴリズムとデータ構造、およびそれらの長所と短所に関する一般的な知識が必要です。



データ構造とアルゴリズムは、プログラムを作成するときに自信を持って使用する必要があるツールです。これらのツールを知っていると、それらを使用するコードベースですでに知っていることがたくさんわかります。さらに、そのような知識により、複雑な問題をより自信を持って解決することができます。アルゴリズムの理論上の制限と、それらを最適化する方法を理解できます。これは、必要なすべてのトレードオフを使用して、可能な限り優れていることが判明するソリューションに最終的に到達するのに役立ちます。



データ構造とアルゴリズムをよりよく理解したい場合は、次のヒントとリソースをご覧ください。

• -, , , , , , . , , . , . — , .
• « ». , , , . — , , . , , , .
• さらにいくつかの本があります：「アルゴリズム。開発ガイド「および「Javaのアルゴリズム、第4版」。それらを使用して、大学のアルゴリズムに関する知識を更新しました。確かに、私はそれらを最後まで読んでいません。それらは私にはかなり乾燥していて、私の日常の仕事には適用できないように見えました。

実際にどのようなデータ構造とアルゴリズムに遭遇しましたか？