基数ソートがハッシュテーブルを凌駕：一意な値を数えるためのパフォーマンス比較

主に一意なuint64値からなる巨大な配列において一意な値を数えるという問題に対し、適切に調整された基数ソートは、通常、ハッシュテーブルよりも高速です。メモリ帯域幅を効率的に利用し、ハッシュ処理とソートプロセスを巧みに融合することで、基数ソートは1MBを超えるデータに対して、調整済みハッシュテーブルと比べて最大1.5倍の高速化を実現し、Rustの優れた「Swiss Table」ハッシュテーブルと比べて最大4倍高速になります。しかし、基数ソートのパフォーマンスはデータ分布が不均一な場合に低下するため、可逆的なハッシュ関数を使用してデータを前処理することで効率を維持できます。この記事では、様々なデータサイズとアクセス頻度における両手法のパフォーマンスをベンチマークし、現実世界のアプリケーションにおける選択戦略について考察します。