Build@Mercari第2〜4週目のテーマ「データ構造／アルゴリズム」を深堀り！#BuildAtMercari

みなさんこんにちは！メルカリBackend Engineering TeamのMark (@TangoEnSkai)です。

現在、Build@Mercariの参加者とBuildチームは、毎週水曜日の夜に研修を実施しています。今日は、Build@Mercariの第2〜4週目で実施した内容をご紹介します。　第一回目のレポートはこちら！

実施した内容はこちら
・ 第2週目データ構造 I
・ 第3週目：データ構造 II
・ 第4週目：アルゴリズム

第2週目：データ構造 I

6月3日、BackendチームのエンジニアであるHunterを講師に迎え、データ構造に関する講義を実施しました。講義のおもな内容はこちら：

本プログラムの目的の一つは、コンピュータサイエンス（CS）のバックグラウンドを持たない参加者に、重要なトピックを学ぶ機会を与えること。プログラミングへの理解を深めてもらうため、コンピューティングに関する基礎的な内容を説明しました。

本プログラムの目的の一つは、コンピュータサイエンス（CS）のバックグラウンドを持たない参加者に、重要なトピックを学ぶ機会を与えること。プログラミングへの理解を深めてもらうため、コンピューティングに関する基礎的な内容を説明しました。

低レベルメモリの表現は、CSを専攻する大学1〜2年生にとっても難しい内容ですが、Hunterのわかりやすい説明で参加者全員、概念を理解することができたと思います。今回学んだ理論や概念を、将来アプリ開発に取り組む際に役立ててほしいです！

連結リストについて説明した後、スタックについて紹介。ここでは、2つの異なるスタックの実装方法も解説しました！

ハンズオン形式で学ぶスタック実装

スタック実装の基本的な考え方だけでなく、アプリケーションレベルでどのように機能するかについても説明しました。以下が、スタックの概念を利用した関数呼び出しの例です。

キューの基本的な動作の概念、理論、そして実装について説明しました。 さらに、2つの異なるキューの実装方法も紹介。 キューの使用例として、CPUスケジューリングについても軽く触れました。

具体的には、最短ジョブ優先（SJF）スケジューリング、オペレーティングシステムにおけるキューの使用、および与えられるプロセスの処理について解説しました。

Week 2の講義資料はこちら

第3週目：データ構造 II

第3週は、データ構造に関するより高度な内容の講義を実施しました。

講義の最後には、グループエクササイズを実施！

第3週は、Backendエンジニア（Notification Team）の@tarotaro0を講師に迎え、各データ構造の特性を理解し、設計についてディスカッションができるレベルを目標に掲げ、講義を行いました。

ハッシュテーブルの基本的な概念と、内部構造について説明しました。なかでも、ハッシュテーブルに関する重要なトピックにも触れました。

・ ハッシュ関数
・ 衝突
・ ハッシュテーブルの利点と検索例
・ 実例

ツリーの種類を紹介した後、メルカリのチーム構造と共に、以下のようなツリーの利点も解説。

・ 階層構造表現
・ 枝分かれ構造表現
・ ヒューマンフレンドリー：直感的に理解できる
・ データの整理・管理が楽

この構造はコンピューターシステムに頻繁に使われています。ディレクトリ（フォルダ）は、ツリー構造におけるデータの階層表現の一つとして考えることができます。

WEBページやドキュメントオブジェクトモデル（DOM）を別の例として挙げました。DOMは、後日Front-endの講義でカバーするトピックの一つなので、内容を覚えてくれていると嬉しいです！

また、メルカリアプリの実例とともにツリー構造についても説明しました。複数のカテゴリが存在し、それらは大、中、小の層に分かれています。これらのカテゴリ層は範囲の広さを表しており、カテゴリの大きさに合わせてカバーする範囲も広くなります。

例えば、メルカリアプリには「レディース」、「メンズ」という大きなカテゴリが存在します。それぞれに中カテゴリがあり、ツリー構造のカテゴライゼージョンが行われています。

データベースインデックスやBツリーの例を説明した後、最後のトピックである「グラフ」を紹介しました。

ハッシュテーブルやツリーの講義と同様に、グラフに関する以下の点も説明！

<h3定義

・ バリエーション／タイプ
・ 利点
・ 例

講義内容

・ 有向／無向グラフ
・ 重み付きグラフ

グラフには以下の利点があります。

・ ノード間の関係性の表現
・ データの関係性および表現
・ ツリー：親子階層
・ グラフ：より広い範囲の関係性を定義することが可能

例えば、メルカリのマイクロサービス移行、Facebookのフレンドコネクション、Google検索エンジンのPageRankアルゴリズム、地下鉄／メトロシステム等に、グラフデータ構造が使われています。

ハッシュテーブル、ツリー、グラフについての説明は以上です！

この週のセッションの最後には、グループワークとショートプレゼン！トピックは「Cウイルスの感染経路の特定」で、以下の条件で実施しました

条件

Cウイルスの感染者に接触すると、一定の確率で感染する

使用可能なリスト

・ 過去に感染していた人々のリストpreviously infected people
・ 感染者と接触した人々（複数回接触した人々を含む）のリスト

課題

・ 新たに感染した人物Xの感染経路を特定するためのシステムを検討
・ 感染の異なるパターンを想像
・ 必要に応じて条件の追加が可能

データ構造の知識を活用しながらシステム設計を考える能力は、優秀なソフトウェアエンジニアにとって欠かすことができない必須スキルの一つであり、ただ単に特定のプログラミング言語で実装の方法を学ぶことよりはるかに大切だと信じています。現場では実世界における事例について考える力が必ず要求されるため、今回実施したエクサイズが参加者の問題解決能力の向上に役立つと嬉しいです。

また、実際にプログラミングを経験してもらうため、宿題として英語辞典の実装を行ってもらいました。

Week 3の講義資料はこちら

第4週目：アルゴリズム

第4週目のトピックは、メルカリで使われているアルゴリズム。画像検索機能に関するユースケースの具体例について説明しました。下記が講義の目標です。

講義内容

以下、アルゴリズムと画像検索の例です。

画像検索とは、機械学習を活用した、ユーザーにより良い検索体験を提供するための機能の一つです。現在、メルカリアプリはiOS端末向けに「画像検索機能」を提供しており、ユーザーは、商品の名前がわからなくても、画像だけで欲しい商品を検索することができます。

講義の初めに、画像検索のデータ流れを示しました。ニューラルネットワークを用いて、ある特徴や性質をベクトルとして抽出し、そのベクトルを近傍検索インデックスに追加します。これは、最近傍検索のアルゴリズム技術の一つに密接に関わっているのです。

シンプルな例を用いてベクトルの計算も行いました。

N次元の概念についても説明！

その後、いくつかの質問について議論を行いました。その一つが、データベース内の検索クエリと、その計算複雑性（計算する際の時間や空間）です。

・　一連の特徴ベクトル間の距離
・　N次元の特徴ベクトルへの距離

しかし、実世界にはとても複雑なベクトル空間が存在します。検索エンジンのパフォーマンスを低下させることなく効率的に計算を行うには、さらなる技術が必要になるため、計算スピートを向上させるための方法についても説明しました。

Week 4の講義資料はこちら

Build@Mercariでは、今後数週間でFrontendとBackendの内容をカバーしていきます。メルカン記事も公開していく予定なので楽しみにしていください！

それでは、また#メルカリな日々で！