プログラムとか日本語とか

ScapegoatTree.vbs 以前実装したスケープゴートツリーを高速化しましょう、はいそうしましょうということでやってみた。スタッククラスを使わずに再帰を行うようにした。それからノードにノードの数を保持するようにした。スケープゴートツリーは平衡を保つための情報は必要なときに算出することができるから、保持する必要がなくメモリー効率が素敵だよーという考えもあるにはあるのだけれども、処理速度があまりに遅いのでノードにノードの数を保持することにした。そういうことにした。CPUに優しいスケープゴートツリーにした。

結果がこれです。はいじゃん。シーケンシャルなデータではAVLTreeのほうが速い、ランダムなデータではスケープゴートツリーのほうが速い。

シーケンシャルなデータ。

	処理時間
要素数	ScapegoatTree	AVLTree
1	0.000	0.000
2	0.000	0.000
4	0.000	0.002
8	0.000	0.002
16	0.002	0.004
32	0.008	0.008
64	0.020	0.018
128	0.045	0.041
256	0.115	0.096
512	0.242	0.209
1024	0.561	0.436
2048	1.234	0.949
4096	2.660	1.938

ランダムなデータ。

	処理時間
要素数	ScapegoatTree	AVLTree
1	0.006	0.006
2	0.002	0.004
4	0.002	0.002
8	0.004	0.004
16	0.004	0.004
32	0.006	0.010
64	0.014	0.020
128	0.027	0.047
256	0.074	0.107
512	0.172	0.225
1024	0.348	0.492
2048	0.785	1.078
4096	1.697	2.365

ScapegoatTree.vbs
前回の方針にもとづいてスケープゴートツリーを実装してみた。
値を追加するところだけ抜粋。スタッククラスを作成してそのオブジェクトを使っている。

Public Sub Add(ByVal key, ByVal value)
	Count = Count + 1
	If (PrevCount < Count) Then
		PrevCount = Count
	End If
	Dim node
	Set node = New ScapegoatNode
	node.Key = key
	node.Value = value
	
	If (RootNode Is Nothing) Then
		Set RootNode = node
	Else
		Dim s
		Set s = New Stack
		Dim n
		Set n = RootNode
		Do
			Call s.Push(n)
			If (key < n.Key) Then
				If (n.LeftNode Is Nothing) Then
					Set n.LeftNode = node
					Exit Do
				Else
					Set n = n.LeftNode
				End If
			Else
				If (n.RightNode Is Nothing) Then
					Set n.RightNode = node
					Exit Do
				Else
					Set n = n.RightNode
				End If
			End If
		Loop
		Call Balance(s)
	End If
End Sub

以前実装したAVLTreeと処理速度を比較した結果がこれです。はいじゃん。

要素数	時間
	ScapegoatTree	AVLTree
1	0.000	0.000
2	0.000	0.000
4	0.000	0.001
8	0.001	0.001
16	0.004	0.002
32	0.011	0.008
64	0.029	0.012
128	0.101	0.025
256	0.316	0.057
512	1.084	0.137
1024	3.974	0.271
2048	14.614	0.597
4096	54.950	1.255

なるほどー、遅い、遅いと思います。誰かスケープゴートツリーを速くしてくださらないかしら（ちら。というわけでスケープゴートツリーの高速化を目論んでみましょうかしら。スタックオブジェクトを使用せずに、再帰を行うようにしたら処理速度が変わるような気がするような、しないような。

むはははははは、おまえも！スケープゴートにしてやんよ！　というわけで、スケープゴートツリーという２分木を実装したくて、説明されているところを探しているのだけれども日本語のページが見つからないでござる。英語のWikipediaのページを見る限りではAVL Treeの平衡の条件をゆるくしたものということなのかしら。木の回転の仕方も違ってくるのかしら？　よくわからぬわ！　ということでもうすこし調べてみよう。

Scapegoat tree - Wikipedia, the free encyclopedia
http://en.wikipedia.org/wiki/Scapegoat_tree続きを読む

ソート・ルーチン (1)遅いソート・ルーチン
http://fussy.web.fc2.com/algo/sort1_slow_sort.htm

サイクルソートを説明している日本語のページが１つしか見つからなかったのだけれども、それが詳しく書いてあってありがたかった。というわけで、VBScriptで実装してみた。

Sub Cyclesort(ByRef a)
	Dim i, c, j, t
	i = 0
	Do
		c = i
		For j = i + 1 To UBound(a)
			If (a(i) >  a(j)) Then
				c = c + 1
			End If
		Next
		If (c = i) Then
			i = i + 1
			If (i >= UBound(a)) Then
				Exit Do
			End If
		Else
			Do While (a(i) = a(c))
				c = c + 1
			Loop
			t = a(c)
			a(c) = a(i)
			a(i) = t
		End If
	Loop
