コミュニティ/BBS

トップ 差分 一覧 Farm ソース 検索 ヘルプ RSS ログイン

BBS

BBS ご利用の際の注意

  • ここには AWK に関するさまざまな話題を記載してください。
  • 件数が増えてきたら古いものから順に過去ログに移動します。過去ログは [BBS] から参照できます。
  • 投稿する前に
    • 過去ログに同様の内容がないかを確認してください。
    • ここに記載された内容に関しては、gawk を利用する際に用いたり、書籍への掲載、他の Web への掲載、他の ML への投稿の際の引用を行うことがあります。ご理解の上、ご利用ください。
    • AWK とは無関係と思われる投稿、コメントに関しては削除させていただきますのでご了承ください。

最近のタイトル一覧

[ 1 2 3 4 5 6 ]

BBS

お名前
件名
本文

awk に関する勉強会 - さいとう (2007年07月31日 00時48分25秒)

このページのログとかを見ていると、awk に関する勉強会の興味がある方が結構多いようです。

関東であれば、言っていただければ、無料で勉強会 (のようなもの) を行っても構いませんので、お気軽にご相談ください。前向きに検討させていただきます。

{{comment multi|w}}

キミならどう書く 2.0 - 2007 (その 1) - さいとう (2007年07月04日 23時03分12秒)

この記事は書きかけです。


キミならどう書く 2.0 - 2007 - その 1

問題は以下のようなものである。

斗桶 (a) に油が 1 斗 (10 升) ある。これを等分したい。7 升枡 (b) と 3 升枡 (c) しかない。この 2 つの枡だけで、5 升ずつ等分する方法を記述せよ。

目的

この「油売り算」ですが非常に不評で、難しい、何をやったらいいか分からない、実用的じゃないといった意見が出ているようです。確かに、難しいかもしれませんし、どういうプログラムを組めばいいか分からないかもしれませんし、油売り算自体は決して実用的な問題ではありません。ところが、この問題は小学校低学年で出題される問題 (噂では小学校の入学試験・・・つまり幼稚園問題だそうです)です。解くことは小学生でもできるのに、LL だとプログラマでもできないなんて変ですよね。

我々は LL 侍ですから、そんな簡単にギブアップするわけにはいきません。

ここでは、かなり回り道をしながら解いていこうと思います。

「油売り算」って何

時は江戸時代、本物の侍の闊歩するこの時代、寛永 4 (1627) 年に吉田光由が書いた和算のベストセラー「塵劫記」に掲載されている問題です。そもそも活版印刷がない時代にベストセラーとなるくらい庶民に親しまれた数学の本です。

「塵劫記」の中には鼠算 (今で言う累乗計算) や高い樹木の測定方法や米俵の数え方や竹を束ねたものの本数を外から計る方法 (今で言う等差級数でいいのかな?) まで含まれています。当時、いろいろな人が解いた形跡は神社仏閣に奉納されていたりしますので、夏休みの自由研究と合わせて調べてみてはどうでしょうか。やはり、侍魂は凄いものです。

そうした武士の時代にできた算術を現代の LL 侍である皆さんがズバッと一刀両断にしてくれることを期待しています。

とにかく描いてみる

「え〜」と思われるかも知れませんが、分からない事象は図に描いてみるのが一番です。少しプログラマチック (?) に (a), (b), (c) の油の中身を (a, b, c) として描いてみます。

初期状態

最初は (a) に 10 升で (b), (c) には 0 升ですから、(10, 0, 0) になるわけです。大きな紙に描いてみましょう。

                             ○
                         (10, 0, 0)

ここで「○」は起点であり、終点を示すものとします。

手を考える

さて、手を考えましょう。中身を移し変えるわけですから、手の数は、

  1. (a) から (b) に移す
  2. (a) から (c) に移す
  3. (b) から (a) に移す
  4. (b) から (c) に移す
  5. (c) から (a) に移す
  6. (c) から (b) に移す

の全部で 6 とおりしかありません。それぞれの手を実行してみましょう。

ただし、あふれる場合には、あふれるギリギリまで油を注いで残りはそのままにします。

                             ○
                         (10, 0, 0)
    ○        ○        ●        ●        ●        ●
( 3, 7, 0)( 7, 0, 3)(10, 0, 0)(10, 0, 0)(10, 0, 0)(10, 0, 0)

左から、順に

  1. (a) から (b) に移した場合
  2. (a) から (c) に移した場合
  3. (b) から (a) に移した場合
  4. (b) から (c) に移した場合
  5. (c) から (a) に移した場合
  6. (c) から (b) に移した場合

で、「●」は既に上で同じものが存在しているものを示しています。つまり、この方法で循環しているかどうかもチェックできますし、循環をチェックすることで余計な計算を省くことができるわけです。素晴らしい。

繰り返す

さて、考えるのはここまでです。あとは、これを繰り返していけばいいわけです。例えば、(3, 7, 0) からどういう枝が描けるかというと、

                             ○
                         ( 3, 7, 0)
    ●        ○        ●        ●        ●        ●
( 3, 7, 0)( 0, 7, 3)(10, 0, 0)( 3, 7, 0)( 3, 7, 0)( 3, 7, 0)

なんと既に 1 とおりしかユニークなものは存在していません。楽勝 (?) です。どうように (7, 0, 3) の枝を描いてみましょう。

                             ○
                         ( 7, 0, 3)
    ○        ●        ●        ●        ●        ○
( 0, 7, 3)( 7, 0, 3)( 7, 0, 3)( 7, 0, 3)(10, 0, 0)( 7, 3, 0)

というように 2 とおりだけです。これを頑張って作図します。このくらいは小学生だってできるわけですから、頑張って、記述して事象を把握しましょう。

完成

すると、こんな図ができるはずです。(すみません、(b) と (c) が説明と逆になっています)つまり、この図をプログラムするわけです。

左を見てください。左 or 右から攻めて行って、解が求まるところを下へ下へ探索するのを深さ優先探索といい、左→右と一段ずつ精査していくのを幅優先探索といいます。つまり、深さ優先探索では場合によっては最適解でない可能性がありますが、幅優先探索は最適解が求まります。

簡単でしょ。

「え〜、簡単じゃないよ」「めんどくさいよ」「2 インチくれ〜」と思う怠惰こそがプログラムのドライブフォースになってくれるわけです。

後述しますが、これは幅優先探索を解いたのと同義なのです。この幅優先探索はこの問題に限らず、最短解が必要とされる場合に良く使われ、迷路、経路探索、一筆書き、などさまざまなところで使うことができるので、この夏休みに覚えておきましょう。なお、探索の中でも最も簡単といわれているものですので、これらの例以外にも良く利用されます。

プログラムする

つまり、初期化状態 (10, 0, 0) から、ゴールである (5, 5, 0) を目指すプログラムです。括弧とカンマで書いているように、リストが使える言語や多値を返すことができる言語だとさらに簡単にできますが、ここでは awk で処理します。awk は関数が少ない分、他の言語からの移植は難しいのですが、他の言語への移植は比較的簡単だと思います。

では、進めましょう。

まず、初期化部分から

真田さん! あわてず、急いで、正確に・・・。

私と同じ苗字の空間騎兵隊の斉藤はそう言っていたような気がするのですが、まさにそのとおりです。

まず、初期化します。プログラムの内容は「引数を取って」とありますが、ここでは決め打ちにします。引数の処理自体はプログラムの本質ではありません。

BEGIN {
  ### 枡の大きさ
  youryou_a = 10; youryou_b = 7; youryou_c = 3;
  ### 最初の油の量
  abura_a = 10; abura_b = 0; abura_c = 0;
  ### 初期状態
  joutai[0] = sprintf("%d,0,0", abura_a);
  ### 最終目標
  mokuhyou = sprintf("%d,%d,0", abura_a / 2, abura_a / 2);
}

こんな感じで進めましょうか。

どんな手があるんだっけ?

前述したように以下の 6 とおりの方法があります。

  1. (a) から (b) に移した場合
  2. (a) から (c) に移した場合
  3. (b) から (a) に移した場合
  4. (b) から (c) に移した場合
  5. (c) から (a) に移した場合
  6. (c) から (b) に移した場合

これを変数 te (手) で分けてみましょう。

function sentaku_te(te, ほげほげ) {
  ### (a) から (b) に移した場合
  if (te == 1) {
    ふがふが 1;
  ### (a) から (c) に移した場合
  } else if (te == 2) {
    ふがぶが 2;
  ### (b) から (a) に移した場合
  } else if (te == 3) {
    ふがぶが 3;
  ### (b) から (c) に移した場合
  } else if (te == 4) {
    ふがぶが 4;
  ### (c) から (a) に移した場合
  } else if (te == 5) {
    ふがぶが 5;
  ### (c) から (b) に移した場合
  } else if (te == 6) {
    ふがぶが 6;
  }
  return 分けた後のそれぞれの油の量;
}

もちろん、文字で分けてもいいのですが、ループで回すことを考えると数字で分けた方が簡単です。

ここで、上記の sentaku_te() (選択手) の引数は分ける前の油の量を受け取るわけですが、先ほど述べているように awk では多値を扱えないので、ここではカンマで区切ったものを受け取って、カンマで区切ったものを返すような形で組んでみましょう。ということは受け取った後にカンマを split() してやればいいわけです。

function sentaku_te(te, abura3) {
  split(abura3, arr_abura3, ",");
  abura_a = arr_abura3[1]; abura_b = arr_abura3[2]; abura_c = arr_abura3[3];
  ### (a) から (b) に移した場合
  if (te == 1) {
    ふがふが 1;
  ### (a) から (c) に移した場合
  } else if (te == 2) {
    ふがぶが 2;
  ### (b) から (a) に移した場合
  } else if (te == 3) {
    ふがぶが 3;
  ### (b) から (c) に移した場合
  } else if (te == 4) {
    ふがぶが 4;
  ### (c) から (a) に移した場合
  } else if (te == 5) {
    ふがぶが 5;
  ### (c) から (b) に移した場合
  } else if (te == 6) {
    ふがぶが 6;
  }
  return sprintf("%d,%d,%d", abura_a, abura_b, abura_c);
}

形が見えてきましたね。

油を移動させる

先の「ふがふが」には、例えば te が 1 だと (a) から (b) に油を移動する前の値を入れて、移動した後の量を返す関数が必要っぽいですね。これを keisan_zengo() (計算前後) としましょう。つまり、移動前と移動後の油の量と、あふれないようにするために移動後の枡の大きさを引数にすれば十分です。

これも返す値が移動後の 2 つの枡に入っている油の量なので、多値で返した方が便利なのですが、awk なのでカンマで区切って渡します。

function keisan_zengo(mae, ato, ato_youryou,   ryou) {
  ryou = ato_youryou - ato;
  ### あふれない場合
  if (mae <= ryou) {
    ato += mae;
    mae = 0;
  ### あふれる場合
  } else {
    ato += ryou;
    mae -= ryou;
  }
  return sprintf("%d,%d", mae, ato);
}

こんな感じでしょうか・・・というか、これでこの関数は完成です。

手と移動を組み合わせる

この 2 つの関数を合体させれば、どういう手の場合に、どれだけ油が移動して、どういう油の状態になるかが取得できます。つまり、「ふがふが」を以下のようにします。

