2次元配列の組み合わせについて

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
ace-k@
記事: 5
登録日時: 1年前

2次元配列の組み合わせについて

#1

投稿記事 by ace-k@ » 1年前

はじめまして.
C++で2次元配列 (vector_A) から任意の2行を取り出し,その2行の要素を内積した値を組み合わせ配列 (vector_B) の要素とする新たな2次元配列を作りたいのですが,どのように実装すればよいでしょうか?
教えて頂けると幸いです.

具体的には,以下のようなことをやりたいと考えています.

コード:

//元の配列: ( i=3, j=4)
std::vector<int> vector_A[i][j] = { 	0,1,0,1,
					1,1,0,0,
					1,1,0,1 };

//生成したい配列: ( i=3, i'=3)                                                  
std::vector<int> vector_B[i][i'] = {	2,1,2,
					1,2,2,
					2,2,3	 };
 

アバター
みけCAT
記事: 6182
登録日時: 8年前
住所: 千葉県
連絡を取る:

Re: 2次元配列の組み合わせについて

#2

投稿記事 by みけCAT » 1年前

ace-k@ さんが書きました:
1年前
どのように実装すればよいでしょうか?
  • パフォーマンス優先か、保守性・わかりやすさ優先か
  • 移植性を重視するか、特定の環境(CPU・GPU・OS・コンパイラなど)だけで動けばいいか
  • 要素の型は固定か、汎用にするか
などの条件によって変わってくると思うので、条件を教えてください。
ace-k@ さんが書きました:
1年前

コード:

//元の配列: ( i=3, j=4)
std::vector<int> vector_A[i][j] = { 	0,1,0,1,
					1,1,0,0,
					1,1,0,1 };

//生成したい配列: ( i=3, i'=3)                                                  
std::vector<int> vector_B[i][i'] = {	2,1,2,
					1,2,2,
					2,2,3	 };
 
それぞれの要素がstd::vector<int>なのですか?
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

ace-k@
記事: 5
登録日時: 1年前

Re: 2次元配列の組み合わせについて

#3

投稿記事 by ace-k@ » 1年前

ご回答ありがとうございます.
情報が足らず申し訳ありません.

実際の要素数はvector_Bが500×500程度になります.
ですが,実装は計算速度は気にせず,分かりやすさを重視したいと思っております.
また,移植性は気にせず,特定の環境で動けばよいです.
私の開発環境は,CPU:core-i7-4810MQ, GPU:Quadro K2100M, OS:windows7, VisualStudio2010pro になります.
要素の型は,int型のみです.

また,2次元配列をvectorで生成しており,各要素はint型になります.

よろしくお願いいたします.

かずま

Re: 2次元配列の組み合わせについて

#4

投稿記事 by かずま » 1年前

ace-k@ さんが書きました:
1年前

コード:

//元の配列: ( i=3, j=4)
std::vector<int> vector_A[i][j] = { 	0,1,0,1,
					1,1,0,0,
					1,1,0,1 };

//生成したい配列: ( i=3, i'=3)                                                  
std::vector<int> vector_B[i][i'] = {	2,1,2,
					1,2,2,
					2,2,3	 };
どの 2行をとっても、内積が 3になることはないと思います。

コード:

#include <iostream>  // cout, endl
#include <vector>    // push_back, begin, end
#include <algorithm> // sort, next_permutation
using namespace std;

int iprod(vector<int>& a, vector<int>& b)  // inner product
{
	int p = 0;
	for (size_t i = 0; i < a.size(); i++) p += a[i] * b[i];
	return p;
}

int main()
{
	vector<vector<int>> a = {
		{ 0, 1, 0, 1 },
		{ 1, 1, 0, 0 },
		{ 1, 1, 0, 1 },
	};
	vector<vector<int>> b;

	size_t m = a.size();
	vector<int> p(m * (m - 1) / 2);
	for (size_t k = 0, i = 0; i < m - 1; i++)
		for (size_t j = i + 1; j < m; j++) p[k++] = iprod(a[i], a[j]);
	sort(begin(p), end(p));
	do b.push_back(p); while (next_permutation(begin(p), end(p)));

	for (size_t i = 0; i < b.size(); i++, endl(cout))
		for (size_t j = 0; j < b[i].size(); j++) cout << " " << b[i][j];
}
実行結果

