Haskellの配列でクイックソート - あどけない話
Haskell の クイックソート としては、以下のようなコードがよく例に出てきます。 quickSortList :: [a] -> [a] quickSortList [] = [] quickSortList (x:xs) = quickSortList lt ++ [x] ++ quickSortList gt where lt = filter (<x) xs gt = filter (>=x) xs これは、小さなリストを何度も連結するので、効率が悪そうです。 そこで、一旦配列に直し、固定領域を使ってソートして、またリストに戻す方がいいのではないかと思い、実装して速度を比べてみました。配列を使うクイックソートのコードは、「珠玉のプログラミング」から拝借しました。ベンチマークも含むコードは、gist に上げています。 結果はこんな感じ(単位はms)： 入力のサイズ 10^4 10
なんでソコに、足し算、掛け算、累乗の記号を使うのですか？ - 檜山正幸のキマイラ飼育記 (はてなBlog)
えっ、それが疑問だったの？ あ、そう。んじゃ、ちょっと説明しましょう。 A、Bが集合だとして、 AとBの直和は、A＋B AとBの直積は、A×B AとBの指数は、BA と書きます。算数の足し算、掛け算、累乗の記号を使うのはなぜ？ いやっ、そもそも、直和＜ちょくわ＞、直積＜ちょくせき＞、指数＜しすう＞ってなに？ と、そんな疑問を持つ人のために。 記号の約束 集合とはいっても、ここでは有限集合だけを例に使うことにします。そして、[0] = {}, [1] = {1}, [2] = {1, 2}, [3] = {1, 2, 3} などと約束します。つまり、[n]と書いてあったらそれは「1からnまでの整数の集まり」です。こういった[n]は有限集合の典型例といえるでしょう。 有限集合Aに対して、#(A) は、Aの要素の個数だとします。例えば、#({a, b}) = 2 です。シャープ記号はナンバー記号
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