function sentaku_te(te, abura3) {
  split(abura3, arr_abura3, ",");
  abura_a = arr_abura3[1]; abura_b = arr_abura3[2]; abura_c = arr_abura3[3];
  ### (a) から (b) に移した場合
  if (te == 1) {
    split(keisan_zengo(abura_a, abura_b, youryou_b), arr_abura, ",");
    abura_a = arr_abura[1]; abura_b = arr_abura[2];
  ### (a) から (c) に移した場合
  } else if (te == 2) {
    split(keisan_zengo(abura_a, abura_c, youryou_c), arr_abura, ",");
    abura_a = arr_abura[1]; abura_c = arr_abura[2];
  ### (b) から (a) に移した場合
  } else if (te == 3) {
    split(keisan_zengo(abura_b, abura_a, youryou_a), arr_abura, ",");
    abura_b = arr_abura[1]; abura_a = arr_abura[2];
  ### (b) から (c) に移した場合
  } else if (te == 4) {
    split(keisan_zengo(abura_b, abura_c, youryou_c), arr_abura, ",");
    abura_b = arr_abura[1]; abura_c = arr_abura[2];
  ### (c) から (a) に移した場合
  } else if (te == 5) {
    split(keisan_zengo(abura_c, abura_a, youryou_a), arr_abura, ",");
    abura_c = arr_abura[1]; abura_a = arr_abura[2];
  ### (c) から (b) に移した場合
  } else if (te == 6) {
    split(keisan_zengo(abura_c, abura_b, youryou_b), arr_abura, ",");
    abura_c = arr_abura[1]; abura_b = arr_abura[2];
  }
  return sprintf("%d,%d,%d", abura_a, abura_b, abura_c);
}

これで全体のプログラムの 2/3 が完成です。量は多いですが、実質は if 文の条件分岐しか使っていません。

次に解いていきます。

解く! Solve!

まず、アルゴリズムを考えてみましょう。

  1. 手を選ぶ (先ほどの 6 種類)
  2. 目標と一致するか?
    1. 一致すれば終了
  3. 同一状況が既にあったか? (「●」にした部分ですね)
    1. なければ記憶
    2. この先に解があるかもしれない・・・続けよう
  4. 全てかつて通った状況ばかりになった
    1. 終了
  5. これをループする

これこそ幅優先探索です。

一般的には以下のようなルーチンになります。

for (senkou = 0; senkou < koukou; senkou++) {
  ### 移動の組み合わせは 6 種類だけ
  for (te = 1; te <= 6; te++) {
    いろいろ処理;
    if (目標と一致) {
      終了;
    }
    ### 同一局面を記憶 (「●」のところ)
    if (記憶されていない) {
      記憶する;
      koukou++;
    }
  }
}

つまり、

  1. 手を選ぶ (中の for 文)
  2. 目標と一致するか? (if 文)
    1. 一致すれば終了
  3. 同一状況が既にあったか? (if 文)
    1. なければ記憶
    2. この先に解があるかもしれない・・・続けよう (ato++)
  4. 全てかつて通った状況ばかりになった (!(mae < ato))
    1. 終了
  5. これをループする (最外の for 文)

脱出条件が分かりにくいのですが、常に senkou (先行) < koukou (後行) でループを回して、まだ調べていないものがあれば koukou++ としてループを回すように働きかけ、そうでなければ senkou++ で脱出する方向に働きかけるというシーソーのようなバランス (不安定という意味ではない) で for 文を回します。

つまり、このループを最初にドライブするために初期値を koukou = 1; のように指定する必要があります。

わき道にずれますが、迷路も同じですよね。

  1. 進む方向を決める
  2. ゴール?
    1. ゴールに到着すれば終了
  3. 同じ道を通った?
    1. 通ってなければ記憶
    2. この先にゴールがあるかもしれない・・・続けよう
  4. 全てかつて通った道ばかりになった
    1. 終了
  5. これをループする

しかも、このアルゴリズムは解があれば絶対に発見できるという素晴らしいものです。そういう便利なものが 10 行程度で記述できるわけです。

「苦労は買ってでもしろ」といいますが、ツイーディーが考案したグラフで解く方法だと 20 行くらいで全てできるものの、水差し問題と油分け算くらいしか使えません。でも、幅優先探索はいろんな局面で使えます。苦労しただけのメリットは大きいです。

そういえば、脱線ついでですが、油分け算と同じような方法で計算できる水差し算は「ダイハード 3」にも出てきましたが、皆さん、解けましたか?気になるのですが、観ながら私は全く解けませんでした。(苦笑)

と、油を売ってないで・・・、そう油は粘性が高いので、枡から枡に移すのに時間がかかるため、お客さんが暇をもてあまさないように、世間話をすることから来ています。まさに、今、油分け算をしながら油を売っているわけです。(苦笑)

実際に処理を書いていく

今までのところを整理しておきましょう。プログラムのコアが見えてきました。

BEGIN {
  ### 枡の大きさ
  youryou_a = 10; youryou_b = 7; youryou_c = 3;
  ### 最初の油の量
  abura_a = 10; abura_b = 0; abura_c = 0;
  ### 初期状態
  joutai[0] = sprintf("%d,0,0", abura_a);
  ### 最終目標
  mokuhyou = sprintf("%d,%d,0", abura_a / 2, abura_a / 2);
  ### 最初は絶対に通るから同一局面として登録しておく
  kensa[joutai[0]] = 1;
  ### 問題を解く
  toku();
}
function toku() {
  koukou = 1;
  for (senkou = 0; senkou < koukou; senkou++) {
    ### 移動の組み合わせは 6 種類だけ
    for (te = 1; te <= 6; te++) {
      joutai[koukou] = sentaku_te(te, joutai[senkou]);
      表示のためにあと少し何かしないとね;
      if (joutai[koukou] == mokuhyou) {
        なんか表示したいな;
        exit;
      }
      ### 同一局面を記憶 (「●」のところ)
      if (kensa[joutai[koukou]] == 0) {
        ### 既に通ったことにして
        kensa[joutai[koukou]] = 1;
        ### 先に進む
        koukou++;
      }
    }
  }
}

こんな感じになります。実はこれで問題は解けているのですが、表示がないと全く分かりません。そこで、表示の部分を考えて見ましょう。

答えを表示する

最初に図を描いた時の括弧の中を表示するために最後に手を入れます。表示を最後に行なうため、今の手を導くための前の手を配列で持っておきます。

具体的には、

function toku() {
  koukou = 1;
  for (senkou = 0; senkou < koukou; senkou++) {
    ### 移動の組み合わせは 6 種類だけ
    for (te = 1; te <= 6; te++) {
      joutai[koukou] = sentaku_te(te, joutai[senkou]);
      maenokioku[koukou] = senkou;
      if (joutai[koukou] == mokuhyou) {
        hyouji_kotae(koukou);
        exit;
      }
      ### 同一局面を記憶 (「●」のところ)
      if (kensa[joutai[koukou]] == 0) {
        ### 既に通ったことにして
        kensa[joutai[koukou]] = 1;
        ### 先に進む
        koukou++;
      }
    }
  }
}

のようにして残っていた部分を作成し、

function hyouji_kotae(kai) {
  if (kai > 0) {
    hyouji_kotae(maenokioku[kai]);
  }
  print joutai[kai];
}

と表示部分を加えます。maenokioku (前の記憶) が通ってきた前の局面の番号を返すようになっています。

接合する

これらを全部つなげて完成します。

BEGIN {
  ### 枡の大きさ
  youryou_a = 10; youryou_b = 7; youryou_c = 3;
  ### 最初の油の量
  abura_a = 10; abura_b = 0; abura_c = 0;
  ### 初期状態
  joutai[0] = sprintf("%d,0,0", abura_a);
  ### 最終目標
  mokuhyou = sprintf("%d,%d,0", abura_a / 2, abura_a / 2);
  ### 最初は絶対に通るから同一局面として登録しておく
  kensa[joutai[0]] = 1;
  ### 問題を解く
  toku();
}
function toku() {
  koukou = 1;
  for (senkou = 0; senkou < koukou; senkou++) {
    ### 移動の組み合わせは 6 種類だけ
    for (te = 1; te <= 6; te++) {
      joutai[koukou] = sentaku_te(te, joutai[senkou]);
      hyouji[koukou] = senkou;
      if (joutai[koukou] == mokuhyou) {
        hyouji_kotae(koukou);
        exit;
      }
      ### 同一局面を記憶 (「●」のところ)
      if (kensa[joutai[koukou]] == 0) {
        ### 既に通ったことにして
        kensa[joutai[koukou]] = 1;
        ### 先に進む
        koukou++;
      }
    }
  }
}
function hyouji_kotae(kai) {
   if (kai > 0) {
     hyouji_kotae(hyouji[kai]);
   }
   print joutai[kai];
 }
function keisan_zengo(mae, ato, ato_youryou,   ryou) {
  ryou = ato_youryou - ato;
  ### あふれない場合
  if (mae <= ryou) {
    ato += mae;
    mae = 0;
  ### あふれる場合
  } else {
    ato += ryou;
    mae -= ryou;
  }
  return sprintf("%d,%d", mae, ato);
}
function sentaku_te(te, abura3) {
  split(abura3, arr_abura3, ",");
  abura_a = arr_abura3[1]; abura_b = arr_abura3[2]; abura_c = arr_abura3[3];
  ### (a) から (b) に移した場合
  if (te == 1) {
    split(keisan_zengo(abura_a, abura_b, youryou_b), arr_abura, ",");
    abura_a = arr_abura[1]; abura_b = arr_abura[2];
  ### (a) から (c) に移した場合
  } else if (te == 2) {
    split(keisan_zengo(abura_a, abura_c, youryou_c), arr_abura, ",");
    abura_a = arr_abura[1]; abura_c = arr_abura[2];
  ### (b) から (a) に移した場合
  } else if (te == 3) {
    split(keisan_zengo(abura_b, abura_a, youryou_a), arr_abura, ",");
    abura_b = arr_abura[1]; abura_a = arr_abura[2];
  ### (b) から (c) に移した場合
  } else if (te == 4) {
    split(keisan_zengo(abura_b, abura_c, youryou_c), arr_abura, ",");
    abura_b = arr_abura[1]; abura_c = arr_abura[2];
  ### (c) から (a) に移した場合
  } else if (te == 5) {
    split(keisan_zengo(abura_c, abura_a, youryou_a), arr_abura, ",");
    abura_c = arr_abura[1]; abura_a = arr_abura[2];
  ### (c) から (b) に移した場合
  } else if (te == 6) {
    split(keisan_zengo(abura_c, abura_b, youryou_b), arr_abura, ",");
    abura_c = arr_abura[1]; abura_b = arr_abura[2];
  }
  return sprintf("%d,%d,%d", abura_a, abura_b, abura_c);
}

う〜ん、巨大になってしまいましたが、if 文の連続なので、このくらいは勘弁して欲しいところです。

実行してみよう

最初の実行は心躍るものです。LL の場合逐次試しながらやるものですが、今回のこの文書のために一切途中でテストなしで作っています。つまり書いている内容に少しでも矛盾があると動かないわけですが・・・やっぱり typo があって動きませんでした。orz (typo は直しましたので、大丈夫です)

$ gawk -f abura.awk
10,0,0
3,7,0
3,4,3
6,4,0
6,1,3
9,1,0
9,0,1
2,7,1
2,5,3
5,5,0

皆さんが最初に描いた図と同じですか?確認してみてください。

ちょうど図の右のラインを通って、左よりも最適な解が選ばれていることが分かります。

graphiz でグラフ化

graphiz で可視化を行ってみたのですが、なんともアッサリ・・・。awk4j に付属の Graph.awk は function しか見てないので、結果的に非常にアッサリしてしまいました。

