プログラミング言語Ⅰ(実習を含む。), 計算機言語Ⅰ・計算機言語演習Ⅰ, 情報処理言語Ⅰ(実習を含む。) C言語入門 第7週 プログラミング言語Ⅰ(実習を含む。), 計算機言語Ⅰ・計算機言語演習Ⅰ, 情報処理言語Ⅰ(実習を含む。)

多次元配列

多次元の値も扱いたい 例えば行列の演算(1,2次元混合) 𝐴𝑥&=𝑏 𝑎 1,1 … 𝑎 1,𝑛 ⋮ ⋱ ⋮ 𝑎 𝑚,1 … 𝑎 𝑚,𝑛 𝑥 1 ⋮ 𝑥 𝑛 &= 𝑏 1 ⋮ 𝑏 𝑚 行列は2次元 ベクトルは1次元

多次元の値も扱いたい 例えば白黒や濃淡画像(2次元) 32 64 128 32 64 128 32 64 128 192 32 64 128 32 64 128 32 64 128 32 64 128 192 32 64 128 192 128 128 192 255 128 128 192 255 x,y座標の各点をマス目で表し 各マス目の明るさを 256段階(8bit)の数値で表す 輝度値や明度値と言う それぞれのマス目の数値に応じて 光らせる明るさを調整すると 絵が描ける

多次元の値も扱いたい 例えば白黒や濃淡画像(3次元) x,y座標の各点の 光の三原色 赤緑青の明るさ(RGB値)を 数値で表す 255 255 255 255 画面を虫眼鏡で見ると こんな感じに 光っているのが見える 255 255 255 255 255

多次元の値も扱いたい 例えば白黒や濃淡画像(3次元) 遠目で見た場合や ソフトウェア上では 色が混ざって このように見える 255 255 255 255 255 255 255 255 255 255

画面表示の仕組み 方眼紙のような構造 光の三原色(RGB=赤緑青)で加法混色 通常、各色8bit(256段階)で電圧調整して明暗表現 計24bit(16,777,216色)=8bit×3(256×256×256 段階)

混色 加法混色 減法混色 画面、光 RGBカラーモデル 印刷、絵の具 CMYカラーモデル Red, Green, Blue Cyan, Magenta, Yellow R Y R M Y M Bk W G B G C B C

メモリの構成 メモリのアドレスは1次元でした 教科書 pp.52-56. 32bitのOSは32bitのアドレス空間 最大 2 32 Bytes=4GiB 64bitのOSは64bitのアドレス空間 最大 2 64 Bytes=16EiB 0x00 0x00000000 0x00000001 0x00000002 0x00000003 0xffffffff : 0x00 0x0000000000000000 0x0000000000000001 0x0000000000000002 0x0000000000000003 0xffffffffffffffff : アドレス 格納値 アドレス 格納値

二次元配列変数 1次元のメモリを折り畳んで2次元にして使う char a[3][4]; // 要素数3*4のchar型変数の宣言 教科書 pp.85-108. 二次元配列変数 1次元のメモリを折り畳んで2次元にして使う char a[3][4]; // 要素数3*4のchar型変数の宣言 a[0][0] ? a[0][1] ? a[0][2] ? a[0][3] ? a[1][0] ? a[1][1] ? a[2][3] ? ... 1行分のデータ メモリのアドレスは1次元なので 実際には2行目以降も 直線状に並んでいる [1] pp.135-137.

二次元配列変数 要素数4の配列を3つ並べた例 char a[3][4]; // 要素数3*4のchar型変数の宣言 教科書 pp.85-108. 二次元配列変数 要素数4の配列を3つ並べた例 char a[3][4]; // 要素数3*4のchar型変数の宣言 a[0][0] ? a[0][1] ? a[0][2] ? a[0][3] ? a[1][0] ? a[1][1] ? a[1][2] ? a[1][3] ? 論理的には 2次元的に並んでいると 考えて使えば良い。 a[2][0] ? a[2][1] ? a[2][2] ? a[2][3] ? [1] pp.135-137.

行列の行と列 m行n列の行列 𝑎 1,1 … 𝑎 1,𝑛 ⋮ ⋱ ⋮ 𝑎 𝑚,1 … 𝑎 𝑚,𝑛 1列 ・・・ n列 1行 : m行