コード:

 1 2 2
 2 1 2
 2 2 1

ace-k@
記事: 5
登録日時: 1年前

Re: 2次元配列の組み合わせについて

#5

投稿記事 by ace-k@ » 1年前

かずまさんご返信ありがとうございます.

コードも参考にさせて頂きます.
ただ,実行結果が私が手計算した結果と異なっているのですが...
たとえば, 行列bの {3,3} の要素は, 行列aの3行目同士の内積なので,1*1+1*1+0*0+1*1 = 3 になんると思ったのですが,
この場合,ご提示いただいたコードのどの部分を修正すると良いですか?

かずま

Re: 2次元配列の組み合わせについて

#6

投稿記事 by かずま » 1年前

3行から任意の 2行を取り出すのは、(a[0], a[1]), (a[0], a[2]),
(a[1], a[2]) の 3通りしかないと考えていました。

1つの行を取り出して、(a[0], a[0]) としてもよいし、
(a[0], a[1]) と (a[1], a[0]) も異なる組み合わせと考えるんですね。

それならもっと簡単です。

コード:

#include <iostream>  // cout, endl
#include <vector>    // push_back, begin, end
using namespace std;

int iprod(vector<int>& a, vector<int>& b)  // inner product
{
	int p = 0;
	for (size_t i = 0; i < a.size(); i++) p += a[i] * b[i];
	return p;
}

int main()
{
	vector<vector<int>> a = {
		{ 0, 1, 0, 1 },
		{ 1, 1, 0, 0 },
		{ 1, 1, 0, 1 },
	};
	size_t n = a.size();
	vector<vector<int>> b(n);

	for (size_t k = 0, i = 0; i < n; i++)
		for (size_t j = 0; j < n; j++) b[i].push_back(iprod(a[i], a[j]));

	for (size_t i = 0; i < b.size(); i++, endl(cout)) 
		for (size_t j = 0; j < b[i].size(); j++) cout << ' ' << b[i][j];
}

コード:

 2 1 2
 1 2 2
 2 2 3

かずま

Re: 2次元配列の組み合わせについて

#7

投稿記事 by かずま » 1年前

かずま さんが書きました:
1年前

コード:

	for (size_t k = 0, i = 0; i < n; i++)
		for (size_t j = 0; j < n; j++) b[i].push_back(iprod(a[i], a[j]));
「k = 0, 」は不要です。

かずま

Re: 2次元配列の組み合わせについて

#8

投稿記事 by かずま » 1年前

かずま さんが書きました:
1年前

コード:

	size_t n = a.size();
	vector<vector<int>> b(n);

	for (size_t i = 0; i < n; i++)
		for (size_t j = 0; j < n; j++) b[i].push_back(iprod(a[i], a[j]));
これだと、n x 0 の b を用意して、あとから、push_back で
列の数を増やしていますが、最初から n x n の b を用意して、
しかも、b[ i] == b[j] であることから、内積の計算回数を減らす
ことができます。

コード:

	size_t n = a.size();
	vector<vector<int>> b(n, vector<int>(n));  // b は n x n

	for (size_t i = 0; i < n; i++)
		for (size_t j = i; j < n; j++)    // j は i 以上
			b[i][j] = b[j][i] = iprod(a[i], a[j]);

かずま

Re: 2次元配列の組み合わせについて

#9

投稿記事 by かずま » 1年前

かずま さんが書きました:
1年前
しかも、b[ i] == b[j] であることから、内積の計算回数を減らす
ことができます。

コード:

訂正。b[i] == b[j] ではなく、b[i][j] == b[j][i] です。

返信

“C言語何でも質問掲示板” へ戻る