2010-04-23

Binary Tree を作ってみた

C 言語のアルゴリズムでは、初歩として勉強する二分木 (Binary Tree)。

思い返してみたら、実は一度もソースコードを書いたことがない。いくら何年もプログラム書いてるからって、それはないだろう! といふことでサンプル・コードを書いてみた。

/**********************************************************************************/
/* Sample Source of Binary Tree                                                   */
/**********************************************************************************/
#include <stdio.h>
#include <stdlib.h>

typedef struct node
{
  struct node* left;
  struct node* right;
  int count;
  int num;
} node_t;

static node_t* add_node(node_t* node, int num)
{
  if (node == NULL){
    node = (node_t*)malloc(sizeof(node_t));
    if (node == NULL){
      fprintf(stderr, "No nodes\n");
      exit(1);
    }

    /* Set data */
    node->num = num;
    /* Child node is not available. */
    node->left = node->right = NULL;
    node->count = 1;
  } else {
    if (num < node->num){
      node->left = add_node(node->left, num);
    } else if (num > node->num) {
      node->right = add_node(node->right, num);
    } else {
      node->count++;
    }
  }
  return node;
}

static node_t* make_btree(int num[], int n, node_t* node)
{
  for (int i=0; i<n; i++){
    node = add_node(node, num[i]);
  }

  return node;
}

static void print_btree(node_t* node)
{
  if (node == NULL){
    return;
  }

  print_btree(node->left);

  printf("%d(%d), ", node->num, node->count);

  print_btree(node->right);
}

#if DEBUG
int main(void)
{
  int n[] = { 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, };
  int m[] = { 1, 1, 1, 3, 5, 9, 17, 31, 57, };
  
  node_t* nodes = NULL;
  nodes = make_btree(n, sizeof(n)/sizeof(int), nodes);
  nodes = make_btree(m, sizeof(m)/sizeof(int), nodes);

  print_btree(nodes);
  printf("\n");

  return 0;
}
#endif  /* DEBUG */

数字を二分木に追加していって、その重複度を数えるプログラム。

実行例はこの通り。

$ make
gcc -W -Wall -g -O2 -std=c99 -DDEBUG  -c -o btree.o btree.c
gcc -W -Wall -g -O2 -std=c99 -DDEBUG -o btree btree.o
$ ./btree
1(5), 2(1), 3(2), 5(2), 8(1), 9(1), 13(1), 17(1), 21(1), 31(1), 34(1), 55(1), 57(1), 

与えた引数は、フィボナッチ数列とトリポナッチ数列の最小の数項。1 が 5 回。3 と 5 が 2 回。それ以外の数字は 1 回ずつ現れているのが見てとれる。

Source Codes

ソースコードの一式 (Makefile 含む) は、gist に上げてある。

git clone git://gist.github.com/375570.git btree

もしよければ、改変などご自由に。

参考文献

C言語アルゴリズム+徹底入門 (標準プログラマーズライブラリ)

参考にはしたけれど、分かりにくい本なのであまりお勧めできない。

2010-04-19

Closure (クロージャー) って何だろう?

何年か前に Closure って何? って質問を受けた。当時、ぼくはその質問に答えることは出来なかった。今も出来る自信がない。だから少し勉強してみた。

初歩の初歩を噛じっただけだけど、考えをまとめるためにエントリーにしてみる。

参考文献

Closure と言えば Lisp ということで、Common Lisp の本を参考にした。

  • 「ANSI Common Lisp」(Paul Graham) pp.96-99
  • 「実践 Common Lisp」(Peter Seibel) pp.66-67

Closure

クロージャは「関数と環境を一緒にしたもの」。これがクロージャーの説明として一番良く聞く文言。

クロージャを知っている人にはこれで十分なのでせう。でも、ぼくにはこの説明はまるで霞を掴むように思える。

更に、「ANSI Common Lisp」から引用する。

関数が外部で定義された変数を参照するとき、その変数をフリー変数と呼ぶ。フリー・レキシカル変数を参照する関数はクロージャ (closure) と呼ばれる。そこでは関数が有効である限り、変数も有効であり続ける。

まだ良く分からない。でも一つ分かった。クロージャは関数だということ。その関数は、フリー・レキシカル変数を参照している。

レキシカル変数とは何か? 今度は「実践 Common Lisp」を引用してみる。

レキシカルなスコープを持つ変数は、束縛フォームの内部にあるコードだけが参照できる。Java、C、Perl、Python にはレキシカルなスコープを持つ「ローカル変数」があるので、こういった言語でプログラムした経験があるならレキシカルスコープにもなじみが深いはずだ。