Row-major と Column-major 本来1次元のメモリをどう区切って使うか？ 行を連続にするか？列を連続にするか？ 𝑎 1,1 … 𝑎 1,𝑛 ⋮ ⋱ ⋮ 𝑎 𝑚,1 … 𝑎 𝑚,𝑛 𝑎 1,1 … 𝑎 1,𝑛 ⋮ ⋱ ⋮ 𝑎 𝑚,1 … 𝑎 𝑚,𝑛 1列 ・・・ n列 1列 ・・・ n列 1行 : m行 Row-major は行方向の要素が メモリ上で連続に並ぶ C言語はこのタイプ Column-major は列方向の要素が メモリ上で連続に並ぶ Fortran等はこのタイプ

メモリ上の配列と二次元配列(行列) Row-major は同じ行が繋がっている a[0][0] a[0][1] a[0][2] : a[1][0] a[1][1] a[1][2] a[2][3] a[2][0] a[2][1] a[2][2] a[1][3] a[0][0] a[0][0] a[0][1] a[0][2] a[0][3] a[0][1] a[1][0] a[1][1] a[1][2] a[1][3] a[0][2] a[2][0] a[2][1] a[2][2] a[2][3] a[0][3] a[1][0] 二次元配列 Row-major a[1][1] int a[m][n]; a[i][j]; int a[m * n]; a[n * i + j]; a[1][2] : : : : C言語はこのタイプ a[2][3] 訂正: 2015-06-20 誤: a[m * i + j] 正: a[n * i + j]

メモリ上の配列と二次元配列(行列) Column-major は同じ列が繋がっている a[0][0] a[1][0] a[2][0] : a[1][1] a[2][1] a[0][2] a[2][3] a[1][2] a[2][2] a[0][3] a[1][3] a[0][0] a[1][0] a[2][0] a[0][0] a[1][0] a[2][0] a[0][1] a[1][1] a[2][1] a[0][2] a[1][2] a[2][2] a[0][3] a[1][3] a[2][3] a[0][1] a[1][1] a[2][1] 二次元配列 Column-major int a[m][n]; a[i][j]; int a[m * n]; a[i + j * m]; a[0][2] : a[2][3] a[0][2] : a[2][3] Fortran等はこのタイプ 訂正: 2015-06-20 誤: a[i + j * n] 正: a[i + j * m]

二次元配列のメモリ上の配置 Row-major と Column-major 教科書 pp.85-108. a[0][0] ? ... Row-major は行方向の要素が連続に並ぶ C言語はこのタイプ 1行分のデータ a[0][0] ? a[1][0] ? a[2][0] ? a[0][1] ? a[1][1] ? a[2][1] ? a[2][3] ? ... Column-major は列方向の要素が連続に並ぶ Fortran等はこのタイプ 1列分のデータ [1] pp.135-137.

三次元配列変数 1次元のメモリを折り畳んで3次元にして使う char a[2][3][4]; // 要素数2*3*4のchar型変数の宣言 教科書 pp.85-108. 三次元配列変数 1次元のメモリを折り畳んで3次元にして使う char a[2][3][4]; // 要素数2*3*4のchar型変数の宣言 [0][0][0] ? [0][0][1] ? [0][0][2] ? [0][0][3] ? [0][1][0] ? [0][1][1] ? [1][2][3] ? ... 1行分のデータ メモリのアドレスは1次元なので 実際には2行目以降も 直線状に並んでいる [1] pp.135-137.

三次元配列変数 要素数3*4の配列を2つ並べた例 char a[2][3][4]; // 要素数2*3*4のchar型変数の宣言 教科書 pp.85-108. 三次元配列変数 要素数3*4の配列を2つ並べた例 char a[2][3][4]; // 要素数2*3*4のchar型変数の宣言 [0][0][0] ? [0][0][1] ? [0][0][2] ? [0][0][3] ? [1][0][0] ? [1][0][1] ? [1][0][2] ? [1][0][3] ? [0][1][0] ? [0][1][1] ? [0][1][2] ? [0][1][3] ? [1][1][0] ? [1][1][1] ? [1][1][2] ? [1][1][3] ? [0][2][0] ? [0][2][1] ? [0][2][2] ? [0][2][3] ? [1][2][0] ? [1][2][1] ? [1][2][2] ? [1][2][3] ? [1] pp.135-137.

