370,103語でのソート、ハッシュ、およびスケッチ
Sorting, hashing, and sketches on 370,103 words (stochastic.blog)
要約
この記事では、370,103の英単語のデータセットに対し、ソート、ハッシュ、および確率的スケッチアルゴリズムを適用した結果を報告しています。各アプローチの時間とメモリのコストを追跡し、特にHyperLogLogがわずか2.71%のエラーで語彙サイズを推定できることを示しています。現代のシステムを高速に保つアルゴリズムのフィールドガイドとして、これらのメカニズムをゼロから構築し、実データで測定します。
全文翻訳
370,103語におけるソート、ハッシュ、およびスケッチ
[画像: Sorting, hashing, and sketches on 370,103 words の特徴的な図]
ポスト2では、Pythonのリスト、辞書、セット、再帰を用いて基礎を築き、言語のコアコンテナが負荷の下でどのように振る舞うかを学びました。今回は、これらのツールを実際のデータセット、すなわちdwyl/english-wordsリポジトリから抽出した370,103個の英単語(1行に1単語)で試します。この記事の終わりまでに、それらを6通りの方法でソートし、4つの異なる構造にハッシュし、4つの確率的アルゴリズムでスケッチし、各アプローチのコスト(時間とメモリ)を追跡します。特筆すべきは、HyperLogLogがわずか4,096レジスタで語彙サイズを2.71%のエラー率で推定できることです。
この記事を、現代のシステムを高速に保つアルゴリズムの実用的なガイドと考えてください。検索ボックスにクエリを入力するたびに、その背後ではソート、ハッシュ、スケッチが行われています。これらのメカニズムをすべてゼロから構築し、実際の単語で測定し、どのアルゴリズムがその複雑さに見合う価値があるかを見ていきます。
データセット
単語リストは、1列の小文字文字列として提供され、メモリ上でおよそ21.63 MBです。生ファイルには重複や欠損値が含まれていますが、クリーニング後には370,103個の一意な単語が残ります。生ファイルには2つの欠損値が見つかりましたが、これらは削除・クリーニングされました。語彙は370,103個の一意な単語で構成され、重複行はありません。単語の長さは右に偏っており、15文字を超える長いテールを持ち、20%のホールドアウトでのアウトオブボキャブラリー(OOV)率は1.0に達します。これは、テスト分割内のすべての単語が未知であることを意味します。最後の数値は重要です。これは、メンバーシップ構造が未知のクエリにしか直面しないことを示しています。
図1は、クリーニングされた語彙の単語長分布を示しています。
[画像: 単語長の度数曲線]
図1: 単語長は3文字から10文字の間に集中し、対数スケールでは長いテールにかけて着実に減少します。
この形状が、後の選択を左右します。長いテールはトライ(Trie)のパスが深くなることを意味し、高いOOV率はハッシュテーブルが継続的なミスに直面することを意味します。
複雑性
何かをソートする前に、コストについて話すための言語が必要です。ビッグオー記法は成長の上限を与え、ビッグシータ記法は正確な漸近クラスを特定し、償却解析は単一の呼び出しではなく、一連の操作にわたるコストを測定します。記事の残りの部分で使用される操作について、これら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回のappendは合計で0.0071秒で完了し、操作あたり約4e-08秒です。これは償却O(1)です。リストの先頭への挿入(insert at position zero)は注意すべき例です。appendの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)