配列の圧縮について

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

配列の圧縮について

#1

投稿記事 by 徹朗 » 5年前

はじめまして, 配列の圧縮方法について質問させていただきます.

例えば,
0 0 1 0 4
0 0 2 0 3
0 0 0 0 0
0 0 0 0 5
0 0 0 0 0
のような正方行列の配列について, 0のみの行(列)についてその行(列)を削除して
1 4
2 3
0 5
のような新たな配列を作成したいのですが, うまく行きません.

2*2程度の行列であれば2次元配列を1次元配列に落として以下の様なプログラムを作成して実装できたのですが,
10*10以上の行列で行うと, この方法では不格好になってしまいます.

コード:

#define N 2

int main(){
int i, j;
int a[SIZE] = {0,1};
int b[SIZE] = {0,2};

  for(i = 0; i < SIZE; i++){
    if(a[i] == 0 && b[i] == 0){
      for(j = i+1; j < SIZE; j++){
	a[j-1] = a[j];
	b[j-1] = b[j];
      }
      i--;
    }
  }
}
よい方法をご存知の方, 回答宜しくお願いします.

cattail
記事: 75
登録日時: 6年前

Re: 配列の圧縮について

#2

投稿記事 by cattail » 5年前

0 0 1 0 4
0 0 2 0 3
0 0 0 0 0
0 0 0 0 5
0 0 0 0 0

を圧縮する方法として
例えば、横方向に、

00104
00203
\05
\045
\05

になるようにすれば
圧縮率は低いですが損失が0でカンタンです。
また、縦に圧縮するともう少し良くなります。
この場合、ですけども。

全然ダメですね、ごめんなさい。

徹朗
記事: 6
登録日時: 5年前

Re: 配列の圧縮について

#3

投稿記事 by 徹朗 » 5年前

返信有難うございます.

たしかにその方法でも圧縮が出来ますね, ただ, 行(列)がすべて0となった時のみに削除を行いたいです.
ちなみにいい忘れていましたが, 元のデータは2次元配列に格納されています.
引き続き, 回答をよろしくお願いします...

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

Re: 配列の圧縮について

#4

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

よい方法かはわかりませんが、新たな配列を作成しやすいJavaで素直に書いてみました。
エラーチェックは省略しました。

コード:

public class Main {
	public static int[][] assyuku(int[][] array) {
		int[] rowData = new int[array.length];
		int[] colData = new int[array[0].length];
		int rowDataSize = 0;
		int colDataSize = 0;
		// 行について調査する
		for (int i = 0; i < array.length; i++) {
			for (int j = 0; j < array[i].length; j++) {
				if (array[i][j] != 0) {
					// 0以外のデータがあったら、その行を拾う
					rowData[rowDataSize++] = i;
					break;
				}
			}
		}
		// 列について調査する
		for (int j = 0; j < array[0].length; j++) {
			for (int i = 0; i < array.length; i++) {
				if (array[i][j] != 0) {
					// 0以外のデータがあったら、その列を拾う
					colData[colDataSize++] = j;
					break;
				}
			}
		}
		// 結果を作成する
		int[][] result = new int[rowDataSize][colDataSize];
		for (int i = 0; i < rowDataSize; i++) {
			for (int j = 0; j < colDataSize; j++) {
				result[i][j] = array[rowData[i]][colData[j]];
			}
		}
		return result;
	}

	public static void printArray(int[][] array) {
		for (int i = 0; i < array.length; i++) {
			if (array[i].length > 0) System.out.print(array[i][0]);
			for (int j = 1; j < array[i].length; j++) {
				System.out.print(" " + array[i][j]);
			}
			System.out.println();
		}
	}

	public static void doTest(int[][] data, String name) {
		System.out.println(name + " input");
		printArray(data);
		int[][] res = assyuku(data);
		System.out.println(name + " output");
		printArray(res);
	}

	public static void main(String[] args) {
		int[][] case1 = {
			{0, 1},
			{0, 2}
		};
		int[][] case2 = {
			{0, 0, 1, 0, 4},
			{0, 0, 2, 0, 3},
			{0, 0, 0, 0, 0},
			{0, 0, 0, 0, 5},
			{0, 0, 0, 0, 0}
		};
		doTest(case1, "case 1");
		doTest(case2, "case 2");
	}
}
実行結果

コード:

case 1 input
0 1
0 2
case 1 output
1
2
case 2 input
0 0 1 0 4
0 0 2 0 3
0 0 0 0 0
0 0 0 0 5
0 0 0 0 0
case 2 output
1 4
2 3
0 5
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

Rittai_3D
記事: 525
登録日時: 7年前

Re: 配列の圧縮について

#5

投稿記事 by Rittai_3D » 5年前

