7. 二次元配列
著者:梅谷 武
各言語における二次元配列の扱いを調べる。
作成:2024-06-10
更新:2024-10-24
7.1 課題
 Ⅲ-6.配列に引き続き二次元配列に関して調べる。rows = 行数、cols = 列数は定数として固定する。
  1. 代入：rows×colsの二次元配列src,dstを生成し、src[i][j] = i * j, i=0,...,rows-1, j=0,...,cols-1.
  2. 複写：dst = src
  3. 写像：dst = f(src), f(x) = x + x.
  4. 自己写像：src = f(src), f(x) = x + x.
 C++とOCamlは64ビット整数配列、Racketは整数配列を用いる。
7.2 プログラム

C++

 copyはクラスで定義された複写代入を用いる。
 array2.cpp: 
#include <chrono>
#include <print>
#include <stdexcept>
#include <vector>
 
void test() {
  int rows = 10000, cols = 1000;
  // assign
  auto start = std::chrono::high_resolution_clock::now();
  std::vector<std::vector<long>> src(rows, std::vector<long>(cols, 0l));
  std::vector<std::vector<long>> dst(rows, std::vector<long>(cols, 0l));
  for (int i = 0; i < rows; ++i)
    for (int j = 0; j < cols; ++j)
      src[i][j] = i * j;
  auto end = std::chrono::high_resolution_clock::now();
  std::chrono::duration<double> duration = end - start;
  std::println("size = {} × {}", rows, cols);
  std::println("src: {} ---> {}", src[0][0], src[rows - 1][cols - 1]);
  std::println("assign time:{:9.6f} [sec]", duration.count());
  // copy
  start = std::chrono::high_resolution_clock::now();
  dst = src;
  end = std::chrono::high_resolution_clock::now();
  duration = end - start;
  std::println("dst: {} ---> {}", dst[0][0], dst[rows - 1][cols - 1]);
  std::println("copy time:  {:9.6f} [sec]", duration.count());
  // map
  start = std::chrono::high_resolution_clock::now();
  for (int i = 0; i < rows; ++i)
    for (int j = 0; j < cols; ++j)
      dst[i][j] = [](long x) { return x + x; }(src[i][j]);
  end = std::chrono::high_resolution_clock::now();
  duration = end - start;
  std::println("dst: {} ---> {}", dst[0][0], dst[rows - 1][cols - 1]);
  std::println("map time:   {:9.6f} [sec]", duration.count());
  // self-map
  start = std::chrono::high_resolution_clock::now();
  for (int i = 0; i < rows; ++i)
    for (int j = 0; j < cols; ++j)
      src[i][j] = [](long x) { return x + x; }(src[i][j]);
  end = std::chrono::high_resolution_clock::now();
  duration = end - start;
  std::println("src: {} ---> {}", src[0][0], src[rows - 1][cols - 1]);
  std::println("self-map:   {:9.6f} [sec]", duration.count());
}
 
int main(int argc, char *argv[]) {
  try {
    test();
  } catch (const std::logic_error &e) {
    std::println(stderr, "Logic error: {}", e.what());
  } catch (const std::runtime_error &e) {
    std::println(stderr, "Runtime error: {}", e.what());
  } catch (const std::exception &e) {
    std::println(stderr, "Another std::exception: {}", e.what());
  } catch (...) {
    std::println(stderr, "Unknown exception.");
  }
  return 0;
}


 makefile: 
CPPG = g++
CPPL = clang++
CPPFLAGS = -std=c++23 -O2
SRC = array2.cpp
EXES = array2_g array2_l
 
all: $(EXES)
 
array2_g: $(SRC)
	$(CPPG) $(CPPFLAGS) -o $@ $(SRC)
 
array2_l: $(SRC)
	$(CPPL) $(CPPFLAGS) -o $@ $(SRC)
 
clean:
	rm -f $(EXES)



