Webアプリケーションにおけるパスルーティングアルゴリズムの解剖

Webアプリケーション開発の開発においては、@app.get("/users/{user_id}")のような一文で処理とパスのマッピングを記述しますよね。しかし、その一行の裏側で、フレームワークがどのようにして正しい処理を呼び出しているか、仕組みを考えたことはありますか？

本トークは、普段当たり前の機能として使いがちなパスルーティングの裏側に目を向けます。Python製WebフレームワークであるDjangoとFastAPI, Litestarを例にとり、そのルーティング機能がどのようなアルゴリズム（単純な正規表現、効率的なTrie木など）によって実現され、どのように実装されているかを、図やコードを交えて解説します。さらに実験を通じて、登録するルートの量や深さに応じて、アルゴリズムごとに実行時間がどのように変わるかを比較します。

このトークを通じて、競技プログラミングで学ぶようなアルゴリズムが、実世界のアプリケーション開発という身近な場所で活きている、その面白さを共有します。Webアプリを構成する重要なパーツであるルーティングへの理解を深め、当たり前に使っている機能がどのように実現しているかを探求する楽しさへと繋がることを目指します。

以下のアウトラインを想定しています。

1. はじめに (3分)

• 自己紹介とこのトークのゴール
• 対象聴衆（Web開発の次の一歩を踏み出したいBeginnerの方へ）

1. 身近なフレームワークにおけるルーティング (5分)

• Django: path() と URLResolver
• FastAPI: Starletteにおけるルーティング実装
• Litestar: traverse_route_map

1. ルーティングアルゴリズムの世界へダイブ (15分)

• アプローチ1：正規表現
  • 正規表現エンジン
  • バックトラッキング
  • Pythonでの正規表現エンジンの実装
• アプローチ2：Trie木
  • Trie木と基数木
  • パスを効率的に探索する仕組みのStep by Stepでの解説
• 計算量の比較

1. 比較実験：速さと柔軟性のトレードオフ (6分)

• 実験概要：URLの数やパスの深さがマッチング速度に与える影響
• 実験結果見る各アプローチの特性
• 考察：パフォーマンスとパスパラメータ対応などの機能（柔軟性）のバランス

1. まとめ (1分)

私が主にWebアプリケーション開発を仕事にしており、当たり前に使っている機能の裏側を知ることに面白さと意義があると考えているから。

• DjangoやFastAPIが、内部でどのようにURLリクエストを解決しているかの基本的な仕組み。
• Trie木/基数木などのアルゴリズムの概念と、そのメリット・デメリット。
• 競技プログラミングなどで学ぶアルゴリズムによって、実用的なソフトウェア開発の実行速度が変わる実例
• 普段当たり前に使っているライブラリやフレームワークの裏側を探求する楽しさ

特になし