nashcft's blog

時々何か書く。

Seven More Languages in Seven Weeks: Julia Day 1の演習問題をやった (ずいぶん前に)

JuliaLang Seven More Languages in Seven Weeks 日記でない

間が空きすぎてしまった...
Day 1 の演習自体は前の記事を書いた後すぐにやってはいたのだけど
下書きを書いた後先に進めている間に詰まったか何かして公開しないまま投げてしまったようです (記憶が朧げ)
とりあえず書いた当時のまま晒すだけ晒しておこう...

github.com

設問の中に5x5x5の配列を作れとあって、3次元以上の配列の作り方を知ってから「じゃあ4次元配列を作ったらどうなるんだろう？」と思って試した結果がこちら:

julia> Array(Int64, 5,5,5,5)
5x5x5x5 Array{Int64,4}:
[:, :, 1, 1] =
 4469252560           0  4469252560           0  4469252560
          0  4469251016           0  4469252560           0
 4469255624           0  4469252560           0  4469252560
          0  4469252560           0  4469252560           0
 4469252560           0  4469252560           0  4469252560

[:, :, 2, 1] =
                   0  7815269745597569819  …  3556471915367379232  0
     140278440639040  7867888721079460201     3556471915367379232  0
 5417930524443302683  2319735731304618779     3539894578555400480  0
 5129700148190993179  2319735477633097777     3539883321446117664  0
 7868170196776672027  2319735477633097777     5132187517736263739  0

[:, :, 3, 1] =
 0  0                    0  7868170196776672027  2319735477633097777
 0  0                    0  7815269745597569819  2319735477633097777
 0  0      140278440639328  7867888721079460201  2319735477633097777
 0  0  5417930524443302683  2319735731304618779  3556471770077798449
 0  0  5129700148190993179  2319735477633097777  3556471915367379232

[:, :, 4, 1] =
 3556471915367379232  20046507979529531  0  0                    0
 3556471915367379232                  0  0  0                    0
 3556471915367379232                  0  0  0                    0
 3539894578555400480                  0  0  0      140278440639616
 3539883321446117664                  0  0  0  5417930524443302683

[:, :, 5, 1] =
 5129700148190993179  2319735477633097777  …  3539883321446117664  0
 7868170196776672027  2319735477633097777          78302376827741  0
 7815269745597569819  2319735477633097777                       0  0
 7867888721079460201  2319735477633097777                       0  0
 2319735731304618779  3556471770077798449                       0  0

[:, :, 1, 2] =
 0                0  5417930524443302683  …  3556471770077798449
 0                0  5129700148190993179     3556471915367379232
 0                0  7868170196776672027     3556471915367379232
 0                0  7815269745597569819     3556471915367379232
 0  140278440639904  7867888721079460201     3556471915367379232

[:, :, 2, 2] =
 3539894578555400480  0  0  0      140278440640192
 6710417459114946848  0  0  0  5417930524443302683
        305851882267  0  0  0  5129700148190993179
                   0  0  0  0  7868170196776672027
                   0  0  0  0  7815269745597569819

[:, :, 3, 2] =
 7867888721079460201  2319735477633097777  3556471915367379232  0  0
 2319735731304618779  3556471770077798449  3539894578555400480  0  0
 2319735477633097777  3556471915367379232  1971786226191053088  0  0
 2319735477633097777  3556471915367379232           1194668379  0  0
 2319735477633097777  3556471915367379232                    0  0  0

[:, :, 4, 2] =
 0                    0  7815269745597569819  …  3556471915367379232
 0      140278440640480  7867888721079460201     3556471915367379232
 0  5417930524443302683  2319735731304618779     3539894578555400480
 0  5129700148190993179  2319735477633097777     6564943274667159840
 0  7868170196776672027  2319735477633097777                 4666417

[:, :, 5, 2] =
 0  0  0                    0  7868170196776672027
 0  0  0                    0  7815269745597569819
 0  0  0      140278440640768  7867888721079460201
 0  0  0  5417930524443302683  2319735731304618779
 0  0  0  5129700148190993179  2319735477633097777