End Sub

ところで、リンク先のページでノームソートというのを初めて知ったのだけれども、いままでこれ挿入ソートだと思ってた。ノームソートを挿入ソートとして紹介しているページもたぶんあるはず。挿入ソートで交換を行うようにしたらノームソートになるのか。

Class LinkedNode
	Public Value
	Public NextNode
	
	Private Sub Class_Initialize()
		Set NextNode = Nothing
	End Sub
End Class

Class LinkedList
	Private Head
	Private Tail
	
	Private Sub Class_Initialize()
		Set Head = New LinkedNode
		Set Tail = Head
	End Sub
	
	Public Sub Strandsort()
		Dim x, y, xt, yt, r
		Set r = Nothing
		Set x = Head.NextNode
		Do
			Set xt = x
			Do
				If (xt.NextNode Is Nothing) Then
					Set Head.NextNode = Merge(x, r)
					Exit Sub
				End If
				If (xt.Value <= xt.NextNode.Value) Then
					Set xt = xt.NextNode
				Else
					Set y = xt.NextNode
					Set yt = y
					Do
						If (yt.NextNode Is Nothing) Then
							Set xt.NextNode = Nothing
							Set r = Merge(x, r)
							Exit Do
						End If
						If (xt.Value <= yt.NextNode.Value) Then
							Set xt.NextNode = yt.NextNode
							Set xt = yt.NextNode
							Set yt.NextNode = xt.NextNode
						Else
							Set yt = yt.NextNode
						End If
					Loop
					Exit Do
				End If
			Loop
			Set x = y
		Loop
	End Sub
	
	Private Function Merge(ByVal x, ByVal y)
		Dim z, zt
		If (y Is Nothing) Then
			Set Merge = x
			Exit Function
		End If
		If (x.Value <= y.Value) Then
			Set z = x
			Set x = x.NextNode
		Else
			Set z = y
			Set y = y.NextNode
		End If
		Set zt = z
		Do
			If (x Is Nothing) Then
				Set zt.NextNode = y
				Exit Do
			End If
			If (y Is Nothing) Then
				Set zt.NextNode = x
				Exit Do
			End If
			If (x.Value <= y.Value) Then
				Set zt.NextNode = x
				Set zt = x
				Set x = x.NextNode
			Else
				Set zt.NextNode = y
				Set zt = y
				Set y = y.NextNode
			End If
		Loop
		Set Merge = z
	End Function

	Public Sub Add(ByVal value)
		Dim node
		Set node = New LinkedNode
		node.Value = value
		Set Tail.NextNode = node
		Set Tail = node
	End Sub
		
	Private Sub Class_Terminate()
		Do While (Not (Head Is Nothing))
			Set Head = Head.NextNode
		Loop
	End Sub
End Class

変数xtのtはtailの略であり、xtはxのしっぽという意味である。変数の名前は短いほうがロジックがわかりやすい気がする。以前マージソートを実装したのだけれども、そのマージソートは変数名を省略せずに実装した。見返してみると、無駄に難しく見えるような気がする。

マージソート: プログラムとか日本語とか
http://moritora.seesaa.net/article/262220799.html

LinkedListのノードを操作するストランドソートを実装したわけなのだけれども、LinkedListをソートするうえでその効率はどんなものなのよと思って他のやりかたと比較してみた。

実装１.ノードを操作するストランドソート（掲載したもの）
実装２.ノードを操作するマージソート
実装３.ノードの値を配列に入れてその配列をマージソートしてノードに値を戻す

10000件のランダムなデータで確認したところ、
実装２が実装１より５倍ほど速かった。
実装３が実装２より１０倍ほど速かった。

LinkedListをソートするときには値を配列に入れてその配列をソートするやり方がいいようだ。なんだかすこしくやしい。

Strand sort - Wikipedia, the free encyclopedia
http://en.wikipedia.org/wiki/Strand_sort

Wikipediaにストランドソートの日本語のページがなかった。いやん。英語のページの表とかコードとかをみてストランドソートを実装してみた。ストランドソートのアルゴリズムは、入力配列から要素を抜き出すことによってソート済みのサブ配列を作成して、結果配列にマージしていく感じのものだろう、たぶん。

サブ配列の長さがいくつになるかわからないので動的配列クラスを作成した。

