HHeLiBeXの日記 正道編

日々の記憶の記録とメモ‥

C++版の文字列split実装の罠

C++ 文字列 カンマ区切り」とかで検索するとヒットする記事等には、以下のようなコードがよく書かれている。(main関数は動作確認のために自分で付け足したもの)

#include <iostream>
#include <string>
#include <vector>
#include <sstream>

using namespace std;

vector<string> split(string str, char delim) {
    vector<string> res;

    stringstream ss(str);
    string buf;
    while (getline(ss, buf, delim)) {
        res.push_back(buf);
    }

    return res;
}

int main(int argc, char** argv) {
    string line;
    while (getline(cin, line)) {
        vector<string> v = split(line, ',');
        for (int i = 0; i < v.size(); ++i) {
            cout << v[i] << endl;
        }
    }

    return EXIT_SUCCESS;
}

上のコードでも多くのケースでは問題がないのだろうけど、このコードには以下の欠陥がある。

  • strが空文字列だった場合、返されるvectorは空になる
  • strdelimで区切った最後のトークンが空文字列だった場合、返されるvectorは期待されるサイズより1つ小さくなる

これらはいずれも、残りが空文字列になった時点でwhileループを抜けてしまうからである。まぁ考えれば当然だわな。

なので、ちゃんと文字列分割を実装しようと思ったら、上記のケースを別扱いして対応する必要がある。その対応を入れたコードが以下になる。

#include <iostream>
#include <string>
#include <vector>
#include <sstream>

using namespace std;

vector<string> split(string str, char delim) {
    vector<string> res;

    if (str.length() == 0) {
        res.push_back("");
    } else {
        stringstream ss(str);
        string buf;
        while (getline(ss, buf, delim)) {
            res.push_back(buf);
        }
        if (str[str.length() - 1] == delim) {
            res.push_back("");
        }
    }

    return res;
}

int main(int argc, char** argv) {
    string line;
    while (getline(cin, line)) {
        vector<string> v = split(line, ',');
        for (int i = 0; i < v.size(); ++i) {
            cout << v[i] << endl;
        }
    }

    return EXIT_SUCCESS;
}

1つ目のケースは、strが空文字列なのだから、長さは当然0になるので、その判定がtrueになる場合は空文字列1つを入れたvectorを返す。

2つ目のケースは、末尾のトークンが空文字列なのだから、strの最後の文字がdelimに等しくなるので、その判定がtrueになる場合は空文字列をvectorの末尾に追加する。

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

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

#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」になっていなければならないというのは意識していたのだが、原因がさっぱり分からず‥

で、いろいろデバッグ出力をしながら考えていたら、ふと気づいた。v1 < v2v2 < 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;
    }
};

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

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

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

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つ目の方法の説明は以下の通り。

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

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

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

非常につまらないミスをやらかして凹んでいるので、反省の意味を込めて、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を含むケース
           ●━━━━━━━━●
(01)●───●
(02)●──────●
(03)●───────────●
(04)●───────────────●
(05)●──────────────────────●
(06)       ●────●
(07)       ●────────●
(08)       ●───────────────●
(09)            ●───●
(10)            ●──────────●
(11)                ●──────●
(12)                   ●───●
  • Rangeの中にendは含まないケース
           ●━━━━━━━━○
(01)●───○
(02)●──────○
(03)●───────────○
(04)●───────────────○
(05)●──────────────────────○
(06)       ●────○
(07)       ●────────○
(08)       ●───────────────○
(09)            ●───○
(10)            ●──────────○
(11)                ●──────○
(12)                   ●───○

overlaps

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

  • Rangeの中にendを含むケース
           ●━━━━━━━━●
(02)●──────●
(03)●───────────●
(04)●───────────────●
(05)●──────────────────────●
(06)       ●────●
(07)       ●────────●
(08)       ●───────────────●
(09)            ●───●
(10)            ●──────────●
(11)                ●──────●

全パターンから除外されたのが以下の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は含まないケース
           ●━━━━━━━━○
(03)●───────────○
(04)●───────────────○
(05)●──────────────────────○
(06)       ●────○
(07)       ●────────○
(08)       ●───────────────○
(09)            ●───○
(10)            ●──────────○

