先日 Gotanda.hs #1 @HERP というイベントがあって、そこでRecursion Schemesで考える並べ替えアルゴリズムというタイトルでA Duality of Sortsという論文の話をLTしたんですが、この記事ではそこで話せなかった論文の後半で解説されている挿入ソートと選択ソートの双対性について書いていきたいと思っています。 ソートアルゴリズムの復習 まずは主役の二人である挿入ソートと選択ソートについて見ていきましょう。 挿入ソートは与えられたリストの先頭から要素を取り出し、これまでに構築したソート済みのリストに挿入していくという処理を繰り返すことでソートを実現するアルゴリズムです。 出典: [Insertion sort - Wikipedia](https://en.wikipedia.org/wiki/Insertion_sort) これをHaskellで実装す
はじめに ネタで「洗脳ソート」を公開したら、思った以上に拡散してしまったので、マジメな方も書かないとまずい、と思い急遽バケットソートのHaskellでの実装を説明する。 いくつかの拡張機能を使うが、それらの説明は後回しにする。雰囲気だけでもお伝えできればと。 バケットソートとは なぜO(n)でソートできるのか ソートは最小でもO(n log(n))時間かかることが証明されている。なのになぜ、O(n)時間でソートができるのか。「粛正ソート」や「洗脳ソート」では、「ソートの結果」における条件をそれぞれつぎのようにゆるくしたことでO(n)時間でのソートが可能になった。 昇順(または降順)にデータが並んでいる ソート前に含まれていた以外のデータが含まれていない (粛正ソートではここまで) ソート前後で値の数が変化しない(洗脳ソートではここまで) これをおそらく「ソート」とは呼べない。だからこそ「ネ
しかし、criterionのエンジンは、計測コードを複数回実行し平均を取る仕組みになっています。そのため、二回目以降はソート済みの配列に対して時間計測を行ってしまっていました。 今回の配列ソートではピボットを中央から取っているため、ソート済みの配列に対しては最大効率になります。つまり前回記事の計測スコアでは、Vector関係は実際より良い数値が出てしまっている事になります。 という訳で、毎回のテストごとに初期化処理を入れるように修正します。 これを行うのは、以下の関数になります。 型を見ればおおよそ使い方が想像できると思いますが、第一引数のIOアクションにより、env型の値を計測外で作成し、それを引数として計測を実施します。 envはNFDataのインスタンスである必要があります。NFDataはseqによく似た、値の簡約を促す関数rnfを公開するクラスです。seqではリスト等の構造に対して
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