レキシカル・スコープとは何ということはない。ありふれたスコープのこと。C 言語なんかで「ローカル変数は括弧の中でしか生きられない」とさんざ言っている。難しいことじゃなかった。レキシカル・スコープという名前に馴染みがなかったというだけの話。

クロージャはレキシカル・スコープな変数を参照するけど、その変数は関数の外部で定義されている。

ここで、「ANSI Common Lisp」のサンプル・コードを見てみる。

(let ((counter 0))
  (defun reset ()
    (setf counter 0))
  (defun stamp ()
    (setf counter (+ counter 1))))

関数 reset と stamp が定義されている。この 2 つの関数は、関数の外側の let 式で定義された変数 counter を参照している。なるほど、確かに counter という変数は let 内のレキシカル・スコープに収まっている。その counter を、関数外部の変数として関数 reset と stamp は呼んでいる。この時、関数 reset と stamp はクロージャになる。クロージャが関数と環境 (この場合、外の変数を指しているのだよね?) を一緒にしたもの、というのも何となく分かる気がする。

せっかくなので、stamp と reset を呼んでみやう。こんな感じに使うことができる。

> (list (stamp) (stamp) (reset) (stamp))
(1 2 0 1)

「ANSI Common Lisp」は「同じことは大域カウンターを使ってもできるが、上のようにすると、カウンタが不注意による書き換えから保護される」と続ける。なるほど。奥が深い。

Ruby で書いてみる

同じコードを Ruby で書いてみる。

class Counter
  def initialize
    @count = 0
  end
  def stamp
    return @count += 1
  end
  def reset
    return @count = 0
  end
end

c = Counter.new()

p c.stamp
p c.stamp
p c.reset
p c.stamp

実行例はこちら。

$ ruby count.rb 
1
2
0
1

Object 型の言語を見て思うのは、まずメンバー変数ありきで、そこにメソッド (関数) が付いているということ。昔、どこかで「Object 言語は構造体に関数を足したもの、クロージャは関数に変数を足したもの」というのを見た記憶がある。当時はよく分からなかったけど、今なら少し分かる気がする。

ANSI Common Lisp (スタンダードテキスト)実践Common Lisp

2010-04-17

Google Chrome Extension TechTalk に参加した

Google Chrome の拡張機能 (Extension) に関する TechTalk が先週開かれた。まずは概要:

アジェンダ及び資料へのリンクは上記案内ページにまとまっている。あまりに完璧なので、このブログで書くことがない程に。

と、リンク先参照だけで終わっては身も蓋もないので、コピペになるけどアジェンダを写しておく。

括弧で囲んだのは、当日の発表資料等へのリンク。

見ての通り内容は盛り沢山。全部を説明する気力もないので骨子だけ。

Google Chrome と HTML5

最近、HTML5 の動きが活発。HTML5 の先には、デスクトップ・アプリと同等のものがウェブ・ブラウザー上で動く世界が待っている。という及川氏の話で TechTalk はスタートした。Google Chrome も HTML5 対応をどんどんと進めていく。

田村氏の話は、特に Opera でサポートが進んでいる HTML5 Forms の Google Chrome における対応状況について。HTML5 Forms については HTML5 TechTalk の過去レビューを読んでもらうとして、Chrome が Opera に追いつこうと頑張っている状況が分かった (とは言っても、まだ Opera には及ばないけれど)。

白石氏の話は、HTML5 で策定中の Web Notifications の解説。何故、Web Notifications を取り上げるかと言うと、この仕様を提案しているのが Google 自身であり、唯一実装しているブラウザーが Google Chrome だから。Web Notifications は Google Calendar などで使われ始めている。

Google Chrome 拡張について

「Google Chrome 拡張入門」と銘打たれた太田氏の発表が、今回の TechTalk のメイン・ディッシュだった。時間にして 60 分。ただただ圧倒されるばかり。メモは追いつかない。嬉しいことに、説明ページを HTML5 で書いていて、内容のほとんどはそのページに書いてある。

このページ、右上に「目次」と薄く書いてある。カーソルを持っていくと、Chrome 拡張入門の「目次」がポップアップ (?) する。また右下には「設定」ボタンがあり、クリックすると font-size の変更及び背景色の変更ウィンドウ (?) が現れる。フォント・サイズ変更がスライド・バーなのも格好良い。Chrome の拡張とは関係ないけれど、HTML5 の未来を感じる素晴らしいサンプルになっている。