言語が指定されていないので、C++で大雑把に書いてみました。
エラーチェックはしていないです。
► スポイラーを表示
実行結果です→http://melpon.org/wandbox/permlink/VCJXV3ASNYAUDuwc
► スポイラーを表示
#追記
出力結果が空白が無くて見にくかったのでちょっと修正しました。
http://melpon.org/wandbox/permlink/WJ9eD7EUpZiOha3N
#さらに追記
何度も何度もすいません。
要素が一つの時に0を追加するのを忘れていました。
http://melpon.org/wandbox/permlink/GaOQruZfwaK2p72q
最後に編集したユーザー Rittai_3D on 2015年7月10日(金) 23:43 [ 編集 2 回目 ]
初心者です

徹朗
記事: 6
登録日時: 5年前

Re: 配列の圧縮について

#6

投稿記事 by 徹朗 » 5年前

[quote="みけCAT" id=3,16804,131607]よい方法かはわかりませんが、新たな配列を作成しやすいJavaで素直に書いてみました。

返信有難うございます.
Javaは学んだことがなかったため詳細は理解できませんでしたが, コメントアウトを参考にC言語で実装することが出来ました.
ありがとうございました!

徹朗
記事: 6
登録日時: 5年前

Re: 配列の圧縮について

#7

投稿記事 by 徹朗 » 5年前

[quote="Rittai_3D" id=3,16804,131608]言語が指定されていないので、C++で大雑把に書いてみました。

返信有難うございます, 無事解決出来ました!
ありがとうございました!

かずま

Re: 配列の圧縮について

#8

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

徹朗 さんが書きました:Javaは学んだことがなかったため詳細は理解できませんでしたが, コメントアウトを参考にC言語で実装することが出来ました.
他の人の参考になるように、その C のプログラムを提示してください。

私は、次のように書いてみました。

コード:

#include <stdio.h>

void compress(void *p, int sz, int *pm, int *pn)
{
    int *a = p, i, j, m, n;
    for (m = i = 0; i < sz; i++)
        for (j = 0; j < sz; j++) {
            if (a[i*sz + j]) {
                if (m < i)
                    for (j = 0; j < sz; j++) a[m*sz + j] = a[i*sz + j];
                m++;
                break;
            }
        }
    for (n = j = 0; j < sz; j++)
        for (i = 0; i < m; i++) {
            if (a[i*sz + j]) {
                if (n < j)
                    for (i = 0; i < m; i++) a[i*sz + n] = a[i*sz + j];
                n++;
                break;
            }
        }
    *pm = m, *pn = n;
}

void print(void *p, int sz, int m, int n)
{
    int *a = p, i, j;
    for (i = 0; i < m; i++) {
        for (j = 0; j < n; j++)
            printf(" %4d", a[i*sz + j]);
        putchar('\n');
    }
}

int a[2][2] = {
    { 0, 1 },
    { 0, 2 },
};
int b[5][5] = {
    { 0, 0, 1, 0, 4 },
    { 0, 0, 2, 0, 3 },
    { 0, 0, 0, 0, 0 },
    { 0, 0, 0, 0, 5 },
    { 0, 0, 0, 0, 0 },
};

int main(void)
{
    int m, n;

    puts("A input"), print(a, 2, 2, 2);
    compress(a, 2, &m, &n);
    puts("A output"), print(a, 2, m, n);

    puts("B input"), print(b, 5, 5, 5);
    compress(b, 5, &m, &n);
    puts("B output"), print(b, 5, m, n);

    return 0;
}

徹朗
記事: 6
登録日時: 5年前

Re: 配列の圧縮について

#9

投稿記事 by 徹朗 » 5年前

かずま さんが書きました:
徹朗 さんが書きました:Javaは学んだことがなかったため詳細は理解できませんでしたが, コメントアウトを参考にC言語で実装することが出来ました.
他の人の参考になるように、その C のプログラムを提示してください。

返信有難うございます.
失礼しました, 非常に見づらいですがこのように書きました.

コード:

#include <stdio.h>

#define N 5

int main(){

  int array[N][N] = {
    {0, 0, 1, 0, 4},
    {0, 0, 2, 0, 3},
    {0, 0, 0, 0, 0},
    {0, 0, 0, 0, 5},
    {0, 0, 0, 0, 0}
  };

  int a1[N][N] = {
    {0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0}
  };

  int a2[N][N] = {
    {0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0}
  };

  int i, j, k;
  int count = 0;
  int count2 = 0;

  for(i = 0; i < N; i++){
    for(j = 0; j < N; j++){
      if(array[i][j] != 0){
        for(k = j; k < N; k++){
          a1[count][k] = array[i][k];
        }
        count++;
        break;
      }
    }
  }

  for(j = 0; j < N; j++){
    for(i = 0; i < N; i++){
      if(array[i][j] != 0){
        for(k = i; k < N; k++){
          a2[k][count2] = a1[k][j];
        }
        count2++;
        break;
      }
    }
  }

  /* 表示 */
  int a3[N-count2][N-count];

  for(i = 0; i < N-count2; i++){
    for(j = 0; j < N-count; j++){
      a3[i][j] = a2[i][j];
      printf("%d ", a3[i][j]);
    }
    printf("\n");
  }

  return 0;
}

