2014-06-21

Daily Julia #3

Julia

最大/最小値関数周りのリネームに関する議論 #7327

RFC: Added find_extrema, ind_extrema by kmsquire · Pull Request #7327 · JuliaLang/julia

Julia では Array の最大最小値の情報を得るための関数がいくつも存在する。

まず maximum, minimum という最大値と最小値のみをそれぞれ得る基本的な関数がある。
また extrema という関数がある。これはArray から最大値と最小値のタプルを返す関数である。
さらに indmax, indmin という Array から最大値あるいは最小値のインデックスを取り出す関数がある。
はたまた findmax, findmin という関数もある。これは値とインデックスのタプルを返却する。

現在ある最大最小値系の関数を表にすると次のようになる。

	value	(value, index)	index
最小値	minimum	findmin	indmin
最大値	maximum	findmax	indmax
最大最小値	extrema	-	-

この Issue は「extrema における ind_extrema, find_extrema を追加しよう」というものだった。だった、というのは途中から議論の方向が「そもそもこの辺りの名前があまりよくない」という風向きになってきたからである。

まず口火を切ったのは Karpinski で、indmin, indmax という名前が lousy in the first place （そもそも気に食わない）と言い、argmax, argmin にリネームすべきと述べた。

すると johnmyleswhite は、argmax, argmin にするのはいいがそれは基本的に数学におけるある関数 f の最大/最小値を意味する言葉なのでインデックスを表す言葉に使うのはいかがなものかとコメントしている。

それにさらに応えて kmsquire 曰くいやいや関数 f をインデックスを値にマッピングする関数として捉えれば問題ないよ云々。高度なことを言っているわけではないが自分が同じように言い返せるかというと無理ですわ。

さて、いくらかの議論ののち kmsquire がまとめたところによると最大/最小値関数周りのネーミングは次のように整理され書き直された。

	value	(value, index)	index
最小値	minimum	findmin	argmin
最大値	maximum	findmax	argmax
最大最小値	extrema	findminmax	argminmax

まだマージされていないがこれ以上あまり議論する余地もないだろうしそのうち取り入れられるだろう。

Git を Libgit2 に置き換える準備が整いつつある？ #7339

WIP: andrioni's Libgit2 work by StefanKarpinski · Pull Request #7339 · JuliaLang/julia

Package のアップデートが遅いので (大量の git のシステムコールがボトルネック？) libgit2 で書き換えて高速化しようという案件。前回の Issue が2013 年の 8 月なのでとっくに終わったものと思っていたら、ようやく一里塚に漕ぎ着けたというところだったのか。

Reimplement Git using libgit2 · Issue #4158 · JuliaLang/julia

関数が属しているモジュールを取るリフレクション #7322

added reflection method by mauro3 · Pull Request #7322 · JuliaLang/julia

これは便利なんじゃなかろうか。

julia> Base.@binding_module sin
Base

julia> Base.@binding_module a
ERROR: Symbol a is not bound in the current module Main and not exported in any 'used' module.
 in error at error.jl:21
 in binding_module at reflection.jl:171

julia> a = 4
4

julia> Base.@binding_module a
Main

julia> Base.binding_module(:a)
Main

Karpinski は REPL 上で属しているモジュール名を印字するようにすればいいんじゃねと言っている。

`cumsum` のパフォーマンスが悪い #7342

To improve performance in cumsum · Issue #7342 · JuliaLang/julia

cumsum は配列を類積和の配列にして返す関数。キャッシュを実装してないから遅い云々。どんなもんかなと実装見たらメタプログラミングされてて軽くビビった。

2014-06-21

字幕情報を利用した Python による動画自動編集 (Videogrep)

昨日 Videogrep というツールがちょっと話題になっていたので使ってみました。字幕情報 (.srt 形式) を用いていわゆる Supercut と呼ばれる編集手法を自動化する Python スクリプトです。

Videogrep: Automatic Supercuts with Python – Sam Lavigne

Supercut とは同じ言い回しやフレーズを言っている（あるいは動作を行っている）場面を寄せ集めてテンポのいい合成映像（モンタージュ）を作ることです。コミカルな演出を狙って使われることが多いようですね。

日本語での検索ワードを知らないので分かりやすい例をパパッと挙げるのは難しいですが、この辺でいかがでしょう。