全パターンから除外されたのが以下の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は含まないケース
           ●━━━━━━━━○
(11)                ●──────○

見ての通り、1パターンしかないので、条件式は以下のようになる。

    public boolean meets(Range that) {
        return this.end == that.begin;
    }

precedes

「precedes」とは、range1がrange2より前に位置するかどうかを判定する述語である。

  • Rangeの中にendを含むケース
           ●━━━━━━━━●
(12)                   ●───●

見ての通り、1パターンしかないので、条件式は以下のようになる。

    public boolean precedes(Range that) {
        return this.end < that.begin;
    }
  • Rangeの中にendは含まないケース
           ●━━━━━━━━○
(12)                   ●───○

見ての通り、1パターンしかないので、条件式は以下のようになる。

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

succeeds

「succeeds」とは、range1がrange2より後に位置するかどうかを判定する述語である。

  • Rangeの中にendを含むケース
           ●━━━━━━━━●
(01)●───●

見ての通り、1パターンしかないので、条件式は以下のようになる。

    public boolean succeeds(Range that) {
        return this.begin > that.end;
    }
  • Rangeの中にendは含まないケース
           ●━━━━━━━━○
(01)●───○

見ての通り、1パターンしかないので、条件式は以下のようになる。

    public boolean succeeds(Range that) {
        return this.begin > that.end;
    }

contains

「contains」とは、文字通りrange1がrange2の範囲を完全に含むかどうかを判定する述語である。

  • Rangeの中にendを含むケース
           ●━━━━━━━━●
(06)       ●────●
(07)       ●────────●
(09)            ●───●

条件式は以下のようになる。

    public boolean contains(Range that) {
        return this.begin <= that.begin && that.end <= this.end;
    }
  • Rangeの中にendは含まないケース
           ●━━━━━━━━○
(06)       ●────○
(07)       ●────────○
(09)            ●───○

条件式は以下のようになる。

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

equals

「equals」とは、言うまでもなくrange1とrange2が同じ範囲を表しているかどうかを判定する述語である。

  • Rangeの中にendを含むケース
           ●━━━━━━━━●
(07)       ●────────●

条件式は以下のようになる。

    public boolean equals(Range that) {
        return this.begin == that.begin && this.end == that.end;
    }
  • Rangeの中にendは含まないケース
           ●━━━━━━━━○
(07)       ●────────○

条件式は以下のようになる。

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

CentOS 7環境にMonoを導入してみる

ふと思い立って、C#のプログラムをCentOS 7上で動かせないかと考え、導入からコンパイル、実行までをやってみたメモ。

参考サイト

環境

$ uname -a
Linux proteus-annex-centos7 3.10.0-862.3.3.el7.x86_64 #1 SMP Fri Jun 15 04:15:27 UTC 2018 x86_64 x86_64 x86_64 GNU/Linux
$ cat /etc/redhat-release 
CentOS Linux release 7.5.1804 (Core) 
$ 

導入

自分の環境では、yum-config-managerが足りなかったので、まずはそれをインストール。

$ su -
# yum -y install yum-utils

そして、Monoのインストール。

# rpm --import "http://keyserver.ubuntu.com/pks/lookup?op=get&search=0x3FA7E0328081BFF6A14DA29AA6A19B38D3D831EF"
# yum-config-manager --add-repo http://download.mono-project.com/repo/centos/
# yum install -y mono-complete

バージョン確認。これは一般ユーザでOK。

$ mono --version
Mono JIT compiler version 5.12.0.233 (tarball Tue May  8 09:28:02 UTC 2018)
Copyright (C) 2002-2014 Novell, Inc, Xamarin Inc and Contributors. www.mono-project.com
        TLS:           __thread
        SIGSEGV:       altstack
        Notifications: epoll
        Architecture:  amd64
        Disabled:      none
        Misc:          softdebug 
        Interpreter:   yes
        LLVM:          supported, not enabled.
        GC:            sgen (concurrent by default)
$ 

ソースコード

いたってシンプルなHello World

using System;

public class Program {
    public static void Main(string[] args) {
        Console.WriteLine("Hello World");
    }
}

