VBAHaskellの紹介　その8　（ソート関連） #VBA

2016/1/9
partition_pointsとpartition_points_predの説明を追加。

2015/12/29
痛恨のメモリリーク発見（VariantClear漏れ）。修正。

2015/12/27
2次元昇順比較関数の中で、次元の判定条件が4月以来ずっと誤っていた(vbSort.cpp)ので修正。

2015-04-18

ソート関連は別にHaskellぽくない。特徴と言えるのは任意の比較関数が使えることくらいだ。


sortIndex	昇順ソート後のインデックス配列を出力
sortIndex_pred	任意の比較関数によるソート後のインデックス配列を出力
permutate (Sub)	配列をソートインデックスを使って実際にソートする
permutate_back (Sub)	permutate で並べ換えられた1次元配列を元の順列に戻す
lower_bound	ソート済み配列からのキーの検索
lower_bound_pred	ソート済み配列からのキーの検索（比較関数使用）
upper_bound	ソート済み配列からのキーの検索
upper_bound_pred	ソート済み配列からのキーの検索（比較関数使用）
equal_range	ソート済み配列からのキーの検索
equal_range_pred	ソート済み配列からのキーの検索（比較関数使用）
partition_points	ソート済み配列から条件によって区分化されている位置の一覧を得る
partition_points_pred	ソート済み配列から条件によって区分化されている位置の一覧を得る（比較関数使用）

個々の機能は分かると思うので、多少注意を要する点だけあげる。

1　出力されるのはソートインデックス

sortIndex と sortIndex_predは対象配列を直接ソートするわけではなく、下図の太文字部分にあたるソート後のインデックスを出力する。¹　sortIndexは昇順ソートであり、降順指定はない。²

対象配列　　　：　3 , 1, 5 , 2 -> 1 , 2 , 3 , 5
インデックス　：　[0 1 2 3]　-> [ 1 3 0 2 ]

2　ソートの実行

ソートした結果の配列を新たに得たいときには、subV 関数または subM 関数 ³　を使う。配列自身をソートしてしまっていいのなら permutate を使う（permutate を使う方が速いはず）。
単純に対象配列をソートするのではなく、ソートインデックスを使うことによって「ある配列のソート順を使って他の配列もソートする」ことができるのがメリットだ。

    ' 配列を m をソートしたときのインデックス列
    index = sortIndex(m)      ' または　index = sortIndex_pred(m, comp)
    ' ソート結果
    result = subV(m, index)             ' 昇順ソート
    result = subV(m, reverse(index))    ' 降順ソート
  ' -------------------------------------------------
    ' m 自身をソートしてしまう方法
    permutate m, index
  ' -------------------------------------------------
    ' または、コピーを作ってそれをソートする
    result = m
    permutate result, index
    ' 他の配列を同じ順にソートすることもできる
    permutate other, index

3　対象配列

対象配列は1次元か2次元のみであり、自動的に判別される。2次元の場合は行をレコードと見たソートであり、列方向のソートはできない。ソートキーはsortIndex 関数の第2引数に指定することが可能で、優先したい順に列番号を並べる。省略した場合には全列がキーとなる（左にあるほうの列が優先）。

    ' 2次元配列 m の0列目, 2列目, 4列目 をソートキーにする
    sortIndex(m, Array(0, 2, 4))

4　比較関数（述語）の使用

sortIndex_predでは2引数の比較関数を与えることによって自由な順序でソートできる。この比較は「第1引数が第2引数より小さい」とき1を、そうでないとき０を返すものとする。比較関数さえ書ければいいので、型がバラバラでもジャグ配列でもソートできる。test_moduleにそのようなテスト関数を追加した。（Function comp000とSub sortTest）
比較関数を書けばその通りにソートできて当然ではあるが、VBAではなかなかできなかった。
ただし比較関数の引数と戻り値の形は、VBAHaskellの紹介その5（関数のシグネチャ）に記載した通りでなければならない。
2次元配列を対象とする場合は1行を一つの配列とみて比較関数を書く。

5　値の検索結果

upper_bound と upper_bound_pred の返り値、そしてequal_range と equal_range_pred の返り値の2番目の要素は検索範囲の最後の要素の「次の」インデックスである。C++標準ライブラリ<algorithm>にあるものと同じだ。

6　多次元配列

3次元以上の配列は対象にしていないが、m(i, j, k)と書いてアクセスする本当の3次元配列ではなく、2次元配列の配列、つまりm(k)(i, j)と書いてアクセスするいわゆるジャグ配列であればソートできる。これ自体は1次元配列だからだ。例えば以下のように比較関数を使うことができる。