[:, :, 1, 3] =
 2319735477633097777  3556471915367379232  18227  0  0
 2319735477633097777  3556471915367379232      0  0  0
 2319735477633097777  3556471915367379232      0  0  0
 3556471770077798449  3539894578555400480      0  0  0
 3556471915367379232  3556466417809240352      0  0  0

[:, :, 2, 3] =
                   0  5129700148190993179  …  3616772148839854368
                   0  7868170196776672027                      71
                   0  7815269745597569819                       0
     140278440641056  7867888721079460201                       0
 5417930524443302683  2319735731304618779                       0

[:, :, 3, 3] =
 0  0                0  5417930524443302683  2319735731304618779
 0  0                0  5129700148190993179  2319735477633097777
 0  0                0  7868170196776672027  2319735477633097777
 0  0                0  7815269745597569819  2319735477633097777
 0  0  140278440641344  7867888721079460201  2319735477633097777

[:, :, 4, 3] =
 3556471770077798449  3539894578555400480  0  0  0
 3556471915367379232  5129935717922582816  0  0  0
 3556471915367379232                    0  0  0  0
 3556471915367379232                    0  0  0  0
 3556471915367379232                    0  0  0  0

[:, :, 5, 3] =
     140278440641632  7867888721079460201  …  3556471915367379232  0
 5417930524443302683  2319735731304618779     3539894578555400480  0
 5129700148190993179  2319735477633097777       20037711886507296  0
 7868170196776672027  2319735477633097777                       0  0
 7815269745597569819  2319735477633097777                       0  0

[:, :, 1, 4] =
 0  0                    0  7815269745597569819  2319735477633097777
 0  0      140278440641920  7867888721079460201  2319735477633097777
 0  0  5417930524443302683  2319735731304618779  3556471770077798449
 0  0  5129700148190993179  2319735477633097777  3556471915367379232
 0  0  7868170196776672027  2319735477633097777  3556471915367379232

[:, :, 2, 4] =
 3556471915367379232  0  0  0                    0
 3556471915367379232  0  0  0                    0
 3539894578555400480  0  0  0      140278440642208
        305904950109  0  0  0  5417930524443302683
                   0  0  0  0  5129700148190993179

[:, :, 3, 4] =
 7868170196776672027  2319735477633097777  3556471915367379232  0  0
 7815269745597569819  2319735477633097777  3556471915367379232  0  0
 7867888721079460201  2319735477633097777  3556471915367379232  0  0
 2319735731304618779  3556471770077798449  6710428716224229664  0  0
 2319735477633097777  3556471915367379232           1194875675  0  0

[:, :, 4, 4] =
 0                    0  5129700148190993179  …  3556471915367379232
 0                    0  7868170196776672027     3556471915367379232
 0                    0  7815269745597569819     3556471915367379232
 0      140278440642496  7867888721079460201     3556471915367379232
 0  5417930524443302683  2319735731304618779     1971797483300335904

[:, :, 5, 4] =
 4667227  0  0                0  5417930524443302683
       0  0  0                0  5129700148190993179
       0  0  0                0  7868170196776672027
       0  0  0                0  7815269745597569819
       0  0  0  140278440642784  7867888721079460201

[:, :, 1, 5] =
  2319735731304618779  0  0  0  0
  2319735477633097777  0  0  0  0
 -6917529027641081856  0  0  0  0
 -6917529027641081856  0  0  0  0
                    0  0  0  0  0

[:, :, 2, 5] =
 0  0  0  0  0
 0  0  0  0  0
 0  0  0  0  0
 0  0  0  0  0
 0  0  0  0  0

[:, :, 3, 5] =
 140278443538256  0  0  0  0
 140278438868112  0  0  0  0
               0  0  0  0  0
               0  0  0  0  0
               0  0  0  0  0

[:, :, 4, 5] =
 0  0  0  0  0
 0  0  0  0  0
 0  0  0  0  0
 0  0  0  0  0
 0  0  0  0  0

