決まり字

runeの場合には普通にスライスしちゃうと、駄目なんだよなー。 扱う文字列はruneですってコードの あちこちで振れ回ってしまうと、重要な関数がruneをサポートしてないよと言われる 始末。上手に扱ってあげないと罠にはまるぞ。

runes()で分解は出来るけど、元に戻す奴(いわゆるjoin(''))が用意されていない。 こういう場合は、即興で作るのが習わし。

>>> fn r2s(xx []rune) string {
...         mut rv := ''
...         for r in xx {
...                 rv += r.str()
...         }
...         return rv
... }
>>> x := 'あきのたの'
>>> w := x.runes()
>>> w
[`あ`, `き`, `の`, `た`, `の`]
>>> r2s(w)
あきのたの
>>> r2s(w[1..4])
きのた

これで良さそう。この関数をメソッドに変更しようとしたら、そんな事は許しませんと キツいお叱りを受けた。残念であります。ついでなんで、joinの実装を眺めておく。

pub fn (a []string) join(sep string) string {
        if a.len == 0 {
                return ''
        }
        mut len := 0
        for val in a {
                len += val.len + sep.len
        }
        len -= sep.len
        // Allocate enough memory
        mut res := string{
                str: unsafe { malloc_noscan(len + 1) }
                len: len
        }
        mut idx := 0
        for i, val in a {
                unsafe {
                        vmemcpy(voidptr(res.str + idx), val.str, val.len)
                        idx += val.len
                }
                // Add sep if it's not last
                if i != a.len - 1 {
                        unsafe {
                                vmemcpy(voidptr(res.str + idx), sep.str, sep.len)
                                idx += sep.len
                        }
                }
        }
        unsafe {
                res.str[res.len] = 0
        }
        return res
}

何か高速化の為と思うんだけど、事前にエリア・サイズを計算して、その分だけ場所 を確保。そして一気に転送してるっぽい。

string限定のjoin()には見切りをつけ、使い方が面倒そうな汎用な関数を見つけたぞ。

// join_to_string takes in a custom transform function and joins all elements into a string with
// the specified separator
@[manualfree]
pub fn join_to_string[T](array []T, separator string, transform fn (elem T) string) string {
        mut sb := strings.new_builder(array.len * 2)
        defer {
                unsafe { sb.free() }
        }
        for i, item in array {
                x := transform(item)
                sb.write_string(x)
                unsafe { x.free() }
                if i < array.len - 1 {
                        sb.write_string(separator)
                }
        }
        return sb.str()
}

これ、いわゆる多相関数。どんなタイプの配列も受け付けますよ。その変り変換関数を 用意してねって奴。

無理して使うなら、こうだ。カスタム関数を定義して使うと言う 面倒さ。(elem T) -> string となる変換関数を用意しろとな。関数名は不要だから、匿名関数でいいよ。 schemeで言う (lambda(..)(….)) だな。

prefix := arrays.join_to_string(word[..i], '',
          fn (it rune) string {return it.str()})

上のコメントにtake なんてのが出てたので、思わずhaskellのtakeやらdropなんて 関数を思い出しちゃったぞ。V言語には、これらの有名な関数が定義されていない。 実装者の怠慢？ いやいや、そんなの配列のスライスでしょ。関数言語脳は、どこかに 仕舞っておけ。

実際の百人一首に対して、決まり字を表示するコードを上の下訳を元に作成してみた。

import os

fn r2s(xx []rune) string {
        mut rv := ''
        for r in xx {
                rv += r.str()
        }
        return rv
}

fn find_unique_prefixes(words []string) map[string]string {
        mut prefix_count := map[string]int{}

        for xx in words {
                word := xx.runes()
                for i in 1 .. word.len + 1 {
                        prefix := r2s(word[..i])
                        prefix_count[prefix] += 1
                }
        }

        mut unique_prefixes := map[string]string{}
        for word in words {
                for i in 1 .. word.len + 1 {
                        prefix := word[..i]
                        if prefix_count[prefix] == 1 {
                                unique_prefixes[word] = prefix
                                break
                        }
                }
        }
        return unique_prefixes
}

