No Such Blog or Diary

ThreadPool があると聞いていたので試した．でもスレッドを全部待つ wait がない．タスクすべての終了を待つような用途は想定していないというか，そもそも .NET 側の非同期系の操作でも使われるらしいのでユーザが明示的に登録したタスクだけを全部待つってのが無理なのか？　とりあえず自前で各スレッドの終了時に処理を書くか，そもそも自前のプールを用意するかすべきなのかも．

この前仮想ハードディスクごと書き途中のソースを削除するとかいうあほなことをしてしまったので，VMware 中の Linux にあるソースを Vista (ホストOS) 上の svn リポジトリで管理したい．外部のサーバにおいてもいいけどネットワークが切れているときに困る．

で，ホストにsshd入れるのがめんどい．そしてホスト側のIPをゲスト側が知るにはどうすればいいか考えるのが面倒．VMware のネットワークドライバのIPって固定なのかな？　そうなら問題ないのだけど．

入力は空白区切りの小文字のみで構成される文字列のリスト．出力はソート結果．あなごるのWord frequency count (FIXED) 用に作ったのだが…　問題の入力に出てくる単語のソートだけで手元のマシンでも6秒弱かかる．

# input: word1 word2 ... wordn
# should be lower-case letters. no spaces except for the separator
 
 
s/ /\n/g
s/$/ /gm
 
# each line is a sorted list
 
:a
 
/\n/!q
 
s/^\(.*\)\n\(.*\)$/@\1: %\2/gm
 
# each line: @word11 word12 ... word1n : %word21 word22 ... word2m
# ':' is a separator of two lists
# '@' is the head of non-merged part of the first list
# '%' is the head of non-merged part of the second list
 
 
:b
 
# each line: sortedpart @word1i ... word1n : %word2j ... word2m
 
s/^[^%@:\n]*$/~&/gm                  # already done 
s/^\(.*\)@\(.*\): % *$/~\1\2/gm      # done (2nd list is consumed completely)
s/^\(.*\)@: \(.*\)%\(.*\)/~\1\2\3/gm # done (1st list is consumed completely)
 
/@/!be
h
 
s/^~.*$/~/gm                          # ignore merged lists
s/^.*@\(\w*\).*%\(\w*\).*$/\1 \2/gm  # prepare to comparation
 
 
#------------------- parallel comparation -----
 
# input: word11 word12\nword21 word22\n...\nwordn1 wordn2
# should be lower-case letters. no spaces except for the separator
# the entry '~' is ignored
 
# algorithm:
#   make pairs of corresponding characters in two words
#   compare all pairs at the same time
#   take the first non-equal result of he comparisons
 
 
s/^\| /&#/gm
s/^#~ *$/~/gm
 
:5
s/#\(\w\)\(.*\)#\(\w\)/\1\3 #\2#/mg
s/#\w.*#$/>/mg
s/# #..*/</mg
s/# #$/=/mg
t5
 
:1
 
:2
/a/b9
y/bcdefghijklmnopqrstuvwxyz/abcdefghijklmnopqrstuvwxy/
b2
:9
 
s/a[^a] /</g
s/[^a]a />/g
s/aa /=/g
 
/[^\n=<>~]/b1
s/^=*\(.\)/\1/gm
s/^\(.\).*/\1/gm
 
#----------- parallel comparation done ------
 
s/\n//g
s/$/#/
G
 
# [<>=]*#\nmergedpart @rest_of_list1 %rest_of_list2\n... 
 
# according to the results of comparations held in the head,
# move a head of either the rest of list1 or list2 to the tail of merged_part.
 
 
:m
s/^[<=]\(.*\)\n\(.*\)@\(\w*\) \(.*\)%\(\w*\)/\1-\2\3 @\4%\5/m
s/^>\(.*\)\n\(.*\)@\(\w*\)\(.*\)%\(\w*\) /\1-\2\5 @\3\4%/m
s/^~\([^\n]*\)\n~/\1-/
tm
s/-/\n/g
s/#\n//
bb
 
:e
s/~//g
ba

一文字目でバケットソートしてマージソートを各バケットに適用とかしないとダメっぽい．とにかく操作文字列長を小さくしないと速度が…

数日前，あなごるのLanguage RankingでsedがTop10外になっているのを見たとき，今回の反攻を思いついた．

なんとなく手の届きそうなところに bash と C がいたので，とりあえず手付かずだった問題を１０問強ほど sumit してこいつらを追い越してみた．ほとんどの問題が sed では計算のしようのない問題で embed 中心．だけど，たまにまともなアルゴリズム（？）でといたのもある．reverse entire input は最後の改行だけずるするとか．Permutations は全部のpermutationをまじめに生成するとTLE食らうので，最初の二文字だけは別生成させた上で残りの４文字文をまじめに生成するハイブリッドなアルゴリズムとか．（今のpermutation生成部は打数削減のために遅くなっていて，そのせいでへんなことをする羽目になっている．なので，打数を余計に消費してでも高速なアルゴリズムに切り換えれば全体の打数を小さく出来るかもしれない．）

あとは123 とか解けるといいんだけどなぁ．sedのファイル読み込みは読み込んだ文字列の加工が出来ないから難しい．どこかに 1 2 3 の値をランダムにとるファイル落ちてねえかなぁ？

追記：permutation生成部を高速化したら生成部それ自身が縮んだ．なのでPermutationsのサイズがかなり小さくなった．ついでに permutator のほうも 9B 縮んだ．やっぱ m オプション便利だわ．

追記の追記：さらに縮んだ．結局最初の permutator から 22B 減少．

Windows だと SetThreadAffinityMask で貼り付けたいコアに対応したビットだけ立てたビットマスクを指定すればよいらしい．でも，どのビットがどのコアに対応しているのかよくわからない．ビットマスクとかのフラットな構造でなく，CPUの接続の階層に従った構造体で指定できると楽なのだけど...

Palindromic Quine を sed で 417bytes．

機械的に作っているのでなかなか縮まない．基本的には，「エスケープした文字列データをそのまま出力しなおす，エスケープ解除して出力する，今まで出力した部分の反転を出力する」，という３つの動作をするプログラムを書いて，そのプログラムをエスケープした文字列をそのプログラム自身に食わせれば望みのものが出来上がる．が，この３つの動作をするプログラムが100bytes近くかかっているので，全体で４倍の400bytes超えになってしまう．

もうちょっと頭使わないとだめかなぁ．中心のプログラムが palindrome ならデータ部分とあわせても３倍ですむのだが...　むずい．ついでに，最後に必ず改行が出てしまうので，その分先頭に余計な改行が必要なのも...