コンパイル

$ mcs HelloWorld.cs

実行

$ mono HelloWorld.exe
Hello World
$ 

大量の座標値を読む場合の効率的な読み方

ふと、AtCoderなどのコンテストでよくある「大量の座標値を読んで何かを求める」という場合に、どういう処理を書いたら一番効率がいいのかと疑問に思ったので試してみたメモ。

テストケース

実際に試したケースは以下の通り

  • Main01.java - Scanner.nextInt()で読む
    • ひたすらScanner.nextInt()で読んでいく
  • Main02.java - String.split(" ")とInteger.parseInt(String)
    • 単なる1文字から成る文字列で分割させてInteger.parseInt(String)でint化
  • Main03.java - StringTokenizer.nextToken()とInteger.parseInt(String)
    • StringTokenizerで分割させてInteger.parseInt(String)でint化
  • Main04.java - String.split("[ ]")とInteger.parseInt(String)
    • 正規表現"[ ]"で分割させてInteger.parseInt(String)でint化
  • Main05.java - String.indexOf(String)とInteger.parseInt(String)
    • String.indexOf(" ")で分割位置を求めて分割し、Integer.parseInt(String)でint化
  • Main06.java - String.indexOf(int)とInteger.parseInt(String)
    • String.indexOf(' ')で分割位置を求めて分割し、Integer.parseInt(String)でint化
  • Main07.java - StringBuilder.indexOf(" ")とInteger.parseInt(String)
    • StringBuilder.indexOf(" ")で分割位置を求めて分割し、Integer.parseInt(String)でint化

以下、そのソースコード

  • Main01.java - Scanner.nextInt()で読む
import java.util.*;

public class Main01 {
    public static void main(String[] args) {
        try (Scanner sc = new Scanner(System.in)) {
            int N = sc.nextInt();
            for (int i = 0; i < N; ++i) {
                int x = sc.nextInt();
                int y = sc.nextInt();
            }
        }
    }
}
  • Main02.java - String.split(" ")とInteger.parseInt(String)
import java.io.*;

