sortの比較関数の実装ではまった

C++

最初、以下のような実装をしていた。

#include <algorithm>
#include <iostream>

using namespace std;

class ValList {
public:
    vector<int> valList;
    ValList(vector<int> &valList) {
        this->valList = valList;
    }
};

class Comp {
public:
    bool operator()(const ValList *v1, const ValList *v2) const {
        for (int i = 0; i < min(v1->valList.size(), v2->valList.size()); ++i) {
            if (v1->valList[i] < v2->valList[i]) {
                return true;
            }
        }
        return false;
    }
};

int main(int argc, char** argv) {
    int n = 20;
    vector<ValList*> v;
    for (int i = 0; i < n; ++i) {
        vector<int> v1;
        v1.push_back(i);
        v1.push_back(n - i);
        v.push_back(new ValList(v1));
    }

    sort(v.begin(), v.end(), Comp());
}

これを実行すると、なぜか「Segmentation fault」が発生する。なぜ？と思ってCompクラスに以下のようなデバッグコードを入れてみたところ・・・

class Comp {
public:
    bool operator()(const ValList *v1, const ValList *v2) const {
if (v1 == NULL) {
cerr << "v1 is null" << endl;
}
if (v2 == NULL) {
cerr << "v2 is null" << endl;
}
        for (int i = 0; i < min(v1->valList.size(), v2->valList.size()); ++i) {
            if (v1->valList[i] < v2->valList[i]) {
                return true;
            }
        }
        return false;
    }
};

v1 is null
Segmentation fault

と、比較関数に渡されている参照がNULLになっている‥

いろいろ調べて、比較関数は「strict weak ordering」になっていなければならないというのは意識していたのだが、原因がさっぱり分からず‥

c++ - Why does std::sort throw a segmentation fault on this code? - Stack Overflow

で、いろいろデバッグ出力をしながら考えていたら、ふと気づいた。v1 < v2とv2 < v1が同時に成り立つことがある実装になっていることに‥

ソートしようとしているデータは以下のようになっている。

[0, 20]
[1, 19]
　：

なので、例えばv1 = [0, 20]とv2 = [1, 19]を比較すると、v1[0] < v2[0](0 < 1)かつv2[1] < v1[1](19 < 20)なので、「strict weak ordering」になっていない。

こういう比較をやるときは、以下の様に実装しなければならない。

class Comp {
public:
    bool operator()(const ValList *v1, const ValList *v2) const {
        for (int i = 0; i < min(v1->valList.size(), v2->valList.size()); ++i) {
            if (v1->valList[i] != v2->valList[i]) {
                if (v1->valList[i] < v2->valList[i]) {
                    return true;
                } else {
                    return false;
                }
            }
        }
        return false;
    }
};

つまり、今回の場合だと、先頭の要素から順に比較して、互いに等しくない要素が現れた時点でtrueかfalseを返さなければならない、ということ。

これに悩んで2時間もはまっていたがな‥

2018-07-11

Nを表すのに必要な最低限のビット数

数学 Java

Javaのあるプログラムで非負整数Nに対する以下のような式を見かけた。

int n = (int)(Math.log10(N) / Math.log10(2) + 1.0);

最初、何を求めているのかしばらく分からなかったのでメモ。

ちなみに以下のように書いても同じ(はず)である。

int n = (int)Math.ceil(Math.log10(N) / Math.log10(2));

上記の答えnが何を表すかというと、タイトルに書いてしまったが、Nを2進数にしたときの長さ、つまりビット数の最小値を求めている。

なぜこれでビット数が求められるのかの証明と、他の求め方を記録しておく。

対数を使った求め方の証明

分かってしまえば簡単な話なのだが、以下のようにして証明できる。

非負整数Nを表現するのに必要なビット数をpとすると、
${\displaystyle 2^p > N }$
が成り立つ。この両辺の常用対数を取ると、
${\displaystyle log_{10}{2^p} > log_{10}{N} }$
${\displaystyle p*log_{10}{2} > log_{10}{N} }$
${\displaystyle p > \frac{log_{10}{N}}{log_{10}{2}} }$
右辺は小数になるので、
${\displaystyle p = \lceil \frac{log_{10}{N}}{log_{10}{2}} \rceil }$

他の求め方

他の求め方としては、以下の2通りがある。

int n = Long.bitCount(Long.highestOneBit(N) - 1) + 1;

int n = Long.toBinaryString(N).length();

1つ目の方法の説明は以下の通り。

まずLong.highestOneBit(N)で最上位のビットのみを残した値を求める。
そこから1を引くと、最上位のビットが0になり、代わりにそれ以下のビットが全て1となる。
Long.bitCount()で1となっているビット数をカウントする。
最上位のビットの分の1を足す。

2つ目の方法は、説明するまでもないと思うが、単純にNを2進数文字列に変換してその長さを取得しているだけ。ただし、この方法は他の2つの方法に比べてStringオブジェクトを生成している分だけメモリコストや時間的コストがかかるので、シビアな状況においては要注意。

2018-07-06

Range同士の関係を判定する述語についてまとめてみる

メモ Java

非常につまらないミスをやらかして凹んでいるので、反省の意味を込めて、Rangeに対して実装できる述語を整理してみるテスト。

ちなみに、Rangeとは開始と終了（begin & end、from & to、left & right、etc.）の範囲を表現することができる何か。

Javaでクラスとして実装すると以下のような感じだろうか。

public class Range {
    private long begin;
    private long end;
    public Range(long begin, long end) {
        // 面倒なので、順序が逆の場合は単にエラーにしておく。
        if (begin > end) {
            throw new RuntimeException("begin > end");
        }
        this.begin = begin;
        this.end = end;
    }
    public long getBegin() {
        return begin;
    }
    public long getEnd() {
        return end;
    }
}

