コーディングイディオム

編集

アルゴリズム

概要

  • 構造化されたプログラミング言語の基本要素を,僕なりに形式・意味の両面から分析し、まとめたもの。
  • 人は騙し騙し仕事というのをしているけれども、プログラミングはそういう騙しが効かないから無理

目次

コメント

  • 極めて重要
  • 図で頑張って描くのは当然やるが、それとは別にプログラムに何を格納しているのかを書いたほうが良い
    • 図を見返してやるのは結構めんどいので
    • assertとかを書く時に間違えない
    • デバッグ楽

ループ

  • for (int i = 0; i < NUM; i++)について。

  • 色んな見方が出来る。

  • 形式的にはプログラムポインタが順々に回るという見方だけ、これだけでプログラミングするのは相当辛かった。

  • ということで、意味的に考えられないかなぁと模索する。

    • 意味論的考察なので、極めて当然のことを書いているし、整理としては理系的に体系化されたものというより、僕の頭の中の整理ってだけ。

  • なお大局的とは、

for (int i = 0; i < NUM; i++) {
    [expression]
}
  • をfor文の外部から見ることを表し、局所的とは上のうちのexpressionを主体とした時のiの役割を考えていることを表す。

反復（大局的）

  • 局所的に見ると視点固定。
  • i個の動作を全て記述するのが面倒だからfor文を使う、というもの。
  • 非常に当たり前のfor文の見方。
  • 簡単な初期化や、Σ、複数の変数への代入など単純なループ。
int i;
int a[10];
for (i = 0; i < 10; i++)
    a[i] = i;

視点固定（局所的）

  • 大局的に見ると反復、全探索。
  • 例えば、行列演算を見る。ここでループ変数i, jは行列のうち注目する変数を行列cのi行j列に限定し、視点を固定する役割を持つ。
for (i = 0; i < N; i++) {
    for (j = 0; j < N; j++) {
        for(k = 0; k < N; k++) {
            c[i][j]+=a[i][k]*b[k][j];
        }
    }
}

  • なお、kループ内はi,j固定すれば直感的に分かりやすく、大局的に反復として見る事ができる。

  • 「Cのi行j列に注目する。この時、内積を取るためにkを動かしながら反復して積を足していく。」という風に読めるようになる。

  • この見方が出来ると、上の解釈のように、頭の中で動く変数の数を劇的に抑えられる。

全探索（大局的）

  • 局所的に見ると視点固定。
  • 「考えられる状態全ての可能性を見る」の見方。
  • こんな問題を想定。card[5] = {1, 3, 4, 7, 17};なる数が記載された5枚のカードがある。これから一枚引いて元に戻す操作を4回行い、その和がkになりえるか？
int flag = 0;
for (int i = 0; i < 5; i++) {
    for (int j = 0; j < 5; j++) {
        for (int h = 0; h < 5; h++) {
            for (int k = 0; k < 5; k++) {
                if (card[i] + card[j] + card[h] + card[k] == k) {
                    flag = 1;
                    break;
                }
            }
        }
    }
}
return flag;

  • 今、4回それぞれにつき5枚のパターンがあったので、探索空間は5^4である。

  • 外部からは、上のプログラムは「ただその探索空間全てを見るための変数を4個張った」、という見方が出来る。

  • 「4回引いた時のカードの組み合わせ」状態を4変数で表現しただけに過ぎない。

  • この見方ができると、複数のforループを同じ「全探索」一つに見ることができて、強力。

  • 上にも書いたが、局所的に見ればループ変数i,j,h,kが決まり、視点が固定された世界でif文を行っているようにも解釈できる。

    • つまり、「今i, j, h, kの番号のカードが既に置いてある。これを足してkになれば万々歳だねbreak」という見方も出来る。
    • しかし、この場合は目的からして全探索として見た方が綺麗だと思う。

最大最小

  • 全探索の亜種
  • 最大最小とは、考えられる状態全ての可能性のうち、最も評価値が高いor低いもの、という意味なので全探索として見れる。
  • 上の問題の条件で、4枚のカードの合計が最も10に近くなるi, j, h, kの組の一つを求めよ、という場合、