$ measure ./array2_g
size = 10000 × 1000
src: 0 ---> 9989001
assign time: 0.121679 [sec]
dst: 0 ---> 9989001
copy time:   0.024020 [sec]
dst: 0 ---> 19978002
map time:    0.019999 [sec]
src: 0 ---> 19978002
self-map:    0.020031 [sec]
======================================
Process exited with status: 0
total time:  0.201912 [sec]
mem  size:     160140 [KB]
code size:        128 [KB]

$ measure ./array2_l
size = 10000 × 1000
src: 0 ---> 9989001
assign time: 0.111077 [sec]
dst: 0 ---> 9989001
copy time:   0.021460 [sec]
dst: 0 ---> 19978002
map time:    0.023139 [sec]
src: 0 ---> 19978002
self-map:    0.015875 [sec]
======================================
Process exited with status: 0
total time:  0.191916 [sec]
mem  size:     160136 [KB]
code size:        101 [KB]

OCaml

 copyは要素毎の代入を用いる。
 array2.ml: 
open Printf
 
let rows = 10000
let cols = 1000
let test =
  (* assign *)
  let start = Unix.gettimeofday () in
  let src = Array.make_matrix rows cols 0 in
  for i = 0 to rows - 1 do
    for j = 0 to cols - 1 do
      src.(i).(j) <- i * j
    done
  done;
  let end_ = Unix.gettimeofday () in
  printf "size= %d × %d\n" rows cols;
  printf "src: %d ---> %d\n" src.(0).(0) src.(rows-1).(cols-1);
  printf "assign time:%9.6f [sec]\n" (end_ -. start);
  (* copy *)
  let start = Unix.gettimeofday () in
  let dst = Array.make_matrix rows cols (-1) in
  for i = 0 to rows - 1 do
    for j = 0 to cols - 1 do
      dst.(i).(j) <- src.(i).(j)
    done
  done;
  let end_ = Unix.gettimeofday () in
  printf "dst: %d ---> %d\n" dst.(0).(0) dst.(rows-1).(cols-1);
  printf "copy time:  %9.6f [sec]\n" (end_ -. start);
  (* map *)
  let start = Unix.gettimeofday () in
  for i = 0 to rows - 1 do
    for j = 0 to cols - 1 do
      dst.(i).(j) <- (fun x -> x + x) src.(i).(j)
    done
  done;
  let end_ = Unix.gettimeofday () in
  printf "dst: %d ---> %d\n" dst.(0).(0) dst.(rows-1).(cols-1);
  printf "map time:   %9.6f [sec]\n" (end_ -. start);
  (* self-map *)
  let start = Unix.gettimeofday () in
  for i = 0 to rows - 1 do
    for j = 0 to cols - 1 do
      src.(i).(j) <- (fun x -> x + x) src.(i).(j)
    done
  done;
  let end_ = Unix.gettimeofday () in
  printf "src: %d ---> %d\n" src.(0).(0) src.(rows-1).(cols-1);
  printf "self-map:   %9.6f [sec]\n" (end_ -. start)
 
  let () =
  try
    test
  with
    | Invalid_argument msg ->
        eprintf "Logic error: %s\n" msg
    | Failure msg ->
        eprintf "Runtime error: %s\n" msg
    | exn ->
        eprintf "Another exception: %s\n" (Printexc.to_string exn)


 makefile: 
OCAMLOPT = ocamlopt
OCAMLFLAGS = -O2
LIBPATH = -I +unix
LIBS = unix.cmxa
SRC = array2.ml
EXES = array2
 
all: $(EXES)
 
array2: $(SRC)
	$(OCAMLOPT) $(OCAMLFLAGS) $(LIBPATH) -o $@ $(LIBS) $(SRC)
 
clean:
	rm -f $(EXES) *.o *.cmx *.cmi



$ measure ./array2
size= 10000 × 1000
src: 0 ---> 9989001
assign time: 0.100334 [sec]
dst: 0 ---> 9989001
copy time:   0.101480 [sec]
dst: 0 ---> 19978002
map time:    0.027907 [sec]
src: 0 ---> 19978002
self-map:    0.018420 [sec]
======================================
Process exited with status: 0
total time:  0.262737 [sec]
mem  size:     160804 [KB]
code size:       3290 [KB]