かずま

Re: 配列の圧縮について

#10

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

徹朗 さんが書きました:失礼しました, 非常に見づらいですがこのように書きました.
{0, 0, 1, 0, 4}, を
{6, 0, 1, 0, 4}, に変えてみてください。
望みどおりの結果にはならないでしょう。

また int a3[N-count2][N-count]; のような、
変数による配列のサイズの宣言は gcc の拡張機能であり、
C の規格に準拠したコンパイラでは使用できないはずです。

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

Re: 配列の圧縮について

#11

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

かずま さんが書きました:また int a3[N-count2][N-count]; のような、
変数による配列のサイズの宣言は gcc の拡張機能であり、
C の規格に準拠したコンパイラでは使用できないはずです。
これは違うのではないでしょうか?
gccの-pedantic-errorssオプションを付けてもC99としてコンパイルが通りました。
また、N1256の117~118ページ(PDF上では129~130ページ)にも、
変数による配列(variable length array type)のサイズの宣言の例が載っています。
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

徹朗
記事: 6
登録日時: 5年前

Re: 配列の圧縮について

#12

投稿記事 by 徹朗 » 5年前

かずま さんが書きました:
徹朗 さんが書きました:失礼しました, 非常に見づらいですがこのように書きました.
{0, 0, 1, 0, 4}, を
{6, 0, 1, 0, 4}, に変えてみてください。
望みどおりの結果にはならないでしょう。

失礼しました, 配列を表示する部分が正しくありませんでした.
ご指摘ありがとうございます.

コード:

  /* 表示 */
  int a3[count][count2];

  for(i = 0; i < count; i++){
    for(j = 0; j < count2; j++){
      a3[i][j] = a2[i][j];
      printf("%d ", a3[i][j]);
    }
    printf("\n");
  }

かずま

Re: 配列の圧縮について

#13

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

みけCAT さんが書きました:
かずま さんが書きました:また int a3[N-count2][N-count]; のような、
変数による配列のサイズの宣言は gcc の拡張機能であり、
C の規格に準拠したコンパイラでは使用できないはずです。
これは違うのではないでしょうか?
gccの-pedantic-errorssオプションを付けてもC99としてコンパイルが通りました。
また、N1256の117~118ページ(PDF上では129~130ページ)にも、
変数による配列(variable length array type)のサイズの宣言の例が載っています。
おっしゃる通りです。「VC++ ではコンパイルできません」と言いたかったのを、
他にも Borland C Compile なんかもそうだろうから違った表現にしようとして、
あんなふうに書いてしました。

C99 からは可変長配列が使えるので、私のプログラムも次のように書けます。

コード:

#include <stdio.h>

void compress(int sz, int a[sz][sz], int *pm, int *pn)
{
    int i, j, m, n;
    for (m = i = 0; i < sz; i++)
        for (j = 0; j < sz; j++)
            if (a[i][j]) {
                if (m < i)
                    for (j = 0; j < sz; j++) a[m][j] = a[i][j];
                m++;
                break;
            }
    for (n = j = 0; j < sz; j++)
        for (i = 0; i < m; i++)
            if (a[i][j]) {
                if (n < j)
                    for (i = 0; i < m; i++) a[i][n] = a[i][j];
                n++;
                break;
            }
    *pm = m, *pn = n;
}

void print(int sz, int a[sz][sz], int m, int n)
{
    int i, j;
    for (i = 0; i < m; i++) {
        for (j = 0; j < n; j++)
            printf(" %4d", a[i][j]);
        putchar('\n');
    }
}

int a[2][2] = {
    { 0, 1 },
    { 0, 2 },
};
int b[5][5] = {
    { 0, 0, 1, 0, 4 },
    { 0, 0, 2, 0, 3 },
    { 0, 0, 0, 0, 0 },
    { 0, 0, 0, 0, 5 },
    { 0, 0, 0, 0, 0 },
};

int main(void)
{
    int m, n;

    puts("A input"), print(2, a, 2, 2);
    compress(2, a, &m, &n);
    puts("A output"), print(2, a, m, n);

    puts("B input"), print(5, b, 5, 5);
    compress(5, b, &m, &n);
    puts("B output"), print(5, b, m, n);

    return 0;
}
使用メモリサイズやコピー回数がなるべく少なくなることを意識したプログラムです。

閉鎖

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