これは、これでプログラムのスマートな状態が見えていると思います。

プロファイリングを利用する

gawk には pgawk というものがあり、簡単なプロファイリングを行なうことができます。具体的には以下のようにして実行します。

$ pgawk -f abura.awk

するとカレントディレクトリに awkprof.out というファイルが作成され、プロファイル結果を確認できます。例えば、今回の場合だと、(最短で) 17 回の手を計算していることになるので、手の生成部分は 17 回であれば、図と同じであることが確認できます。確認してみましょう。

  # gawk profile, created Thu Jul  5 13:25:21 2007

  # BEGIN block(s)

  BEGIN {
     1    youryou_a = 10
     1    youryou_b = 7
     1    youryou_c = 3
     1    abura_a = 10
     1    abura_b = 0
     1    abura_c = 0
     1    joutai[0] = sprintf("%d,0,0", abura_a)
     1    mokuhyou = sprintf("%d,%d,0", abura_a / 2, abura_a / 2)
     1    kensa[joutai[0]] = 1
     1    toku()
  }

  # Functions, listed alphabetically

    10  function hyouji_kotae(kai)
  {
    10    if (kai > 0) { # 9
     9      hyouji_kotae(maenokioku[kai])
    }
    10    print joutai[kai]
  }

   101  function keisan_zengo(mae, ato, ato_youryou, ryou)
  {
   101    ryou = ato_youryou - ato
   101    if (mae <= ryou) { # 63
    63      ato += mae
    63      mae = 0
    38    } else {
    38      ato += ryou
    38      mae -= ryou
    }
   101    return sprintf("%d,%d", mae, ato)
  }

   101  function sentaku_te(te, abura3)
  {
   101    split(abura3, arr_abura3, ",")
   101    abura_a = arr_abura3[1]
   101    abura_b = arr_abura3[2]
   101    abura_c = arr_abura3[3]
   101    if (te == 1) { # 17
    17      split(keisan_zengo(abura_a, abura_b, youryou_b), arr_abura, ",")
    17      abura_a = arr_abura[1]
    17      abura_b = arr_abura[2]
    84    } else {
    84      if (te == 2) { # 17
    17        split(keisan_zengo(abura_a, abura_c, youryou_c), arr_abura, ",")
    17        abura_a = arr_abura[1]
    17        abura_c = arr_abura[2]
    67      } else {
    67        if (te == 3) { # 17
    17          split(keisan_zengo(abura_b, abura_a, youryou_a), arr_abura, ",")
    17          abura_b = arr_abura[1]
    17          abura_a = arr_abura[2]
    50        } else {
    50          if (te == 4) { # 17
    17            split(keisan_zengo(abura_b, abura_c, youryou_c), arr_abura, ",")
    17            abura_b = arr_abura[1]
    17            abura_c = arr_abura[2]
    33          } else {
    33            if (te == 5) { # 17
    17              split(keisan_zengo(abura_c, abura_a, youryou_a), arr_abura, ",")
    17              abura_c = arr_abura[1]
    17              abura_a = arr_abura[2]
    16            } else {
    16              if (te == 6) { # 16
    16                split(keisan_zengo(abura_c, abura_b, youryou_b), arr_abura, ",")
    16                abura_c = arr_abura[1]
    16                abura_b = arr_abura[2]
              }
            }
          }
        }
      }
    }
   101    return sprintf("%d,%d,%d", abura_a, abura_b, abura_c)
  }

     1  function toku()
  {
     1    koukou = 1
    17    for (senkou = 0; senkou < koukou; senkou++) {
   101      for (te = 1; te <= 6; te++) {
   101        joutai[koukou] = sentaku_te(te, joutai[senkou])
   101        maenokioku[koukou] = senkou
   101        if (joutai[koukou] == mokuhyou) { # 1
     1          hyouji_kotae(koukou)
     1          exit
        }
   100        if (kensa[joutai[koukou]] == 0) { # 17
    17          kensa[joutai[koukou]] = 1
    17          koukou++
        }
      }
    }
  }