fn drop(n int, s string) string {
        rv := s.runes()
        return r2s(rv[n..])
}

fn main() {
        mut words := []string{}
        for a in os.read_lines('genko.txt')! {
                s := a.split_by_space()
                words << '${s[1]} ${s[2]} ${s[3]}'
        }
        result := find_unique_prefixes(words)
        for k, v in result {
                sz := v.runes().len
                println('${v}|${drop(sz,k)}   ${sz}')
        }
}

sakae@lu:h100$ ./kimariji | sort
 :
ながか|らん こころもしらず くろかみの   3
ながら|えば またこのごろや しのばれん   3
なげき|つつ ひとりぬるよの あくるまは   3
なげけ|とて つきやはものを おもわする   3
なつ|のよは まだよいながら あけぬるを   2
なにし|おわば おうさかやまの さねかずら   3
なにわえ|の あしのかりねの ひとよゆえ   4
なにわが|た みじかきあしの ふしのまも   4
 :
わがい|おは みやこのたつみ しかぞすむ   3
わがそ|では しおひにみえぬ おきのいしの   3
わすら|るる みをばおもわず ちかいてし   3
わすれ|じの ゆくすえまでは かたければ   3
わたのはら こ|ぎいでてみれば ひさかたの   7
わたのはら や|そしまかけて こぎいでぬと   7
わび|ぬれば いまはたおなじ なにわなる   2

普通なら決まり字は着色する(面倒なエスケープ・シーケンスを駆使して)んだろうけど、 コピペすると色あせちゃうんで、バーチカル・バーで区切りを入れてみた。また、右側 の数字は、決まり字の文字数を表示してる。7ってなってるのは、区切りのスペースを 含んでいるからです(あしからず)。

main()内の事でちょっと補足しとく。mapをforでスキャンする時、1つの変数で受けるとvalue にバインドされる。2つの変数で受けるとkey,valueになるんですね。前回、ちょっと苦情 しちゃったけど、撤回します。まあ、色々な場面に遭遇しないと分からんわな。 それから、haskellとかの自慢の種であるdrop相当を定義して使ってみた。

専用の計測コマンドが用意されてた。(V 0.4.10 6b3521f)

sakae@lu:h100$ v time ./kimariji > /dev/null
>    9.099 ms. Exit code:   0. Command: ./kimariji
sakae@lu:h100$ v time ./kimariji > /dev/null
>    9.956 ms. Exit code:   0. Command: ./kimariji

sakae@lu:h100$ v time ./kimariji > /dev/null
>    4.909 ms. Exit code:   0. Command: ./kimariji
sakae@lu:h100$ v time ./kimariji > /dev/null
>    4.942 ms. Exit code:   0. Command: ./kimariji

下のグループは出荷用のコードでの時間。 v timeって、汎用なの？

sakae@lu:h100$ time make
v kimariji.v
real    0m0.333s
user    0m0.285s
sys     0m0.075s
sakae@lu:h100$ v time make
v kimariji.v
>  312.703 ms. Exit code:   0. Command: make

そうらしいね。どんなコードになってるか、確認しとけ。

