Shoeisha Technology Media

CodeZine(コードジン)

特集ページ一覧

Java meets Python - 第3回 構造体とクラス:二分木

よろずプログラマーのためのPython導入ガイド (5)

  • ブックマーク
  • LINEで送る
  • このエントリーをはてなブックマークに追加

Java/Pythonも「C言語で書かれたアプリケーション」の一つです。どちらも、C言語で作成された部品を集積して、高機能を提供します。C言語のバイブルとされるK&Rでは、二分木を使って単語の頻度を求める事例を紹介しています。この事例を通して、C言語のDNAを持つ、 Pythonの世界へと誘います。

目次

はじめに

 連載3回目は、前半をプログラミング歴3年の河野兄弟が、後半をプログラミング歴7年の後藤いるかが担当しますので、よろしくお願いします。

 Javaの立場からすると、Jythonはシンタックスシュガーを提供するものと見なせます。同様に、Cの立場からは、Java/Pythonもその選択肢の一つにすぎません。そこで、K&Rの例題をPythonの立場から再考してみるのも一興です。

 極論すると、Java/Pythonも「C言語で書かれたアプリケーション」の一つです。どちらも、C言語で作成された部品を集積して、高機能を提供します。C言語のバイブルとされるK&Rでは、二分木を使って単語の頻度を求める事例を紹介しています。この事例を通して、C言語のDNAを持つ、Pythonの世界へと誘います。

対象読者

 こんな症状を抱えているなら……。

  • 今さらC言語なんて。
  • K&Rを読破したことがなく、引け目を感じている。
    【効能】 C言語を見る目が変わってくるかも。
    【副作用】 C言語でもOOPしたくなってくるかも。
    【服用上の注意】 本文にPythonとあるのは、断りがなければJythonにも通用します。

何を今さらC言語?

 K&Rと言えば、C言語のバイブルとされ、世界中で愛読されています。一般書と肩を並べて、専門書がロングセラーを続けるという、希有な事例の一つです。特に、hello worldを出力するコードの断片は、世界で最も有名なプログラムになりました。最近では「K&Rを読んだことがない」という新人に遭遇しますが、新しいプログラミング言語を学ぶときには、なぜかhello worldの事例を繰り返し引用します。

 これから、Pythonを学ぼうとするときに、まるで「寝てる子を起こすな」とでも言われんばかりに「何を今さらC言語」という声が聞こえてきそうです。極論すると、Javaに限らず、Ruby/Pythonさえも「C言語で書かれたアプリケーション」の一つにすぎません。プログラミング言語Objective-Cの開発者でもあるBrad Coxさんは、ソフトウェアICという概念を提唱しました。機械語をトランジスターと見なすなら、C言語はIC、Java/C#はLSI、Ruby/Pythonは超LSIにも匹敵します。低機能の部品を集積した高機能の部品を駆使してハードウェアを組み上げる過程は、ソフトウェアの世界にも通用します。これらの部品を駆使して、高品質/高生産性を維持しながら、テクノロジーは進歩してきました。

 C++に満足していたら、Javaが産声を上げることはなかったかもしれません。歴史は繰り返すと言います。今もこの瞬間に世界中のどこかで、Ruby/Pythonに飽き足らない人々が、新しいプログラミング言語の誕生に立ち会っているかもしれません。その新たな生命にも、おそらく、C言語のDNAが組み込まれていることでしょう。

 今回は、C言語のDNAを持つ、Pythonの世界へと誘います。同じDNAを持つJava/C#との違い(付属のコード参照)を眺めてみるのも一興ですよ。

♪あの頃のまま
 監修者(ひよ子)自身も、80年代の後半には、C言語を使ってOOPを実践していました。C++に飽き足らず、悪戦苦闘していたものです。Smalltalkには遠く及ばず、お世辞にも洗練された代物ではありませんが、それでも、Cを駆使してOOPの三本柱(抽象データ型/継承/ポリモフィズム)を支援していました。クラスもただの型紙ではなく、実体を持つfirst-class objectとして扱えるようにしました。やがて、NIHCLの存在を知り、C言語によるOOPは、無事成仏させることになるのですが、それも今では懐かしい青春のヒトコマです。
 C言語によるOOPは、他の記事『Cで実現する「ぷちオブジェクト指向」』が参考になります。また、Bertrand Meyerさんの著書も参考にしてください。
 オブジェクト指向は、パラダイムの一つであって、言語で規定するものではありません。FortranでOOPしてみるのも一興です。もし途方に暮れるという人がいたら、オブジェクト指向をまだ理解できていないのかもしれません。Javaでプログラミングできることと、OOPを理解していることとは、どうやら別次元のようです。

