2015/04/16


Golang で言語処理100本ノックの No.3 の問題を解いてベンチマークとってみた - Qiita
http://qiita.com/megu_ma/items/01029c3ca24fb9820373

正規表現や strings.Trim 等はとても便利なのですが、いかんせん単一の関数呼び出しに対して真面目にループを回す作りになっており、戻り値がコピーされる前提の作りになっています。例えば

func answer1() []int {

    // 単語に分解
    words := strings.Split(sentence, " ")

    var pi []int
    for _, word := range words {
        word = strings.Trim(word, ",")
        word = strings.Trim(word, ".")
        // pi = append(pi, utf8.RuneCountInString(word))
        pi = append(pi, len(word))

    }

    return pi

}

このコードの場合

  1. strings.Split で文字列の先頭から終端まで検査しながらループ
  2. words で単語数分ループ(W)
  3. strings.Trim で単語の長さ分ループ(W × 2)

という無駄なループが回ります。正規表現に至っても同じ。

func answer2() []int {

    // 文を正規表現で単語に分解
    words := regexp.MustCompile(`\s|"|,|\.`).Split(sentence, -1)

    var pi []int
    for _, word := range words {
        // 文末がスプリットされた場合、words の配列の最後に空文字が入る
        if word != "" {
            // pi = append(pi, utf8.RuneCountInString(word))
            pi = append(pi, len(word))
        }
    }

    return pi

}
  1. パターン文字列長分ループ
  2. 検査対象文字列に対して Split でマッチングループ
  3. words で単語数分ループ(W)

となります。これを1度のループ(lenはカウントしない物とします)で回す事が出来ます。

func answer3() []int {

    var pi []int
    var prev, i int
    b := []byte(sentence)
    l := len(b)
    for i < l {
        for ; i < l; i++ {
            if ('a' <= b[i] && b[i] <= 'z') || ('A' <= b[i] && b[i] <= 'Z') {
                break
            }
        }
        if i < l {
            prev = i
            for ; i < l; i++ {
                if !(('a' <= b[i] && b[i] <= 'z') || ('A' <= b[i] && b[i] <= 'Z')) {
                    break
                }
            }
            pi = append(pi, i-prev)
        }
        i++
    }

    return pi

}

ループ内にループがあり、一見は二重ループが回っている様に見えますが、実際には文字列長に対して先頭位置から終端位置、つまりこのテストケース Now I need a drink, alcoholic of course, after the heavy lectures involving quantum mechanics. で言えば 94 文字分しか処理が行われません。

  1. 文字列長分ループ

だけとなります。一見読みづらいかもしれませんが

  • コピーを減らす
  • ループ回数を減らす

これを守ると速いプログラムが書ける様になります。

PASS
BenchmarkAnswer1          300000              5340 ns/op
BenchmarkAnswer2          100000             21620 ns/op
BenchmarkAnswer3         3000000               552 ns/op
ok      _/C_/dev/go-bench       6.508s

僕の環境だとおよそ10倍速い結果となりました。


追記

methane さんがもうちょっと綺麗なのを書いてくれました。

func answer4(s string) []int {
    res := make([]int0len(s)/6)
    cnt := 0
    for _, c := range s {
        switch {
        case 'a' <= c && c <= 'z''A' <= c && c <= 'Z':
            cnt++
        default:
            if cnt != 0 {
                res = append(res, cnt)
                cnt = 0
            }
        }
    }
    if cnt != 0 {
        res = append(res, cnt)
        cnt = 0
    }
    return res
}

2015/04/09


おなじみC/C++から使えるJSONライブラリを紹介するコーナー。まずは過去のまとめ。

僕は C++ では STL が好きなので JSON をパースした後の構造も、std::mapstd::vector で文字列も std::string なのが好きです。なので picojson をひたすら使ってきましたが、picojson と同じ様に STL フレンドリな JSON ライブラリが ujson(μjson) です。

awangk / ujson — Bitbucket
https://bitbucket.org/awangk/ujson

特徴は以下の通り。

  • 単純な API で小さなライブラリ
  • 小綺麗なフォーマットでの JSON 出力
  • UTF-8 を扱える速いパーサ
  • 自由なライセンス
  • C++11 フレンドリ