▶ ことりちゃんのﾎﾉｶﾁｬﾝ集完全版 - YouTube

ポルノグラフィティの曲から「僕」だけを集めてみた - ニコニコ動画:GINZA

英語のみですが Supercut 動画だけを集めたサイトもあるようです。

Supercut.org — Home of the Obsessive Video Montage

インストール

事前準備

まず ffmpeg が必要です。音声ファイルを書き出す際 ogg 形式を利用するらしいので libvorbis エンコーダも必要です。

OS X & Homebrew の場合は以下のコマンドで一発インストールできます。

$ brew install ffmpeg --with-libvorbis

Linux の人も apt-get あたりを使えば簡単にインストールできるのではないでしょうか。Windowsの人は MinGW なり Cygwin なりを使うのでしょうがちょっと大変かも知れません。

続いてここのrequirements.txt に記載されているライブラリ群をインストールしましょう。

$ git clone https://github.com/antiboredom/videogrep
$ cd videogrep
$ pip install -r requirements.txt

moviepy やら pytube やらリッチなライブラリに依存してますな…

脱線

moviepy 単体でも動画編集やネタ GIF を作るのに便利です。以下の記事は moviepy を使ってネタ GIF を作る技法を惜しみなく伝えており非常に面白いです。

Making GIFs from Video Files with Python - del( self )

上の requirements.txt には載ってないですが moviepy でリサイズを使おうとすると PIL か scipy か OpenCV を必要としたと思います。Videogrep ではリサイズ機能は使わないんですが欲しくなることもあるのでインストールしておくといいでしょう。

$ pip install pillow

使ってみる

今のところ Python スクリプトとしてのみ使えるようです。git clone して videogrep.py のあるフォルダに降り、

$ python videogrep.py --input /path/to/{target.{mp4|srt}|folder} --search 'search phrase'

というのが基本的な使い方になります。このコマンド一発で、あとは 'search phrase' に引っかかった場面を supercut した動画を吐き出してくれます。ここで注意しなければならないのは /path/to/target.{mp4|srt} のあるフォルダには同名の動画or字幕ファイル target.{mp4|srt} も置かれている必要があるということです。これはやや不自由ですがそういう規約として作ったみたいなので受け入れるしかないです。

しかし利用例として誰にでも手に入れられる日本語動画と字幕がないかと探してみたのですがなかなか難しいですね。映画字幕というサイトもあるようですが元の映画を持ってないと厳しい。

ところで関係ないですがここで羽生さんの TEDxTokyo の動画を貼っておきます。

まず YouTube の字幕ファイルは（存在すれば） videogrep/tools/getyoutubecc.py を使えば手に入ります。

$ python getyoutubecc -v [動画のID] -l ja
[動画のID].srt というファイルができている

動画をダウンロードするには videogrep/tools/videodownloader.py が使えますがこれは投稿者のビデオ一覧からまとめて落とすためのものらしいので一つの動画を落とすのには不便です。pytube がせっかくインストールされているので自作のスクリプトでごにょごにょしてみるのもオツでしょう。getyoutubecc にしろ videodownloader にしろ簡単なスクリプトなので Python 初心者の人は読んでみるともしかしたら勉強になるかもしれません。

字幕ファイルと動画ファイルが揃ったら同じ名前にリネームし、あとは最初の使い方で述べたようにコマンドを実行すれば自動的に変換されます。

$ python videogrep.py --input habu.mp4 --search "ですね"
Creating clips.
25.664 to 27.397: 私はですね 普段はほとんど
29.495 to 31.571: こうやって話をするのがですね
34.069 to 37.341: せっかくですね こういった機会を頂きましたので
41.244 to 46.575: 今日はですね 棋士というのがどんな風なプロセスで
56.246 to 59.056: 「読み」というものなんですね
69.238 to 71.865: 基本中の基本というのがですね
84.153 to 87.258: その三手の読みということですね
87.258 to 89.967: これは将棋に限らずですね
92.013 to 94.164: 結構そういうことをですね
97.868 to 99.575: 通常の場合はですね

... （中略） ...

MoviePy: building video file supercut.mp4
----------------------------------------
Writing audio in supercutTEMP_MPY_to_videofile_SOUND.ogg
Done writing Audio in supercutTEMP_MPY_to_videofile_SOUND.ogg !

