1次元配列と多次元配列の処理効率の違い!

Question

極端な例えですが、10次元配列 ```Arr10```の一番深い(?)ところにある値```^_^```を取り出すときと、その配列```Arr10```の全ての値を一次元に収めた```Arr1```から同じ値(```^_^```)を取り出すのでは、処理速度、処理負荷、処理効率はどちらがいいですか?

######条件 / 質問
- ```Arr1```に格納される値は```Arr10```に格納されている値の並び(人目線)と同じ
```
/* 例 */
Arr10 = [['^'], ['_'], ["^_^"];
Arr1 = ['^', '_', "^_^"];
```
- 取り出す値```^_^```は人間から見て配列の一番最後に存在する
- 言語は問わない
---

- 多次元配列と通常の配列に同じ値を同じ量(条件の例と同じ意味)入れた時、どちらが処理効率(速度、負荷)がいいか?

- 次元数及び格納する値が増えることにより```Arr10```と```Arr1```の優勢劣勢は逆転するのか?

- インタプリタ、コンパイラ言語で違いはあるのか?

```質問に不自然な点があればご指摘ください。(初心者なので...)```スクリプト言語

Accepted Answer

こんにちは。

配列ということですので、全要素に対してランダムアクセスできるものと考えます。
話を簡単にするため、MxNの2次元配列を想定します。

int foo[M][N];
int bar[M*N];
の例えば(i, j)要素へのアクセス性能を考えてみます。

これはfoo[i][j]へのアクセスとbar[i*N+j]へのアクセスの比較に帰着できます。
foo[i][j]も内部的にi*N+jを計算します。
すると、最適化されたi*N+jの計算速度と、汎用な機能を用いたi*N+jの計算速度の差になります。
コンパイラの場合も前者の方が僅かに速いかも知れませんが、恐らく大差ないと思います。
インタプリタの場合、前者はCやC++言語等のコンパイラが生成したコードで計算され、後者はインタプリタで計算されますので、前者の方が高速に処理される筈です。

Answer

Rubyで三次元ですが検証コードを書いてみました。
```Ruby
# frozen_string_literal: true

def create_three1(l, m, n)
  Array.new(l * m * n) do |i|
    [i % l, i / l % m, i / l / m].join('-')
  end
end

def get_three1(l, m, _n, list, x, y, z)
  list[x + y * l + z * l * m]
end

def create_three3(l, m, n)
  Array.new(n) do |i|
    Array.new(m) do |j|
      Array.new(l) do |k|
        [k, j, i].join('-')
      end
    end
  end
end

def get_three3(_l, _m, _n, list, x, y, z)
  list[z][y][x]
end

if __FILE__ == $PROGRAM_NAME
  size = 100
  list1 = create_three1(size, size, size)
  list3 = create_three3(size, size, size)
  rs_list = 100000.times.each.map { [rand(size), rand(size), rand(size)] }

  begin_time = Time.now
  rs_list.each do |rs|
    get_three1(size, size, size, list1, rs[0], rs[1], rs[2])
  end
  end_time = Time.now
  puts "#{((end_time - begin_time) * 1000).to_i}ms"

  begin_time = Time.now
  rs_list.each do |rs|
    get_three3(size, size, size, list3, rs[0], rs[1], rs[2])
  end
  end_time = Time.now
  puts "#{((end_time - begin_time) * 1000).to_i}ms"
end
```
1.5〜2倍ぐらい三次元の方が遅かったです。

Answer

一次元よりも配列の方が早そうですが、
システム環境基準やアルゴリズムに
よると思います。

Answer

多次元構造のデータを扱うなら、ほとんどの場合、元の構造に合わせた多次元配列の方が効率がいいです。そうでなければ各種プログラミング言語で多次元配列をサポートしている意味がありません。
1次元構造のデータを扱うなら、ほとんどの場合1次元配列の方が効率がいいです。というか、1次元構造のデータを多次元配列に格納するメリットはありません。

Answer

c言語は演算を行って多次元配列のアドレスを求めます。
メモリ:0123456789...番地
[0][0]=0番地
[0][1]=1番地
[0][2]=2番地
[1][0]=3番地
[1][1]=4番地
[1][2]=5番地
みたいな感じで、[0][0]を基準にアドレスを計算します。
2次元番号*要素数+1次元番号=番地
みたいな感じですかね。実際に内部を覗いたわけではないのでわかりません。
要素数が増えるほど計算に時間がかかります。(掛け算ができるCPUなら変わらない)

javaなどの言語は、一次元配列のオブジェクトの中に更に一次元配列のオブジェクトを格納して、それを繰り返すことで多次元配列を実装します。
一番外側の一次元配列にアクセスしたあと、その内側の一次元配列にアクセスしていきます。
単純に考えると、二次元配列へのアクセス時間は一次元配列へのアクセス時間の倍です。

**注意**
特にc言語に関しては検定用に教わった内容や挙動からの推察なので、あまり真に受けないでください。
演算の効率はOSなどにも影響されるので、常に同様の効率を発揮するわけではありません。
どちらの種類の多次元配列にせよ、不必要な多次元配列の使用は可読性や処理効率を下げるので避けるべきですが、かと言って無理やり一次元配列にする必要はありません。

Answer

多次元配列の実装に依るでしょうね。

Answer

処理系/実装依存じゃないですか?

C/C++ だと多次元配列(固定長)は内部的に一次元として扱われますし。
可変長だとn次元配列上の要素参照にはn回の間接参照を伴うハズ。

関連した質問