μjson は MIT ライセンスで提供されています。ただし double の変換(IEEE double)に v8 でも使われている double-conversion というライブラリを使用しており、その部分については double-conversion のライセンスに委ねられます。

double の変換を行うという事で、つまり Bignum が扱えます。picojson はヘッダオンリーですが、ujson はビルド済みライブラリをリンクしてビルドします。

#include <iostream>
#include <string>
#include <algorithm>
#include <ujson.hpp>

struct book_t {
  std::string title;
  std::vector<std::string> authors;
  int year;
};

book_t
make_book(ujson::value v) {
  if (!v.is_object())
    throw std::invalid_argument("object expected for make_book");

  book_t book;
  std::vector<std::pair<std::string, ujson::value>> object =
    object_cast(std::move(v));

  auto it = find(object, "title");
  if (it == object.end() || !it->second.is_string())
    throw std::invalid_argument("'title' with type string not found");
  book.title = string_cast(std::move(it->second));

  it = find(object, "authors");
  if (it == object.end() || !it->second.is_array())
    throw std::invalid_argument("'authors' with type array not found");
  std::vector<ujson::value> array = array_cast(std::move(it->second));
  book.authors.reserve(array.size());
  for (auto it = array.begin(); it != array.end(); ++it) {
    if (!it->is_string())
      throw std::invalid_argument("'authors' must be array of strings");
    book.authors.push_back(string_cast(std::move(*it)));
  }

  it = find(object, "year");
  if (it == object.end() || !it->second.is_number())
    throw std::invalid_argument("'year' with type number not found");
  book.year = int32_cast(it->second);

  return book;
}

int
main(int argc, char* argv[]) {
  auto v = ujson::parse(R"(
    {
      "title":"foo",
      "authors":["bar", "baz"],
      "year": 123
    }
  )");
  auto t = make_book(v);
  std::cout << "title:" << t.title << std::endl;
  std::for_each(t.authors.begin(), t.authors.end(), [&](std::string& x) {
    std::cout << "author:" << x << std::endl;
  });
  std::cout << "year:" << t.year << std::endl;
  return 0;
}

オブジェクトにキーが存在した場合に find でイテレータを戻してくれるのでかなりスッキリ書けます。


2015/03/26


Goでchannelがcloseしてるかどうか知りたい というアンチパターン - beatsync.net

そもそもGoのchannelがcloseしてるかどうかを知りたいっていう理由は、だいたい「Goのchannelはナイーブだから」というところに起因するのはないかと思います。

https://beatsync.net/main/log20150325.html

golang には元々 closed() という、channel が閉じられているかどうかを返す組み込み関数がありました。しかし廃止されました。

closed は API としては目的を達成出来ているのですが、builtin が1つ増える、channel から取り出す前に一度確認する必要があるという理由で削除されたと私は記憶しています。

Goでchannelがcloseしてるかどうか知りたい というアンチパターン - beatsync.net

selectをつかってブロックする可能性のある文をcaseにかけば一番最初にブロックが外れたやつに分岐します。で、これは@fujiwaraさんに教えてもらった技ですが、なんもしないdefaultを書けばブロックせずにすぐdefaultにおちるとのこと。

https://beatsync.net/main/log20150325.html

実際には closed() が無くなった訳ではなく、型アサーションと同じインタフェースに置き換えられました。

Issue 4243072: code review 4243072: go code: replace closed(c) with x, ok := <-c - Code Review

LGTM http://codereview.appspot.com/4243072/diff/5001/src/pkg/os/inotify/inotify_li... File src/pkg/o...

https://codereview.appspot.com/4243072/
x, ok := <-c

戻り値の2つ目に channel から取り出せたかどうかが bool で返ります。

例: Go Playground

select はどちらかと言うと、複数の channel を同時に待てる仕組みであり、閉じている channel の case には飛ばないという理由で動いています。ですのでどうしても select は嫌だという方は以下の様に書くと良いです。(注意: ブロックはするので select とは動作が違う事に注意)

if x, ok := <-c; ok {
    // x を使った処理
}