確かに

   101    if (te == 1) { # 17
    17      split(keisan_zengo(abura_a, abura_b, youryou_b), arr_abura, ",")
    17      abura_a = arr_abura[1]
    17      abura_b = arr_abura[2]

のようになっており、17 回計算されていることが分かります。

気が付いたと思いますが、このプロファイル結果は Allman スタイルというか GNU スタイルに近いというか、K & R スタイルでないんですね。経典である「プログラム言語 AWK」では、また少し違うスタイルだったりします。

BEGIN {
          print "Hello World.";
      }

こんな感じ・・・(配布しているプログラムは K & R スタイルで書かれています) まぁ、宗教戦争になりそうなのですが、私は K & R です。(当然?)

また、このプロファイリングには便利な副作用があります。汚いプログラムをほぐしてくれます。(w

この awk でできたテトリスこと awktris 読めますか?こういったものも読みやすく Allman スタイルで出力してくれます。時間があればやってみてください。

もっと簡単に解く

小学生でも・・・と書いたものの、結構大変です。この油分け算にはもっと簡単に解ける方法があるのです。

この問題は「塵劫記」から取っていますが、ヨーロッパでもワインで同じような問題がありますが、ツィーディーがグラフで簡単に解く方法を求めており、これで解くのが簡単です。

アルゴリズムは特化することで鋭さを増し、さらにシャープな切れ味になります。幅優先探索が「お箸」だとすれば、こちらは「蟹フォーク」でしょうか。(w

グラフで解く

以下のようなグラフを用意します。赤丸のところがゴールになります。

横軸に (c) の容量、縦軸に (b) の容量を取ります。これでひたすら (c) を使って、(b) に注ぎ込んでいきます。

探索で言えば、1 つの枝をたどっていくことになります。最適な解を見つけるために多大な努力をするよりも、最適解ではなくても簡単に見つけることができれば、それはそれでハッピーです。この問題にも、「塵劫記」にも、「最適解を求めよ」とは書いていません。

さて、(c) に油を 3 升入れるという作業は水平に矢印を延ばす作業となり、これを (b) に注ぐと言う作業は (b) を 3 升増やして (c) を空にする作業になります。これをどんどん繰り返します。

すると、あるところで (b) に入らなくなって、あふれてしまいます。さて、どうすればいいのでしょうか?

答えは簡単で「(b) に入るだけ油を入れて、(c) をそのままに、(b) の油を (a) に戻す」と次に進めます。これを繰り返していくわけです。

本当に半分にできるかどうかは、やってみないと分からないのですが、実際にやってみると以下のようになります。

手で描いても、先ほどの幅優先探索よりもはるかに簡単です。

プログラムする

さて、このグラフをプログラムするとどうなるのでしょうか?

単純に、(c) でくみ上げて、(b) に移して、(b) がいっぱいなら (b) を 0 に戻す・・・これだけです。繰り返しは while 文でも再帰でも問題ありません。

つまり、条件分岐と繰り返しの問題になってしまうのです。

こうなってしまえば、特に解説はしませんが、以下のようなプログラムになります。

#! /usr/bin/gawk -f
BEGIN {
  ### 各壷の容量 (a > b > c)
  mass["a"] = ARGV[1]; mass["b"] = ARGV[2]; mass["c"] = ARGV[3];
  move_oil();
}
function move_oil() {
  oil["c"] = mass["c"];
  print "a から c に " oil["c"] " 升移す" oil["b"];

  if (oil["b"] + oil["c"] < mass["b"]) {
    oil["b"] = oil["b"] + oil["c"];
    print "c から b に " oil["c"] " 升移す" oil["b"];
    oil["c"] = 0;
    if (oil["b"] == mass["a"]/2) {
      print "上手に分けられました!";
      exit;
    }
  } else {
    print "c から b に " mass["b"] - oil["b"] " 升移す";
    if (oil["b"] + mass["b"] - oil["b"] == mass["a"]/2) {
      print "上手に分けられました!";
      exit;
    }
    tmp_oil =  mass["c"] - (mass["b"] - oil["b"]);
    oil["b"] = 0;
    print "b を a に戻して" oil["b"];
    oil["b"] = tmp_oil;
    print "c から b に " tmp_oil " 升移す" oil["b"];
  }
  move_oil();
}

実行してみましょう。

$ gawk -f abura.awk 10 7 3
a から c に 3 升移す
c から b に 3 升移す
a から c に 3 升移す
c から b に 3 升移す
a から c に 3 升移す
c から b に 1 升移す
b を a に戻して
c から b に 2 升移す
a から c に 3 升移す
c から b に 3 升移す
上手に分けられました!

どこかで見た回答例ですね。そう、私はこれを作成した段階で問題をアップして、幅優先探索では解いていませんでした。(苦笑)

図をプログラムにしたわけですが、いかがでしたでしょうか?

次なるステージへ

実はパズルものの多くはこの幅優先探索で解けるのですが、やはり見た目が難しい (理解しにくい) ということで本戦の「キミならどう書く」でも毎回パズルのような案が出ますが消えて行っていました。今回、難しい、分からない、なんぞこれ〜と文句を言われても、この夏休みにこの Boot Camp (?) で幅優先探索を知っておけば、一気にレパートリーが増えます。来年、ダメでも再来年に向け、力を蓄えて、皆さんも出場してみてください。

謝罪

難しく、分かりにく問題を出して申し訳ありません。でも、幅優先探索はきっと皆さんの血となり肉となってくれるものと信じています。さらに、昔から「プログラムはアルゴリズムとデータ構造」と言われますが、両方を考えなければ解けない問題でもあり、問題としては良問だと思っています。

最後まで見ていただいた方へ

長い長い内容でしたが、どうだったでしょうか?え? 回答例と違う? 違っていいんです。(え

本質と面白いところを分かってくれれば良いと考えています。実際に本戦の「キミならどう書く」でも違う仕様で動作しているものも散見されますので、押さえるところを押さえておけば良いと思います。

もともと去年の「キミならどう書く 2.0」で、解答や狙いといった部分が書かれていないのは残念だと私が発言しているところからスタートしています。小さなプログラムはそれだけでいろいろ皆さんで突付かれながら Fizz-Buzz 問題のように膨れ上がっていくものもありますが、その問題の「狙い」って何だろうと考えることはありませんか?そうした目的意識のある学習は重要だと思います。

考えてみれば難しいところはないはずです。一歩一歩何をやっているかを考えて行ってみてください。

人間は考える葦である。

そうそう

私、懲りてません。第 2 段をやります!お楽しみに!

参考サイト

  • 油分け算
  • 水差し問題
    • プログラムはほとんど使わせてもらいました。分かりやすいプログラムに感謝します。

Re:備忘録 - さいとう (2007年07月05日 00時29分10秒)

  • やっぱり図がおかしい。(プロファイルから判明) (済)
  • プロファイリングの結果も添付した方が良いのでは? (済)

{{comment multi|w}}

Mersenne twister for (g)awk? - さいとう (2007年06月29日 00時03分59秒)

乱数のメルセンヌツイスターですが、誰も答えないと思ったら、こんな回答が来てましたね。

You might try contacting Arnold Robbins, the author of gawk. I saw his name mentioned in some of the sources for the sfmt Mersenne Twister implementation.

Arnold ってそういう人だったんですね。

{{comment multi|w}}

「LL 魂」のご案内 - さいとう (2007年06月05日 21時29分25秒)

今年も Lightweight Language の祭典「LL Conference」の時期になりました。さまざまな LL の競演をお楽しみください。

告知文 - さいとう (2007年06月05日 21時33分52秒)

告知文を掲載しておきます。

=====================================================================
              Lightweight Language Spirit 開催のお知らせ
=====================================================================

  2003年はLL Saturday、2004年はLL Weekend、2005年はLL Day and Night、
2006年はLL RingとしてLLファンの期待に応えてきたLightweight Language
カンファレンスが、今年もやってきます。

  今年は、Lightweight Language Spirit(通称:LL魂)として、LLにかける
熱き魂を披露します。
  LLにかけるプログラマ達の想い、夢、野望を丸1日ご堪能ください。

  昨年までと同様、今年も各プログラミング言語コミュニティの協力を得て、
それぞれの言語の特徴などを比較しながら理解できるセッションを多数用意する
予定です。

  ここ数年の間に、軽量プログラミング言語の果たす役割は大きく、そして応用
範囲はより広くなってきています。LL魂は、これら軽量プログラミング言語
が一堂に会す珍しいイベントです。さまざまな軽量プログラミング言語の実力、
楽しさ、面白さを体験するまたとない機会です。ぜひ、ご参加ください。

◆開催概要

名称:Lightweight Language Spirit(通称: LL魂)
主催:LL魂実行委員会
協賛:(株)アスキー、日本UNIXユーザ会、Kahuaプロジェクト、
      Tokyo Perl Mongers、日本PHPユーザ会、日本Pythonユーザ会、
      日本Rubyの会、日本 GNU AWK ユーザー会 ほか

開催日:2007年8月4日(土)
時間  :10:30(開演)〜21:00(終了予定)
場所  :日本教育会館
    (http://www.jec.or.jp/)
参加費:3,500円(予定)
定員  :500名(予定)

内容:軽量プログラミング言語に関する総合カンファレンスです。
      各出版社による関連書籍の展示・販売も行う予定です。
URL :http://ll.jus.or.jp/2007/

参加申込: 2007年6月4日(月)チケット発売開始(予定)

問い合わせ先:LL魂実行委員会
              E-mail:info2007@ll.jus.or.jp

※ 詳しい情報は、http://ll.jus.or.jp/2007/ にて発表していきます。
======================================================================

チケットについて - さいとう (2007年06月05日 21時34分24秒)

チケット購入方法について掲載しておきます。

======================================================================
    Lightweight Language Spirit チケット発売のお知らせ
======================================================================

  8月4日(土)に日本教育会館 一ツ橋ホールにて開催するLightweight Language
Spiritのチケットを、6月4日(月)10:00から発売します。

  例年数日で完売する人気のイベントチケットとなります。今年は500席を用意
してお待ちしておりますが、参加を検討されている皆様はお早めにお買い求め
ください。

  チケットはローソンチケットにて購入することができます。

         --チケット情報--

・イベント名: Lightweight Language Spirit
・Webサイト: http://ll.jus.or.jp/2007/
・取り扱い: ローソンチケット(Lコード: 34401)
・発売開始: 6月4日(月)10:00
・販売価格: 3,500円
・販売枚数: 500枚

・チケットの購入方法は以下の通りです。

  1) ローソン店内に設置されているLoppi(ロッピー)で予約・購入する。
     店頭のLoppiで直接購入することができます。24時間購入可能です。

  2) 電話で予約の上、ローソン店内のLoppiで発券する。
     電話番号 0570-084-003 に電話して予約することができます。
     音声による案内は24時間受付です。

  3) ローソンチケットのWebサイトから予約し、ローソン店内のLoppiで発券する。
     ローソンチケットの有料会員に登録する必要があります。詳しくは
     ローソンチケットのWebサイト(http://www2.lawsonticket.com/)を
     ご覧ください。

  いずれの場合も、Lコード(34401)を指定することで簡単に購入できます。
  なお、購入方法の詳細は、ローソンチケットの予約・購入マニュアルを
  ご覧ください。
  http://www2.lawsonticket.com/pc/p54/manual/index.asp?

・販売期間
  - Web/電話でのチケット予約受付期間: 8月2日(木)23:59まで
    8月3日(金)以降はLoppiなどを利用した店頭での直接購入のみ可能
  - 店頭でのチケット購入期限: 8月3日(金)23:59まで
  - なお、Web/電話で予約したチケットの引取期限は予約日の翌日から2日間で、
    2日目は23:00までとなります。
  - 予定枚数を完売した場合は、販売期間中でも販売を終了します。

・お問い合わせ先
  - チケット購入に関するお問い合わせ: ローソンチケット
  - イベントに関するお問い合わせ: Lightweight Language Spirit実行委員会
    E-mail: info2007[at]ll.jus.or.jp

======================================================================

{{comment multi|w}}

Beta release of gawk 3.1.6 now available - さいとう (2007年05月27日 23時33分14秒)

gawk 3.1.6 のβ版がダウンロード可能になりました。

以下からダウンロード可能です。

Re:3.1.5 から 3.1.6 への変更点 - さいとう (2007年06月04日 23時13分55秒)

変更点の翻訳を以下に書いておきます。

3.1.5 から 3.1.6 への変更点
---------------------------

1. `gawk 'program' /non/existant/file' でコアダンプしなくなりました。

2. gawk が伝統的なピリオド (.) のではなく、実行されている実行環境のロケー
   ルの設定を使って入力データを解析するということに世界中の非常に多くの
   人が不満を持っていました。そこで、gawk はちゃんと標準準拠であったの
   ですが、ユーザーの勝利 (Triumph For The Users) の証として、--posix
   オプションが指定されるか環境変数 POSIXLY_CORRECT がセットされた時だ
   け gawk は実行環境のロケールの小数点を使います。この変更で (小数点と
   実行環境のロケールが原因の) FAQ からこの項目がなくなることを切望しま
   す。

3. `gawk -v BINMODE=1 ...' が再び動作するようになりました。

4. `/dev/user' のような内部ファイル名が再び動作するようになりました。

5. 実行環境が "C" ロケールではないロケールでのワイド文字列に関する問題
   が全てで処置されました。(少なくとも、私達はそうだと思っています。)

6. `ansi2knr' の使用はもはやサポートされません。ANSI C コンパイラーを使
   ってください。

7. Autoconf 2.61, Automake 1.10 と Gettext 0.16.1 にアップデートされま
   した。

8. getopt* と regex* ファイルは現在の GLIBC CVS と同期されました。バー
   ジョンとマイナーな修正は ChangeLog を見てください。

9. --lint-old オプションのワーニングを加えました。

10. gawk は名前と IP アドレスを探すのに getaddrinfo(3) を用いるようにな
    りました。これにより IPv6 形式のアドレスを使えるようになり、最終的
    には `/inet6/...' や `/inet4/...' をホスト名に加えるという道筋を築
    くことになりました。

11. gawk は valgrind にも対応したと信じています。少なくともテストの実行
    はうまく行っています。

12. 整数フォーマットの中で非常に大きな数のフォーマットや表示に関する問
    題の扱いは対処されて修正されました。

13. gawk は "+inf", "-inf", "+nan" と "-nan" を対応する IEEE 浮動小数点
    値に変換するようになりました。これらの文字列 (大文字小文字区別なし)
    だけ機能します。--posix オプションと一緒に用いると、gawk はシステム
    の strtod を直接呼び出します。You asked for it, you got it, you deal
    with it.

14. YYDEBUG の定義は -D コマンドラインオプションで可能になりました。

15. gawk は Tandem NSK/OSS システムでも動作するようになりました。

16. Lint メッセージの合理化: 遭遇するたびに毎回メッセージを出すのではな
    く、多くのメッセージが一度だけ表示されるようになりました。

17. strftime() 関数は省略可能な 3 つめの引数を受け付けるようになりまし
    た。それは、もしゼロでも null でない場合、時刻はその地域の時刻の代
    わりに協定世界時 (UTC) として書式設定がなされます。

18. 連接と `| getline' ("echo " "date" | getline stuff のようなもの)の
    優先順位が以前のものに戻り Unix の awk と合うようになりました。

19. gawk がコマンドラインのディレクトリをスキップする新しい configure
    時のフラグ --disable-directories-fatal オプションが加わりました。Unix
    の awk がそうであるので、この挙動は --traditional オプションとして
    使われます。

xx. 多くのバグが修正されましたが、詳細は ChangeLog を見てください。

Re:3.1.5 から 3.1.6 への変更点 - さいとう (2007年06月05日 21時07分48秒)

少し変更しました。

{{comment multi|w}}

「UNIX Magazine」の 4 月号に「もっと便利に awk を使ってみよう」勉強会の様子が掲載されています - さいとう (2007年05月27日 23時19分35秒)

「UNIX Magazine」の 4 月号に「もっと便利に awk を使ってみよう」勉強会の様子が掲載されています。jus の高橋さんが勉強会の様子を書かれています。

{{comment multi|w}}

awke - さいとう (2007年05月23日 00時03分30秒)

awk の拡張だそうです。

取り急ぎ、メモで書いておきます。

http://www.awke.org/

Re: - さいとう (2007年05月23日 00時08分49秒)

Ed Morton らは gawk の拡張にしないかと誘っているようですね。

これも、取り急ぎ。

Re:awke の拡張関数について (翻訳してみた) - さいとう (2007年05月23日 23時42分30秒)

awke の特徴のひとつである追加関数を以下に翻訳して置きます。UNIX 環境または gawk なら自己解決できそうなものばかりですが・・・。

date()
人間が可読できる形式で現在の日付と時間を返しますが、システムの設定とロケールに従います。引数のない /usr/bin/date と同じです。
dumpArray(array)
配列の内容を標準出力にダンプします。デバッグに有益です。内容は根本的に awk が配列に保存しているデータの順序でダンプされます。
hilite(aString)
デフォルトカラーを使って文字列をハイライトさせます。戻り値: ハイライトの文字列は標準の awk 関数を使って表示可能な文字列。
hiliteColor(aString, aColor)
hilite(aString) と同様ですが、ユーザーは使用する色を指定できます。aColor は HL_RED, HL_GREEN などのように、HL_XXXXXX として特定される定数のひとつを用いる必要があります。戻り値: ハイライトの文字列は標準の awk 関数を使って表示可能な文字列。
hiliteDefault(aColor)
hilite() 関数のための標準の色を指定します。指定されるまでは、HL_YELLOW が標準です。aColor は HL_RED, HL_GREEN などのように、HL_XXXXXX として特定される定数のひとつを用いる必要があります。
now()
現在の時間と日付を基準時点からの秒数で返します。この関数はタイマーを作る時に有益です。
quicksort(array, nElementsCount?)
再帰的ではないクイックソート。この関数は基本的に数値として処理するように定義されていますが、ほとんどの場合には、辞書順として動作します。つまり配列の内容は数値としても文字列でも使えます。quicksort() の振る舞いは数値と文字列を含んだ配列の内容には不向きです。配列は内部的にソートされ、関数は配列の中にどれだけの要素があるかを特定するのに nElementsCount? を必要とします。
sleep(nSeconds)
現時点で sleep する値を nSeconds で入力します。秒単位の精度で、/usr/bin/sleep のコールの制限とシステム依存によります。
substitute(r, s, h, t)
gawk/gensub() の置き換え。拡張された正規表現 r にマッチするようにターゲット文字列 t を探します。もし h が 'g' または 'G' であれば、r を s で全て置き換えます。そうでなければ、h はどの r にマッチしたものを置き換えるかを示す番号になります。テキスト s を置き換える際に、順序 n、ここで n は 1 から 9 までの数字ですが、n 番目に挿入されたサブ表現 (subexpression) にマッチするテキストのみを指定します。順序 0 は完全にマッチしたテキストを示し、文字 & として振舞います。変更された文字列は返されて t 自体は変更されません。r は文字列として記述します (例えば /(.).\1/ の代わりに "(.).\\1" となります)。

Re: - さいとう (2007年05月23日 23時54分22秒)

面白そうなのが、非再帰 Quick Sort かな。そこまでこだわる理由は分かりません。

{{comment multi|w}}

翻訳について - さいとう (2007年01月08日 22時23分41秒)


cvs 版の gawk.texi ならびに gawk.po の翻訳を日本 GNU AWK ユーザー会で行っていますが、以下に翻訳方針をまとめておきます。

他の翻訳物との違和感をなくするため、manpage を翻訳している JM Project の指針を参考にさせていただきました。

また、これらは決定事項ではありませんので、BBS へ掲載させていただいていると同時に、おかしい部分に関してはコメントに書き加えていっていただけると助かります。

文末の表現について

全体としての文体の統一のため、 特に理由がなければ「である」調を用いてください。つまり以下のような文末になります。

  • 「〜だ。」
  • 「〜である。」
  • 「〜する。」
  • 「〜できる。」
  • 「〜となる。」

句読点について

句読点は「、」および「。」を使用してください。ただし、英単語や英文の部分の区切りには「,」「.」を用います。

原文のコメント化

校正作業や改版作業の便宜を図るため、必ず原文をコメントで残しておいてください。具体的には、行頭に "@c" を付けることでコメントされます。

用語 (述語) について

コマンド名、関数名、引き数名などは翻訳せず、アルファベットのままで記述します。また、カタカナでも通用する用語に関してはカタカナを優先します。

音引きについて

片仮名語の語尾の音引き (ー) には以下の方針を用いてください。既に日本語になっているものについてはそれを用います。

以下は JIS Z 8301:1996 の例です。

  • その言葉が 3 音以上の場合には、語尾に長音符号を付けない。
    • エレベータ
  • その言葉が 2 音以下の場合には、語尾に長音符号を付ける。
    • カバー
  • 複合語は, それぞれの成分語について、上記を適用する。
    • モータカー
  • 長音符号で書き表す音、はねる音、および、つまる音は、それぞれ 1 音と認め、よう (拗) 音は 1 音と認めない。
    • テーパ、ダンパ、ニッパ、シャワー

実際の翻訳

手続き

実際の翻訳物は Google Code を用いて管理されており、コミットするためには登録が必要です。その旨を斉藤 (hi_saito@yk.rim.or.jp) までご連絡していただければ、コミット権限を付与します。

  • Google のアカウントが必要になります。

check out だけの場合

以下のようにすると check out できます。

$ svn checkout http://jgauc.googlecode.com/svn/trunk/ jgauc

この際に Subversion が必要になります。

翻訳宣言

gawk.texi は巨大な単一ファイルのため、翻訳が重ならないように翻訳するセクションを宣言してください。ここで言うセクションとは、ここに記述されたセクション名です。

査読

完訳を優先しますが、査読は翻訳メンバーで行います。

文字コード

文字コードは euc-jp とします。これは現行の ja.po も euc-jp になっているためですが、今後 UTF-8 化されることも予想されますので、十分に注意してください。

  • euc-jp が扱えるエディタが必要です。

原文コメント

前述のとおりです。

@c This is Edition @value{EDITION} of @cite{@value{TITLE}:
@value{SUBTITLE}},
@c for the @value{VERSION}.@value{PATCHLEVEL} (or later) version of the GNU
@c implementation of AWK.
これは AWK の GNU による実装の @value{VERSION}.@value{PATCHLEVEL} (ま
たはそれ以降) のバージョン用の @cite{@value{TITLE}: @value{SUBTITLE}}
の@value{EDITION} 版です。

Texinfo の述語について

新しい単語が登場するとき、Texinfo コマンドを使用して @dfn{data-driven} のようになることが多いですが、これは @dfn{データ駆動}(data-driven) のように訳語を@dfn{}で囲み言語をその直後にカッコで囲んで残してください。

翻訳メモリ

Kbabel のようなもので取り込めるのかもしれませんが、特に利用していません。

備考

{{comment multi|w}}

Patch to fix A-Z and internationalization bug - さいとう (2006年11月03日 20時39分05秒)

Sam Trenholme からの投稿で C ロケール以外の /[A-Z]/ の挙動に関して修正するべきだというものがありました。

具体的には、

$ echo 'abc' | LANG=en_US.UTF-8 gawk '/[A-Z]/{print}'
abc

のような挙動はおかしいということです。gawk とマルチバイト文字と正規表現で一度 BBS に投げている内容です。{{comment multi|w}}

「現場力を高める見える化手法プロジェクトファシリテーション」 〜モチベーションアップのツールと場つくり〜 - さいとう (2006年10月21日 20時29分51秒)

平鍋先生を向かえての jus の勉強会が行われ、参加してきました。

平鍋先生は私の中では awker です。(え?

日時
2006 年 10 月 19 日 18:30-20:30
場所
東京体育館第一会議室

自己紹介

平鍋先生は 1998 年大学卒業なので、私よりも 5 年年上です。最初に CAD 開発を手掛け、C と shell という「硬いものと柔らかいもの」を使い分けているそうです。また、基本的にはオブジェクト指向派で、「技術 > プロセス」であると考えていたらしいのですが、2000 年に XP の世界に入ったそうです。なお、平鍋さんを紹介したのは jus の佐藤さんだそうです。某 F 社ではアジャイルというか業務内容の見直しで呼ばれたこともあるそうで、某 N 社の話題も挙がっていました。

永和システムの代表取締役で、従業員は 200 名あまりだそうです。そのため、他社のプロジェクトの外注を受けて仕事をする機会もあるそうです。

まぁ、どうでもいいんですが、平鍋先生はギターのコード変換を awk で処理したスクリプトを紹介したこともあり、私の Blog でも紹介したこともありました。Blog でも書かれていたように HDD を整理していた時に見つかった過去の遺産だそうですが、次回の awk 勉強会には興味を示されていました。

使用した資料はネット上にも掲載されている物で、誰でも閲覧可能ですが、やはり本人から講義を受けると誤認識していた部分も多々ありました。こうした部分を少しまとめたいと思います。

内容

使用した資料はほとんど以下のものと同じです。また、実際には使用されませんでしたが、朝会ガイドも添付されていました。

実はどちらも、某社で私が見つけてきて実践してみようとしていたものなので、以下は資料を見て自分が考えていたことと、講義とのギャップについてのメモになっています。

プロジェクトの成功は、Moving Target

「2 年後売れると思って開発した製品は、2 年後になると売れない」ということがあるように、流動的な仕様と現実とのギャップを狭くしていくことが目的です。また、「今、どこにいるのかを明確にし、揺れる需要に最後にミートする」ようにしていきます。これは「風に揺れるリンゴを揺れるはしごの上に乗ってつかむようなもの」だそうです。

見える化

重要なのは、「一箇所に、大きく書かれてあって、自分、相手、審判と観客全員が見ている」ことです。

バーンダウンチャート

バーンダウンとは「鎮火する」の意味です。縦軸に要求件数を、横軸に 1 回のイテレーションを取ります。イテレーションの単位は、1 週間くらいとし、必ず手でプロットします。見える化には必ずアナログ的なものを用います。

途中で進捗と予定が開いているところがありますが、ここで「今週はヤバイぞ」という異常を見えるのが分かります。ここで、優先度を変更するだとか、頑張って残業するなど、行動を行わせることが目的です。

車のタコメータも同じで、レッドゾーンに入ると危険な状態にあることを見える化しているものと同じです。

かんばん

「今、何をやっているか分かるようにする」ことが目的です。ToDo? に名前を書いて Doing に移しますが、手で名前を書くことでコミットの意識を持たせます。また、指示待ちではなく、自分で取っていくことが望ましいです。

ポータブルかんばん

これは某 C 社で実践した例で、まな板立てにかんばんを挿して使っています。その名も「かんばん -nano」。

次のページはウォーターフォールでのかんばんの例で、某 Y 社で使われているものです。ソフトの開発は見えにくいものですが、物理的なもので表現することが重要で、「指で指せるもの」であることが重要です。

また、形のないものを形にするだけで右脳 (空間把握能力を司る) が活性化し、チームの中での共通理解になります。Excel は物ではないため、望ましくありません。

朝会

「朝、声を出す」ことが重要です。詳しくは朝会ガイドを参照してください。また、時間は 15 分とし、それ以上は「2 次会」で行います。

ここでの発表は、

  • 昨日やったこと
  • 今日やること
  • 問題点

の 3 点のみとします。

また、「部外者には発言権がありません」

あんどん

あんどんにより「欠陥の長期滞在を排除」することが重要です。1 つでも問題があれば点灯させます。「欠陥のムダは欠陥の大きさ×滞在時間」であるため、ラインを止める権限は作業者にあります。

また、海外では XFD (eXtreme Feedback Device) というそうです。

例えば、

  • お客様からの不具合
    • →ランプが点滅
  • 社内への周知徹底
    • →ランプが点灯に変わる
  • 問題解決
    • ランプが消灯

というように使います。

だるま

だるまの目は「Begin と End」です。

ペアボード

ノートは人に知らせるには向いていないし、事務所にあるホワイトボードはポータビリティが低いのが欠点です。また、1 人 1 個のペアボードを持つのが望ましいです。

100 円ショップで購入した画板にホワイトボードの表面を張ったもので、総額 200 円のものを使っているそうです。(大きさは A4)また、飲み会でも使用したり、ライブハウスなどで使っても効果的だそうです。(平鍋先生はリクエスト曲をペアボードに書いてリクエストしたこともあるそうです)

色つき UML

UML である必要はなく、物理構造を明らかにして、指で指せるようにするもので、「ここ」とか「あそこ」が通じるようにすることが重要です。決して正確である必要はありません。できれば A1 の紙が望ましいそうです。

具体的には「潜水艦の作戦司令室」のようなものだそうです。

ふりかえり (1)

「金曜日の 3 時間」はふりかえりの時間とか決めておきます。必ず「問題 vs 私たち」となるようにします。「問題の理解」が重要であり、「問題ばらし」とまで言われています。また、ふりかえりを行うことで理解と解決が同時に進んでいきます。

ふりかえり (2)

チームが毎週金曜日に Keep と Try をやるだけで効果があります。また、全てを解決するのではなく、「自分たちで来週できるもの」を解決していきます。

ふりかえり (3)

英語では Retrospective と言われ、「前向きなふりかえり」と訳されます。

上には線表を書いて、下に自分たちがやったことを並べます。そうすることで「僕たちは良くやったよね」となり、自分の物語が自分たちの物語に変わっていきます。また、「打ち上げ」はプロジェクトのひとつですので、必ず「打ち上げ」をします。

マインドマップ

マインドマップは、「ノート術」のひとつです。真ん中にテーマを書き、絵など視覚的インパクトの強いものを入れますが、これが思い出すときのブックになります。

人間の記憶力にはあまり差がありませんので、思い出す時のフックの大きなものを作ることが重要です。

Demos (JUDE)

この JUDE で作られたマインドマップは TAB 区切りのツリー構造になっていますので、Excel にペーストすればツリー構造の表になり、PowerPoint? にペーストすればスライドの見出しが完成します。

にこにこカレンダー

にこにこカレンダーはムードの見える化です。これを見れば「一人だけダメダメだったら、声をかけてあげたり、相談する」などの行動に移すことができます。

にこにこカレンダーの例

リリース日を過ぎるとニコニコが増え、リリース日に近づくにつれて厳しくなってきているのが目に見えて分かります。問題は、厳しくなっている時にいかにモチベーションを上げていくかです。

見えなければ行動ができない

今まで書いた部分は全て参考になりそうなものですが、全てを行うものではありません。

「ファシリテーション」とは

ファシリテーションとは「場作り」です。

アジャイルソフトウェア開発

XP の中に、「終わったら必ず顧客と食事をすることもプロセスのひとつである」と書かれている。「勇気」だとか「敬意」といったアナログ的なものが見直されています。

リーンソフトウェア開発

「リーン」とは、「痩せている」の意味で「無駄のない」というトヨタの言葉の置き換えです。また、「リーンソフトウェア開発」の第 2 版が出ます。

トヨタ生産方式からのヒント

Pull 型の生産はまさにアジャイルであり、「欲しいものを 1 つづつ作っていく」とこです。

一人ひとりに工夫の権利が与えられることで、チームで工夫したりチーム全体が向上していきます。

日本語では「ハネムーンナンバー」(何人寿退社しても大丈夫か?) と言われますが、「トラックナンバー」と言う言葉があり、プロジェクトで「何人トラックに轢かれても大丈夫か」・・・つまり、ペアで作業を行い多くの人のスキルを上げていく必要があります。

タイムリーにも Matz さんが書いています。(さいとう注)

PF のなりたち

ファシリテーションは参加型意思決定であり、実践は日々変化していくものです。まさに「風に揺れるリンゴ」です。

目的 : なぜ PF が重要か

PF は場作りであり、プロジェクトマネージメントではありません。QoEL (Quality of Engneering Life) の向上である。(ちなみに QoL は、人生の時間よりも質を高めるためにホスピスなどで用いられる言葉です)

見える化

見える化は「行動に繋がる見える化」でなければいけません。

名前付け

名前は自分と他人に気付きを促すものです。

問題対私たちの構図

WinWin? はまさに「私たち」が勝ったことです。(だから 2 つ)

カイゼン

自分たちで来週からできることだけがカイゼンです。

全体構成

リズムも重要で、必ず人間のリズムでなければいけません。

導入のポイント

20 代、30 代の人が必ず中心に行います。

最近、Life Hacks と言う言葉がありますが、まさに「Getting Project Done」が PF です。

Without Practice, No Emergence

750 年続いている教えには何かが必ずあります。

懇親会

平鍋先生のファシリテーションに限らず、多種多様な話題が飛び交う懇親会になりました。なので、全てを書ききることすら困難なので、パス。ただ、平鍋先生の終始にこやかな顔が印象的でした。

また、「ギターコードを見る chordview」の awk スクリプトの話をすると、非常に喜んでくれました。

あとがき

適当にメモしたものから書き起こしていますので、不適切な表現や間違っているところがありましたら、ご指摘ください。後で、他でこのメモを使うため、リンクなどは Wiki ライクでない表記がありますが、お許しください。


コメント

Re:訂正 - さいとう (2007年02月28日 23時51分39秒)

平鍋先生の名前が平林に一部なっていました。申し訳ありませんでした。

{{comment multi|w}}

「もっと便利に awk を使ってみよう」勉強会について - さいとう (2006年10月14日 20時11分18秒)

日本 UNIX ユーザ会の主催でもっと便利に awk を使ってみようという勉強会を開催させていただくことになりました。

せっかくの勉強会ですから、当日参加される方で「こんなことが知りたい」といった内容がありましたら、以下に書き込んでください。

できるだけ参考にさせていただいて、少しでも皆さんのお役に立てるような勉強会にしたいと思います。

よろしくお願いします。

アジェンダについて - さいとう (2006年10月14日 20時19分06秒)

既にアジェンダは大体決めていて、以下のとおりです。

  • What is AWK?
    • 簡単な awk の紹介をしていきます。
  • AWK syntax
    • 簡単な awk の文法の紹介をしていきます。
  • One liners
    • できるだけ誰でも使えそうな一行野郎の紹介をします。
  • Examples
    • 少し複雑な例を紹介します。
  • About i18n
    • gawk の国際化について簡単に紹介します。
  • Crazy AWKer's program
    • 「100 行野郎」を超えるような凄い awk のプログラムを紹介します。
  • What is xgawk?
    • xgawk について簡単に紹介します。
  • Examples of xgawk
    • xgawk の例を簡単に紹介します。
  • Community
    • 「日本 GNU AWK ユーザー会」について簡単に紹介します。
  • Books
    • 日本で出版されている awk 関連書籍を紹介します。
  • Q & A
    • 本勉強会を通しての質疑応答を行います。

{{comment multi|w}}

Get started with GAWK: AWK language fundamentals - さいとう (2006年10月05日 00時11分15秒)

以下のページで、"Get started with GAWK: AWK language fundamentals" というドキュメントが公開されています。

awk の最小限の部分を丁寧に解説してくれていますが、複雑な awk スクリプトの紹介よりも、役立つ小道具のような感じで書かれています。{{comment multi|w}}

キミならどう書く 2.0 - ROUND 3 - まとめ - さいとう (2006年09月03日 00時34分08秒)


まずは普通に書いてみる。

キミならどう書く 2.0 - ROUND 3 - にあるサンプルの * の個数と異なるが、以下のようにしてできる。少し無駄を多めに作っているけど、これでほぼ完成である。

#! /usr/bin/gawk -f
#=====================================================================
# http://ll.jus.or.jp/2006/blog/doukaku3
# キミならどう書く 2.0 - ROUND 3 -
#---------------------------------------------------------------------
# たとえば以下のようなものです.
#
#% ./graph 2 5 9
#  2/ 16 : *****
#  5/ 16 : ************
#  9/ 16 : ********************
#
# このプログラムでは最大の数値に対応する '*' の数を 20 とし,与えられた
# 数値に応じた数の '*' を出力しています.
#=====================================================================
BEGIN {
  #===================================================================
  # バーの最大値
  if ( max_bar == "" ) {
    max_bar = 20;
  }
  #===================================================================
  # 必要な ARGV だけ抽出
  for ( i = 1; i <= ARGC - 1; i++ ) {
    data[i] = ARGV[i];
    num_data++;
  }
  for ( i = 1; i <= num_data; i++ ) {
    printf( "%3d/%3d : %s\n", data[i], get_sum( data ), \
                              bar( data[i], data ) );
  }
}
#=====================================================================
# 配列中の最大値を見つける
function get_max( arr,  i, max ) {
  for ( i in arr ) {
    if ( arr[i] > max ) {
      max = arr[i];
    }
  }
  return max;
}
#=====================================================================
# 配列の総和を求める
function get_sum( arr,  i, sum ) {
  for ( i in arr ) {
    sum += arr[i];
  }
  return sum;
}
#=====================================================================
# "*" の文字列を得る
function bar( num, arr,  num_star, i, bar_star ) {
  num_star = int( num / get_max( arr ) * max_bar );
  for ( i = 1; i <= num_star; i++ ) {
    bar_star = sprintf( "%s*", bar_star );
  }
  return bar_star;
}

実行結果

実行結果は以下のとおり。

$ gawk -f graph.awk 2 5 9
  2/ 16 : ****
  5/ 16 : ***********
  9/ 16 : ********************

変数 max_bar で最大のバーの長さを可変にしてある。

$ gawk -v max_bar=60 -f graph.awk 2 5 9
  2/ 16 : *************
  5/ 16 : *********************************
  9/ 16 : ************************************************************

Collatz 予想の 97 を描画させてみる

右のグラフはキミならどう書く 2.0 - ROUND 2 - まとめで OOo で描画させたものであり、これを描画させてみることにする。

まず、collatz.awk を用意。(以前のものと異なっています。)

#! /usr/bin/gawk -f
BEGIN {
  if ( ARGV[1] == "" ) {
    max = 100;
  } else {
    max = ARGV[1];
  }
  count = 0;
  max_num = 0;
  collatz( max );
}
function collatz( num ) {
  printf( "%d ", num );
  if ( max_num < num ) {
    max_num = num;
  }
  if ( num == 1 ) {
    result = 1;
    count++;
    printf( "\n" );
  } else {
    if ( num % 2 == 0 ) {
      result = collatz( num / 2 );
    } else {
      result = collatz( 3 * num + 1 );
    }
    count++;
  }
  return result;
}

graph.awk の printf() 関数の桁数を 5 桁にして、以下のように実行します。引数として値を与えるので、以下のような書式になります。

$ gawk -v max_bar=60 -f graph.awk `gawk -f collatz.awk 97`
   97/103254 :
  292/103254 : *
  146/103254 :
   73/103254 :
  220/103254 : *
  110/103254 :
   55/103254 :
  166/103254 : *
   83/103254 :
  250/103254 : *
  125/103254 :
  376/103254 : **
  188/103254 : *
   94/103254 :
   47/103254 :
  142/103254 :
   71/103254 :
  214/103254 : *
  107/103254 :
  322/103254 : **
  161/103254 : *
  484/103254 : ***
  242/103254 : *
  121/103254 :
  364/103254 : **
  182/103254 : *
   91/103254 :
  274/103254 : *
  137/103254 :
  412/103254 : **
  206/103254 : *
  103/103254 :
  310/103254 : **
  155/103254 : *
  466/103254 : ***
  233/103254 : *
  700/103254 : ****
  350/103254 : **
  175/103254 : *
  526/103254 : ***
  263/103254 : *
  790/103254 : *****
  395/103254 : **
 1186/103254 : *******
  593/103254 : ***
 1780/103254 : ***********
  890/103254 : *****
  445/103254 : **
 1336/103254 : ********
  668/103254 : ****
  334/103254 : **
  167/103254 : *
  502/103254 : ***
  251/103254 : *
  754/103254 : ****
  377/103254 : **
 1132/103254 : *******
  566/103254 : ***
  283/103254 : *
  850/103254 : *****
  425/103254 : **
 1276/103254 : ********
  638/103254 : ****
  319/103254 : **
  958/103254 : ******
  479/103254 : ***
 1438/103254 : *********
  719/103254 : ****
 2158/103254 : **************
 1079/103254 : *******
 3238/103254 : *********************
 1619/103254 : **********
 4858/103254 : *******************************
 2429/103254 : ***************
 7288/103254 : ***********************************************
 3644/103254 : ***********************
 1822/103254 : ***********
  911/103254 : *****
 2734/103254 : *****************
 1367/103254 : ********
 4102/103254 : **************************
 2051/103254 : *************
 6154/103254 : ***************************************
 3077/103254 : *******************
 9232/103254 : ************************************************************
 4616/103254 : ******************************
 2308/103254 : ***************
 1154/103254 : *******
  577/103254 : ***
 1732/103254 : ***********
  866/103254 : *****
  433/103254 : **
 1300/103254 : ********
  650/103254 : ****
  325/103254 : **
  976/103254 : ******
  488/103254 : ***
  244/103254 : *
  122/103254 :
   61/103254 :
  184/103254 : *
   92/103254 :
   46/103254 :
   23/103254 :
   70/103254 :
   35/103254 :
  106/103254 :
   53/103254 :
  160/103254 : *
   80/103254 :
   40/103254 :
   20/103254 :
   10/103254 :
    5/103254 :
   16/103254 :
    8/103254 :
    4/103254 :
    2/103254 :
    1/103254 :

と、時計方向に 90 度回転したものができました。

まとめ

今回はサラリと流してみたいが、本来はこのグラフを転置させて同じような上下のバーグラフを描画したかったのだが、意外に難しいのとあまり本質ではないことから、ここで終わりとします。


コメント

{{comment multi|w}}

キミならどう書く 2.0 - ROUND 2 - まとめ - さいとう (2006年07月14日 23時33分15秒)

キミならどう書く 2.0 - ROUND 1 - はどうだったでしょうか?個人的には LL Ring のページに「なぜ解説がないのか?」と思ってしまうのですが、単なるアルゴリズムで終わらないように前回同様に今回も詳しく見ていきます。

今回も、

ライブラリなど花拳繍腿、自作こそ王者の技よ

というわけでスクラッチばかりです。

キミならどう書く 2.0 - ROUND 2 - のお題は「Collatz 予想」または「角谷予想」や「3x+1 問題」と呼ばれているものです。

日本語の Wikipedia に記載がないので、英語版で検索してみると以下の URL に詳細が記載されています。

つまり、Collatz は任意の自然数 n に対して、

  • n が偶数の時は 2 で割る
  • n が奇数の時は 3 をかけて、1 を足す

という操作を行っていくと、必ず 1 に収束する、という予想をしたというもので、未解決問題集のひとつとされています。

下記の URL を見れば、膨大な計算が現在も続けられていることも分かります。

さて、上記の n に対して 100 を実行した際の最大ステップとその際の n を求めよという解釈で進めます。

普通に作ってみる

自己再帰で組むのが楽そうなので、作ってみました。

#! /usr/bin/gawk -f
BEGIN {
  if ( ARGV[1] == "" ) {
    num = 100;
  } else {
    num = ARGV[1];
  }
  for ( i = 1; i <= num; i++ ) {
    count = 0;
    collatz( i );
    if ( count > max ) {
      max = count;
      max_num = i;
    }
  }
  printf( "%d max=%d\n", max_num, max );
}
function collatz( num ) {
  if ( num == 1 ) {
    result = 1;
    count++;
  } else {
    if ( num % 2 == 0 ) {
      result = collatz( num / 2 );
    } else {
      result = collatz( 3 * num + 1 );
    }
    count++;
  }
  return result;
}

少し荒削りな部分もありますが、簡単に作れます。

  • ARGV でも値 n を読み込めるようにします。
    • 100 だけじゃつまらないので、100 以外も簡単に指定できるようにしておきます。
  • 1〜100 は for ループで回します。
    • この際に最大ステップも求めています。
  • 関数として Collatz の式を定義しています。
    • ここでステップ数もカウントしています。

実行してみましょう

答えは、97 の時に 119 ステップです。バックグラウンドでいろいろ動作している中で計算させましたが、非常に高速に結果を出しています。

$ time gawk -f collatz.awk 100
97 max=119

real    0m0.045s
user    0m0.016s
sys     0m0.028s

計算速度に関しては面白いことが分かります。次に n を 10, 100, 1000, 10000, 100000 で計算させた時の時間を求めてみましょう。

Time n = 10 n = 100 n = 1000 n = 10000 n = 100000
real 0m0.031s 0m0.055s 0m0.428s 0m6.308s 1m6.532s
user 0m0.000s 0m0.016s 0m0.336s 0m4.896s 1m2.028s
sys 0m0.020s 0m0.036s 0m0.036s 0m0.060s 0m0.120s

100000 を超えたあたりから莫大な計算時間が発生していることが分かります。

つまり、この「Collatz の予想」の面白いところでもあるのですが、n が 1 に収束する場合でも、途中で非常に大きな値をとって、収束に時間のかかることがあるという可能性があります。

ここからが面白いところ?

では、実際にどうなっているのでしょうか?少しの改良で途中の結果をログとして出力させることができますので、以下のように変更して実行してみることにします。

#! /usr/bin/gawk -f
BEGIN {
  if ( ARGV[1] == "" ) {
    num = 100;
  } else {
    num = ARGV[1];
  }
  for ( i = 1; i <= num; i++ ) {
    count = 0;
    collatz( i );
    if ( count > max ) {
      max = count;
      max_num = i;
    }
  }
  printf( "%d max=%d\n", max_num, max );
}
function collatz( num ) {
  printf( "%d ", num );  # ←
  if ( num == 1 ) {
    result = 1;
    count++;
    printf( "\n" );      # ←
  } else {
    if ( num % 2 == 0 ) {
      result = collatz( num / 2 );
    } else {
      result = collatz( 3 * num + 1 );
    }
    count++;
  }
  return result;
}

矢印の部分の printf を追加してみました。

さて、ここで得られた結果で n = 97 の部分をグラフにしてみます。縦軸には最大値、横軸にはステップ数を取っています。

アッサリと収束するどころか、10000 に近い値になっていることが分かります。この最大値は n^a (a=2.1...) を超えないと予想されています。つまり 97^2.1 = 14866.91 を超えてないことになります。

さて、本当なのでしょうか?

先ほどのログから 9232 が最大であることから、確かに超えません。

実は、これが証明できれば、無限に発散することがないため、無限ループにならない限り、この Collatz の予想は正しいことになるわけです。

32 bit を超えて

この話を書いていると、小飼さんの Blog で以下のようなものがありました。

木村さんが言うには、gawkdobule で数値を扱っていて、double の mantissa は 52bit (+けちビット) あるので、通常の gawk でも 113383 は計算できます。

"One True AWK" で調べると確かに 113383 で引っかかるので、以前は 32 bit 整数でリミットしていたものと思われます。

ずーっと 113383 まで計算させるのが面倒なので、以下のように改造してみます。

#! /usr/bin/gawk -f
BEGIN {
  if ( ARGV[1] == "" ) {
    max = 100;
  } else {
    max = ARGV[1];
  }
  count = 0;
  max_num = 0;
  collatz( max );
  printf( "%d max=%d(%d)\n", max, count, max_num );
}
function collatz( num ) {
  if ( max_num < num ) {
    max_num = num;
  }
  if ( num == 1 ) {
    result = 1;
    count++;
  } else {
    if ( num % 2 == 0 ) {
      result = collatz( num / 2 );
    } else {
      result = collatz( 3 * num + 1 );
    }
    count++;
  }
  return result;
}

計算させると、

$ gawk -f collatz.awk 113383
113383 max=248(2482111348)
               ~~~~~~~~~~

ちなみに、同じく小飼さんの Blog に出ている以下のものも計算できます。

ここに出ているものくらいであれば、gawk で計算可能範囲です。

篩を考える

先のキミならどう書く 2.0 - ROUND 1 - では、エラトステネスの篩という便利な篩があり、頭の中で素数を求める場合にも目の粗い篩を使っているわけですが、同じようにできないでしょうか?ここでは n が大きな値の探索に限ってみます。

まず、偶数の場合ですが、次が n/2 になるので、既に探索済みのものになり、調べる必要がなくなります。

と思ったら、3n+1 問題の中で、

これは自身なし

n=10000000000

g(9780657630) = 1133

4222.760u 4223.620s 2:23:12.06 98.3% 0+0k 0+0io 95pf+0w

というものがあり、9780657630 が偶数です。

しかし、9780657631 も 1133 ステップであることから、同じステップ数のものは複数存在する可能性があることを示唆しています。

次に、例えば、4n+1 の形の奇数の場合には、次が 3*(4n+1)+1 = 4*(3n+1) となるため、2 で 2 回割れます。つまり 3*(4n+1)+1 = 4*(3n+1) → 2*(3n+1) → 3n+1 となり、探索の必要がないでしょう。

if 文で組み込むと以下のようになります。

#! /usr/bin/gawk -f
BEGIN {
  if ( ARGV[1] == "" ) {
    num = 100;
  } else {
    num = ARGV[1];
  }
  for ( i = 1; i <= num; i++ ) {
    if ( i % 2 != 0 || ( n - 1 ) % 4 != 0 ) {
      count = 0;
      collatz( i );
      if ( count > max ) {
        max = count;
        max_num = i;
      }
    }
  }
  printf( "%d max=%d\n", max_num, max );
}
function collatz( num ) {
  if ( num == 1 ) {
    result = 1;
    count++;
  } else {
    if ( num % 2 == 0 ) {
      result = collatz( num / 2 );
    } else {
      result = collatz( 3 * num + 1 );
    }
    count++;
  }
  return result;
}

これを元に少し振るいにかけて 100000 の速度を見てみます。

Time ノーマル 篩あり
real 1m8.703s 1m9.386s
user 1m2.380s 1m3.044s
sys 0m0.364s 0m0.380s

あまり変わりませんね。むしろ遅いくらい。(w

実はこれ、if 文の "||" (OR) が影響しているようです。

if 文のところを

    if ( i % 2 != 0 ) {

にすると、

Time ノーマル 篩あり 偶数除去
real 1m8.703s 1m9.386s 0m44.331s
user 1m2.380s 1m3.044s 0m33.282s
sys 0m0.364s 0m0.380s 0m0.424s

と劇的 (?) に高速になりました。

こうしたあらかじめ人間が数学的な根拠から行う高速化としては、3n+1 問題:まだまだ高速化あたりに出ていますので、参考にしてみてください。

確かに Haskell や高速 CPU を用いると高速に解が求まるのかもしれませんが、その前に考えるということをしてみませんか?

最後に

私は数学者でも数学科の卒業でもなければ、大学時代に数学の単位を落としかけたことがある程度なので、この「Collatz の予想」がどのくらい凄いことなのかは分かりません。ただし、Collatz の予想を解くよりも、その背景の方が気になるので、いろいろ書いてみました。

LL だからこそ手軽に調べられる利点を生かして、いろいろと調べてみました。個人的には、先のキミならどう書く 2.0 - ROUND 1 - においても、かなり可読性が高い (C 言語ライクである) 部類に属していると思っており、特定の言語しか習得していなくても、ある程度読める言語であることが分かります。逆に、他の言語 (関数型言語は別ですが) を習得していれば、記述することも容易な言語ではないでしょうか。

さて、今回の最後はそうしたことを日本の awker 用に書いてくださった gawk のメンテナー Arnold Robbins の言葉で閉めたいと思います。お付き合いありがとうございます。

Awk is often called a "little" language. And in terms of number of features, that's true. But the features it does have, both singly and in combination, provide both power and elegance. You can do a lot of things with small, easy to read (and easy to write!) programs. If you invest the time to learn awk, you may find that you don't really *need* to invest a lot more time learning some of the other languages out there.

awk はしばしば「小さい」言語と呼ばれます。 特徴の点では、それは本当です。しかし、それが単独と組み合わせで持つ特徴は、パワーとエレガントの両方を提供してくれます。 小さく、読みやすい (そして、書くのも簡単です !) プログラムで多くのことができます。awk を学ぶ時間を費やすなら、ずっと多くの時間を他の言語のいくつかを学びながら費やす必要はないと本当にわかるでしょう。

…決まった。(コンプリート! (w

locale-dependent assertion failure in gawk 3.1.5 - さいとう (2006年07月08日 00時27分01秒)

以下のようなバグが報告されています。

報告者は Andrew J. Schorr。少しは UTF-8 の問題に気が付いてくれるかな。

ただし、今までのパッチを当てたこれを適用してもダメですね。

http://lists.nongnu.org/archive/html/bug-gnu-utils/2006-07/msg00015.html


Re: - さいとう (2006年07月08日 03時03分55秒)

http://lists.nongnu.org/archive/html/bug-gnu-utils/2004-04/msg00060.html

上記のバグと同じという話が出ています。

Re: - きむら (2006年07月08日 15時07分28秒)

Andrewによるパッチがでてますね。*また* wstptr か!(笑)ところで2番目のパッチはおいらのと同じでないかい? >Andrew

Re: - さいとう (2006年07月09日 12時16分45秒)

とりあえず Arnold の判断待ちになってるみたいですが、きむらさんのパッチが適用されるといいですね。{{comment multi|w}}

conversion error - さいとう (2006年07月07日 00時45分47秒)

以下のエラーが報告されています。

文字列と数値の変換時のエラーでパッチも Arnold から出ています。

http://lists.nongnu.org/archive/html/bug-gnu-utils/2006-07/msg00005.html

{{comment multi|w}}

キミならどう書く 2.0 - ROUND 1 - まとめ - さいとう (2006年06月26日 23時45分26秒)

はじめに

LL Ring の前哨戦として「キミならどう書く 2.0 - ROUND 1 -」という内容のイベントが催され、6/26 時点ではコメントに書き込んだ方が 23 名、トラックバックが 65 名と非常に盛況のうちに終了のゴングが鳴らされました。

100 までの整数から素数を列挙せよ

このお題は「高橋メソッド」でお馴染みの (いや、Ruby, RoR で有名な) 高橋さんのアイデアを高野さんがアレンジしたものです。

さて、素数って何でしょうか?因数分解を習う中学の時に習ったのですが、なかなか言葉にすると難しいです。Wikipedia による素数を見ると、以下のように書かれています。

素数(そすう)とは、1とその数自身以外に正の約数を持たない(つまり1とその数以外のどんな自然数によっても割り切れない)、1 より大きな自然数のことである。

さて、実はここに出題者の引っ掛けがありました。1 は素数ではないのです。これに気が付けば 1 を特別扱いするよりも最初から除外した方が楽になります。

具体的には、

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

が素数になります。

普通に考えてみよう

ここにも書いた内容ですが、私の嫁が言うには、

素数って直感で思いつくものでは!?

だそうです。直感と言うよりも、整数 n を 2 から n -1 までで割っていって、割り切れなければ n は素数ということを頭の中で行っていたそうです。

つまり、

#! /usr/bin/gawk -f
BEGIN {
  for ( num = 1; num <= 100; num++ ) {
    for ( div = 2; div <= num; div++ ) {
      if ( num % div == 0 ) {
        if ( num != div ) {
          break;
        } else {
          printf( "%d ", num );
        }
      }
    }
  }
  print;
}

という計算を脳内で行っていたことになります。時間のかかるアルゴリズムですが、非常に素直で誰にも分かりやすいものだと言えます。

さて、分かりやすいのですが、本当に整数 n までの全ての値を検査していく必要があるのでしょうか?答えは NO です。キミならどう書く 2.0 - ROUND 1 - の各言語の解答に多く書かれているように、中の for ループで break で脱出する際には、以下のように div * div > num で脱出させると計算量が少なくなります。

  for ( div = 2; div <= num; div++ ) {
    if ( div * div > num ) {
      return num;
      break;
    }
    if ( num % div == 0 ) {
      return 0;
    }
  }

エラトステネスの篩

Wikipedia によれば「エラトステネスの篩」という素数計算方法があります。

例えば、素数 2 で割り切れるものは最初に除外してしまい、次に素数 3 で割り切れるものは除外して…と徐々に篩 (ふるい) にかけていくようにして計算することからこのように呼ばれます。

awk での解法は以下のようになります。

#! /usr/bin/gawk -f
BEGIN {
  max = 100;
  for ( i = 2; i <= max; i++ ) {
    num_arr[i] = i;
    for ( j = 2; j <= max; j++ ) {
      if ( num_arr[i] % j == 0 && num_arr[i] != j ) {
        num_arr[i] = 0;
      }
    }
  }
  for ( i = 2; i <= max; i++ ) {
    if ( num_arr[i] != 0 ) {
      printf( "%d ", num_arr[i] );
    }
  }
  print;
}

「エラトステネスの篩」にまだ残っているかどうかの情報を保持しなけえばならないため、配列を用いています。主要 LL と異なり、awk には配列操作関数が充実していません。そこで、古いから落ちたものを 0 として、あとで数え上げる時に 0 のものを除外する方法を用いています。

当然、ここでは配列を用いるため、非常に大きな数を処理する場合、大量のメモリも同時に消費してしまいます。

awk にも配列操作関数が欲しいところですが、その配列または文字列、数値列に値が入っているかどうかを検査する関数があれば、自分で書けそうな気もします。

ライブラリなど花拳繍腿、自作こそ王者の技よ

とは Ruby をはじめ多くの言語で活躍されている木村さんがパロディとして使った言葉ですが、ライブラリの少ない awk だからこそ、アルゴリズムを作る人の腕が試されるわけです。

LLR2006 - 1,000,000(番目|まで)の素数

Perl の jcode.pm や encode.pm で有名な小飼さんが、Perl5, Python, Ruby, ANSI C, Haskell, Javascript で記載されています。

同じように awk でも記載してみました。ほとんど同じアルゴリズムを使うことで、言語間の比較が容易になります。ただ、少し異なっており、

  • function の内部を for a in arr でループさせていない
  • awk には join がない

という部分が異なります。前者は awk の場合、配列の要素数に変更があっても、それをダイナミックに for a in arr の中で変更できないからです。(合ってます?)

#! /usr/bin/gawk -f
BEGIN {
  max = 100;
  if ( ARGC == 2 ) {
    max = ARGV[1];
  }
  for ( i = 2; i <= max; i++ ) {
    is_prime( i );
  }
  for ( i = 1; i <= num_prime; i++ ) {
    printf( " %s", prime[i] );
  }
  print;
}
function is_prime( n ) {
  for ( d = 1; d <= num_prime; d++ ) {
    if ( prime[d] * prime[d] > n ) {
      break;
    }
    if ( n % prime[d] == 0 ) {
      return 0;
    }
  }
  prime[++num_prime] = n;
  return n;
}

三大言語との速度比較

手元の Celeron 600 MHz の Fedora Core 5 マシンで試すと以下のようになりました。

Perl, Python, Ruby のコードは LLR2006 - 1,000,000(番目|まで)の素数に掲載されていたものをそのまま用いています。

$ time perl prime.pl 1000000 > /dev/null

real    0m30.795s
user    0m30.634s
sys     0m0.080s
$ time ruby prime.rb 1000000 > /dev/null

real    1m3.633s
user    0m58.136s
sys     0m0.192s
$ time python prime.py 1000000 > /dev/null

real    0m31.086s
user    0m29.418s
sys     0m0.228s
$ time gawk -f prime_number_7.awk 1000000 > /dev/null

real    1m28.382s
user    1m23.109s
sys     0m0.176s

awk は惜敗という結果になりましたが、同じものを One True AWK で行ってみると、さらに遅い結果となりました。つまり、gawk はオリジナルの awk と比較してかなり最適化されているのではないでしょうか?

以下が One True AWK の結果です。

$ time ~/bin/awk -f prime_number_7.awk 1000000 > /dev/null

real    3m7.120s
user    2m59.355s
sys     0m0.396s

is_prime() を作っておきましょう

せっかくなので、上の is_prime() をいつでも使えるようにしておきましょう。

#! /usr/bin/gawk -f
BEGIN {
  print is_prime( 13 );
  print is_prime( 14 );
}
#=====================================================================
# is_prime()
# - return number, if it is prime number.
# - return 0, if it is not prime number.
function is_prime( num,   div ) {
  for ( div = 2; div <= num; div++ ) {
    if ( div * div > num ) {
      return num;
      break;
    }
    if ( num % div == 0 ) {
      return 0;
    }
  }
}
#=====================================================================

頻繁に使う関数とも思えませんが、載せておきます。

まとめ

素数を計算する方法を見てきたわけですが、いかがでしたでしょうか?キミならどう書く 2.0 - ROUND 1 - にはさまざまな言語で記述された素数計算方法が掲載されています。

義務教育を受けた人であれば誰でも知っている素数ですが、それをアルゴリズムにして表現する難しさ…いや、楽しさを味わってもらえたのではないでしょうか?

最後に Donald E. Knuth の台詞で終わりにします。

It has been often said that a person does not really understand something until he teaches it to someone else. Actually a person does not really understand something until he can teach it to a computer, i.e., express it as an algorithm.

以下、翻訳です。

よく他の誰かに教えるまで、人が本当に何であるかを理解していないと言われます。それをコンピュータに教えることができるまで、実際に人は本当に何であるかを理解していません、すなわち、アルゴリズムとしてそれを言い表してください。


コメント

{{comment multi|w}}

gawk 3.1.5 20060623 版 - さいとう (2006年06月23日 01時04分27秒)

gawk 3.1.5 はマルチバイトの文字列関数が使えるため、日本人には非常に有用なバージョンであるものの、一部では「gawk 3.1.6 のスケジュールは?」とか「もっと頻繁にリリースするべきでは?」と言われているようにバグが多いのが実情です。

そこで、私の方で確認できているパッチ当てたものを用意してみましたので、"Own Risk" でお使いください。したがって、問題があっても私は責任を負いません。

動作テストは Fedora Core 5 にて確認していますが、動作保障するものではありません。

以下適用したパッチ

以下のパッチを適用しています。

20060623 版での追加適用

20051223 版での追加適用

ただし、この一連のスレッドに関する議論はまだ行われている最中に Aharon Robbins のパッチのみを適用しています。

20051218 版での追加適用

20051202 版での追加適用

20051008 版での適用

ビルド方法

ビルド方法は、ドキュメント/インストールガイドに従うものとしますが、以下のようにしてビルドを行っています。

$ ./configure --enable-switch CFLAGS="-g -O3 -march=i686"
$ make
$ make check
$ su
# make install

また、"make check" は問題なく "ALL TESTS PASSED" であることは確認しています。

おまけ

各パッチの適用の際に、pot ファイルのインデックスが乱れたため、再度以下のようにして po ファイルを更新させています。

$ cd po
$ make gawk.pot-update
$ make update-po
$ make update-gmo

一応、全て翻訳完了の状態にしてありますので、そのままお使いください。


{{comment multi|w}}

/dev/fd/n bug in gawk 3.1.5 - さいとう (2006年06月14日 23時55分37秒)

/dev/fd/n のバグの報告がされています。

3.1.0 あたりからエンバグされているみたいですが、報告されないということはあまり使っている人もいないってことでしょうかね。

http://lists.nongnu.org/archive/html/bug-gnu-utils/2006-06/msg00032.html


Re: - さいとう (2006年06月18日 20時11分32秒)

http://lists.nongnu.org/archive/html/bug-gnu-utils/2006-06/msg00053.html

上の URL にパッチが Arnold から投げられています。

必要な方はどうぞ。

{{comment multi|w}}

gawk 3.1.5 array question... - さいとう (2006年04月30日 21時51分25秒)

以下の URL に投げられた質問で、

if(x["b"] == "a")   # <== this initializes x["b"] ???
  print "ok";

という部分が表示されないというものです。

awk は x["b"] で参照された際に初期化 (作成) されますが、条件は True になりません。(なったら怖い)

Jurgen が回答していますが、存在しているかどうかを判断するには、

if (("b" in x) && x["b"] == "a")
  print "ok"

のようにするそうです。

http://lists.nongnu.org/archive/html/bug-gnu-utils/2006-04/msg00053.html


{{comment multi|w}}

[ 1 2 3 ]


最終更新時間:2007年07月30日 22時13分08秒