Sub test_1_1()
    Dim data As Variant
    ' 長さ10の配列
    ReDim data(0 To 9)
    Dim i As Long
    For i = 0 To 9 Step 1
        ' それぞれの要素が 3×3 配列 （乱数）
        data(i) = makeM(3, 3, uniform_int_dist(9, 0, 9))
    Next i
    Dim s As Variant
    s = sortIndex_pred(data, p_less_1_1)
    Dim data2 As Variant
    data2 = data
    permutate data2, s
    printM "  ソート前 | ソート後"
    printM "---------------------"
    For i = 0 To 9 Step 1
        ' ソート前とソート後を並べて表示
        printM catC(data(i), catC(makeM(3, 1, "|"), data2(i)))
        printM "---------------------"
    Next i
End Sub

' 2次元配列 m を m(1, 1) の位置の値で比較する比較関数
Function less_1_1(ByRef a As Variant, ByRef b As Variant) As Variant
    less_1_1 = IIf(a(1, 1) < b(1, 1), 1, 0)
End Function
    Function p_less_1_1(Optional ByRef firstParam As Variant, Optional ByRef secondParam As Variant) As Variant
        p_less_1_1 = make_funPointer(AddressOf less_1_1, firstParam, secondParam)
    End Function

  ソート前 | ソート後
---------------------
  3  6  7  |  5  1  6
  7  6  6  |  2  0  4
  1  7  6  |  7  2  7
---------------------
  6  4  6  |  1  0  9
  5  4  3  |  7  2  5
  6  5  6  |  9  4  4
---------------------
  5  1  6  |  8  0  9
  2  0  4  |  3  3  1
  7  2  7  |  5  5  8
---------------------
  6  2  8  |  8  3  2
  5  8  4  |  6  3  1
  6  7  1  |  3  1  9
---------------------
  0  3  6  |  6  4  6
  5  4  7  |  5  4  3
  3  4  9  |  6  5  6
---------------------
  1  9  8  |  0  3  6
  1  5  2  |  5  4  7
  0  4  9  |  3  4  9
---------------------
  8  0  9  |  1  9  8
  3  3  1  |  1  5  2
  5  5  8  |  0  4  9
---------------------
  8  3  2  |  7  8  7
  6  3  1  |  8  5  1
  3  1  9  |  0  2  5
---------------------
  7  8  7  |  3  6  7
  8  5  1  |  7  6  6
  0  2  5  |  1  7  6
---------------------
  1  0  9  |  6  2  8
  7  2  5  |  5  8  4
  9  4  4  |  6  7  1
---------------------

ソートに限らず、多次元配列よりジャグ配列の方が都合がいいことが多い。

7　ソート済み配列からの区分点抽出

partition_points と partition_points_pred はソート済み配列から条件によって区分化されている位置の一覧を得るための関数で、後者は比較関数（述語）を使用するバージョンである。区分点には UBound(配列) + 1 が含まれる。(2016/1/28 に仕様変更)

' [0,1,2,3,4,5]に属する15個の整数を作ってソートしておく
m = uniform_int_dist(15, 0, 5)
permutate m, sortIndex(m)
' インデックスと値を見る
Debug.Print "  No  m" : printM unzip(zip(a_rows(m), m), 2)
  No  m
   0  0    ' <--
   1  0
   2  1    ' <--
   3  2    ' <--
   4  2
   5  2
   6  2
   7  3    ' <--
   8  3
   9  3
  10  4    ' <--
  11  4
  12  4
  13  5    ' <--
  14  5
           ' <-- UBound + 1
' m の要素が変化する境界を一覧
printM partition_points(m)
  0  2  3  7  10  13  15

VBAHaskellの紹介　その7　（bind1stとbind2nd）
VBAHaskellの紹介　その1　（最初はmapF）

これに限らず、基本的に関数は副作用を持たないようにしている。 ↩
出力されたインデックスを reverse すれば事足りるからだ。 ↩
Haskell_4_vectorモジュールにある部分配列を得る関数 ↩

VBAHaskellの紹介 その8 （ソート関連）

1 出力されるのはソートインデックス

2 ソートの実行

3 対象配列

4 比較関数（述語）の使用

5 値の検索結果

6 多次元配列

7 ソート済み配列からの区分点抽出

VBAHaskellの紹介　その8　（ソート関連）