Writing video into supercutTEMP_MPY_to_videofile.mp4
|#####-----| 1396/2747  50% [elapsed: 00:39 left: 00:38, 35.53 iters/sec]Warning: in file supercut.mp4.tmp0.mp4, 2764800 bytes wanted but 0 bytes read,at frame 1397/1398, at time 58.21/58.22 sec. Using the last valid frame instead.
Done writing video in supercutTEMP_MPY_to_videofile.mp4 !

Now merging video and audio:

MoviePy Running:
>>> ffmpeg -y -i supercutTEMP_MPY_to_videofile_SOUND.ogg -i supercutTEMP_MPY_to_videofile.mp4 -vcodec copy -acodec copy supercut.mp4
... command successful.

Your video is ready ! Fingers crossed for the Oscars !

--output filename で出力ファイル名を指定しないとデフォルトでは supercut.mp4 というファイルが出来上がります。ちゃんと自動カットされているでしょうか？

弁解： 羽生先生を選んだのはたまたま字幕が付いていたというだけで他意はありませんスイマセン。10 分弱のプレゼンで 40 回「ですね」と言っていたのでおもしろおかしく抽出した面は否めませんが、さすがに趣味が悪いのでアップロードは控えておきます。動画を手元に置いておく習慣がないのでテストデータを探すのにも一苦労したという話でした。

高度な使い方

Videogrep: Automatic Supercuts with Python – Sam Lavigne

複数の動画ファイルを一度にまとめたり、pattern を利用して文章構造を解析することも可能なようです。また頻出ワードを探すのには N-gram などのような手法でコロケーションを調べたりするとよりメカニカルに編集できて面白いかもしれません。ちなみに pattern でできる文章構造の解析は言語が限られている（英語の他にも複数言語使えるが日本語はない）ようなので日本語をちゃんと解析したかったら自力で MeCab を叩くことになるでしょう。

おまけ：srt ファイルの作り方

動作は確認してないですが HN でいくつかの字幕作成エディタの名前が挙がっています。

Aegisub Advanced Subtitle Editor

アニメ字幕作成のスタンダードらしい。Windows, OS X, Linux すべてで動作する

Subtitle Editor

GTK+2 製の *nix 環境で動作するエディタ

Home [VisualSubSync]

Windows 用

subler - Google Project Hosting

Mac OS X 向け

Gnome Subtitles | Video subtitling for the GNOME desktop

これも *nix 環境向け

2014-06-20

Daily Julia #2

Julia

この連載には Julia 周辺の気になるトピックを集めておく、ということ以外の方針らしい方針は存在しない。要するにチラ裏である。情報の速報性にはあまりこだわらずパッケージ類なども適宜触っていこうと考えている。ブログを更新することそれ自体が目的なのです。

goto マクロがマージされた #5699