配列変数の使用例 同じ次元・要素数でもいろんな解釈で使える char a[3][4]; char a[2][3][4]; a[ch][t]; 教科書 pp.85-108. 配列変数の使用例 同じ次元・要素数でもいろんな解釈で使える char a[3][4]; char a[2][3][4]; a[ch][t]; a[t][y][x]; a[t][x]; a[y][x]; a[z][y][x];

二次元配列の演習 行列の演算

演習: 行列とベクトルの演算 𝐴 を3×3の行列、 𝒃,𝒙 を3次元のベクトルとしたときに以下の計算を行うプログラム作ってみましょう。 積(matrix_vector_mul_practice_1.c) 𝒃=𝐴𝒙: 𝑏 𝑖 = 𝑗=1 𝑛 𝑎 𝑖,𝑗 𝑥 𝑗

演習: 行列の演算 加算(add)、減算(sub)、要素単位の乗算(times)、行列乗算(mtimes)、 転置(transpose) 𝐴,𝐵 を3×3の行列としたときに以下の計算を行うプログラム作ってみましょう。 加算(add)、減算(sub)、要素単位の乗算(times)、行列乗算(mtimes)、 転置(transpose) 加算: 𝐶=𝐴+𝐵: 𝑐 𝑖,𝑗 = 𝑎 𝑖,𝑗 + 𝑏 𝑖,𝑗 減算: 𝐶=𝐴−𝐵: 𝑐 𝑖,𝑗 = 𝑎 𝑖,𝑗 − 𝑏 𝑖,𝑗 要素単位の乗算: 𝐶=𝐴.∗𝐵: 𝑐 𝑖,𝑗 = 𝑎 𝑖,𝑗 𝑏 𝑖,𝑗 行列乗算: 𝐶=𝐴∗𝐵: 𝑐 𝑖,𝑗 = 𝑘=1 𝑚 𝑎 𝑖,𝑘 𝑏 𝑘,𝑗 転置: 𝐶= 𝐴 𝑇 : 𝑐 𝑖,𝑗 = 𝑎 𝑗,𝑖 訂正: 2015-06-20 誤: 𝐶=𝐴+𝐵 正: 𝐶=𝐴.∗𝐵 訂正: 2015-06-20 誤: 𝐶=𝐴+𝐵 正: 𝐶=𝐴∗𝐵

演習: 行列の演算 matrix_vector_xxx_practice_1.c を元にして以下のファイル名で作成せよ 加算: matrix_vector_add_practice_1.c 減算: matrix_vector_sub_practice_1.c 要素単位の乗算: matrix_vector_times_practice_1.c 行列乗算: matrix_vector_mtimes_practice_1.c 転置: matrix_vector_transpose_practice_1.c

重複した処理をループにまとめる 数式をループに変換する ループの組み立て

ループの組み立て 重複した処理をまとめる 追加: 2015-06-20 sum = 1 + 1 + 1 + 1 + 1; 演算を構成する項を縦に並べる sum = 0; // 初期化 for (i = 0; i < 5; i++) { sum += 1; } sum = 1 + 1 + 1; 各項を単文で書き直す sum = 0; // 初期化 sum += 1; sum = 1; sum += 1; 積算の場合 初期値を与えて 各単文を 全く同じ処理の 繰り返しにする 5回繰り返している

ループの組み立て 重複した処理をまとめる 追加: 2015-06-20 sum = 1 + 2 + 3 + 4 + 5; 演算を構成する項を縦に並べる sum = 0; // 初期化 for (i = 1; i <= 5; i++) { sum += i; } sum = 1 + 2 + 3 + 4 + 5; ループカウンタを活用する sum = 0; // 初期化 sum += 1; sum += 2; sum += 3; sum += 4; sum += 5; 各項を単文で書き直す sum = 1; sum += 2; sum += 3; sum += 4; sum += 5; 積算の場合 初期値を与えて 各単文を 全く同じ処理の 繰り返しにする 1～5まで増えている