[:, :, 5, 5] =
 0                0  140278443539344                0  0
 0                0  140278438866256  140278438864720  0
 0                0  140278443538768  140278438868016  0
 0  140278443538896  140278443540944                0  0
 0  140278438867888                0                0  0

なんでや...
ちなみに5次元配列、6次元配列を作るとちゃんと0で初期化された配列が返ってくる（そこまでしか試していない）。

julia> Array(Int64, 5,5,5,5,5)
5x5x5x5x5 Array{Int64,5}:
[:, :, 1, 1, 1] =
 0  0  0  0  0
 0  0  0  0  0
 0  0  0  0  0
 0  0  0  0  0
 0  0  0  0  0

[:, :, 2, 1, 1] =
 0  0  0  0  0
 0  0  0  0  0
 0  0  0  0  0
 0  0  0  0  0
 0  0  0  0  0

[:, :, 3, 1, 1] =
 0  0  0  0  0
 0  0  0  0  0
 0  0  0  0  0
 0  0  0  0  0
 0  0  0  0  0

[:, :, 4, 1, 1] =
 0  0  0  0  0
 0  0  0  0  0
 0  0  0  0  0
 0  0  0  0  0
 0  0  0  0  0

[:, :, 5, 1, 1] =
 0  0  0  0  0
 0  0  0  0  0
 0  0  0  0  0
 0  0  0  0  0
 0  0  0  0  0

[:, :, 1, 2, 1] =
 0  0  0  0  0
 0  0  0  0  0
 0  0  0  0  0
 0  0  0  0  0
 0  0  0  0  0

...

[:, :, 3, 5, 5] =
 0  0  0  0  0
 0  0  0  0  0
 0  0  0  0  0
 0  0  0  0  0
 0  0  0  0  0

[:, :, 4, 5, 5] =
 0  0  0  0  0
 0  0  0  0  0
 0  0  0  0  0
 0  0  0  0  0
 0  0  0  0  0

[:, :, 5, 5, 5] =
 0  0  0  0  0
 0  0  0  0  0
 0  0  0  0  0
 0  0  0  0  0
 0  0  0  0  0

Seven More Languages in Seven Weeks の Juliaパートを読む: Day 1

JuliaLang Seven More Languages in Seven Weeks 日記でない

Julia入門の為に買ったSeven more Languages in Seven Weeksを読み始めたので1日分ずつブログに書いて記録する事にした。

この本で扱われているJuliaのバージョンは0.3.0だけど自分の環境が0.4.0-devなので、その辺の差異は夜道さんのJulia本やブログ記事、公式docで調べつつ進めている。

Day 1: Resistance Is Futile

インストールの話などもそこそこに、まずはJuliaの型の紹介から始まる。
延々とtypeof()に値を突っ込んでみていく。気になったのでtypeof()に型名を入れるとDataTypeと出力された。
型紹介の最後にDictが出てきたがこれは0.3.xと0.4.xでは定義方法が異なる。

# v0.3
# {}で括ると型の束縛のないDictができる。
julia> {:a => 12}
Dict{Any,Any} with 1 entry:
  :a => 12

# []で括ると値からの型推論で型が固定される。
julia> [:a => 12]
Dict{Symbol,Int64} with 1 entry:
  :a => 12

# 前に(KeyType => ValueType)と書く事で型を指定できる。
julia> (ASCIIString => Float32)["a" => 1.2]
Dict{ASCIIString,Float32} with 1 entry:
  "a" => 1.2f0

# v0.4
# Dict(key => value, ...)と定義する。この定義方法だと型推論される。
julia> Dict(:a => 12)
Dict{Symbol,Int64} with 1 entry:
  :a => 12

# 型を明示的に指定する際はDict{KeyType, ValueType}(key => value, ...)
julia> Dict{Any, Any}(:a => 12)
Dict{Any,Any} with 1 entry:
  :a => 12

次は演算子の紹介。除算関係には関数もある。この辺について夜道さんのJulia本に挙動の違いが書かれている。/を使うとInt同士の除算でも返り値がFloatになるが、div()を使うと返り値は整数値になる。div()の引数にFloatを入れると、Float型の整数(1.0とか)が返却される。
後はbit表現する為のbits()とか、bit演算子とか。