Add labels and gotos. (Fixes #101) by dcjones · Pull Request #5699 · JuliaLang/julia

マクロとして @goto, @label が組み込まれた。早速 HEAD を更新して動かそうとしたら次のコードがエラー。

function f()
  @goto x

  println("not printed.")
  
  @label x
end

ERROR: label 0 not found

エラーメッセージが 0-origin なのは 1-orgin を採用している Julia への暗黙の抗議に見える。

さてなんで動かないのかなーということだが、ここでのやりとりを見るに @goto を最後の式と使うことはまだできず、明示的な return をしないとだめである。

追記： 以下のプルリクで直った。

Fix error on functions ending with @goto. by dcjones · Pull Request #7312 · JuliaLang/julia

実装がよく分からないのだが julia-syntax.scm から AST をいじっているようだ。Scheme 難しい。

float(AbstractArray) と complex(AbstractArray) のパフォーマンス改善 #7308

Performance: float(AbstractArray) and complex(AbstractArray) by catawbasam · Pull Request #7308 · JuliaLang/julia

名前を付けた関数と比較して無名関数は 3.3 倍遅かった。ProfileView.jl のデモを見ていたら気づいたとのこと。無名関数はやはり遅いのか。

しかしこうなると色々直すべき所あるんじゃないだろうか。例えば typeof もこんな感じで無名関数でちゃちゃっと書かれているが、こういうのもパフォーマンス上の問題を引き起こしたりしないのだろうか？

typesof(args...) = map(a->(isa(a,Type) ? Type{a} : typeof(a)), args)

julia/base/interactiveutil.jl at master · JuliaLang/julia

実測してないからやいのやいの言っても仕方ないか。それとも型キャストみたいにパフォーマンスに敏感になるほど使わないのかな…

話はずれるが、ProfileView の作者が notebook でデモを動かそうとしたら SVG (mime?) がちゃんと表示されなかったので IJulia 方面に Issue を立てたようだ。実は自分もこれを動かそうとしたときに気づいたけど「これバグ？」って Issue 立てるのは心理的障壁高いなー。

ProfileView Example and abstractarray.jl

`staged` な関数 (メソッド) に関する議論 #7311

Staged Functions · Issue #7311 · JuliaLang/julia

あまりよく理解できないが、メタプログラミング方面の強力な提案であるらしい。

@staged function foo{T<:Real}(::Type{T},::Type{T})
  quote
    $T
  end
end

というふうに書くと、

julia> foo(1,1)
Int64

foo(::Int64, ::Int64) という特殊化されたメソッドがコンパイルされる。Jeff Bezanson の言葉を引いておく。

macros are so last century - Google グループ

A staged method is very similar to a normal method, except instead of computing a result value from input values, it constructs code from the types of the arguments, and that code will then be called on the actual run-time argument values.

disallow f (a,b) · Issue #7232 · JuliaLang/julia

関数とカッコの間にスペースを置くスタイルをエラーにするべきという議論。マクロとカッコの間にスペースを置くとエラーになるのでそれとの兼ね合いから不可ということにしたい？マクロにカッコを強制するか否かという点についても議題に上っているようだが、それを強制すると @inbound や @parallel を書く時にだるいことになるなどなど。

Literate Julia?

Literate Julia? - Google グループ

Literate Haskell みたいなのを作る気ありませんか、と聞いているのかもしれないが微妙にオフトピとして見られてるっぽい？　紹介されているサードパーティ製のライブラリにちょっと興味があるので見てみる。

jocco

Docco の Julia ポート。METADATA.jl に登録されてないので Pkg.add できない。そもそも去年から更新されていないので 0.3 対応も進んでないっぽい。

Markdown.jl

こちらは現在進行形で開発が続いているようだ。Markdown パーサを自前で書いており GitHub Flavoured Markdown もパースできるらしい。将来的に Literate な記法や HTML, PDF, ターミナル, IJulia notebook へのアウトプットを行えるようにすると言っているが、pandoc の力を借りる気はないのか、という気もしないでもない。

2014-06-18

Daily Julia #1

Julia

Julia にもっと近づきたいという気持ちが出てきたので ML や master の開発周りを眺めながら話題をメモってみる。自分にはちょっと流速が速すぎるので見落としは多くまるで網羅的じゃないですが、内容より更新速度重視ということでやっていきます。

Grisu アルゴリズムの実装 #7291

WIP: Grisu by quinnj · Pull Request #7291 · JuliaLang/julia

WIP ではあるが、浮動小数点数を正しく高速に 10 進変換する Grisu アルゴリズムというものが実装された。大量のテストコードが追加されており気魄が感じられる。

Grisu at Avik’s Ruminations

Grisu というか浮動小数点数周りがよくわからないので、リンク先を読み下しながら知識を整理してみる。

復習： 浮動小数点数は符号と指数部と仮数部のビット列から成り立っている。例えば 64 ビットのマシンでの Float は指数部 11 ビット、仮数部 52 ビット、符号 1 ビットからなる。

浮動小数点数を画面に表示したり、文字列に変換したりするとき、ビット列で表現された浮動小数点数を 10 進表現に直す必要がある。ここで注意しなければいけないのは、2進表現された浮動小数点数では表現しきれない10進小数があるということだ。Julia は Float16 が使えるのでそれを用いて丸め誤差が起こっていることを簡単に観察できる。

julia> float16(0.1)
float16(0.099976)

これは有限精度のコンピュータを使っている以上避けられないことではあるのだが、それでは困ることもあるので（どう困るのかよいシチュエーションが思い浮かばないが、まあいろいろ困るだろう）、正確に 10 進変換するアルゴリズムが必要とされたのであろう。正確な 10 進変換が満たすべき性質は次のように書ける。

read( show(d) ) == d

つまり変換と逆変換を行って元の数に戻るような 2 つの関数が欲しいのだ。

こうした浮動小数点数から 10 進数への変換に関する研究は 1990 年の How to print floating-point numbers accurately がよく知られている。この論文で発表されたアルゴリズムは Dragon4 という。なんだそのかっこいいネーミング。

Dragon4 は高速なアルゴリズムであり netlib の dtoa.c に取り込まれ広く使われていた。だが、実装には任意長精度の数値型を必要とし (いわゆる bignum)、そのために実用上の速度は遅くコードも長くて複雑になるという問題があった。

Dragon4 の高速な代替として提案されたのが Grisu である。これは 2010 年に考案された。

【PDF注意】 Printing floating-point numbers quickly and accurately with integers

Grisu は任意精度計算をせず Int64 しか使わないので高速である。ただし欠点もあり、浮動小数点数全体の 0.5 % に対して正確な計算がうまくできないことがあるとのことだ。失敗した計算をフォローするとパフォーマンスが落ちるとの由。

Grisu が現実世界のどこで使われているのかというと、JavaScript の V8 エンジンに取り込まれていることで有名であったらしい (実際には double-conversion という独立なプロジェクト)。

Julia ではこれまでマクロによって C++ の実装を叩いていただけであったが、このたび pure Julia による実装が書かれたということで実にめでたいというお話でした。

関連

Implement proper print_shortest for Float16 · Issue #5959 · JuliaLang/julia

Port of Double-Conversion library to native Julia

quinnj/Grisu.jl

Dates.jl が Base にマージされた #7285

Merge Dates.jl package into Base by quinnj · Pull Request #7285 · JuliaLang/julia

Datetime.jl もあるようだが関係性がよく分からない。

quinnj/Dates.jl

quinnj/Datetime.jl

2014-04-30

Firefox 29におけるVimperatorでナビゲーションバーを消す方法

UI が刷新されたようで表示からナビゲーションバーが消せなくなっている。

set gui=nonavigation

なんか一回目失敗したけど再起動してやり直したらうまくいった。なんというconventional tips...

2014-04-23

Julia のマクロによる日本語文字列リテラル

くだらない小ネタでしかも二番煎じっていう…

Fun with Unicode and Julia - IainDunning.com

Julia のソースコードには日本語が使える
Julia ではマクロでユーザー定義の文字列リテラルを宣言できる

2 について例示すると、正規表現リテラル r"^\s*(?:#|$)" のようなものもマクロで定義された正規表現オブジェクトに過ぎない (see julia/base/regex.jl at master · JuliaLang/julia)。

以上の知識を利用すると変なリテラルを作れるよんという話。

草リテラル

文章に草を生やします。

macro 草_str(text)
    sentences = split(text, r"[、。]")
    string(join(sentences, "ｗｗｗ"), "ｗｗｗ")
end

例

julia> 草"笑った、面白い。"
笑ったｗｗｗ面白いｗｗｗｗｗｗ

突然の死リテラル

なんか突然死にます。

macro 凸_str(text)
    len = length(text)
    upper = join(fill("人", (2 + len)))
    lower = join(fill("Y", (2 + len)), "^")

    result = string(
                "＿$(upper)＿\n",
                "＞　$(text)　＜\n",
                "￣$(lower)￣"
                )
    result
end

例

julia> 凸"突然の死"
＿人人人人人人＿
＞　突然の死　＜
￣Y^Y^Y^Y^Y^Y￣

モールス信号リテラル

これは日本語関係ないですが思いついたので載せとく。アルファベットをモールス信号に変換してくれる。

macro m_str(text)
    # コピペ
    # http://svn.python.org/projects/python/trunk/Demo/scripts/morse.py
    morsetab = {
        'A' => ".-",              'a' => ".-",
        'B' => "-...",            'b' => "-...",
        'C' => "-.-.",            'c' => "-.-.",
        'D' => "-..",             'd' => "-..",
        'E' => ".",               'e' => ".",
        'F' => "..-.",            'f' => "..-.",
        'G' => "--.",             'g' => "--.",
        'H' => "....",            'h' => "....",
        'I' => "..",              'i' => "..",
        'J' => ".---",            'j' => ".---",
        'K' => "-.-",             'k' => "-.-",
        'L' => ".-..",            'l' => ".-..",
        'M' => "--",              'm' => "--",
        'N' => "-.",              'n' => "-.",
        'O' => "---",             'o' => "---",
        'P' => ".--.",            'p' => ".--.",
        'Q' => "--.-",            'q' => "--.-",
        'R' => ".-.",             'r' => ".-.",
        'S' => "...",             's' => "...",
        'T' => "-",               't' => "-",
        'U' => "..-",             'u' => "..-",
        'V' => "...-",            'v' => "...-",
        'W' => ".--",             'w' => ".--",
        'X' => "-..-",            'x' => "-..-",
        'Y' => "-.--",            'y' => "-.--",
        'Z' => "--..",            'z' => "--..",
        '0' => "-----",           ',' => "--..--",
        '1' => ".----",           '.' => ".-.-.-",
        '2' => "..---",           '?' => "..--..",
        '3' => "...--",           ';' => "-.-.-.",
        '4' => "....-",           ':' => "---...",
        '5' => ".....",           '"' => ".----.",
        '6' => "-....",           '-' => "-....-",
        '7' => "--...",           '/' => "-..-.",
        '8' => "---..",           '(' => "-.--.-",
        '9' => "----.",           ')' => "-.--.-",
        ' ' => " ",               '_' => "..--.-"
    } 
    join(map(x -> morsetab[x], collect(text)), " ")
end

例

julia> m"Hello, World."
.... . .-.. .-.. --- --..--   .-- --- .-. .-.. -.. .-.-.-

マクロじゃなきゃダメなんですか？関数じゃダメですか？

実用性のなさは置いといて、マクロはコンパイル時に解決されるので実行は速くなります。

おまけ：寿マクロ

もはや文字列リテラル関係ないし何の意味もないが小ネタ放出ということで。

function を寿にできると嬉しいらしい。

macro 寿(x)
    eval(x)
end

@寿 f(x) = x # 関数が定義できる。めでたい。

反省

しかしネタにしても数少ないな。草リテラルと同じ語尾変える系ならいくらでも作れるけど、プログラミングっぽい実用新案は思いつかないから仕方ない。本気でやらないとつまらんよこういうのは。

2014-03-26

Julia で関数合成

Julia で簡単なファイル処理をしていたら、ふと関数合成ができないかと考えた。

julia> split(strip(line))

julia> *(split, strip)(line) # こんな感じにしたい

Julia は第一級関数をもち多重ディスパッチを利用できる言語だ。なので関数合成でも簡潔かつ比較的奇麗に実装できる。

julia> *(f::Function, g::Function) = x -> f(g(x))
* (generic function with 127 methods)

julia> (split * strip)("Hello, world!\n") 
2-element Array{String,1}:
 "Hello,"
 "world!"

便利ですね。これくらい誰でも思いつきそうだが、標準ライブラリには見当たらない。

えー。多重ディスパッチの威力を見せつけるいい機会なのに。

そう思いつつググってみると、同じことを考える人はとうの昔にいたし、作者も常に念頭に置いているようだった。当たり前ですな。

remove * for function composition? · Issue #2485 · JuliaLang/julia

下手の考え休むに似たり。理由はリンク先で指摘されているが、標準に入っていない理由は端的に遅いからだそう。

最大/最小値関数周りのリネームに関する議論 #7327

Git を Libgit2 に置き換える準備が整いつつある？ #7339

関数が属しているモジュールを取るリフレクション #7322

cumsum のパフォーマンスが悪い #7342

インストール

事前準備

使ってみる

高度な使い方

おまけ：srt ファイルの作り方

goto マクロがマージされた #5699

float(AbstractArray) と complex(AbstractArray) のパフォーマンス改善 #7308

staged な関数 (メソッド) に関する議論 #7311

Literate Julia?

Grisu アルゴリズムの実装 #7291

Dates.jl が Base にマージされた #7285

草リテラル

突然の死リテラル

モールス信号リテラル

マクロじゃなきゃダメなんですか？ 関数じゃダメですか？

おまけ：寿マクロ

反省

`cumsum` のパフォーマンスが悪い #7342

`staged` な関数 (メソッド) に関する議論 #7311

マクロじゃなきゃダメなんですか？関数じゃダメですか？