さて、これに述語をメソッドとして追加していきたいのだが、その前に「述語」って何？って話からしていくと、要はそのRangeが他のRangeと被ってるの？含んでるの？等しいの？とかそういうことである。

述語として考えられるものは、Rangeが表す意味によって2系統に分けられる。

Rangeの中にendを含むケース
Rangeの中にendは含まないケース

つまり、new Range(1, 10)としたときに、10をRange(範囲)に含むか含まないかということである（各プログラム言語でRangeがどう扱われるかについては、以前に「rangeによるrangeの違い - HHeLiBeXの日記正道編」でまとめたので、興味があれば参考にしてください）。

で、それぞれのケースに於いて、どんな述語が考えられるかを列挙したのが以下である。

Rangeの中にendを含むケース
- overlaps
- precedes
- succeeds
- contains
- equals
Rangeの中にendは含まないケース
- overlaps
- meets
- precedes
- succeeds
- contains
- equals

こんなところだろうか（ほかにあったら教えて・・）。

「Rangeの中にendは含まないケース」にだけ「meets」というのがあるが、これはendがexclusiveだからこその述語である。これらは「Rangeの中にendを含むケース」では「overlaps」に内包されるものである（beginとendが例えば整数値しか取らないようなケースでは、「range1.end + 1 == range2.begin」は「meets」じゃないのか？という議論もあるが、それはここでは考えないことにする）。

では順に見て行こう‥と言いたいところだが、上記の順で見ていくと説明が二重になりそうなので、述語ごとに見ていくことにする。

それぞれの述語の説明において、パターンを図示し、最終的に判定式にまとめ上げていく。

なお、それぞれの図示の中での記号の意味は以下の通りである。

「●」はその値をRangeに含むこと
「○」はその値をRangeに含まないこと
「━」は「range1」の範囲に含まれる値
「─」は「range2」の範囲に含まれる値
左側の「●」はbeginを表す
右側の「●」または「○」はendを表す

全パターンの列挙

まずは、「range1」と「range2」の位置関係について、全パターンを列挙してみようと思う。

Rangeの中にendを含むケース

　　　　　　　　　　　●━━━━━━━━●
（０１）●───●
（０２）●──────●
（０３）●───────────●
（０４）●───────────────●
（０５）●──────────────────────●
（０６）　　　　　　　●────●
（０７）　　　　　　　●────────●
（０８）　　　　　　　●───────────────●
（０９）　　　　　　　　　　　　●───●
（１０）　　　　　　　　　　　　●──────────●
（１１）　　　　　　　　　　　　　　　　●──────●
（１２）　　　　　　　　　　　　　　　　　　　●───●

Rangeの中にendは含まないケース

　　　　　　　　　　　●━━━━━━━━○
（０１）●───○
（０２）●──────○
（０３）●───────────○
（０４）●───────────────○
（０５）●──────────────────────○
（０６）　　　　　　　●────○
（０７）　　　　　　　●────────○
（０８）　　　　　　　●───────────────○
（０９）　　　　　　　　　　　　●───○
（１０）　　　　　　　　　　　　●──────────○
（１１）　　　　　　　　　　　　　　　　●──────○
（１２）　　　　　　　　　　　　　　　　　　　●───○

overlaps

overlapsとは、一言で言うと、2つのRange間に重なりがあるかどうかの判定である。列挙した全パターンのうち、overlapsに該当するのはそれぞれ以下のとおりである。

Rangeの中にendを含むケース

　　　　　　　　　　　●━━━━━━━━●
（０２）●──────●
（０３）●───────────●
（０４）●───────────────●
（０５）●──────────────────────●
（０６）　　　　　　　●────●
（０７）　　　　　　　●────────●
（０８）　　　　　　　●───────────────●
（０９）　　　　　　　　　　　　●───●
（１０）　　　　　　　　　　　　●──────────●
（１１）　　　　　　　　　　　　　　　　●──────●

全パターンから除外されたのが以下の2パターンである。

range2.end < range1.begin
range1.end < range2.begin

つまり、それ以外は「overlaps」とみなされるので、以下のような条件式で判定できる。

    public boolean overlaps(Range that) {
        return this.begin <= that.end && that.begin <= this.end;
    }

Rangeの中にendは含まないケース

　　　　　　　　　　　●━━━━━━━━○
（０３）●───────────○
（０４）●───────────────○
（０５）●──────────────────────○
（０６）　　　　　　　●────○
（０７）　　　　　　　●────────○
（０８）　　　　　　　●───────────────○
（０９）　　　　　　　　　　　　●───○
（１０）　　　　　　　　　　　　●──────────○

全パターンから除外されたのが以下の4パターンである。

range2.end < range1.begin
range2.end = range1.begin
range1.end = range2.begin
range1.end < range2.begin

注意してほしいのは、endはRangeに『含まれない』ということである。

まとめると、以下のような条件式で「overlaps」を判定できる。

    public boolean overlaps(Range that) {
        return this.begin < that.end && that.begin < this.end;
    }

meets

「meets」とは、range1がrange2にちょうど接続するかどうか（連続した1つのRangeにマージできるかどうか）を判定する述語である。

ものによっては「metBy」という述語を入れる場合もあるが、「range1.meets(range2) == range2.metBy(range1)」なのでここでは考えない。

Rangeの中にendを含むケース

先にも述べたように、これは「overlaps」に内包されると考えるので、このケースでの「meets」は無いとみなす。

Rangeの中にendは含まないケース

　　　　　　　　　　　●━━━━━━━━○
（１１）　　　　　　　　　　　　　　　　●──────○