なお、2010-04-17 発売の Software Design 5 月号で「Chrome ブラウザ拡張実践入門」を書き下ろしているとのこと。上記ウェブページと併せて持っておけば、一通りの入門になるんじゃないかと思う (ので、ぼくは SD 5 月号を予約した)。

Software Design ( ソフトウェアデザイン ) 2010年 05月号 [雑誌]

あと、「Google Calendar for Todayの紹介と拡張内ページ間通信の実例」では Chrome 拡張に使われる background.html と popup.html でライフタイムが前者が長く後者が非常に短いとの話があった。そこで、取得したデータを何度もポップアップ表示するやうな拡張は、background.html でデータを取得・保存し、popup.html に渡すとポップアップの度にデータを取りに行かないので良い、という Tips を教わった。

他のライトニング・トークも面白いもの、興味深いものが多かった。基本 Google Chrome 拡張の実例だったけれど、内容を咀嚼しきれていないので割合。

あとがき

とにかく楽しかった。一年以上会っていない友人にも会えて、テンションが高くなった。かういふ技術講演には、できるだけ足を運びたい。そして何か成果を出したい。気持ちばかり焦って、何も出来ていないのが痛いところ。。。

2010-04-09

iPhone 4.0 プレビュー・イベント開催

2010-04-09 午前 2 時から、Apple は iPhone 4.0 のプレビュー・イベントを開いた。新しい iPhone OS は、今夏リリース。開発者用のプレビュー版は今日 (2010-04-09) リリースされる。

iPhone 4.0 の対象は iPhone 3GS と iPod touch 第 3 世代。iPhone 3G と iPod touch の第 2 世代では一部の機能 (マルチタスク!) が使えない。けれどアップデートは可能。iPhone OS 4.0 の iPad への提供は今秋を予定。

iPhone で追加される新機能は 100 以上。今回のプレビュー・イベントでは 7 つの機能に絞って招介が行なわれた。もちろん一番手は、お待ちかねのマルチタスク機能!!

1. マルチタスク機能

遂にマルチタスク機能が iPhone に搭載される。アプリの切り替えは、ホーム・ボタンのダブル・クリックから。すると、Mac のドック機能のように起動中のアプリのアイコンが現れる。一度に現れるアイコンの数は 4 つまでみたいだけど、そこは横スクロールが可能。

開発者向けの話をすると、マルチタスク機能は API として提供される。肝は 7 つの API。

  1. Background Audio
  2. VOIP
  3. Background Location
  4. Push Notification
  5. Local Notification
  6. Tast Completion
  7. Fast App Switching

Background Audio は、バックグラウンドに回っても音楽を鳴らせる機能。Pandora を始めとするインターネット・ラジオ用アプリでの利用が期待される。

VOIP は Voice Over IP の略で、Skype のやうな IP 電話の機能。着信があると、画面のトップに赤い帯が出て、電話がかかってきたことを知らせてくれる。このお知らせバーをダブル・タップすると、他のアプリを動かしながらでも通話が可能。

Background Location は、バックグラウンドでも GPS を動かし続ける機能。カーナビ・アプリなんかは、この機能がないと、バックグラウンド中に自分の位置を見失ってしまう。また、Loopt (Google Latitude と同種のアプリ) なんかも GPS の情報をバックグラウンドで取得できるやうになる。GPS の利用については気配りがされていて、アプリごとに GPS 利用の是非が問われる。ユーザーが OK を返すと、24 時間、そのアプリは GPS をバックグラウンドで利用可能になる。

Push Notification は、前のバージョンで実装された機能。バックグラウンドでお知らせ通知を受け取ることができる。Local Notification は、その GPS 限定版かな?

Task Completion は、処理 (タスク) をバックグラウンド中でも実行する機能。例えば、Flickr の写真アップロード機能を走らせたり、なんてことができる。

Fast App Switching は、アプリ切替時にその時のアプリの状態を保存できる機能。ゲームの途中でアプリを切り替えたりする時には、必須な機能だね。この API がないと、またゲームを最初からやり直さなくちゃいけなくなる。

2. フォルダー機能

フォルダー機能は、ホーム画面で提供される。Windows や Mac のフォルダーと同じやうに、アプリのアイコンをその中に入れられる。

今まで、アプリ・アイコンは画面一杯に配置されていた。アプリの数が増えると、画面をいくつもまたいで移動する必要があった。フォルダー機能はその煩わしさから解放してくれる。

フォルダーは、ドックの中にも配置可。フォルダーの名前はアプリのジャンルから自動生成される。もちろん、後で手で編集することも可能。フォルダー機能のおかげで、インストールできるアプリの数は 180 から大きく増えて 2160 個になる。

