今回すんごいスコープを絞ったタイトルにしたけど、それには訳がある。
このブログで過去にマージソートのコードを紹介した。
thom.hateblo.jp
その際コードを作るのにとても苦労したので、もう少し配列を抽象的に扱えるクラスを作って楽にマージソートしようと思い立った。
ただ、クラスを作るにあたってもやはり苦労するポイントが同じなので、今回は改めて計算式を再考し、その妥当性を検証しようという記事である。
具体的に苦労したのは、配列を二つに分けるパート。
たとえば配列の最小値が0で最大値が10のとき、要素数は11個ある。
これをなるべく均等に分けると、5個と6個になる。
配列のインデックスでいうと、0～4と、5～10である。
つまり0, 10という配列インデックスから、分割された0, 4, 5, 10という4つのインデックスを導き出す必要があるのだが、実は私、こういう計算が大の苦手。
そもそもインデックスが2～10だったら？とか、奇数と偶数でパターンは大丈夫か？とか、とにかく頭の中で成功イメージが湧かずに心配になる。
そこで、その計算の検証をシート上で目に見える形でやった。
普段これは裏方作業なので記事になることは無いのだが、こういう思考プロセスも何かしら参考になるんじゃないかと思って見せることにした。
ただそれを記事にしたらもうそれだけで疲れてしまって、マージソート完成まで書ききる気力は無いだろうなと思って今回はスコープを絞ることにした。
案の定、最近記事執筆ペースが落ちている私は、ここまでの前書きだけでひぃひぃ言っている。
さて、イメージした検証はこんな感じ。
- シート上に手動で0～10のインデックスヘッダーを用意しておく(濃い黄色)
- マクロで配列の最小インデックスから最大インデックスまでを塗る(薄い黄色)
- マクロで中間点に"Split Here"を書き込む
- 目視で「ああ、ちゃんと半分に割れてるね」を確認する
本当は配列を作ってLBoundやUBoundで試すんだけれど、今回は計算式の妥当性検証なので変数lbとubで代用。
まず計算式を考えてみる。
半分に分けるためには、まず要素数を求める必要がある。
要素数はインデックスの最大値(変数 ub)から、インデックスの最小値(変数 lb)を引いて、1を足せば求まる。
要素数 = ub - lb + 1
例えば配列のインデックスが0 ～ 10に当てはめると、
10 - 0 + 1 = 11個
例えば配列のインデックスが2 ～ 10に当てはめると、
10 - 2 + 1 = 9個
確かに合ってる。
これを何個と何個に分けるかの計算は分割された配列の前半の個数を求めれば良いので、2で割って余りを切り捨てれば良い。
前半の個数 = 要素数 \ 2
※ブログのフォントでバックスラッシュに見えるものは、円マークです。これは割り算ですが、計算結果として整数を返します。
つまり最初の式と混ぜるとこうなる。
前半の個数 = (ub - lb + 1) \ 2
そして前半の個数を前半のインデックスの終値に変換するには。。。
たとえばインデックス0から始まる場合で5個の要素を取り出すと0, 1, 2, 3, 4 で終値が4。
インデックスが2で5個なら、2, 3, 4, 5, 6 で6。
計算式は
前半のインデックス終値 = 開始インデックス + 前半の個数 - 1
が成り立ってるっぽい。
インデックスがマイナス開始だったらどうか。
開始値が-1の場合、-1, 0, 1, 2, 3。 計算すると、 -1 + 5 - 1 = 3。
あってる。
混乱するのはこのあたり。なんで？って言われても知らない。
複数ケースに当てはめてちゃんと成り立つのでとしか。。
また先ほどの式と混ぜると、こうなる。
前半のインデックス終値 = lb + ((ub - lb + 1) \ 2) - 1
ちなみに要素数が1つしかない場合はインデックス終値がlbより小さくなってしまうが、もともと分割できないのでこれは仕方ない。
あとはlbとubを変化させながらこの式を使ってシート上にどこで分割するかを表示させていく。
完成したコードがこちら。
Sub 実験() Dim lb, ub Dim 行: 行 = 2 Const 列Offset = 1 For lb = 0 To 10 For ub = lb To lb + 10 Range(Cells(行, lb + 列Offset), Cells(行, ub + 列Offset)).Interior.Color = rgbLightYellow If ub - lb + 1 > 1 Then Cells(行, lb + ((ub - lb + 1) \ 2) - 1 + 列Offset).Value = "SplitHere" End If 行 = 行 + 1 Next Next End Sub
実行結果はこうなる。
目視で確認してみても、問題なく半分に割れてそう。
広域を確認してみる。
よし、イケる。この式だ！
ということで、最終的に以下の式の妥当性が検証された。
前半のインデックス終値 = lb + ((ub - lb + 1) \ 2) - 1
配列分割にあたって求めるべき全体はこうなる。
前半のインデックス始値：lb
前半のインデックス終値：lb + ((ub - lb + 1) \ 2) - 1
後半のインデックス始値：前半のインデックス終値 + 1
後半のインデックス終値：ub
実態
配列インデックス関連の計算は考えてると頭がこんがらがって思考が破綻するので実際に実験してみるという方法で攻略することが多い。
今回は記事を書くにあたって改めて論理的に計算式を思考してみたけれど普段はそんなことしてなくて、lbとubを使って「だいたいこうかな？」って勘で計算式を作ってみて、こうやってシート上でざくっと表示させてみる。それで目視でうまくいってたらその式を使うという割と雑なことをしている。
要は、理屈は分からんけどうまくうごいた！という極めて信頼性の低い根拠でも、充分なテスト量を確保することによって統計的な信頼性を確保するという手法。
ちなみに前回マージソートをやったときの前半のインデックス計算式は実質lb + ((ub - lb) \2)というかなりザックリしたもの。
でもシート上で実際に試してみると、今回の式と位置は微妙に違うけどちゃんと半分に割れてる。
5:6で割るところが6:5になったり、違いといえばそれくらい。全く問題ない。
考えてみればlb + ((ub - lb + 1) \ 2) - 1って、赤字の+1が2で割られるから+0.5、外の青字の1と相殺されて-0.5なので、インデックスを半分に分けるという目的においては、誤差の範囲に収まる。だからlb + ((ub - lb) \2)で問題ないんだな。