sw := time.new_stopwatch()
ecode := os.system(cmd)
elapsed := sw.elapsed()
stook_time := '${f64(elapsed.microseconds()) / 1000.0:8.3f} ms'
eprintln('> ${term.ecolorize(term.bright_yellow, stook_time)}.
	     Exit code: ${ecode:3}.
	     Command: ${term.ecolorize(term.green,  cmd)}')

これが核心部分だった。eprintlnの部分は本当は1行なんだけど、見易い 様に3行にしてる。色付け関数が用意されてるのね。でも、コピペで退色 しちゃうんだよな。

ソースにちょっと計測ポイントを追加すると、各区間のラップタイムを取得できる。

import benchmark                                       // at begining file

fn main() {
        mut b := benchmark.start()                     // add
        mut words := []string{}
        for a in os.read_lines('genko.txt')! {
                s := a.split_by_space()
                words << '${s[1]} ${s[2]} ${s[3]}'
        }
        b.measure('read table')                       // add
        result := find_unique_prefixes(words)
        b.measure('calc prefixes')                    // add
        for k, v in result {
                sz := v.runes().len
                println('${v}|${drop(sz,k)}   ${sz}')
        }
        b.measure('output result')                    // add
}

こうしておいてcompile & run。コンパイルが速いのでイライラは全く無い。

sakae@lu:h100$ make r
v -g kimariji.v
./kimariji
 SPENT     0.669 ms in read table
 SPENT     5.696 ms in calc prefixes
あきの|たの かりおのいおの とまをあらみ   3
  :
もも|しきや ふるきのきばの しのぶにも   2
 SPENT     1.764 ms in output result

FBIは犯罪捜査にプロファイルを導入して成功を収めた。 vlangでも犯罪的に遅い関数を炙り出して、スピードアップに寄与 する為の仕掛けが用意されてる。下記の様に簡単に使えるぞ。

sakae@lu:h100$ v -prof LOG run kimariji.v
sakae@lu:h100$ sort  -k 2 -nr LOG | head
             1         36.850ms          0.119ms       36849609ns main__main
             1         26.471ms          0.372ms       26470504ns main__find_unique_prefixes
          2022         19.531ms          2.021ms           9659ns main__r2s
         21086         10.360ms          1.742ms            491ns rune_str
         21086          8.617ms          2.777ms            409ns utf32_to_str
           300          7.301ms          0.972ms          24336ns string_runes
         21086          7.150ms          3.845ms            339ns string__plus
           100          6.498ms          0.031ms          64981ns main__drop
          1922          5.639ms          0.625ms           2934ns map_get_and_set
         21086          4.545ms          2.651ms            216ns utf32_to_str_no_malloc

自前で用意したjoin相当の関数であるr2sが足を引っ張っているなあ。これを join_to_string に変更したら、どれぐらい速くなる？ やってみる価値大だな。 なお、各フィールドの意味は、下記。

The format is 4 fields, separated by a space, for each v function:
  a) how many times it was called
  b) how much *nanoseconds in total* it took
  c) an average for each function (i.e. (b) / (a) )
  d) the function name

あれ、フィールドが5個あるなあ。まあ、新興の言語なんで硬い事は言うまい。 それよりも便利に使えるのが一番だ。でも、vlibがどんどん進化してくんで、古いバージョン では利用できない事が多々有る。常に最新にしておくのが吉。v upは気楽にできるからね。

r2sの中身をvlib提供の関数に入れ替えてみた。

import arrays

fn r2s(xx []rune) string {
        return arrays.join_to_string(xx, '', fn (it rune) string {
                return it.str()
        })
}

結果は？ 逆に遅くなってしまいましたね。残念であります。

sakae@lu:h100$ v time ./kimariji >/dev/null
>   47.281 ms. Exit code:   0. Command: ./kimariji
sakae@lu:h100$ v time ./kimariji >/dev/null
>   43.980 ms. Exit code:   0. Command: ./kimariji

一応、プロファイルの結果を載せておきます。

    1         40.799ms          0.079ms       40799450ns main__main
21086         37.586ms          1.795ms           1783ns anon_fn_5253ca1212341c43_rune__string_110
    1         33.915ms          0.375ms       33915185ns main__find_unique_prefixes
 2022         26.192ms          3.867ms          12953ns arrays__join_to_string_T_rune
21086          9.600ms          1.638ms            455ns rune_str
21086          7.962ms          2.530ms            378ns utf32_to_str
41150          6.549ms          2.346ms            159ns strings__Builder_write_string
 1922          5.665ms          0.626ms           2947ns map_get_and_set
  300          5.382ms          0.712ms          17940ns string_runes
  100          4.275ms          0.017ms          42750ns main__drop

匿名関数が悪さしてます。関数呼出って非常にコストがかかる行為って 知見が得られました。