3. メーラー機能の強化

  • United inbox。複数のメール・サービスのメールを、一つの受信箱として表示する機能。
  • Organize by thread。メッセージのスレッド化。デモでは、どう見えるかまではよく分からなかった。
  • Open Attachments。添付ファイルを開く機能。添付ファイルを開くアプリは、App Store で購入したものの中から選べる。

4. iBooks

iPhone OS にも iBooks が来る!

5. 企業向けの機能

あまり興味もないので、機能の列挙だけ:

  • Even better data protection (データ保護機能の強化)
  • Mobile Device Management (?)
  • Wireless app distribution (?)
  • Multiple Exchange accounts (複数の Exchange アカウントをサポート)
  • Exchange Server 2010 (Exchange Server 2010 に対応)
  • SSL VPN Support (VPN が使えるようになる?)

6. Game Center

Social Game 機能が付いた。ゲームの中で、次のことができるやうになる。

  • 友人の招待
  • Matchmaking (?)
  • リーダー・ボード (ハイ・スコア達成者のリスト表示?)
  • Achievements (?)

ごめん。最後にやったゲームはスーパーマリオ 4 なので、ゲームのことはよく分からない。

7. iAd

モバイル広告!! この iAd の良い所は、広告からウェブ・ページへと飛ばされるということがないこと (本当に本当かなぁ?)。基本、アプリ内アプリとして動作するらしい。

それ以外の機能

  • Bluetooth キーボードのサポート
  • ホーム・スクリーンの壁紙変更
  • ビデオでタップしてフォーカス
  • 5 倍のデジタル・ズーム
  • ギフト・アプリ (?)
  • カレンダーへのアクセス
  • 写真ライブラリーへのアクセス
  • 写真に GPS 情報付与
  • Geotagging
  • プレイリストの作成
  • アプリケーション内 SMS
  • スペル・チェッカー

あとがき

今回、第 4 世代 iPhone (iPhone HD?) の発表はなかった。iPhone OS 4.0 の機能は、きっと新 iPhone でこそフルに発揮されると思う。

ぼくは iPhone 3G を使っている。今年の 7 月には 2 年縛りが解ける。マルチタスクの使えないとう iPhone 3G とはおさらばして、新 iPhone に乗り換えたい。夏までに第 4 世代 iPhone の発売はあるのか?

iPhone OS 4.0 はぼくの期待を膨らませ、ちょっと iPhone HD へと心を馳せさせた。

2010-04-07

フリー <無料> からお金を生みだす新戦略 (クリス・アンダーソン)

「ロングテール」という言葉を生みだした Chris Anderson (クリス・アンダーソン) が、新著「Free (フリー)」を発売した。読みたいと思っていたところ、知人が買ったというので借りて読ませてもらった。

フリー

「フリー」は、ロングテールの時と同じく、ネットの特殊性に注目して「フリー (無料)」で物やサービスを提供できるやうになったことを数多くの事例を混えながら説明している。

「ロングテール」の時のポイントは、ネットの世界では在庫が無限に持てることだった。在庫を持つことの費用が限りなくゼロに近いことが、現実世界と違っていることがポイントだった。

「フリー」のポイントは、ハードディスクとネットワーク帯域が無限に持てるようになってきたこと。保存と運搬 (通信) に対して、費用が限りなくゼロに近づき始めたことがポイントと言う。

まあ、これは話の序の口。データ保存と通信の費用がゼロになる。というだけでは、お金もうけは出来ない。そこで、どう知恵を絞って「無料」から「お金」を生みだすか? その工夫を読むところが本書の面白いところ。例えば、価格の下落スピードが以前とは比べものにならなくなったので、先を見越して特売価格を付けても (その時は赤字のように見えて) 安価の見返りに得られる膨大なシェアなどに後押しされて、最終的には黒字になった、という風に話が進んでいく。通して読むと、「フリー (無料)」の大枠が見える構成になっている。

もしちょっと立ち読みしたいなら、本のところどころに入っている一ページ・エッセイがおすすめ。実際の企業を取り上げていて、「フリー」から金儲けしたエピソードがまとめられている。その中には、ネットの世界に限った話ではなくて、新聞社のエピソードだったり、自転車レンタル会社の話なんかもある。ロングテールは、かなりネットの中で閉じた概念だったけど、今回のフリーはネットの世界に限らない。同じやうな産業構造を見つければ、一工夫できてしまう。本書の魅力は、その間口の広さもあるかもしれない。

フリー~〈無料〉からお金を生みだす新戦略