Racket

 copyは行毎のvector-copyを用いる。
 array2.rkt: 
#lang racket
(require iso-printf)
 
(define (test)
  (define rows 10000)
  (define cols 1000)
  ; assign
  (define start (current-inexact-milliseconds))
  (define src (for/vector ([i rows]) (make-vector cols 0)))
  (for ([i rows])
    (for ([j cols])
      (vector-set! (vector-ref src i) j (* i j))))
  (define end (current-inexact-milliseconds))
  (printf "size = %d × %d\n" rows cols)
  (printf "src: %d ---> %d\n"
    (vector-ref (vector-ref src 0) 0)
    (vector-ref (vector-ref src (- rows 1)) (- cols 1)))
  (printf "assign time:%9.6f [sec]\n" (/ (- end start) 1000.0))
  ; copy
  (set! start (current-inexact-milliseconds))
  (define dst (vector-map (λ (row) (vector-copy row)) src))
  (set! end (current-inexact-milliseconds))
  (printf "dst: %d ---> %d\n"
    (vector-ref (vector-ref dst 0) 0)
    (vector-ref (vector-ref dst (- rows 1)) (- cols 1)))
  (printf "copy time:  %9.6f [sec]\n" (/ (- end start) 1000.0))
  ; map
  (set! start (current-inexact-milliseconds))
  (for ([i rows])
    (for ([j cols])
      (vector-set!
        (vector-ref dst i) j
        ((λ (x) (+ x x)) (vector-ref (vector-ref src i) j)))))
  (set! end (current-inexact-milliseconds))
  (printf "dst: %d ---> %d\n"
    (vector-ref (vector-ref dst 0) 0)
    (vector-ref (vector-ref dst (- rows 1)) (- cols 1)))
  (printf "map time:   %9.6f [sec]\n" (/ (- end start) 1000.0))
  ; self-map
  (set! start (current-inexact-milliseconds))
  (for ([i rows])
    (for ([j cols])
      (vector-set!
        (vector-ref src i) j
        ((λ (x) (+ x x)) (vector-ref (vector-ref src i) j)))))
  (set! end (current-inexact-milliseconds))
  (printf "src: %d ---> %d\n"
    (vector-ref (vector-ref src 0) 0)
    (vector-ref (vector-ref src (- rows 1)) (- cols 1)))
  (printf "self-map:   %9.6f [sec]\n" (/ (- end start) 1000.0)))
 
(define (main args)
  (with-handlers
    ([exn:fail? (λ (e) (eprintf "%s\n" (exn-message e)))]
     [exn? (λ (e) (eprintf "Unexpected: %s\n" (exn-message e)))])
  (test)))
 
(main (current-command-line-arguments))



$ raco exe array2.rkt
$ measure ./array2
size = 10000 × 1000
src: 0 ---> 9989001
assign time: 0.228139 [sec]
dst: 0 ---> 9989001
copy time:   0.125182 [sec]
dst: 0 ---> 19978002
map time:    0.075887 [sec]
src: 0 ---> 19978002
self-map:    0.071697 [sec]
======================================
Process exited with status: 0
total time:  0.994747 [sec]
mem  size:     304992 [KB]
code size:      12447 [KB]
7.3 まとめ
 測定結果を表にまとめる。単位は秒[sec]。
測定項目 GCC Clang OCaml Racket
assign 0.122 0.111 0.100 0.228
copy 0.024 0.021 0.101 0.125
map 0.020 0.023 0.028 0.076
self-map 0.020 0.016 0.018 0.072
 測定時間には領域生成時間が含まれることがあり、単に既存変数へ破壊的代入をするだけの場合と差がでるので比較の際にはソースを読んで何が測定されているか見る必要がある。例えばOCamlのcopyがmapより遅いのは二次元配列:dstの生成時間が含まれるからであり、それを除けばcopyはmapより速くなると推測される。
This document is licensed under the MIT License.
Copyright (C) 2024 Takeshi Umetani