Scheme
アルゴリズム
幾何学
2019-01-12

アルゴリズム: ベクトルの比較でしくじった件について

お仕事で、ベクトル(幾何学の「点」)のソートをしたいことが時々あって、ベクトルの汎用的な比較関数を考えてみたんだ。簡単だろうと高をくくって作ってみたら、しくじったから今回 Qiita に書いてみた。

条件

任意の次数
当面のお仕事で必要なのは2次元のベクトルでしかないけど任意の次数を扱えることにした。あっ、ベクトルは線形リスト形式だよっ。だけど、もちろん、比較するベクトルは同次元ねっ。
右側優先
座標値の比較では右側の値を優先して比較するんだ。たとえば $3$ 次元ベクトルであれば、$x$ 座標値と $y$ がどんな値だとしても $z$ 座標値で大小判定して、$z$ 座標値が同じであれば $y$ 座標値で大小判定するってことだよっ。これは何次元のベクトルでも同じで右側の座標値の大小判定を優先させて、値が同じであれば一つ左側の座標値で同じように判定をするってことただよ。
任意の個数
Scheme の < 関数と同じように、($2$ 個以上で)たくさんのベクトルを一気に比較できるってこと。$\lt(\{\overrightarrow{p_0},\ \overrightarrow{p_1},\ \overrightarrow{p_2},\ \overrightarrow{p_3},\ \overrightarrow{p_4}\})$ というような比較、つまり $\overrightarrow{p_0}\lt\overrightarrow{p_1}\lt\overrightarrow{p_2}\lt\overrightarrow{p_3}\lt\overrightarrow{p_4}$ というような比較ができるということだよっ。
効率的
当たり前けど、できるだけ無駄な計算はしないようにするということ。
実数
これは本質ではないけど、要するに座標値は実数の範囲という前提で、比較には < 関数を使うよってこと。複素ベクトルを扱わないよっこと。

しくじりポイント: 座標値を横串優先で比較しようとしたこと

最初に考えたのは横串優先比較。横串優先比較というのは、例えば、

$$\{(x_1,y_1,z_1),\ (x_2,y_2,z_2),\ \cdots, (x_n,y_n,z_n)\}$$

というベクトル列の比較で、

$\{z_1,z_2,\cdots,z_n\}$ を比較してから、$\{y_1,y_2,\cdots,y_n\}$ を比較して、その後に、$\{x_1,x_2,\cdots,x_n\}$ を比較して、みたいな処理すること。だけどこの方式はダメダメだとゆうことに気づいたんだ。

「小也イコール」で問題に気づいた

これがダメだと最初に気づいたのは「小也しょうなりイコール($\le$)」の比較だった。

例えばこんなベクトルの列 $P=\{\overrightarrow{p_0},\overrightarrow{p_1},\overrightarrow{p_2},\overrightarrow{p_3},\overrightarrow{p_4}\}$ の比較の場合、

$P$ $x$ $y$ $z$
$\overrightarrow{p_0}$ $1$ $2$ $3$
$\overrightarrow{p_1}$ $4$ $11$ $7$
$\overrightarrow{p_2}$ $9$ $8$ $7$
$\overrightarrow{p_3}$ $10$ $1$ $7$
$\overrightarrow{p_4}$ $14$ $15$ $16$

横串優先で比較するやり方だと、最初の比較($z$ 座標値の比較)

$$3 \le 7\le 7\le 7\le 16$$

の時点で、「$P$ は小也イコールの関係である」という結果になってしまう。

だけど、$\overrightarrow{p_1}$ と $\overrightarrow{p_2}$ と $\overrightarrow{p_3}$ の関係は $y$ 座標値で決まる $\overrightarrow{p_1}\gt \overrightarrow{p_2} \gt \overrightarrow{p_3}$ だよねっ。

横串優先比較は「小也」でも問題があった

この時点では、横串優先比較の方式で問題が起きるのは「小也イコール」の場合であって「小也」の場合には問題ではないだろうと考えていたんだけど、横串優先比較の問題は「小也」でも起きる事に気づいた。

例えばこんなベクトルの列 $Q=\{\overrightarrow{p_0},\overrightarrow{p_3},\overrightarrow{p_2},\overrightarrow{p_1},\overrightarrow{p_4}\}$ の比較の場合、

$Q$ $x$ $y$ $z$
$\overrightarrow{p_0}$ $1$ $2$ $3$
$\overrightarrow{p_3}$ $10$ $1$ $7$
$\overrightarrow{p_2}$ $9$ $8$ $7$
$\overrightarrow{p_1}$ $4$ $11$ $7$
$\overrightarrow{p_4}$ $14$ $15$ $16$

この時点で気づいたのは、横串優先比較の方式の問題は「小也」でも起きているということ。

横串優先で比較するやり方だと、最初の比較($z$ 座標値の比較)

$$3 \lt 7 \lt 7 \lt 7 \lt 16$$