public class Main02 {
    public static void main(String[] args) {
        try (BufferedReader in = new BufferedReader(new InputStreamReader(System.in))) {
            int N = Integer.parseInt(in.readLine());
            for (int i = 0; i < N; ++i) {
                String[] ss = in.readLine().split(" ");
                int x = Integer.parseInt(ss[0]);
                int y = Integer.parseInt(ss[1]);
            }
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
}
  • Main03.java - StringTokenizer.nextToken()とInteger.parseInt(String)
import java.io.*;
import java.util.*;

public class Main03 {
    public static void main(String[] args) {
        try (BufferedReader in = new BufferedReader(new InputStreamReader(System.in))) {
            int N = Integer.parseInt(in.readLine());
            for (int i = 0; i < N; ++i) {
                StringTokenizer st = new StringTokenizer(in.readLine());
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());
            }
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
}
  • Main04.java - String.split("[ ]")とInteger.parseInt(String)
import java.io.*;

public class Main04 {
    public static void main(String[] args) {
        try (BufferedReader in = new BufferedReader(new InputStreamReader(System.in))) {
            int N = Integer.parseInt(in.readLine());
            for (int i = 0; i < N; ++i) {
                String[] ss = in.readLine().split("[ ]");
                int x = Integer.parseInt(ss[0]);
                int y = Integer.parseInt(ss[1]);
            }
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
}
  • Main05.java - String.indexOf(String)とInteger.parseInt(String)
import java.io.*;

public class Main05 {
    public static void main(String[] args) {
        try (BufferedReader in = new BufferedReader(new InputStreamReader(System.in))) {
            int N = Integer.parseInt(in.readLine());
            for (int i = 0; i < N; ++i) {
                String s = in.readLine();
                int idx = s.indexOf(" ");
                int x = Integer.parseInt(s.substring(0, idx));
                int y = Integer.parseInt(s.substring(idx + 1));
            }
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
}
  • Main06.java - String.indexOf(int)とInteger.parseInt(String)
import java.io.*;

public class Main06 {
    public static void main(String[] args) {
        try (BufferedReader in = new BufferedReader(new InputStreamReader(System.in))) {
            int N = Integer.parseInt(in.readLine());
            for (int i = 0; i < N; ++i) {
                String s = in.readLine();
                int idx = s.indexOf(' ');
                int x = Integer.parseInt(s.substring(0, idx));
                int y = Integer.parseInt(s.substring(idx + 1));
            }
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
}
  • Main07.java - StringBuilder.indexOf(" ")とInteger.parseInt(String)
import java.io.*;

public class Main07 {
    public static void main(String[] args) {
        try (BufferedReader in = new BufferedReader(new InputStreamReader(System.in))) {
            int N = Integer.parseInt(in.readLine());
            for (int i = 0; i < N; ++i) {
                StringBuilder sb = new StringBuilder(in.readLine());
                int idx = sb.indexOf(" ");
                int x = Integer.parseInt(sb.substring(0, idx));
                int y = Integer.parseInt(sb.substring(idx + 1));
            }
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
}

データ生成

データは以下のスクリプトで生成した。

#! /bin/bash

for n in 80000 160000 320000 640000 1280000 ; do
    ( echo ${n} ; for ((i = 1; i <= n; ++i)); do echo "${i} ${i}" ; done ) > in/$(printf "%07d" ${n}).txt
done

実行スクリプト

テストの実行は以下のスクリプトで行った。

#! /bin/bash

for cls in $@ ; do
    javac -d . ${cls}.java || exit 1
done
for f in in/*.txt ; do
    echo "===${f}==="
    for cls in $@ ; do
        printf "%-8s: " ${cls}
        cat ${f} | /usr/bin/time -f "%MKB / %esec" java -Xms1192m -Xmx1192m ${cls}
    done
done

以下のように呼び出す。

$ ./run.sh Main01 Main02 Main03 Main04 Main05 Main06 Main07

実行結果

出力結果は以下の通り。

===in/0080000.txt===
Main01  : 157044KB / 0.63sec
Main02  : 62940KB / 0.28sec
Main03  : 50528KB / 0.20sec
Main04  : 128936KB / 0.45sec
Main05  : 48324KB / 0.18sec
Main06  : 46600KB / 0.18sec
Main07  : 52804KB / 0.18sec
===in/0160000.txt===
Main01  : 265428KB / 0.85sec
Main02  : 88084KB / 0.35sec
Main03  : 67468KB / 0.25sec
Main04  : 217240KB / 0.60sec
Main05  : 59660KB / 0.26sec
Main06  : 60032KB / 0.21sec
Main07  : 76748KB / 0.24sec
===in/0320000.txt===
Main01  : 356544KB / 1.00sec
Main02  : 138256KB / 0.40sec
Main03  : 105100KB / 0.29sec
Main04  : 355560KB / 0.91sec
Main05  : 88500KB / 0.32sec
Main06  : 87328KB / 0.28sec
Main07  : 116480KB / 0.34sec
===in/0640000.txt===
Main01  : 357572KB / 1.35sec
Main02  : 238488KB / 0.50sec
Main03  : 177380KB / 0.43sec
Main04  : 357616KB / 0.92sec
Main05  : 127000KB / 0.36sec
Main06  : 129108KB / 0.33sec
Main07  : 186420KB / 0.37sec
===in/1280000.txt===
Main01  : 356480KB / 2.14sec
Main02  : 354196KB / 0.70sec
Main03  : 321064KB / 0.51sec
Main04  : 356188KB / 1.33sec
Main05  : 216928KB / 0.45sec
Main06  : 212696KB / 0.46sec
Main07  : 315560KB / 0.50sec

このままだと分かりづらいので、メモリと実行時間に分けて一覧表にしてみる。

  • メモリ使用量(KB)
テストケース\行数 80000 160000 320000 640000 1280000
Main01 157044 265428 356544 357572 356480
Main02 62940 88084 138256 238488 354196
Main03 50528 67468 105100 177380 321064
Main04 128936 217240 355560 357616 356188
Main05 48324 59660 88500 127000 216928
Main06 46600 60032 87328 129108 212696
Main07 52804 76748 116480 186420 315560
  • 実行時間(秒)
テストケース\行数 80000 160000 320000 640000 1280000
Main01 0.63 0.85 1.00 1.35 2.14
Main02 0.28 0.35 0.40 0.50 0.70
Main03 0.20 0.25 0.29 0.43 0.51
Main04 0.45 0.60 0.91 0.92 1.33
Main05 0.18 0.26 0.32 0.36 0.45
Main06 0.18 0.21 0.28 0.33 0.46
Main07 0.18 0.24 0.34 0.37 0.50

メモリ使用量、実行時間ともに、以下の2つが処理が単純なので効率が良いが、String.split(String)を使う場合に比べてコードが長くなる。

  • Main05.java - String.indexOf(String)とInteger.parseInt(String)
    • String.indexOf(" ")で分割位置を求めて分割し、Integer.parseInt(String)でint化
  • Main06.java - String.indexOf(int)とInteger.parseInt(String)
    • String.indexOf(' ')で分割位置を求めて分割し、Integer.parseInt(String)でint化

コードの単純さでは以下の2つが分かりやすいが、上の2つに比べると処理効率が悪い。

  • Main02.java - String.split(" ")とInteger.parseInt(String)
    • 単なる1文字から成る文字列で分割させてInteger.parseInt(String)でint化
  • Main04.java - String.split("[ ]")とInteger.parseInt(String)
    • 正規表現"[ ]"で分割させてInteger.parseInt(String)でint化

これは、Stringクラスのソースコードを見ると分かるのだが、Main02のケースでは内部的にArrayListを生成するので、メモリと処理時間を少し余計に食う。また、Main04のケースではPatternクラスに移譲しているので更にメモリと処理時間を食う。

プログラミングコンテストのような処理速度の速さが求められるケースでは、Main01のScannerを使うケースは読み込むデータが少量の場合に限られるだろう。Main03のStringTokenizerを使うケースは、コンテストにおいてはFastScannerという自前実装の中でよく見る。

Main05とMain06が処理効率的には良いが、文字列が3つ以上のトークンから成る場合を考えると処理が面倒になってくるので、その場合は、メモリ等を多少食うが、素直にString.split(" ")を使うのが良いだろう。

mapのoperator[]の罠

mapを使ったあるプログラムを書いていて、やたらとメモリを食うので、何だろうといろいろ試行錯誤しながら調べてみたら、どうもmapの使い方に問題があるのではないかということが分かってきた。

mapのリファレンスを探して読んでみると、以下のようなことが書いてある。

https://cpprefjp.github.io/reference/map/map/op_at.html

戻り値

キーxに対応する値を返す。対応する要素が存在しない場合は、要素をデフォルト構築して参照を返す。

「デフォルト構築」ってなんぞや?・・・

そこで、(いろいろすっ飛ばして)検証プログラムを書いてみた。

#include <iostream>
#include <map>

using namespace std;

int main(int argc, char** argv) {
    map<int, int*> m;

    int a = 1;
    int b = 2;

    // (1)
    {
        map<int, int*>::iterator it = m.find(1);
        cout << "(1) " << (it == m.end()) << endl;
    }

    // (2)
    {
        int* p = m[1];
        cout << "(2) " << (p == NULL) << endl;
    }

    // (3)
    {
        map<int, int*>::iterator it = m.find(1);
        cout << "(3) " << (it == m.end()) << ":" << (it->second == NULL) << endl;
    }

    // (4)
    {
        m[1] = &a;
        map<int, int*>::iterator it = m.find(1);
        cout << "(4) " << (it == m.end()) << ":" << (it->second == NULL) << ":" << (it->second == &a) << endl;
    }

    return EXIT_SUCCESS;
}

出力は以下のようになる。

(1) 1
(2) 1
(3) 0:1
(4) 0:0:1

(1)ではitm.end()に等しいのに、(2)でm[1]をやった後に(3)でもう一度findを使うと、今度はm.end()と等しくならなくなっている、つまり、mapの中に何かしらのエントリが存在する状態になっているようだ。

(4)はついでだが、m[1]に何かを代入すると、当然ながらその値がmapに入ることになる。

これは罠だなぁ‥覚えておこう‥