続いてDictionaryとSetの紹介。定義の方法はさっき書いた通り。値の取り出し方はdict[key]の他、存在しないkeyを指定した際のdefault値も指定するget(dict, key, default)もある。keyを全て取得するkeys()の返り値はKeyIteratorになる。collect()でIteratorから配列を作成する。

julia> numbers = Dict(:a => 1, :b => 2, :c => 3)
Dict{Symbol,Int64} with 3 entries:
  :b => 2
  :c => 3
  :a => 1

julia> numkey = keys(numbers)
KeyIterator for a Dict{Symbol,Int64} with 3 entries. Keys:
  :b
  :c
  :a

julia> numkey[2]
ERROR: MethodError: `getindex` has no method matching getindex(::KeyIterator{Dict{Symbol,Int64}}, ::Int64)
Closest candidates are:
  getindex(::(Any...,), ::Int64)
  getindex(::(Any...,), ::Real)
  getindex(::FloatRange{T}, ::Integer)
  ...

julia> collect(numkey)[2]
:c

inは演算子と関数とがあるDictionaryに対してin()を用いるときは第一引数がkeyとvalueのpairでなければならない。
Setにはunion(), intersection(), setdiff(), issubset()等の関数が備えられている。

Array。indexが1スタートなのが違和感ある。基本的に1つのArrayに複数の型の要素を入れられる。型指定するときはType[]と書く。zeros(), ones(),fill()といった初期化用の関数がある。あとはindex指定にendとかsliceがある。 sliceを使って再代入すると指定範囲全てに変更が適用される。 次元まわりは以下のような感じ。

julia> [1,2,3]
3-element Array{Int64,1}:
 1
 2
 3

julia> [1 2 3]
1x3 Array{Int64,2}:
 1  2  3

julia> [[1,2,3],[4,5,6],[7,8,9]]
9-element Array{Int64,1}:
 1
 2
 3
 4
 5
 6
 7
 8
 9

julia> [1 2 3; 4 5 6; 7 8 9]
3x3 Array{Int64,2}:
 1  2  3
 4  5  6
 7  8  9

コンマでなくてセミコロンでもいいみたい。線形代数関係の演算をする為の関数も色々ある。eye()でidentity matrixを定義できたり、.*で要素ごとの乗算ができたり、Arrayの後に'をつけるとtransposeができたり。

Day 1の解説部分はこれでおしまい。この後に練習問題があるので解いてどこかに放り投げる予定。

Neo4jユーザーグループ再結成 ＆ Neo4j 無料セミナーに参加してきた #Neo4jUsersGroup

Neo4j イベント 日記でない

再結成だったそうで。最初の結成の頃はOrinetDB触ってた頃だけど気づかなかったっぽい。

Neo4jユーザーグループ再結成 ＆ Neo4j 無料セミナー - connpass

Read more

JavaScriptのRegexとそれの効率的なコードの書き方

日記でない JavaScript

これは過去にQiitaに投稿したもの

High Performance JavaScriptに書かれているJavaScriptにおけるregular expressionの書き方に関するメモ。
Regexpの処理に関しては他言語と共通かも判りませんが。

結論

  • Backtrackingを起こさないような作りにしよう

Backtracking

解析中にある文字でマッチングに失敗した際、直近の処理の分岐点まで遡る事。
遡った後、まだマッチングが行われていない選択肢(e.g. 次の文字、|で隔てられた右側の候補)から処理を再開する。

quantifier/alternationに関する処理の流れ

  • quantifier: *, +?, {n}など
  • alternation: |
例

/h(ello|appy) hippo/.test("hello there, happy hippo")

  1. 1文字目hがマッチする。それ以降の文字に対するマッチングを開始する。
  2. alternationによる候補(左の候補から順に試行を行う)elloとのマッチングを行う。
  3. elloまでマッチするが次の文字(h vs t)でfail。backtrackしてalternationの分岐に移動し次の候補appyのaからマッチングを始める。failなのでbacktrack。
  4. 2文字目以降とregexp先頭のhとのマッチングを繰り返し、14文字目のhがマッチ。2.と同様分岐からelloとのマッチングへ。
  5. e vs aの時点でfail。backtrackして分岐に戻り、次の候補appyとマッチング開始。
  6. そこから先が全てマッチングに成功し、happy hippoとマッチ。

