こっぱみぢんこ

無駄の極み

千羽鶴って、貰って困るものランキングの上位ランカーだよな。役に立たないし、捨てるにもなんだか躊躇いが感じられて。って、貰ったことは無いんだけどさ。

寺や神社で定期的に古いお守りを処分するイベントがあるのは、処分するときの心理的な負担を軽減するためなのかもしれないな。ま、寺社の側の主目的は、迷信グッズをまた新しく買わせることなんだろうけど。

+

先日の問題について考えてみる。

最長重複文字列（最も長く重複している部分文字列）を探すプログラムを作れ。例えば

Ask not what your country can do for you, but what you can do for your country.

であれば「 can do for you」が最長重複文字列となる。

例文程度なら、何となく全体を眺めていれば見つかるだろう。でも、こうした簡単な問題をいざプログラムで解決しようとすると、意外に面倒だったりするんだよな。

同じ文字列を探す。文字通り、文字列は文字の列な訳だから、まずは単純に同じ文字を探すところから始まるだろう。同じ文字を見つけて、もしあったら、そこから後ろに続く文字が同じ部分を取り出す。さらに同じ文字があるか探して、もしあったらまた後ろに続く文字が同じ部分を取り出す。先に取り出したのと長さを比べて、長い方を残す。これを先頭の文字から繰り返して、最後に残ったのが答え。あれ？意外に簡単そうだな。

ということで、JavaScriptで上記をそのままコードにしてみた。


function search( s ) {
    var answer = "";
    for ( var i = 0; i < s.length - 1; i++ ) {
        answer = getLonger( answer, subSearch( s.substring( i ) ) );
    }
    return answer;
}
function subSearch( s ) {
    var answer = "";
    for ( var i = 1; i < s.length - 1; i++ ) {
        answer = getLonger( answer, getSame( s, getNext( s.substring( i ), s.charAt( 0 ) ) ) );
    }
    return answer;
}
function getNext( s, c ) {
    var i = s.indexOf( c );
    return i != -1 ? s.substring( i ) : "";
}
function getSame( s1, s2 ) {
    for ( var i = 0; s1.charAt( i ) === s2.charAt( i ) && i < s2.length; i++ ) ;
    return s1.substring( 0, i );
}
function getLonger( s1, s2 ) {
    return s1.length >= s2.length ? s1 : s2;
}

本当に簡単だったな。って、入門記事の例題なんだから簡単なのが当たり前か。一応それぞれの関数の説明を残しておく。

search( s ): 文字列 s から最長重複文字列を取り出す。関数名に「最長重複文字列」が見当たらないのは気にしない。
subSearch( s ): 文字列 s の先頭からと同じ並びの最長重複文字列を取り出す。
getNext( s, c ): 文字列 s から、文字 c で始まる文字列を取り出す。
getSame( s1, s2 ): 文字列 s1 と s2 の先頭から重複文字列を取り出す。ここで　s1 は s2 より長いものとする。
getLonger( s1, s2 ): 文字列 s1 と s2 で長い方を返す。

例題でテストすると、


search( "Ask not what your country can do for you, but what you can do for your country." );

ちゃんと「 can do for you」と答えが返ってくる。

返ってくるのだが、これは何だかモヤモヤするな。

モヤモヤするポイントの一つが、全部が同じ文字の場合。例えば「AAA〜A」に適用した結果は、1文字少ない「AA〜A」になるのだが、これは最長重複文字列の定義に合っているのだろうか。いや、合ってはいるんだろうが、何だか感情的に納得いかないというか…

モヤモヤポイントのもう一つが、各関数の中が for ばかりで、何か不細工っぽいところ。扱う対象が文字列なので reduce や map といった便利な Array のメソッドが使えないからこうなっているのだが、いや、文字列を文字の配列に変換すれば使えるのだが、これはこれでまた何か違う気がするし。

せっかくなので、for を全部再帰で書き直してみた。


function search( s, answer ) {
    if ( s.length <= answer.length ) {
        return answer;
    }
    return search( s.substring( 1 ), getLonger( answer, subSearch( s, 1, answer ) ) );
}
function subSearch( s, i, answer ) {
    var si = s.substring( i );
    if ( si.length <= answer.length ) {
        return answer;
    }
    return subSearch( s, i + 1, getLonger( answer, getSame( s, getNext( si, s.charAt( 0 ) ), 0 ) ) );
}
function getNext( s, c ) {
    var i = s.indexOf( c );
    return i != -1 ? s.substring( i ) : "";
}
function getSame( s1, s2, i ) {
    if ( s1.charAt( i ) !== s2.charAt( i ) ) {
        return s1.substring( 0, i );
    }
    return getSame( s1, s2, i + 1 );
}
function getLonger( s1, s2 ) {
    return s1.length >= s2.length ? s1 : s2;
}

とりあえず for は消えたけど、今一つすっきりしないな。見た目はむしろゴチャゴチャしてきた。再帰の停止判定の効率を上げるためなんだけど、引数が増えたのもちょっと。再帰版だと


search( "Ask not what your country can do for you, but what you can do for your country.", "" );

となるんだよね。第2引数が微妙。だからと言ってもう一段外側に関数を用意するのも、search の先頭で answer が undefined だったら空文字列にするとかも、どれも今一つ…

と思ったが、第2引数も使い道は有るな。これがあることで「ここに指定した文字列よりも長い最長重複文字列を取り出す」という使い方が出来る。これはこれで便利かもしれないな。って、どれだけ便利だろうが、使う機会はほとんど無いんだけどさ。

来週、本屋で正解を確認しよう。正解と言っても、雑誌の記事は関数型プログラミングの入門で言語は Haskel だったので、実装ではなく考え方が同じかどうかというレベルだけど。

2013 06 08

無駄の極み

+