概要 特定のデータが、ある集合やリストに含まれるかどうかを判定するために線形探索や二分探索などいくつかのサーチアルゴリズムが使われますが、 本稿ではメモリの使用効率、探索の際の計算量が優れているブルームフィルタを用いたアルゴリズムについてま…

今回、多くの要素を持ち、必ずしもソートされていないコレクションに対して特定の値を探す際に効果的なHash-Basedサーチアルゴリズムについてまとめます。 日本語ではハッシュ法による探索アルゴリズムと呼ばれることもあります。 Hash-Basedサーチアルゴリ…

シェルソートは前回紹介した挿入ソートの改良版アルゴリズムです。 挿入ソートは一般的に、配列がほとんどソートされた状態で効率的に機能するもので、それ以外の場合では大きくパフォーマンスが落ちるのですが シェルソートではその欠点を補う仕組みになっ…

先月、Javascript advent calendarで、v8の配列ソートアルゴリズムにおいて、 配列の要素数に応じて挿入ソートとクイックソートを使い分けているという記事を書きました。 v8における配列ソートについて - kakts-log 今回は、挿入ソートについてまとめてみた…