ペンキ屋シュレミール

有名な本なのでこんなとこ見てる人はたいてい知っていると思うのですが、Joel on Softwareにこんな話が載っていた(打ち直すのが面倒なので検索したらここで見つかったのでコピペ)。

シュレミールは道路の真ん中に破線を描くペンキ塗りの仕事を得た。最初の日、ペンキの缶を道路に持ち出すと、彼は300ヤード描き上げた。「よくやった！君は仕事が早いな！」とボスは言って、1コペイカくれた。
次の日、シュレミールは150ヤードしか進まなかった。「まぁ、昨日ほどじゃないが、それでも早いほうだ。150ヤードなら立派なもんだ」と言って、1コペイカくれた。
その次の日、シュレミールは30ヤード描いた。「たった30！」とボスは叫んだ。「そんなんじゃダメだ！最初の日にはその10倍もやったじゃないか！いったいどうしたっていうんだ？」
「仕方ねぇです」シュレミールは答えた。「毎日ペンキの缶から遠くなってくんで！」

もちろんこれはたとえ話で、オーダーが本来O(N)になるはずなのにO(N²)かかってしまう腐れたアルゴリズムについて述べたものだ。んで、本で取り上げられている具体例は、strcat()で文字列を次々に繋いでいく例。確かにstrcat()は文字列を毎回頭からスキャンするので、ペンキ屋シュレミールと同じように効率が悪い。
では、crowbarやDiksamはどうなっているかというと…
http://kmaebashi.com/programmer/devlang/diksam_src_0_2/S/18.html#234

static DVM_Object *
chain_string(DVM_VirtualMachine *dvm, DVM_Object *str1, DVM_Object *str2)
{
    int result_len;
    DVM_Char    *left;
    DVM_Char    *right;
    DVM_Char    *result;
    DVM_Object *ret;

    if (str1 == NULL) {
        left = NULL_STRING;
    } else {
        left = str1->u.string.string;
    }
    if (str2 == NULL) {
        right = NULL_STRING;
    } else {
        right = str2->u.string.string;
    }
    /* 問題は、このへんから */
    result_len = dvm_wcslen(left) + dvm_wcslen(right);
    result = MEM_malloc(sizeof(DVM_Char) * (result_len + 1));

    dvm_wcscpy(result, left);
    dvm_wcscat(result, right);
    /* このへんまで */

    ret = dvm_create_dvm_string_i(dvm, result);

    return ret;
}

わはは。
だが、言い訳するわけではないが、この問題を解決したければDVM_String構造体に文字列長を持たせれば、プログラムのほとんどの箇所には修正を加えずに直すことができる(ていうかだからこそ私はこの問題を知っていながら放置したわけで)。こういう方法のほうが、Joel on Softwareで紹介されている1バイト目に文字列長を埋め込む方式(だから、Excelではあちこちで文字列長が255文字に制限されているのだそうな…*1 )よりずっとマシなのではないか。
現場のおやじである私の目から見て、この本は最近よく見かけるハッカーマンセー的な主張に比べて同意できる点が多いと思うんだけれども、ところどころ首をひねるところもあったりする。このネタはもう数回書けるかも。

*1:もちろん、もうメモリなんて腐るほどあるからせめて65535文字まで許そうよ、と思っても、過去のデータファイルの互換性を考えればそうはいかない、という事情もあるかと思うが。