greedyとlazy (nongreedy)マッチングの処理の違い

// 例文
var example = '<p>a paragraph.</p>';

// greedy
/<p>.*<\/p>/.test(example);
// lazy
/<p>.*?<\/p>/.test(example);

greedyの場合、.*でのマッチングでa paragraph</p>まで全て検査し、その後残りの<\/p>とのマッチングの為に1文字ずつbacktrackして.*に含まれる文字を減らしながら検査していく。
lazyの場合<p>までマッチングした後、.*?と空文字がマッチした状態から<のマッチングを開始し、対象の文字列中の<にマッチするまでbacktrack->1文字.*?のマッチ対象に含めながら1文字ずつ検査を進めていく。
マッチさせたいパターンからbacktrackingの回数を求め、適切な方を選ぶ。

不要なbacktrackingを防ぐ

トークンをオーバーラップさせない

隣り合ったトークンが対象についてオーバーラップしないようにする。
例えば適当な文章から""で括られている文をマッチさせたい時に/".*?"/ではなく/"[^"\r\n]*"/を使うとか 。前者では.と"による対象文字列中の"へのオーバーラップが生じ、backtrackingが起こる分岐点が発生している。後者にはオーバーラップが無い。

Lookaheadを使う

Lookaheadとは: https://developer.mozilla.org/en/docs/Web/JavaScript/Guide/Regular_Expressions#special-lookahead JavaScriptには無いatomic groupingの機能を模倣する事が出来る。
atomic groupにマッチした文字列はbacktrackingで検査が再開されるポイントにはならないので余計な検査が行われない。
Lookaheadは通常その中に含まれるregexpをマッチ対象として扱わない(上記リンクに挙動の例があります)が、以下の様にregexpをcapturing groupに包んで、lookaheadの外にバックリファレンスを与える事でマッチした対象として扱う事が出来る。

/...(?=(pattern))\1.../

使いどころとしてはmarkup言語に対して検査を行う時。

分岐箇所を極力小さく

複数単語のマッチングに対してalternationで単語ごとに分けるのではなく異なる部分だけ切り出す感じ。
以下例

instead of use
cat | bat [cb]at
red | read rea?d
red | raw r(?:ed｜aw)
(. | \r | \n) [\s\S]

補足としてcharacter class ([\s\S]とか) を使った方がエンジンの実装的にalternation使うより速いっぽい。

ベンチマークの方法

backtracking捕捉の為、作ったregexpに対して大部分がマッチするけどマッチしないパターンを含む長い文字列を使う。

そもそも使わない

検査対象が非常に具体的な場合はString型のメソッドで処理した方が安上がりだったりする。

その他

シンプルに、具体的に、明示的に、等々

第15回Solr勉強会 メモ #SolrJP

Solr Lucene イベント 日記でない

特に前知識など無しに参加してみた。技術調査的なノリだった。

