フラッシュソート

http://www.neubert.net/FSOIntro.html
オーダーNのソーティングアルゴリズム。抽象的な理論ばっか勉強してたので、リハビリ代わりにSchemeで書いてみようと思ったけど、原理がよく分からない･･･。論文(?)読みづらいし。

まず、全体を大雑把な大きさ(=key value)でグループに分けてグループをソートして(partial-sort)、更に、そうやって、分けた各グループを再帰的にソートして(要素数が十分小さいときは、挿入ソートを使うのは定石通り)、最後にくっつけるという感じなのかな、多分。発想的には、基数ソート(だっけ?)に近いものがある。イントロで、"sorting algorithms based on the classification of elements"とか書いてるのは、このへんのことなんでしょう。きちんと理解しないまま、とりあえず、無理やり書いてみる



(define (fsort L)

  (letrec

   ((partial-sort

     (lambda (L m)

       (let ((vmin (eval (cons 'min L) (interaction-environment)))

	     (vmax (eval (cons 'max L) (interaction-environment))))

        (if (= vmax vmin) #f

	  (let loop ((rest L) (v (make-vector m '())) (c (/ (- m 1) (- vmax vmin))))

	    (if (null? rest) v

	      (let ((k (x->integer (* c (- (car rest) vmin)))))

	        (begin

		  (vector-set! v k (cons (car rest) (vector-ref v k)))

		  (loop (cdr rest) v c))))))))))

   (cond

    ( (< (length L) 50) (sort L) )

    ( (partial-sort L 50) => (lambda (x) (apply append (map fsort (vector->list x)))) )

    ( else L ))))
(eval (cons 'min L) (interaction-environment))とかやってるのは、(apply min L)だと、大きいリストを与えると、Gaucheに、要素数が大きすぎるって怒られるので。あと、roundもfloorもtruncateも返すのは、整数値じゃなく、あくまで実数値なので、vector-refの引数に使えなくて困ったり、vector-set!とか使ってるし、ださいとか。一応、これで正しく動く模様

一応ベンチマークを取ってみた



(use math.mt-random)

(use gauche.time)
(define (qsort L) ;比較用のクイックソート

 (letrec

  ((separate

    (lambda (v L L1 L2)

      (cond

       ( (null? L) (append (qsort L1) (cons v (qsort L2))) )

       ( (< v (car L)) (separate v (cdr L) L1 (cons (car L) L2)) )

       ( else (separate v (cdr L) (cons (car L) L1) L2) )))))

  (if (< (length L) 50) (sort L) (separate (car L) (cdr L) '() '()))))
(define (gen-random-list len range)

 (let ((m (make  :seed (sys-time))))

   (let loop ( (ret '()) (i len) )

     (if (= i 0) ret

       (loop (cons (mt-random-integer m range) ret) (- i 1))))))
(define test-list (gen-random-list 10000 1000))
(time (list? (fsort test-list)))

(time (list? (qsort test-list)))

(time (list? (sort test-list)))
list?とかやってるのは、ソート結果がずらずら表示されるのを抑止するためで、もっとましなやり方はいくらでもあるでしょう。結果。


;(time (list? (fsort test-list)))

; real   0.094

; user   0.094

; sys    0.000

#t

;(time (list? (qsort test-list)))

; real   0.063

; user   0.063

; sys    0.000

#t

;(time (list? (sort test-list)))

; real   0.000

; user   0.000

; sys    0.000

#t
組み込みのsort>>(超えられない壁)>>qsort>fsort
という結果に。あと、でかいリストをfsortに与えると、何故かGaucheが落ちる。


"vm.c", line 716: Assertion failed: SCM_IDENTIFIERP(val0)

VM 0x101dce58 -----------------------------------------------------------

   pc: Segmentation fault (core dumped)
みたいなエラーメッセージが。とりあえず、vm.cの該当部分見ても、パッと見ではよく分かんないので、まあいいや

半環論

A Completeness Theorem for Kleene Algebras and the Algebra of Regular Events
を読んだ。

omega-完備な(大まかにいうと、可算無限和が定義できるような)べき等半環をclosed semiring(CSR)と呼ぶ。CSRには、標準的な仕方でKleene閉包が定義できて(xのKleene閉包をe+x+x*x+x*x*x+etc..で定義する)、いつでもKleene代数になる。SをCSRとすると、S係数の行列半環Mat(n,S)もCSRになって、普通にKleene閉包が定義できる。同様に、Kleene代数Kに対しても、Mat(n,K)にKleene代数の構造を入れることができる

#CSRでないKleene代数は、いくらでも存在するが、Kozenの論文"On Kleene algebras and closed semirings"のセクション4で、*-continuous Kleene代数の自然な完備化によって、CSRが得られることが示されている。同じ論文内で、*-continuousでないKleene代数も構成されているけど、*-continuousでないKleene代数が、単なる例のための例以上のものであるのかどうかは、よく分からない

http://d.hatena.ne.jp/m-a-o/20060906#p2
あたりを見れば、有限オートマトンの計算が、Kleene代数上の行列計算になっていることは明らかだけど、推移閉包の計算(知らないけど)や、重み付きグラフの最短経路を求めるダイクストラのアルゴリズムなんかも、半環係数の行列計算と解釈できるという話が、最初のほうにさらっと書いてあるけど、この話は本題より面白かった。言われて見れば、あの手の形の計算は結構色んな所で出会ってるじゃないかな、という気もする。何にしろ、何の役に立つかはっきりしてる話は精神衛生上いい

主定理の証明は、殆ど、状態数最小の決定性有限オートマトンの構成を、Kleene代数上の行列計算の話に翻訳してるだけで、自然なものになっている


半環論の軽い歴史と現状については、
http://moonstone.math.ncku.edu.tw/AlgebraConference/golantalk.pdf
がよくまとまっていると思った。といっても、自身最近まで、半環なんて名前すら聞いたことなかったけど、オートマトン、最短経路問題だけでなく、Hoare論理の「代数化」として半環を使うとか、巡回セールスマン問題が半環係数の多項式の計算に過ぎないという話等、応用範囲はかなり広いらしい

現時点で、半環の例として知ってるのは、有限オートマトンに関係する(非可換)多項式半環と、あとは、max-plus代数、min-plus代数(トロピカル代数)、それに、半環係数の行列半環。勿論、全ての環は半環だし、自然数の集合も半環になる。

他に、可換ではあるけれども、非自明な半環を系統的に構成する手法としては、適当な代数系の表現論を使う方法がある。例えば、有限群の有限次元表現の同型類には、直和表現とテンソル積表現によって、和と積が入る。この"表現半環"Rには、表現の次元を対応させる写像dim:R->Natによって、自然数半環Natへの準同型が定まるという性質がある。更に、この表現半環は、元の有限群の構造を(原理的には)殆ど決めてしまう。通常は、Grothendieck構成によって、表現環を考えるけれど、表現半環を考える方が自然なのかもしれない。同様の構成は、リー群の有限次元表現の全体や、多様体上の有限次元ベクトル束の全体についても、行うことができる。2つの位相空間がホモトピー同値ならば、それそれの空間上のベクトル束の同型類は一対一に対応する