int min_i, min_j, min_h, min_k;
int min_ijhk_val = INF;
for (int i = 0; i < 5; i++) {
    for (int j = 0; j < 5; j++) {
        for (int h = 0; h < 5; h++) {
            for (int k = 0; k < 5; k++) {
                int ijhk_val = ABS(card[i] + card[j] + card[h] + card[k] - 10);
                if (min_ijhk_val > ijhk_val) {
                    min_ijhk_val = ijhk_val;
                    min_i = i; min_j = j; min_h = h; min_k = k;
                }
            }
        }
    }
}
return flag;

  • と、全探索空間を張るi,j,h,kに対応するijhk_val=f(i, j, h, k)の最小化を行えば良い。

  • なお、最小最大問題は普通配列などに格納されているものを使うので、以下のように書くと可視性が良くなる。

int min_i, min_j, min_h, min_k;
int min_ijhk_val = INF;
for (int i = 0; i < 5; i++)
    for (int j = 0; j < 5; j++)
        for (int h = 0; h < 5; h++)
            for (int k = 0; k < 5; k++)
                if (min_ijhk_val > ABS(card[i] + card[j] + card[h] + card[k] - 10))
                    min_ijhk_val = ABS(card[min_i = i] + card[min_j = j] + card[min_h = h] + card[min_k = k] - 10);

return flag;

量化記号

  • 「全てのi, jについてP(i, j)を満たす」(), 「P(i, j)を満たすi, jが存在する」()の条件式の実装について。
  • 直感的に実装可能で、かつ可読性の高い実装方法について考える。

全称記号

  • n変数でなる条件式を実装する方法について書く。

  • なので、初期化はfaf = 1とする。

  • 全探索をかけて、一個でもNGなら全称はNGなので、fafを0にして全部breakする。

    • ここで、初めのループではif (!P(a)) の中でbreakすることも出来るけど、他のところとの整合性的な観点から、if文は僕は分けます(下例の16行目と18行目)。

  • 例, i, j in [1, NUM] (x[i] + y[j]) % 2 == 0

  • [https://robotich.ddns.net/svn/tmp/wakatabe/cpractice/forall.cpp (リンク切れ) https://robotich.ddns.net/svn/tmp/wakatabe/cpractice/forall.cpp (リンク切れ)]

#include <iostream>
#define NUM 6

int main(int argc, char** argv)
{
    int x[NUM] = {1, 2, 3, 4, 5, 6};
    int y[NUM] = {1, 2, 3, 4, 5, 6};

    //--------------------------------------------------------------------
    // for all i, j in [1, NUM], (x[i] + y[j]) % 2 == 0 ? faf = 1 : faf = 0;
    //--------------------------------------------------------------------
    int faf = 1; // for all flag
    for (int i = 0; i < NUM; i++) {
        for (int j = 0; j < NUM; j++) {
            // cont-condition
            if (!((x[i] + y[i]) % 2 == 0))
                faf = 0;
            if (!faf)
                break;
        }
        if (!faf)
            break;
    }
    std::cout << faf << std::endl;

    return 0;
}
  • めんどい場合
    • faf &= f(i)だと、f(i)がboolじゃないとバグるので、faf = faf && f(i)とする
int a[1000] = {};
bool faf = 1;
for (int i = 0; i < 1000; i++) {
  faf = faf && (a[i] == 0);
}
cout << faf << endl;

存在記号

#include <iostream>
#define NUM 6

int main(int argc, char** argv)
{
    int x[NUM] = {1, 2, 3, 4, 5, 6};
    int y[NUM] = {1, 2, 3, 4, 5, 6};

    //----------------------------------------------------------------------
    // there exists i, j in [1, NUM], (x[i] + y[j]) % 3 == 0 ? tef = 0 : tef = 1;
    //----------------------------------------------------------------------
    int tef = 0; // there exists flag
    for (int i = 0; i < NUM; i++) {
        for (int j = 0; j < NUM; j++) {
            // condition
            if ((x[i] + y[i]) % 3 == 0)
                tef = 1;
            if (tef)
                break;
        }
        if (tef)
            break;
    }
    std::cout << tef << std::endl;

    return 0;
}

全称記号(1変数の場合)

#include <iostream>
#define NUM 6

int main(int argc, char** argv)
{
    int x[NUM] = {1, 2, 3, 4, 5, 6};
    int y[NUM] = {1, 2, 3, 4, 5, 6};

    //----------------------------------------------------------------------
    // for all i in [1, NUM], (x[i] + y[i]) % 2 == 0 ? faf = 1 : faf = 0;
    //----------------------------------------------------------------------
    int i;
    for (i = 0; i < NUM; i++) {
        // cont-condition
         if (!((x[i] + y[i]) % 2 == 0))
             break;
    }
    int faf = (i == NUM);
    std::cout << faf << std::endl;