D 1.0   D 2.0
About Japanese Translation

Last update Sun Dec 10 22:56:58 2006

Lisp vs. Java... D?

by Lionello Lunesu, Oct. 18th 2006

２週間前、Josh Stern が digitalmars.D newsgroup に リンクを投稿 しました。 そのリンク先は、 あるプログラミングの問題を説明したページです。 元々は、 38人のC, C++, Java プログラマに同じプログラムを書かせて Java と C++ の効率を比較するというテーマのページでした。

公開以来、多くのプログラマがその問題に回答を寄せています。そんな中のひとつでは、Lisp が2時間という開発時間と(空行、コメントを除いて)45行というコード行数の面で、 明らかに Java や C++ より優れた結果を残しています。 C++では、最短の開発時間の記録は 3時間で、 最短のコードは107行でした。

たまたま時間ができたので、私もちょっと挑戦してみることにしました。 自分は10年来の C++ プログラマなのですが、 これは D言語 のスキルを試してみるいい機会かもしれない、と思ったのです。

他の実装は見ずに、ただ元々の問題文 だけを読んでとりかかりました。読み始めてからプログラミングを終えるまで、 かかった時間は 1時間と15分 です。プログラムは、 空行やコメント、assert、unittest、契約と、(Lispと合わせて) 末尾の閉じ括弧 } を除くと、たった55行でした。（繰り返しておくと、 C++ の最短バージョンは107行です）

プログラムのする作業は、基本的には次の通りです。まず辞書ファイルから全部の単語を読み込みます。 一文字一文字に(電話番号の文字のように)対応する数字が決まっているので、 この対応関係に基づいて、電話番号のリストが書かれたもう一つのテキストファイルを読み取って、 電話番号をさきほどの辞書にある単語の列で表す方法を全通り表示します。 詳細は上のリンクをたどってください。

Dでの実装がこんなに簡単だった理由はなんでしょう？ 欲しい機能が全てそこにあったから、 と感じです。使えた機能はこんなところです:

実際にプログラミングしている間、手を止めて何か考えたりする必要は全くありませんでした。 辞書を格納するコンテナについて考え出すと同時に、 プログラムが勝手にできあがっていきました。どうやら "勝者" であるLisp版も、 辞書を似たような方法で扱っていたようです。

コンパイル方法

ご自分でプログラムを走らせてみるには、まず dictionary.txt と input.txt をダウンロードしてください。次に 最新の D コンパイラ が必要です。コンパイルするには、 新しくphoneno.dという名前のファイルを作って、 下のDのコードをコピー＆ペーストします。あとは、以下のコマンドで実行できます: 

dmd -run phoneno.d

// Created by Lionello Lunesu and placed in the public domain.
// このファイルは、オリジナル版からは変更されています。
// （スクリーンに収まるように整形されています。）
module phoneno;     // 無くてもよい
import std.stdio;   // writefln     
import std.ctype;   // isdigit     
import std.stream;  // BufferedFile

// 可読性のため (char[][][char[]] みたいなものはちょっと...)    
alias char[] string;
alias string[] stringarray;

/// 文字列から非数字を切り分ける (COW)
string stripNonDigit( in string line ) 
{
    string ret;
    foreach(uint i, c; line) {
        // Error: std.ctype.isdigit at C:\dmd\src\phobos\std\ctype.d(37) 
        // conflicts with std.stream.isdigit at C:\dmd\src\phobos\std\stream.d(2924)
        if (!std.ctype.isdigit(c)) {
            if (!ret)
                ret = line[0..i];    
        }    
        else if (ret)
            ret ~= c;    
    }    
    return ret?ret:line;
}

unittest {
    assert( stripNonDigit("asdf") == ""  );
    assert( stripNonDigit("\'13-=2 4kop") ==  "1324"  );
}

/// アルファベット以外を無視して、単語を数字に変換
string wordToNum( in string word )
{
// 変換テーブル
const char[256] TRANSLATE =    
    "                                "  // 0   
    "                0123456789      "  // 32     
    " 57630499617851881234762239     "  // 64   
    " 57630499617851881234762239     "
    "                                "
    "                                "
    "                                "    
    "                                ";
    string ret;
    foreach(c; cast(ubyte[])word)
        if (TRANSLATE[c] != ' ')
            ret ~= TRANSLATE[c];
    return ret;
}

unittest {
 // 問題の説明にあった表のデータで wordToNum のテスト
 assert( "01112223334455666777888999" ==
   wordToNum("E | J N Q | R W X | D S Y | F T | A M | C I V | B K U | L O P | G H Z"));
 assert( "01112223334455666777888999" == 
   wordToNum("e | j n q | r w x | d s y | f t | a m | c i v | b k u | l o p | g h z"));
 assert( "0123456789" == 
   wordToNum("0 |   1   |   2   |   3   |  4  |  5  |   6   |   7   |   8   |   9"));
}

void main( string[] args )
{
    // この連想配列は数字を単語の配列にマップする
    stringarray[string]    num2words;

    foreach(string word; new BufferedFile("dictionary.txt" ) )
        num2words[ wordToNum(word) ] ~= word.dup;        // dup必須

    /// 与えられた数字に対する候補をすべて探す
    /// (非数字をstrip済みの文字列を渡すこと)
    stringarray _FindWords( string numbers, bool digitok )
    in {
        assert(numbers.length >  0);    
    }    
    out(result) {
        foreach (a; result)
            assert( wordToNum(a) == numbers );
    }    
    body {
        stringarray ret;
        bool foundword = false;
        for (uint t=1; t<=numbers.length; ++t) {
            auto alternatives = numbers[0..t] in num2words;
            if (!alternatives)
                continue;
            foundword = true;
            if (numbers.length >  t) {
                // 候補の全てを、
                // 残りの部分の候補と結合（残りの部分が数字で始まってもよい）
                foreach (a2; _FindWords( numbers[t..$], true     ) )
                    foreach(a1; *alternatives)
                       ret ~= a1 ~ " " ~ a2;
            }
            else    
                ret ~= *alternatives;    // 全ての候補を記録
        }
        // 数字をそのまま残して使うケース。数字を使ってよい場面で、かつ
        // 他に候補が見つからなかった場合に限る。
        // "ret.length" を調べる方が "foundword" を調べるより
        // 良いと思われるが、他の実装がこうなっているようなので
        if (digitok && !foundword) { //ret.length == 0  
            if(numbers.length >  1) {
                // 数字を残りの部分の候補と結合
                // (残りの部分は数字で始まってはいけない)
                foreach (a; _FindWords( numbers[1..$], false ) )
                    ret ~= numbers[0..1] ~ " " ~ a;
            }    
            else    
                ret ~= numbers[0..1];    // 単純にこの数字を結合
        }    
        return ret;
    }

    /// (オリジナル版ではこの関数はinline化されている) 
    /// 与えられた電話番号に対応する文字列を全て見つける
    /// Returns: 文字列の配列
    stringarray FindWords( string phone_number )
    {
        if (!phone_number.length)
            return null;
        // 電話番号から数字でない文字を取り除き、
        // 再帰関数に渡す (先頭の数字が残ってもよい)
        return _FindWords( stripNonDigit(phone_number), true );    
    }    
    
    // 電話番号読み込み
    foreach(string phone; new BufferedFile("input.txt"   ) )
        foreach(alternative; FindWords( phone ) )
            writefln(phone, ": ", alternative );
}