2015/04/30


とは言っても焼き直しですが

Natural Order String Comparison

Natural Order String Comparison by Martin Pool Computer string sorting algorithms generally don't or...

http://sourcefrog.net/projects/natsort/

こにらにあった natsort を golang で焼きなおしてみました。

mattn/natural - GitHub
https://github.com/mattn/natural
package main

import (
    "fmt"
    "github.com/mattn/natural"
)

func main() {
    a := []string{
        "３",
        "1",
        "10",
        "2",
        "20",
    }
    natural.Sort(a)
    for _, s := range a {
        fmt.Println(s) // 1 2 ３ 10 20 
    }
}

ファイル名をソートする場合等に便利そうです。

Posted at by



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 による実行結果 でもちゃんと動いています。便利ですね。

Posted at by



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([]int, 0, len(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
}
Posted at by