質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

プログラミング言語

プログラミング言語はパソコン上で実行することができるソースコードを記述する為に扱う言語の総称です。

配列

配列は、各データの要素(値または変数)が連続的に並べられたデータ構造です。各配列は添え字(INDEX)で識別されています。

Q&A

解決済

7回答

11924閲覧

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

退会済みユーザー

退会済みユーザー

総合スコア0

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

プログラミング言語

プログラミング言語はパソコン上で実行することができるソースコードを記述する為に扱う言語の総称です。

配列

配列は、各データの要素(値または変数)が連続的に並べられたデータ構造です。各配列は添え字(INDEX)で識別されています。

0グッド

0クリップ

投稿2016/08/25 07:52

編集2016/08/25 07:57

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

######条件 / 質問

  • Arr1に格納される値はArr10に格納されている値の並び(人目線)と同じ
/* 例 */ Arr10 = [['^'], ['_'], ["^_^"]; Arr1 = ['^', '_', "^_^"];
  • 取り出す値^_^は人間から見て配列の一番最後に存在する
  • 言語は問わない

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

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

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

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

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答7

0

Rubyで三次元ですが検証コードを書いてみました。

Ruby

1# frozen_string_literal: true 2 3def create_three1(l, m, n) 4 Array.new(l * m * n) do |i| 5 [i % l, i / l % m, i / l / m].join('-') 6 end 7end 8 9def get_three1(l, m, _n, list, x, y, z) 10 list[x + y * l + z * l * m] 11end 12 13def create_three3(l, m, n) 14 Array.new(n) do |i| 15 Array.new(m) do |j| 16 Array.new(l) do |k| 17 [k, j, i].join('-') 18 end 19 end 20 end 21end 22 23def get_three3(_l, _m, _n, list, x, y, z) 24 list[z][y][x] 25end 26 27if __FILE__ == $PROGRAM_NAME 28 size = 100 29 list1 = create_three1(size, size, size) 30 list3 = create_three3(size, size, size) 31 rs_list = 100000.times.each.map { [rand(size), rand(size), rand(size)] } 32 33 begin_time = Time.now 34 rs_list.each do |rs| 35 get_three1(size, size, size, list1, rs[0], rs[1], rs[2]) 36 end 37 end_time = Time.now 38 puts "#{((end_time - begin_time) * 1000).to_i}ms" 39 40 begin_time = Time.now 41 rs_list.each do |rs| 42 get_three3(size, size, size, list3, rs[0], rs[1], rs[2]) 43 end 44 end_time = Time.now 45 puts "#{((end_time - begin_time) * 1000).to_i}ms" 46end

1.5〜2倍ぐらい三次元の方が遅かったです。

投稿2016/08/25 11:51

raccy

総合スコア21733

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

退会済みユーザー

退会済みユーザー

2016/08/25 13:24

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

0

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

投稿2016/08/25 10:33

Yatsurugi

総合スコア1628

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

退会済みユーザー

退会済みユーザー

2016/08/25 10:48

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

0

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

投稿2016/08/25 09:57

catsforepaw

総合スコア5938

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

退会済みユーザー

退会済みユーザー

2016/08/25 10:49

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

0

ベストアンサー

こんにちは。

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

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

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

投稿2016/08/25 09:17

Chironian

総合スコア23272

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

退会済みユーザー

退会済みユーザー

2016/08/25 10:48

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

0

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

投稿2016/08/25 08:27

intelf___

総合スコア868

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

退会済みユーザー

退会済みユーザー

2016/08/25 10:48

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

0

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

投稿2016/08/25 08:27

PineMatsu

総合スコア3579

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

退会済みユーザー

退会済みユーザー

2016/08/25 10:48

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

0

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

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

投稿2016/08/25 08:09

編集2016/08/25 08:20
episteme

総合スコア16614

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

退会済みユーザー

退会済みユーザー

2016/08/25 10:48

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

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問