370,103語でのソート、ハッシュ、およびスケッチ

ポスト2では、Pythonのリスト、辞書、セット、再帰を用いて基礎を築き、負荷下での言語のコアコンテナの振る舞いを学びました。今回は、これらのツールを実際のデータセット、つまりdwyl/english-wordsリポジトリから抽出した1行に1単語ずつ記述された370,103の英単語で試します。この記事の終わりまでに、単語を6通りの方法でソートし、4つの異なる構造にハッシュし、4つの確率的アルゴリズムでスケッチし、それぞれの方法にかかる時間とメモリを追跡します。特筆すべきは、HyperLogLogがわずか4,096レジスタのみを使用して、2.71%のエラーで語彙サイズを推定できることです。 このポストは、現代のシステムを高速に保つアルゴリズムのフィールドガイドと考えてください。検索ボックスにクエリを入力するたびに、その裏側ではソート、ハッシュ、スケッチが行われています。これらのメカニズムをそれぞれゼロから構築し、実際の単語で測定し、どのアルゴリズムがその複雑さに見合う価値があるかを見ていきます。 データセット 単語リストは、メモリ上で約21.63MBの単一列の小文字文字列として提供されます。生ファイルには重複と欠損値が含まれており、クリーニング後のユニークな単語は370,103語です。生ファイルには2つの欠損値があり、それらを削除してクリーニングしました。語彙は370,103のユニークな単語に落ち着き、重複行はありません。単語の長さは右に偏っており、15文字を超える長いテールがあり、20%のホールドアウトでの未知語率（OOV rate）は1.0に達します。これは、テスト分割内のすべての単語が未知であることを意味します。最後の数値は重要です。これは、メンバーシップ構造が未知のクエリにのみ直面することを意味します。 図1は、クリーニングされた語彙の単語長分布を示しています。 図1: 単語長は3文字から10文字の間に集中し、長いテールでは対数スケールで着実に減少します。 この形状が、後の選択を左右します。長いテールはトライ（trie）のパスが深くなることを意味し、高いOOV率はハッシュテーブルが継続的なミスに直面することを意味します。 複雑性 何かをソートする前に、コストについて話すための言語が必要です。ビッグオー記法（Big-O notation）は成長の上限を示し、ビッグシータ記法（Big-Theta notation）は正確な漸近クラスを特定し、償却解析（amortized analysis）は単一の呼び出しではなく、一連の操作にわたるコストを測定します。ポストの残りの部分で使用される操作に対して、これら3つすべてを測定します。 50,000語での組み込みソートは0.0011秒、100,000語では0.0022秒、200,000語では0.0053秒かかります。入力が2倍になると時間は約2倍になり、これはn log nアルゴリズムの典型です。PythonのデフォルトであるTimsortは、ビッグシータ(n log n)に位置します。 リストへの追加（append）は異なる話です。200,000回の追加は合計0.0071秒で完了し、操作あたり約4e-08秒です。これは償却O(1)です。 リストの先頭への挿入（insert at position zero）は注意すべき例です。追加の40倍少ない5,000項目しか挿入しませんが、操作は0.0019秒かかり、操作あたり依然として3.8e-07秒と遅いです。その差は、漸近解析が定数が正直であれば実際の動作を予測するという教訓全体です。 ソート バイナリサーチはソートされた配列を必要とするため、そこから始めます。固定シードで5,000語をサンプリングし、ソートして、バイナリサーチがインデックス1234で既知の単語を見つけ、無意味な文字列に対して-1を返すことを確認します。次に、古典的なソートを自分で実装します。 def quicksort(arr): if len(arr) <= 1: return arr pivot = arr[len(arr) // 2] left = [x for x in arr if x < pivot] middle = [x for x in arr if x == pivot] right = [x for x in arr if x > pivot] return quicksort(left) + middle + quicksort(right) サブ問題、文字列、検索トリック ポスト6では、再帰と分割統治法を最初の原則から構築し、問題を独立した半分に分割して答えを組み合わせる方法を学びました。この記事では、これらのツールをより難しい問題クラスに向けます。サブ問題が重複する場合、文字列がきれいに分割されない場合などです。 一回の座学で学ぶ情報理論 ポスト3と4では、確率的基礎を構築し、ベイズの定理で信念を更新する方法を学びました。今回は、その仕組みを具体的な問題に適用します。テキストの断片に実際にどれだけの情報が含まれているか？この記事では、WikiText-2でその量を測定します。 落とし穴のない統計的検定 ポスト3では、成人人口統計データセットを分布、相関、外れ値のフェンスを通して探求し、モデル化する前にデータに語らせることを学びました。今回は、その探索的基盤を応用し、すべてのデータサイエンティストが最終的に直面する質問をします。私たちが目にするパターンは本物か、それとも… 国勢調査データにおける確率と推定 前回のポストでは、成人人口統計データセットをクリーンで分析準備完了の状態に整理しました。今回は、そのクリーンなデータを確率と推定のコアアイデア（ベイズの定理、実在の人口を記述する分布、信頼性を正当化する極限定理など）の実験室に変えます。