Class ArrayList
	Private Data()
	Private Length
	
	Public Function GetLength()
		GetLength = Length
	End Function
	
	Private Sub Class_Initialize()
		ReDim Preserve Data(3)
		Length = 0
	End Sub
	
	Public Function GetElement(ByVal index)
		GetElement = Data(index)
	End Function
	
	Public Sub Add(ByVal element)
		If (UBound(Data) < Length) Then
			ReDim Preserve Data(Length + Length - 1)
		End If
		Data(Length) = element
		Length = Length + 1
	End Sub
	
	Public Sub Clear()
		ReDim Data(3)
		Length = 0
	End Sub
	
	Public Function ToString()
		Dim a
		a = Data
		ReDim Preserve a(Length - 1)
		ToString = Join(a, ",")
	End Function
End Class

Sub Strandsort(ByRef src)
	Dim subList
	Set subList = New ArrayList
	Dim result()
	ReDim Preserve result(UBound(src))
	Dim resultLow
	resultLow = UBound(result) + 1
	Dim newLow
	Do While (0 <= UBound(src))
		Call subList.Add(src(0))
		Dim i, j, e
		j = 0
		e = src(0)
		For i = 1 To UBound(src)
			If (e <= src(i)) Then
				subList.Add(src(i))
				e = src(i)
			Else
				src(j) = src(i)
				j = j + 1
			End If
		Next
		ReDim Preserve src(j - 1)
		newLow = resultLow - subList.GetLength()
		Call StrandsortMerge(subList, result, resultLow, newLow)
		resultLow = newLow
		Call subList.Clear()
	Loop
	ReDim Preserve src(UBound(result))
	For i = 0 To UBound(src)
		src(i) = result(i)
	Next
End Sub

Sub StrandsortMerge(ByVal subList, ByRef result, ByVal resultLow, ByVal newLow)
	Dim s, r, n, sUpp, rUpp
	s = 0
	sUpp = subList.GetLength() - 1
	r = resultLow
	rUpp = UBound(result)
	n = newLow
	Do
		If (s > sUpp) Then
			Exit Sub
		ElseIf (r > rUpp) Then
			Do
				result(n) = subList.GetElement(s)
				n = n + 1
				s = s + 1
			Loop While (s <= sUpp)
			Exit Sub
		Else
			If (subList.GetElement(s) < result(r)) Then
				result(n) = subList.GetElement(s)
				n = n + 1
				s = s + 1
			Else
				result(n) = result(r)
				n = n + 1
				r = r + 1
			End If
		End If
	Loop
End Sub

ストランドソートの処理速度はバブルソートより速く、マージソートより遅かった。Wikipediaの英語のページをみると、ストランドソートはLinkedListをソートするときに使われるのさみたいなことが書かれているような気がする。LinkedListを使う実装を試みたのだけれども、意外と難しかった。もうすこし考えてみよう。できたら後日記事にしましょう。はいそうしましょうということで、また後日。

ReDimステートメントは配列のサイズを変えるときに使用されるものだ。Preserveを指定することで値を保持することができる。Preserveを指定すると値がコピーされるぶん実行速度が遅くなるんでしょふふん、みたいに思っていたのだけれども、確認してみたらぜんぜん違っていた。

Sub Main()
	Dim a(), b(), i, t
	t = Timer()
	For i = 0 To 100000
		ReDim a(i)
	Next
	t = Timer() - t
	Call WriteLine("ReDim:" & t)

	t = Timer()
	For i = 0 To 100000
		ReDim Preserve b(i)
	Next
	t = Timer() - t
	Call WriteLine("ReDim Preserve:" & t)
End Sub

Sub WriteLine(ByVal value)
	Call WScript.StdOut.WriteLine(value)
End Sub

Call Main()

出力

ReDim:154.5078
ReDim Preserve:0.5078125

ReDimよりReDim Preserveのほうが300倍速い。Preserveを省略すると配列の要素がEmptyになるのだけれども、その処理に時間がかかるようだ。
ところでMSDNには以下のように書かれている。

ReDim ステートメント
http://msdn.microsoft.com/ja-jp/library/cc392468.aspx

> ReDim ステートメント
> 
> 動的配列変数を宣言し、そのメモリ領域の割り当てや再割り当てを行
> います。
> 
> ReDim [Preserve] varname(subscripts) [, varname(subscripts)] . . .
> 
> 引数
> 
> Preserve
>     次元の大きさを変更しても、その配列に既に格納されている値を
>     そのまま保持しておく必要がある場合に指定します。

値を保持する必要があるときにPreserveを記述するように書かれているけれども、実行速度を考えるならば基本的にはPreserveを記述して、要素を空にする必要があるときのみPreserveを省略するべきだ。なのでPreserveの説明文は、配列を空にする必要がある場合には省略してください、にするべきだ。