「区間」のソートあれこれ

註:本エントリは等幅フォントで見ないと訳の分からない部分があります。Firefoxではきちんと見えるのですが、Google Chromeではなぜかmonospaceが等幅になりません…。というわけで、本エントリはFirefox推奨。SafariでもOKでした。IEは知らん。

さて、昨日の続きです。昨日は区間とは何かということを主に書いてきたのだが、今日はこれをどのようにソートしたらいいのか。あれこれ考えた結果、むしろ多分数学的に優位(有意?)なソートロジックってのは多分存在しないので、主観的にどれが一番理に適っていると感じるのかなぁ、というところをつついてみたい。

そんなわけで、解答はないので、ブクマとか※で、どれが一番イケてると感じたか*1、教えてほしいなぁ。今日は技術とか理屈の紹介じゃなくて、読者をアンケートに付き合わせて俺が考えを整理したいだけです、すみませんがお付き合いをば…。

区間のcompareに先だって、限界のcompareについて

<lower Infinity>
<lower closed 1>
<lower open 1>
<upper open 1>
<upper closed 1>
<lower closed 5>
<lower open 5>
<upper open 5>
<upper closed 5>
<upper Infinity>

区間は2つ(上下)の限界から出来ているというのは昨日のエントリの通り。[5, 8) だったら「閉じた5」と「開いた8」から成ってる。では、この「限界」をソートするのはどんなロジックか?

実はじっくり考えると色々面倒だった*2んだけど、恐らくみんな考えた末に、このソート順にたどり着くんじゃないかな、と思ってる。

まず、単純に限界値で比較(小さい方が先)して並べる。値が同じ場合は、下側無限限界は何よりも先、上側無限限界は何よりも後になる*3。値と上下が同じだったら開閉で比較。下限だったら閉じている方が先で、上限だったら開いている方が先。

まぁ、文言による仕様よりも例示した方が分かりやすいかな。右のような順で並べるんだ。

このエントリにおける区間の表記法(オリジナル)

とりあえず、区間 [5, 8) って表記は文中に書くには便利なんだけど、ソートを考えた時に「どっちが先か」考えるにあたって、見づらい。ので、asciiで数直線ぽいものを書いてみることにした。

           1         2         3
 0123456789012345678901234567890
      [--)                        ← [5, 8)  普通の区間
