HHeLiBeXの日記 正道編

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

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

Java

ふと、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(" ")を使うのが良いだろう。