2015/04/28


PostgreSQL だと、generate_series という集合生成関数があり、例えば

postgres=# select generate_series(1, 10) x;
 x
----
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
(10 行)

こういう連番がサックリと作れる訳なのですが、SQLite3 にはこの様な関数が用意されていません。かといって、この generate_series の為に SQLite3 拡張を作って enable_load_extension する(例: Big Sky :: SQLite で twitter のタイムラインを select する。)のはちょっと辛い。しかしながらどうしても必要な場面というのは出てきます。例えば FizzBuzz とか FizzBuzz とか、あと FizzBuzz なんかでも必要ですね。

そういう場合に使えるのが with recursive です。

SQLite Query Language: WITH clause

A recursive common table expression can be used to write a query that walks a tree or graph

https://www.sqlite.org/lang_with.html#recursivecte

これを使うと、通常の SQL 文に再帰属性を付与する事が出来ます。

with recursive
generate_series(x) as (
 select 1
 union all
 select x+1 from generate_series limit 12
select x from generate_series;

関数的としても扱えませんし、少し面倒臭いですが無いよりはマシです。

これを使えば FizzBuzz も簡単。

with recursive
generate_series(x) as (
 select 1
 union all
 select x+1 from generate_series limit 100
select
  case 
  when 0 = x % 15 
  then 'FizzBuzz' 
  when 0 = x % 5 
  then 'Buzz' 
  when 0 = x % 3 
  then 'Fizz' 
  else ''||x
  end
from
  generate_series

SQL Fiddle による実行結果 でもちゃんと動いています。便利ですね。


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 でイテレータを戻してくれるのでかなりスッキリ書けます。