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

Question

極端な例えですが、10次元配列 Arr10の一番深い(?)ところにある値^_^を取り出すときと、その配列Arr10の全ての値を一次元に収めたArr1から同じ値(^_^)を取り出すのでは、処理速度、処理負荷、処理効率はどちらがいいですか?

######条件 / 質問

• Arr1に格納される値はArr10に格納されている値の並び(人目線)と同じ

/* 例 */
Arr10 = [['^'], ['_'], ["^_^"];
Arr1 = ['^', '_', "^_^"];

• 取り出す値^_^は人間から見て配列の一番最後に存在する
• 言語は問わない

---

• 多次元配列と通常の配列に同じ値を同じ量(条件の例と同じ意味)入れた時、どちらが処理効率(速度、負荷)がいいか?

• 次元数及び格納する値が増えることによりArr10とArr1の優勢劣勢は逆転するのか?

• インタプリタ、コンパイラ言語で違いはあるのか?

質問に不自然な点があればご指摘ください。(初心者なので...)スクリプト言語

Answer 1

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倍ぐらい三次元の方が遅かったです。

Comments

[退会済みユーザー]

検証までしてくださりありがとうございます!
とても参考になりました!

Answer 2

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

Comments

[退会済みユーザー]

ありがとうございます!
参考になりました!

Answer 3

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

Comments

[退会済みユーザー]

ありがとうございます!
参考になりました!

Answer 4

こんにちは。

配列ということですので、全要素に対してランダムアクセスできるものと考えます。
話を簡単にするため、MxNの2次元配列を想定します。

int foo[M][N];
int bar[M*N];
の例えば(i, j)要素へのアクセス性能を考えてみます。

これはfoo[i][j]へのアクセスとbar[iN+j]へのアクセスの比較に帰着できます。
foo[i][j]も内部的にiN+jを計算します。
すると、最適化されたiN+jの計算速度と、汎用な機能を用いたiN+jの計算速度の差になります。
コンパイラの場合も前者の方が僅かに速いかも知れませんが、恐らく大差ないと思います。
インタプリタの場合、前者はCやC++言語等のコンパイラが生成したコードで計算され、後者はインタプリタで計算されますので、前者の方が高速に処理される筈です。

Comments

[退会済みユーザー]

ありがとうございます!
内部のことを考えるのも大事ですね!表面ばかりにとらわれていました!
参考になりました!

Answer 5

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などにも影響されるので、常に同様の効率を発揮するわけではありません。
どちらの種類の多次元配列にせよ、不必要な多次元配列の使用は可読性や処理効率を下げるので避けるべきですが、かと言って無理やり一次元配列にする必要はありません。

Comments

[退会済みユーザー]

ありがとうございます!
参考になりました!

Answer 6

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

Comments

[退会済みユーザー]

ありがとうございます!
参考になりました!

Answer 7

処理系/実装依存じゃないですか?

C/C++ だと多次元配列(固定長)は内部的に一次元として扱われますし。
可変長だとn次元配列上の要素参照にはn回の間接参照を伴うハズ。

Comments

[退会済みユーザー]

ありがとうございます!
参考になりました!