二分木を使って

 K&R; 6.5 Self-referential Structuresでは、自己参照的構造体となる二分木(binary tree)を使って、出現頻度(ヒストグラム)を求める事例が紹介されます。

 "No node may have more than two children; it might have only zero or one."(K&R, p.139)とあるように「二分木は、左右に部分木を持つ再帰的な構造」となります。そして、再帰的な構造には、再帰呼び出しを素直に適用するのが良いでしょう。

K&R, p.140
struct tnode {        /* the tree node: */
    char *word;           /* points to the text */
    int count;            /* number of occurrences */
    struct tnode *left;   /* left child */
    struct tnode *right;  /* right child */
};

 構造体tnodeは、二分木を構成する要素を規定します。

class Tnode:
    def __init__(self, word="", count=0, left=None, right=None):
        self.word  = word
        self.count = count
        self.left  = left
        self.right = right

 クラスTnodeは、構造体tnodeと等価です。二分木の各ノードには、単語wordとその出現頻度countと共に、左右の部分木left/rightを保持します。

K&R, p.141
struct tnode *addtree(struct tnode *p, char *w)
{
    int cond;

    if (p == NULL) {
        p = talloc();
        p->word = strdup(w);
        p->count = 1;
        p->left = p->right = NULL;
    } else if ((cond = strcmp(w, p->word)) == 0)
        p->count++;
    else if (cond < 0)
        p->left = addtree(p->left, w);
    else
        p->right = addtree(p->right, w);
    return p;
}

 C言語版の関数addtreeは、二分木の各ノードpに、単語wを追加します。

def addtree(p, w):
    if not p:
        p = Tnode(w, 1)
    elif w == p.word:
        p.count += 1
    elif w < p.word:
        p.left  = addtree(p.left , w)
    else:
        p.right = addtree(p.right, w)
    return p

 関数addtreeは、単語を追加した後のノードpをリターン値とします。記憶領域を確保して、初期設定を行うなどの作業はすべて、クラスTnodeに委ねます。

間順走査では

 再帰呼び出しaddtreeによって、二分木を間順走査(inorder traversal)します。ifに続く条件式not pを満たすときには、左右の部分木が存在しません。指定した単語wが二分木に存在しないなら、そこに新たなノードを生成Tnode(w,1)します。クラス呼び出しTnode(w,1)によって、左右の部分木left/rightには、規定値Noneを設定します。そのため、新たに追加したノードは、左右の部分木を持たない端点となります。このように、引数を省略したときの規定値を利用すると、コードが簡潔になります。単語wが未登録なら、その出現頻度countの初期値を1とします。

 最初のelifに続く条件式w==p.wordを満たすときには、2つの文字列が一致します。指定した単語wが登録済みなので、その出現頻度countの値を1つ増やします。次のelifに続く条件式w<p.wordを満たすときには、指定した単語wの方が小さくなります。文字列の大小比較は、各文字のASCIIコード値で行われます。指定した単語wが、左部分木に存在する可能性があるので、addtree(p.left,w)の引数に左部分木を指定します。同じ条件式を満たさないときには、右部分木に存在する可能性があるので、addtree(p.right,w)の引数に右部分木を指定します。

♪あの素晴らしい愛をもう一度
 Cにおける普通の変数とポインタ変数との区別は、Java/Pythonでは不要です。概念モデルでは、情報隠蔽の原則に従って実現方法の違いを捨象できるので、抽象度の高い記述が可能です。Cにおける*->の記法の違いは、情報隠蔽の原則に反するばかりか、カプセル化もないがしろになり、その実現方法が白日の下に曝されます。さらに、C++では.*->*が追加されて、事態はさらに混沌とします。これは、西暦二千年問題と同じ病巣を抱え、ささいな要求仕様の変更の先には、膨大なメンテナンスの悪夢が待ち受けています。プログラマーは「隠蔽されるべき実現方法」をことあるごとに再現させられる羽目に陥り、単純な肉体労働に貴重な時間を奪われます(情報隠蔽とカプセル化との混同も、C++の功罪の一つです)。
 未熟な言語仕様のツケは、プログラマーが清算することになります。ともすると、一つの言語と添い遂げて、そのことに気付かないまま生涯を閉じかねません。やがて、新しい言語との出会いが転機となります。「今までの苦労はなんだったの」という叫び声は、オフィスのパーティションに隠蔽され、管理者の耳元までは届かないものです。

  • ブックマーク
  • LINEで送る
  • このエントリーをはてなブックマークに追加

修正履歴

  • 2007/12/05 09:51 タイトルを修正しました。

著者プロフィール

バックナンバー

連載:よろずプログラマーのためのPython導入ガイド

もっと読む

All contents copyright © 2005-2019 Shoeisha Co., Ltd. All rights reserved. ver.1.5