の時点で、「$Q$ は小也の関係ではない」という結果になってしまう。

だけど、$\overrightarrow{p_3}$ と $\overrightarrow{p_2}$ と $\overrightarrow{p_1}$ の関係は $y$ 座標値で決まる $\overrightarrow{p_3} \lt \overrightarrow{p_2} \lt \overrightarrow{p_1}$ だよねっ。

正解(…たぶん)

ここまで考えてきて、横串優先で比較しようとしていたのがイケナイんだと思ったんだ。なぜ横串優先でやろうとしたのかといえば、Scheme の < 関数が複数の値を一気に比較できることを利用して、

(apply < (map car points))

みたいなコードを書こうと考えたからんだよねっ。

だから考え方を見直して、実直に二項演算の述語関数を作ってそれを畳み込むように適用する方向で考え直してみたんだ。つまり、

$$\left(\overrightarrow{p_0} \lt \overrightarrow{p_1}\right)\ \land\ \left(\overrightarrow{p_1} \lt \overrightarrow{p_2}\right)\ \land\ \cdots$$

という二項演算の繰り返しをするってこと。

小也イコール

問題の「小也イコール」の実装はこうしたんだ。コードは Scheme 言語で書いたよっ。

まずは二項演算の実装を下に書いたよ。2つのベクトル thisanother はリストの形式で与えられるとして、右側の値が比較の優先だから tsas はそれぞれのリストを逆順(reverse)にしたものだよっ。

(let le2 ((ts (reverse this)) (as (reverse another)))
  (or (and (null? ts) (null? as)) ; 最後まで行ったということは「this=another」だよねっ。
    (and (pair? ts) (pair? as) ; 長さが違うベクトルの比較は許さないっヽ(`Д´#)ノ ムキー!!
      (or (< (car ts) (car as)) ; 「小也」の関係を確認するんだ。
        (and (= (car ts) (car as)) ; この座標値が「等しい也」の場合だけ
          (le2 (cdr ts) (cdr as)) ; 次の座標値の比較をするんだ。
        )
      )
    )
  )
) ; let le2

この演算を最初のベクトルと次のベクトルでやって、


  • もし偽値ならこの時点で計算を止めて関数全体としてのも返り値も偽値にするんだ。
  • もし真値なら二番目のベクトルと三番目のベクトルで同じ計算をする。

ということを最後のベクトルまでやって、最後まで行ったら、真値を関数全体としての返り値にするんだ。

というわけで全体のコードをこうした。任意個数のベクトルを受け取りたいから、3番目以降のベクトルを可変個数のパラメーターとして others で受け取るようにしたよっ。

(define (LVector_le this another . others)
  (let every:le2 ((ts (reverse this)) (as (reverse another)) (others others))
    (and
      (let le2 ((ts ts) (as as))
        (or (and (null? ts) (null? as))
          (and (pair? ts) (pair? as)
            (or (< (car ts) (car as))
              (and (= (car ts) (car as))
                (le2 (cdr ts) (cdr as))
              )
            )
          )
        )
      ) ; let le2
      (or (null? others)
        (every:le2 as (reverse (car others)) (cdr others))
      )
    ) ; and
  ) ; let every:le
) ; define LVector_le

小也

「小也」の二項演算のコードは「小也イコール」のコードとよく似ているんだ。ハッキリいうと、最後まで到達した時のコードが違うだけのこと。「小也イコール」のコードから2行削除しただけのコードなんだっ。削除したところを注釈文として残したよっ。

(let lt2 ((ts (reverse this)) (as (reverse another)))
; (or (and (null? ts) (null? as)) ; 最後まで行ったということは「this=another」だよねっ。
    (and (pair? ts) (pair? as) ; 長さが違うベクトルの比較は許さないっヽ(`Д´#)ノ ムキー!!
      (or (< (car ts) (car as)) ; 「小也」の関係を確認するんだ。
        (and (= (car ts) (car as)) ; この座標値が「等しい也」の場合だけ
          (lt2 (cdr ts) (cdr as)) ; 次の座標値の比較をするんだ。
        )
      )
    )
; )
) ; let lt2

とゆうわけで、全体のコードはこんなふうになった。

(define (LVector_lt this another . others)
  (let every:lt2 ((ts (reverse this)) (as (reverse another)) (others others))
    (and
      (let lt2 ((ts ts) (as as))
        (and (pair? ts) (pair? as)
          (or (< (car ts) (car as))
            (and (= (car ts) (car as))
              (lt2 (cdr ts) (cdr as))
            )
          )
        )
      ) ; let lt2
      (or (null? others)
        (every:lt2 as (reverse (car others)) (cdr others))
      )
    ) ; and
  ) ; let every:lt
) ; define LVector_lt

おしまい

高をくくってたら案外ハマった。あとはこれをお仕事で使う SKILL 言語に翻訳しておしまい。(・∀・)