Lucene / Solr Revolution 2014 Report : 株式会社ロンウィット 打田さん

  • Lucene FST (Finite State Transducer)とSolrTextTaggerの紹介。
  • conferenceに関してはスライドを読んでくださいとの事。
  • 多言語対応やsemantic searchのアーキテクチャについてのセッションがあった。
  • 多言語対応に関してはプレゼンの際には省略されたが、言語の扱い方を3つの戦略に分け、それぞれのPros/Consを挙げている。
    • 言語毎にfieldを分ける場合、実装がシンプルになるが対応言語数が増えるにつれてパフォーマンスが落ちるので何かしら手を打つ必要が出てくる。
    • 言語毎にcollection / coreを分ける場合、言語数に関わらずスピードが出て、検索対象となるfieldは1つなのでパーサの選択何でも良いが、環境含め複雑さが増す。
    • 全ての言語を1つのfieldに入れる手法はSolrには機能として派存在しないらしい。何か自分で書くっぽい。
  • Semantic search = query augmentation (再現率の向上) + ranking tuning
    • 入力された検索ワードに対して類似の単語や付加情報を追加し、重み付けを加えたものを実際の検索に用いる。
  • 拡張は以下の4ステップで行われる:
    1. ドメイン特化したフレーズモデルの作成 (machine learningなどを利用)
    2. SolrTextTaggerに1.で作成したフレーズを食わせる
    3. SolrTextTaggerで検索クエリからフレーズ抽出、tagging
    4. クエリを書き換える
    5. 1.のMLに関する所がセッションではあまり話されなかったと言っていたが、Lucene / Solrにがメインのconferenceだからそんなものでは?
  • SolrTextTaggerはLucene/Solrを応用したフレーズタガー。2つの単語認識とフレーズ認識の2段階でFSTを用いている。
  • このFSTの実装がLuceneFST
    • Finite State TransducerとはFinite State Automataが受理時に何かしらの値を出力する機能を持ったもの (?)
      • でもSTTでは出力を使ってないらしい

    • "Essentially, an FST is a SortedMap<ByteSequence,SomeOutput>, if the arcs are in sorted order."

  • これを使ったらLuceneのFuzzyQueryが100倍速くなった(!)
  • 応用として自然言語処理における高速・省メモリ辞書に使えるかも。
  • デモ、図説、etc...

Read more

Relational Theory for Computer Professionalsを読んだ

relational_theory SQL 日記でない

Relational Theory for Computer Professionals: What Relational Databases Are Really All About (Theory in Practice)

Relational Theory for Computer Professionals: What Relational Databases Are Really All About (Theory in Practice)

すでにだいぶ前の話ではありますが。
大学時代NoSQLはそれなりに追っていたのですがRDBはそうでもなかったので、一度理論側からしっかり勉強してみようと言う事で、1冊目にこの本を選びました。
200ページそこそことそれほど分量もなくさくっと読めるかと思ったら結構手こずりました。その辺に関しては後ほど。

構成としては3つのパートに分かれており、パート1がrelational modelについて、パート2はデータベースのトランザクションとデザインについて、パート3はSQLについて述べられています。Relational modelのoperationについてはTutorial Dで、SQLはISO標準に基づいて記述されています。パート1とパート3を対応させるように書かれており、理論と実装の差異がより明確に浮かび上がらせ、この対比を通してrelational theory本来の簡潔さや表現力の高さを主張しています。
AppendixではTutorial Dの補足的な解説や定義について、また集合論のちょっとしたまとめが付随してるので、数学的な背景に自身の無い人でも必要最低限は押さえられると思います。

内容とは関係ないですが、とてもwordyな本だという印象を持ちました。もっと簡潔に書いてくれたらもっと評価高かったんだけどな...。
あとDate氏はSQL嫌いなんだろうなーと思いました。Prefaceののっけから"... considered as a concrete realization of the abstract ideas of the relational model, SQL is very deeply flawed" なんて言ってますし。その後も　SQLは全然relationalじゃないよーと度々主張していたり、パート3の最終章ではその具体例を列挙していたり。

RDBやそのoperationの集合論的な捉え方をある程度習得できたし、よりrelationalなSQLの書き方も解った所で、さて次は何を読もうか。

TortoiseHg (+Mercurial)のmerge toolやdiff toolがちゃんと使えるようになるまで

hg tortoisehg 日記でない

ひょんな事からLinux上でTortoiseHgを使う事になったがdiff toolやmerge toolにgvimdiffを設定した所上手く起動せず、二進も三進もいかなくなってtwitterでぼやいたら入門TortoiseHg+Mercurialの著者フジワラさん(@flyingfoozy)を始め複数人の方に助けていただいたので、教えていただいた内容をまとめます。
なおこの記事は私のケースと同じくgvimdiffを設定する場合のみ扱っています。より一般的な情報についてはフジワラさんによる解説記事を参照してください。

Read more