トップ «前の日記(2010-07-13) 最新 次の日記(2010-07-19)» 編集

はじめてのにき

ここの位置付け

2004|11|
2005|03|04|05|06|07|08|09|10|11|12|
2006|01|02|03|04|05|06|07|08|09|10|11|12|
2007|01|02|03|04|05|06|07|08|09|10|11|12|
2008|01|02|03|04|05|06|07|08|09|10|11|12|
2009|01|02|03|04|05|06|07|08|09|10|11|12|
2010|01|02|03|04|05|06|07|08|09|10|11|12|
2011|01|02|03|04|05|06|07|08|09|10|11|12|
2012|01|02|03|04|05|06|07|08|09|10|11|12|
2013|01|02|03|04|05|06|07|08|09|10|11|12|
2014|01|02|03|04|05|06|07|08|09|10|11|12|
2015|01|02|03|04|05|06|07|08|09|10|11|12|
2016|01|02|03|04|05|06|07|08|09|10|11|12|
2017|01|02|03|04|05|06|07|08|09|10|11|12|
2018|01|02|03|04|05|06|07|08|09|10|11|12|
2019|01|02|03|04|05|06|07|08|09|10|11|12|
2020|01|02|03|04|05|06|07|08|09|10|11|12|
2021|01|02|03|04|05|

ToDo:


2010-07-18

_ niconico

http://twitter.com/lyrical_logical/status/18776878242

芸風的に雌豚先生復活とかだと嬉しいなー。 動画丁寧すぎるのがそれっぽくないけど。

(10:09)

_ wake

C++ で書いたらだいぶ速くなった。 20-30倍くらいか。

基本正規表現だけだからこんなに速くなると思ってなかったんだけど、 まぁ Ruby の方のコードは色々適当なのが悪いんじゃないかと思う。

all: "$(loop0)"

loop3000000: "DONE\n"
loop(\d+): loop$(add($1,100))

#include "std/num.wake"

とかが 2 秒とかかかってて、 ちょっとまだ遅すぎるよなーという感がある。 16kHz とかくらいか。

ターゲットが増えると遅くなるってのはいけてないので、 なんかそのへんなんとかなるといい。

二つほど方法はあって

  • 正規表現を合成する
  • 各正規表現の先頭部分に関して trie を作る

とかかなぁ。

正規表現の合成って特に後方参照的な意味で 難しそうな気がするけどどうなんだろうな。 普通に \1 とかの番号を振りなおすだけでいいのかな。 とりあえず \10 とかは使えるんだなーと確認した。

うーんでも trie かな

(13:59)

_

うざい遊びをしててすいません

単にこのエロ動画の話 http://www.nicovideo.jp/watch/sm11381844

(14:18)

_ memset

http://twitter.com/hamano/status/18818137867

https://review.source.android.com/#patch,sidebyside,14699,1,libc/memset.c

ありそうすぎて笑った。

/bin/grep -r --include='*.cc' --include='*.h' --include='*.cpp' --include='*.c' memset *

とかしてみたところ、

SDL_command/SDL_command.c:    memset(cmd->input_queue, -1, sizeof(int)*input_queue_size);
marathon/SequenceAlignment/sa2.cc:    memset (F, -1, sizeof (F));

ごく稀にはあることがわかった。

(14:32)

_ dc.sed

簡単だと思っていた引き算が意外とめどい

dc.sed は何故 add と sub を同時にできてるんだ…

: addsub1
	s/\(.\{0,1\}\)\(~[^,]*\)\([0-9]\)\(\.*\),\([^;]*\)\(;\([^;]*\(\3[^;]*\)\).*X*\1\(.*\)\)/\2,\4\5\9\8\7\6/
	s/,\([^~]*~\).\{10\}\(.\)[^;]\{0,9\}\([^;]\{0,1\}\)[^;]*/,\2\1\3/
#	  could be done in one s/// if we could have >9 back-refs...
/^~.*~;/!b addsub1

ええ理解不能です

(15:43)

_ ああそうか

引き方を先にマッチさせればいいのか。 やはり簡単だった…

(15:45)

_ ぼとるねっく

perftools でプロファイル取ってみたところ、 正規表現とかでは全然なくて、 malloc 多すぎとかだった。 とりあえず string::reserve 呼ぶとだいぶ速くなった。

あと tcmalloc 使うとだいぶ速くなる。

ベンチマークは大事だなぁと思った。

で、前回の話から考えると、 std::string じゃなくて自分で string 作った方が速くなるんないか…

(18:02)

_ perftools

libpcre の symbol 取れねーなーと悩んでいた。 profile の末尾についてる /lib/libpcre... とかを /usr/lib/debug 以下のものに置換すればとりあえず取れるみたいだ。

inline 展開のせいでよくわからんのだけど、 たぶん、

  • 少なくとも 31.8% は pcre_compile
  • 20% くらいが pcre_get_substring_list ?

って感じっぽい気がする。 とりあえず後者は簡単に減らせるはずだ。 pcre_exec の返す ovector のフォーマットが わかるといいんだけどな。

      The  first  two-thirds of the vector is used to pass back captured sub-
      strings, each substring using a pair of integers. The  remaining  third
      of  the  vector is used as workspace by pcre_exec() while matching cap-
      turing subpatterns, and is not available for passing back  information.
      The  number passed in ovecsize should always be a multiple of three. If
      it is not, it is rounded down.

3倍ってなんだと思ってたんだけど、そういうことか…

(20:09)

_ pcre_get_substring_list を取り除いた

全然速くならない。 普通に pcre_exec が遅かったみたいだった。

RE2 はどうかなーと思ったんだけど、 backreference が無いみたいなので論外だった…

Irregexp とか YARR とか使ってみるという手もあるんかな。

ぱっと見では YARR の方が切り出しやすそうな雰囲気かなぁ… と思ったけど wtf とかに依存してやがるな。

Irregexp にするか… とか思ったあたりで何やってるんだろうと思いはじめてきた。

(20:59)

本日のツッコミ(全2件) [ツッコミを入れる]
_ naruse (2014-05-24 01:33)

正規表現ライブラリ、TREってのもありますね。http://laurikari.net/tre/

_ shinh (2014-05-24 01:33)

おお、ぱっと見良さそうですね。速ければ、ですが。ありがとうございます。

お名前:
E-mail:
コメント:
人生、宇宙、すべての答え
本日のリンク元

2010年
7月
1 2 3
4 5 6 7 8 9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28 29 30 31
1.shinh(2014-05-24 01:33) 2.Gimite(2014-05-24 01:33) 3.シンX(2014-05-24 01:33)
search / home / index

全てリンクフリーです。 コード片は自由に使用していただいて構いません。 その他のものはGPL扱いであればあらゆる使用に関して文句は言いません。 なにかあれば下記メールアドレスへ。

shinichiro.hamaji _at_ gmail.com / shinichiro.h