<-----]                           ← (-∞, 5] 下側無限区間
         (----------------------> ← (8, +∞) 上側無限区間
<-------------------------------> ← (-∞, +∞) 両側無限区間(全区間)
       @                          ← {6} 単一要素区間
 EMPTY                            ← {} 空区間

まぁ、こんな感じで。

さて、区間のソートだ

でだよ、やっと本題だ。これをソートしたい訳です。ここからはComparable#compareTo(Object other)の実装として考えていきます。同一だったら0、otherの方が小さければ1、otherの方が大きければ-1を返すって奴です。

色々考えているウチに、4つの仕様ができあがりました。

  1. 下側同士の比較を優先して、同じだったら上側同士の比較を使う {lower -> upper}
  2. 上側同士の比較を優先して、同じだったら下側同士の比較を使う {upper -> lower}
  3. 下側同士の比較を優先して、同じだったら上側同士の結果に -1 を掛けたものを使う {lower -> upper * -1}
  4. 上側同士の比較を優先して、同じだったら下側同士の結果に -1 を掛けたものを使う {upper -> lower * -1}


まぁ、上の2つは誰でも思いつくと思う。そんな中、下の2つが出てきた理由を説明しておく。色々な区間の中で、空区間 {} と全区間 (-∞, +∞) は特殊なもので、かつ、対照的な関係にある気がした*4のです。つまり、ソートした時に先頭と末尾にそれぞれ位置する要素な気がした訳です。そんな中、1と2の結果を見てみると、どうにもそうならない…。というわけで、後から検証する結果を反転させてみたら、思うような結果になった、という訳です。

で、他にも比較仕様のアイデアなどあったら、是非教えてください。

ではお待ちかね*5。色んな区間をソートした結果4つをご覧下さい。

{lower -> upper}
           1         2         3
 0123456789012345678901234567890
<)
<]
<-----)
<-----]
<----------)
<----------]
<---------------)
<---------------]
<--------------------)
<--------------------]
<------------------------------->
 @
 [----)
 [----]
 [---------)
 [---------]
 [--------------)
 [--------------]
 [-------------------)
 [-------------------]
 [------------------------------>
 (----)
 (----]
 (---------)
 (---------]
 (--------------)
 (--------------]
 (-------------------)
 (-------------------]
 (------------------------------>
      @
      [----)
      [----]
      [---------)
      [---------]
      [--------------)
      [--------------]
      [------------------------->
      (----)
      (----]
      (---------)
      (---------]
      (--------------)
      (--------------]
      (------------------------->
           @
           [----)
           [----]
           [---------)
           [---------]
           [-------------------->
           (----)
           (----]
           (---------)
           (---------]
           (-------------------->
                @
                [----)
                [----]
                [--------------->
                (----)
                (----]
                (--------------->
                     @
                     [>
                     (>
 EMPTY

{lower -> upper * -1}
           1         2         3
 0123456789012345678901234567890
<------------------------------->
<--------------------]
<--------------------)
<---------------]
<---------------)
<----------]
<----------)
<-----]
<-----)
<]
<)
 [------------------------------>
 [-------------------]
 [-------------------)
 [--------------]
 [--------------)
 [---------]
 [---------)
 [----]
 [----)
 @
 (------------------------------>
 (-------------------]
 (-------------------)
 (--------------]
 (--------------)
 (---------]
 (---------)
 (----]
 (----)
      [------------------------->
      [--------------]
      [--------------)
      [---------]
      [---------)
      [----]
      [----)
      @
      (------------------------->
      (--------------]
      (--------------)
      (---------]
      (---------)
      (----]
      (----)
           [-------------------->
           [---------]
           [---------)
           [----]
           [----)
           @
           (-------------------->
           (---------]
           (---------)
           (----]
           (----)
                [--------------->
                [----]
                [----)
                @
                (--------------->
                (----]
                (----)
                     [---------->
                     @
                     (---------->
 EMPTY

{upper -> lower}
           1         2         3
 0123456789012345678901234567890
 EMPTY
<)
<]
 @
<-----)
 [----)
 (----)
<-----]
 [----]
 (----]
      @
<----------)
 [---------)
 (---------)
      [----)
      (----)
<----------]
 [---------]
 (---------]
      [----]
      (----]
           @
<---------------)
 [--------------)
 (--------------)
      [---------)
      (---------)
           [----)
           (----)
<---------------]
 [--------------]
 (--------------]
      [---------]
      (---------]
           [----]
           (----]
                @
<--------------------)
 [-------------------)
 (-------------------)
      [--------------)
      (--------------)
           [---------)
           (---------)
                [----)
                (----)
<--------------------]
 [-------------------]
 (-------------------]
      [--------------]
      (--------------]
           [---------]
           (---------]
                [----]
                (----]
                     @
<------------------------------->
 [------------------------------>
 (------------------------------>
      [------------------------->
      (------------------------->
           [-------------------->
           (-------------------->
                [--------------->
                (--------------->
                     [---------->
                     (---------->

{upper -> lower * -1}
           1         2         3
 0123456789012345678901234567890
 EMPTY
<)
 @
<]
 (----)
 [----)
<-----)
      @
 (----]
 [----]
<-----]
      (----)
      [----)
 (---------)
 [---------)
<----------)
           @
      (----]
      [----]
 (---------]
 [---------]
<----------]
           (----)
           [----)
      (---------)
      [---------)
 (--------------)
 [--------------)
<---------------)
                @
           (----]
           [----]
      (---------]
      [---------]
 (--------------]
 [--------------]
<---------------]
                (----)
                [----)
           (---------)
           [---------)
      (--------------)
      [--------------)
 (-------------------)
 [-------------------)
<--------------------)
                     @
                (----]
                [----]
           (---------]
           [---------]
      (--------------]
      [--------------]
 (-------------------]
 [-------------------]
<--------------------]
                     (---------->
                     [---------->
                (--------------->
                [--------------->
           (-------------------->
           [-------------------->
      (------------------------->
      [------------------------->
 (------------------------------>
 [------------------------------>
<------------------------------->

…多分じっくり見ないとサッパリよくわかりません。でも、どの結果もそれなりに綺麗に並んでるのですよ。この中のどれが主観的に「イイ」と感じるでしょうか?

教えてくださいm(_ _)m

*1:つまり、主観だ。

*2:限界値が同一で、上側限界と下側限界の比較の場合は、開閉にかかわらず下側を先と判断する。これが以外と直感的じゃない気がしたんだけど、こうしないと他と矛盾する。

*3:限界値が同一で、上側限界と下側限界の比較の場合は、開閉にかかわらず下側を先と判断する。

*4:主観です。

*5:…誰も待ってねぇだろうなぁ、とは思うんですが。今回のネタってこのブログの読者層に全くフィットしないよねw