ループの組み立て 重複した処理をまとめる 追加: 2015-06-20 sum = a[0]*b[0]+a[1]*b[1]+・・・+a[N-1]*b[N-1]; 演算を構成する項を縦に並べる sum = 0; // 初期化 for (i = 0; i < N; i++) { sum += a[i]*b[i]; } sum = a[0]*b[0] + a[1]*b[1] ⋮ + a[N-1]*b[N-1]; ループカウンタを活用する 各項を単文で書き直す sum = 0; // 初期化 sum += a[0]*b[0]; sum += a[1]*b[1]; ⋮ sum += a[N-1]*b[N-1]; sum = a[0]*b[0]; sum += a[1]*b[1]; ⋮ sum += a[N-1]*b[N-1]; 0～N-1 まで 増えて いる 積算の場合 初期値を与えて 各単文を 全く同じ処理の 繰り返しにする

ループの組み立て 数式とC言語の対応を考える 追加: 2015-06-20 加筆: 2015-06-26 ループの組み立て 数式とC言語の対応を考える 数式 C言語 定石の書き方から変形 𝑠= 𝑖=1 𝑛 1 𝑠= 𝑖=1 𝑛 𝑖 積算項: 1↔𝑖 1の積算 𝑖の積算 s = 0; for (i = 1; i <= n; i++) { s += 1; } s = 0; for (i = 1; i <= n; i++) { s += i; }

ループの組み立て 数式とC言語の対応を考える 追加: 2015-06-20 加筆: 2015-06-26 ループの組み立て 数式とC言語の対応を考える 数式 C言語 定石の書き方から変形 𝑠= 𝑖=1 𝑛 𝑖 𝑏 𝑖 = 𝑗=1 𝑛 𝑎 𝑖,𝑗 𝑥 𝑗 結果: 𝑠→ 𝑏 𝑖 カウンタ: 𝑖→𝑗 積算項: 𝑖→ 𝑎 𝑖,𝑗 𝑥 𝑗 𝑖の積算 𝑎 𝑖,𝑗 𝑥 𝑗 の積算 s = 0; for (i = 1; i <= n; i++) { s += i; } b[i] = 0; for (j = 1; j <= n; j++) { b[j] += a[i][j] * x[j]; }

ループの組み立て 数式とC言語の対応を考える 追加: 2015-06-20 加筆: 2015-06-26 ループの組み立て 数式とC言語の対応を考える 要素数𝑛個の数列や配列は 数学では 𝑎 1 ⋯ 𝑎 𝑛 と書く場合が多いが C言語では a[0]⋯a[n-1] になる 数式 C言語 𝑏 𝑖 = 𝑗=1 𝑛 𝑎 𝑖,𝑗 𝑥 𝑗 𝑏 𝑖 = 𝑗=0 𝑛−1 𝑎 𝑖,𝑗 𝑥 𝑗 C言語に合わせて 添え字を1つずらす 単純に置きかえ 範囲: 1:𝑛 → 0:𝑛−1 → 0:𝑛 𝑎 𝑖,𝑗 𝑥 𝑗 の積算 𝑎 𝑖,𝑗 𝑥 𝑗 の積算 b[i] = 0; for (j = 1; j <= n; j++) { b[j] += a[i][j] * x[j]; } b[i] = 0; for (j = 0; j < n; j++) { b[j] += a[i][j] * x[j]; }

ループの組み立て 数式とC言語の対応を考える 追加: 2015-06-20 加筆: 2015-06-26 ループの組み立て 数式とC言語の対応を考える 数式 C言語 𝑏 𝑖 = 𝑗=0 𝑛−1 𝑎 𝑖,𝑗 𝑥 𝑗 全ての 𝑏 𝑖 についてループして計算 𝑎 𝑖,𝑗 𝑥 𝑗 の積算 𝑎 𝑖,𝑗 𝑥 𝑗 の積算 for (i = 0; i < m; i++) { b[i] = 0; for (j = 0; j < n; j++) { b[j] += a[i][j] * x[j]; } b[i] = 0; for (j = 0; j < n; j++) { b[j] += a[i][j] * x[j]; }

参考文献 [1] B.W.カーニハン/D.M.リッチー著 石田晴久 訳、プログラミング言語C 第2版 ANSI 規格準拠、共立出版(1989)