Takenoff Labs

Lotus Notes/Domino に関する Tips や、クラシックの名曲などを紹介します

[Notes/Domino] Lotus Script で配列をソートする

Lotus Script で配列をソートしたい場面はかなりあると思います。が、標準では残念ながらソート関数は用意されていません。

そこで、大抵の場合、(基数ソートなどを除けば)最も速いと言われるクイックソートのアルゴリズムでソートルーチンを作成すると思いますが、普通に再帰処理でクイックソートを作成すると、ある程度大きな配列でスタックオーバーフローエラーが発生してしまいます(- -;

再帰処理以外でクイックソートを組むのもナンなので、今回は代替案として、比較的新しいソートアルゴリズムである、コムソートを紹介します。

コムソートの仕組みについては、Wikipediaをご覧ください。ここでは、コムソートのメリットとデメリットを列挙します。

メリット

  • メモリ使用量が少ない(ゆえにスタックオーバーフローは起こらない)
  • データの状態に左右されず、速度はほぼ安定している。(クイックソートは、データの状態によっては非常に遅くなる。まぁ改良版もあるが)
  • クイックソートにはかなり負けるものの、バブルソートよりは圧倒的に速い。最近のマシンでは、実用上問題無いレベル。
  • 非常に短く簡潔なコードで書ける。(クイックソートで再帰処理を使用するとファンクションが2つになるが、ファンクションは1つで済む)
  • コードが短いので、カスタマイズしたい場合(比較処理を変えたいなど)、コピペして少しいじるだけで手軽に対応できる。

デメリット

  • パッと見で、なぜソートされるのかが理解しにくい。(まぁWikipediaへのリンクを貼っておくとかしておけばいいでしょうが)
  • クイックソートよりはかなり遅いので、速度が要求される場合は不向き。
  • リスト変数(連想配列)にはそのままでは適用できない。リスト変数用にカスタマイズするのも、ちょっと面倒?

Notes は、比較的速度が要求されない処理が多いですから、実用上、コムソートで事足りるのではないかと思ってます。わたしは最近コムソートばかり使っています。

ソースコードは、3流(技術屋 and 本読み)さんのサイトにありましたので、そちらを紹介しておきます(Notesでもそのまま使えます)。

http://d.hatena.ne.jp/marujx/20060925

(2009/06/21追記)
わたしはノーツ開発ではハンガリアン記法が好きなので(他の言語ではやらないけど)、変数名を変更したものを記載しておきます。

Public Function ArySort(varAry As Variant) As Variant
	Const COMBGAP = 1.3
	
	Dim varRetAry As Variant
	Dim varTmp    As Variant
	Dim lngMin    As Long
	Dim lngMax    As Long
	Dim i         As Long
	Dim j         As Long
	Dim lngGap    As Long
	Dim blnEnd    As Boolean
	
	varRetAry = varAry
	
	lngMin = Lbound(varRetAry)
	lngMax = Ubound(varRetAry)
	
	lngGap = lngMax - lngMin
	
	blnEnd = False
	
	Do While lngGap > 1 Or blnEnd = False
		lngGap = Int(lngGap / COMBGAP)
		
		If lngGap = 9 Or lngGap = 10 Then lngGap = 11
		
		If lngGap < 1 Then lngGap = 1
		
		blnEnd = True
		For i = lngMin To lngMax - lngGap
			j = i + lngGap
			If varRetAry(i) > varRetAry(j) Then
				varTmp = varRetAry(i)
				varRetAry(i) = varRetAry(j)
				varRetAry(j) = varTmp
				blnEnd = False
			End If
		Next
	Loop
	
	ArySort = varRetAry
End Function
1 Star2 Stars3 Stars4 Stars5 Stars (2 votes, average: 5.00 out of 5)
読み込み中...

トラックバック

トラックバックはありません

コメント

コメントはありません

※コメントは承認制となっております。管理者が承認するまで表示されません。申し訳ありませんが、投稿が表示されるまでしばらくお待ちください。





(以下のタグが使えます)
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

For spam filtering purposes, please copy the number 5773 to the field below:

^
×