ちょっとしたことから、アルゴリズムの復習をしようと思い立ち、O’Reillyから出ている『入門データ構造とアルゴリズム』を読み始めました。しかし、この本はしょっぱなから誤植やミスが目立つため、豊富なドリルは役に立ちそうですが、心もとない雰囲気があります。
それでも我慢して冒頭を読み進めていたのですが、突然 分割統治法のマスター定理 なるものが出てきて、特に式の説明もなく、こんなもの覚えられるか！とさじを投げました。

尚、マスター定理というのは、再帰処理によって問題を解くアルゴリズム(たとえばマージソート)の計算量を(場合によって)求めることができる定理で、計算が容易です。
日本語で検索をしてもなかなか解説している資料に出会わないのですが、英Wikipediaに簡単な説明があります。

Master theorem - Wikipedia, the free encyclopedia

この説明を読むと、CLRS本として知られるMITプレス発行の『Introduction to Algorithms』によって知られるようになった定理だと書いてあります。
この本自体は以前手に入れたまま放置していたのですが、せっかくなので該当箇所を読んでみることにしました。が、該当箇所を読むだけではいまいち理解できません。

もしかして、ここは本当に覚えるべきところなのか。

気になってきたので、この本を教科書として採用しているMITの講義録を視聴してみることにしました。

MITの講義を視聴する

2005年に行われた講義がオンライン学習用に公開されています。

Introduction to Algorithms (SMA 5503) | Electrical Engineering and Computer Science | MIT OpenCourseWare

第1回の講義では、概要説明がしばらく続いたあとで、アルゴリズムとは何かという説明があって、その後挿入ソートとマージソートを具体例として計算量の概念を紹介しています。プログラマならこのあたりは余裕ですね。
(余談ですが、演習課題はまず自力で考え、30分以上悩んでも解答がわからなければ、時間の無駄だから友達に聞こうっていうアドバイスが、さすが合理的だなと思いました。あとは、何をしたら単位がもらえないとか、そういう話をきちんとするのも良いですね。)

マスター定理は第2回の講義で扱われています。この先生は天才肌っぽい感じがします(1981年生まれで教授!)が、本人も言及している通りハイスピードで説明が進みます。でも、ついてこれなかったらすぐ聞いてね！ペース落とすから！っていうのが優しい配慮ですね。

この2回の講義を通しで聴いて、ようやくマスター定理の言わんとするところが見えてきました。これは暗記するような性質のものではなく、意味を理解することが大切でした。

資料も充実

授業の英語についていけなくても、きちんとレジュメが配信されています。下の資料は第2回の分ですが、ずいぶんきちんと書かれていて、復習用(フォローアップ)に最適です。

Asymptotic Notation and Recurrences - lec2.pdf

自分が通っていた大学もノートは取らなくて済むようにレジュメが配られることが多かったですが、こんなにわかりやすくなかったですね。。これだけ用意してもらえるなら、授業は先生の一挙手一投足に集中することができますね。

MITは厳しい

これだけ見ると、さすが世界屈指の大学だけあって充実してるなという印象です。が、その分求められるものも結構シビアです。この講義は1週間に2回ずつ、各1.5時間で行われ、だいたい1週間に1回、以下のような宿題が課せられます。

ps1.pdf

この中でProblemというのが提出課題でExerciseは自主課題ですが、Problemを提出しないと、期末成績がどんどん減点されていきます。課題自体も結構多いのに、問題自体もなかなか味のある内容です。
Exercice 1-3. はその前の課題に証明が書いてあるのに気づかず、個人的にかなり苦戦しました。。

ふと、第1回の講義でlogが絡んだ総和の計算が出てきて、数学はPrerequisitesだからね！と先生が冗談めかして言っているのを思い出しました。確かにシラバスにもはっきり書いてあります。要求がはっきりしているのも、アメリカらしいと感じます。

まとめ

ふとアルゴリズムの復習をしようと思い立った結果、気がついたらMITの講義を2回聞き、課題を解いていました。
世間ではCLRS本を輪読したり、独学している方もいるようですが、もしかすると講義録に沿って学習を進めていくことで、割合短期間に終わらせることができるかもしれません。

個人的には冒頭に言及していたO’Reillyのアルゴリズムの本がコンパクトなので、あくまでそちらをメインに据えたいなと考えていますが、もしかしたらMIT講義録に移行するかもしれません。

飽きっぽくなかなか大きなことは続かない性格ですが、2016年は継続力も磨ければなぁと思います。

2016年が明けました。今年もよろしくお願いします。

さて、Arch Linux上でpdfを閲覧する方法です。他のディストロ同様に、好みのpdfビューワをインストールすれば良いのですが、

• 日本語のpdfをきちんと表示する
• 英単語から辞書を引く

という点について、メモを残しておきます。

日本語pdfをきちんと表示する

Archをインストールして、いくつか日本語フォントも入れて、GUIを整備して、ようやくpdfを読もうと思った時、大抵は文字化けしたpdfが表示されるという冴えない結果になります。
人によってはいわゆる豆腐文字が表示されたり、あるいは単純に日本語が空白に置き換わってしまうケースもあるでしょう。

Linuxで用いられるpdfビューワの多くが内部的な処理にPopplerを利用しています。自分が使っているAtrilも依存パッケージにpoppler-glibを含んでいます。Popplerを利用しているpdfビューワでは、フォントが埋め込まれているようなケースで日本語を表示するにはpoppler-dataパッケージを入れる必要があります。

1

# pacman -S poppler-data

インストール後pdfを表示すると、正しく日本語が表示されるかと思います。

英単語から辞書を引きたい

OSXなどの標準的なpdfビューワーやKindleアプリなどでは、英単語を選択するだけで英英辞書などが意味をポップアップ表示してくれて、便利ですね。

これと似たような挙動を実現する辞書ソフトとして、複数の辞書フォーマットに対応しているGoldenDictを導入します。

1

# pacman -S goldendict

起動後、以下の設定を行います。

• 編集->辞書メニューから辞書ファイルの置き場を指定し、再スキャンを行います。
• 編集->環境設定メニューを開きます。
  • インターフェイスタブでダブルクリックでの翻訳を有効にします。
  • スキャンポップアップタブを開き、スキャンポップアップ機能を有効にします。特定のキーを押しているときのみポップアップさせることもできます。

肝心の辞書ファイルは

• Babylon(.BGL)
• StarDict(.ifo, .dict, .idx, .syn)
• Dictd(.index, .dz)
• Lingvo(.dsl, .lsa, .dat)

といったLinuxでよく使われている辞書ツールの辞書形式に対応しています。
また、オンライン辞書を利用することも可能です。(初期設定のものはクエリが古くて使えないようですが)

例えばBabylonで利用可能なフリー辞書は以下からダウンロード可能です。

Dictionaries for every subject - free of charge

専門的な分野の辞書や、昔のWebster英大辞典なども(著作権が切れているため)利用できます。もし手持ちのデジタル辞書があれば、それらも利用できるでしょう。

MacBook AirでArch Linuxを動かしていると、OSXの時の画面と比べて色合いが異なる印象を受けます。これはデフォルトのカラープロファイルがMacで使っていたものと異なるためです。

自分の環境では、やけに画面が青白く、バックライトを弱くしても目に刺さるような感じがありました。逆に言えば、それだけMacのいわゆる尿液晶に慣れてしまっているのかもしれません。
一応、ブルーライト対策としてはOSXで使用しているf.luxに似たアプリとして、Redshiftを導入済みですが、どうも違和感が拭えません。

そこで、OSXのカラープロファイルをArch上でも再現することにしました。

基本的にはMacBook - ArchWikiのカラープロファイルの項を参考にしています。

OSXのカラープロファイルを取得する

OSXを起動し、/Library/ColorSync/Profiles/Displays/下にあるカラープロファイル(*.icc)をDropBoxか何かのArchからもアクセスできる場所にコピーします。

xcalibの導入

AURとして提供されているxcalibをインストールします。

1

$ yaourt -S xcalib

試しにカラープロファイルを変更してみましょう。

1

$ xcalib <path>/your.icc

画面の色合いが変化すれば正しく動作しています。

自動起動用スクリプト

先ほどのコマンドを毎回ログイン毎に実行したくはないので、自動的に実行されるようにします。お使いのGUI環境次第ですが、Enlightenmentの場合は以下のようにできます。

shファイルの作成

適当な名前をつけて、スクリプトファイルを作成します。

1
2

#!/bin/sh
xcalib <path>/your.icc

これを実行可能にします。

1

$ chmod +x <path>/your_script.sh

スタートアップアプリケーションとして登録

次に、これをスタートアップアプリケーションとして登録します。
Enlightenmentのメニューから設定->設定パネル->アプリケーション->Personal Application Lanchersを選択します。
追加ボタンを押し、先ほどのスクリプトファイルに適当な名前を付けて登録します。

これで、次回以降のログイン時に、Macのカラープロファイルが適用された状態になります。

ちょっとした違いですが、感覚的にはだいぶ見やすくなった気がします。

前回の続きです。
今回はFirefoxやGoogle Chromeのプロファイル以外のキャッシュディレクトリもRAM上に置くようにします。

必要なことは簡単で、キャッシュディレクトリをProfile-sync-daemonの管理下に移動し、元の場所にシンボリックリンクを貼るだけです。

Firefox:

1
2

$ mv $HOME/.cache/mozilla/firefox/<profile> $HOME/.mozilla/firefox/<profile>/cache
$ ln -s $HOME/.mozilla/firefox/<profile>/cache $HOME/.cache/mozilla/firefox/<profile>

Google Chrome:

1
2

$ mv $HOME/.cache/google-chrome/Default $HOME/.config/google-chrome/cache
$ ln -s $HOME/.config/google-chrome/cache $HOME/.cache/google-chrome/Default

Profile-sync-daemonでの管理フォルダの場所がわからない場合は

1

$ psd parse

から、sync targetの項目で確認できます。

MacBook Air(mid-2012)にArch Linuxを載せて(デュアルブート)動かしています。
FirefoxやChromeを使う際に、ブラウザキャッシュの頻繁な書き込みがSSDの寿命を短くするといった言及をいくつか見たので、対応することにしました。

以下の記事と、Arch Wikiの該当ページを参考に、現時点での最新方法を残しておきます。

Arch Linux を SSD に移した時のメモ | Basic Werk

上記記事で言及されている/etc/fstabの設定についてはArch Linux導入時に済ませているので、割愛します。Arch Wikiの導入ガイドに従っていれば済んでいるかと思います。

profile-sync-daemon (AUR)

ブラウザキャッシュやプロファイルをRAM上で管理するためのサービスを提供します。内部的にはrsyncを利用して同期を取るようです。

Profile-sync-daemon - ArchWiki

AURパッケージなのでyaourtの利用を推奨します。

1

$ yaourt -S profile-sync-daemon

Wikiでは/etc/psd.confを設定ファイルとして利用すると書かれていますが、現時点(v6.20)では既にこの方法は陳腐化しています。代わりにユーザのホームフォルダで設定ファイルを管理するようになっています。

1

$ profile-sync-daemon parse

を実行すると、設定ファイルがどこに置かれたかが表示されますので、そのファイルを編集します。デフォルトでは$HOME/.config/psd/psd.confあたりになるようです。

自分の環境ではfirefox(メイン)とgoogle-chrome(AmazonプライムやYoutube用)を使っているので、以下のように設定しています。

1

BROWSERS="firefox google-chrome"

また、可能であればoverlayfsを有効にすることで、RAMの使用量を減らし、同期を高速化できます。(事前準備については後述)

1

USE_OVERLAYFS="yes"

設定ファイルを更新後、サービスを起動します。次回再起動時以降に、自動起動できるようにします。

1
2

$ systemctl --user start psd.service
$ systemctl --user enable psd.service

overlayfsの設定

Linuxのカーネルが3.18.0以降ではoverlayfsが利用可能です。

1

$ uname -r

でバージョンの確認ができます。

管理者権限で

1

# modprobe overlay

してoverlayモジュールをロードします。環境によってはoverlayfsの場合もあるようです。

起動時に読み込ませるためには/etc/modules-load.d/overlay.conf(名前は自由)を作成し、読み込ませたいモジュール名としてoverlayを記述します。

1
2

# 起動時に読み込むモジュール名のみ指定
overlay

overlayfsが有効にならない

上記の設定などが済んだあとで、正しく設定がされているかどうかを確認してみましょう。

1
2
3
4
5

$ psd parse
 ERROR! To use overlayfs mode, <username> needs sudo access to /usr/bin/psd-overlay-helper

 Add the following line to the end of /etc/sudoers to enable this functionality:
   <username> ALL=(ALL) NOPASSWD: /usr/bin/psd-overlay-helper

権限周りで怒られていますね。visudoして、最下行を追加します。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

$ psd parse
Profile-sync-daemon v6.20 on Arch Linux

 Systemd service is currently active.
 Systemd resync-timer is currently active.
 Overlayfs v23 is currently active.

Psd will manage the following per /home/<username>/.config/psd/psd.conf:

 browser/psname:  firefox/firefox
 owner/group id:  <username>/100
 sync target:     /home/<username>/.mozilla/firefox/ffzva242.default
 tmpfs dir:       /run/user/1000/<username>-firefox-ffzva242.default
 profile size:    193M
 overlayfs size:
 recovery dirs:   none

 browser/psname:  google-chrome/chrome
 owner/group id:  <username>/100
 sync target:     /home/<username>/.config/google-chrome
 tmpfs dir:       /run/user/1000/<username>-google-chrome
 profile size:    77M
 overlayfs size:
 recovery dirs:   none

今度は正しく動作していることが確認できました。

実際には、各ブラウザはプロファイル以外のキャッシュも管理しているので、これらもRAM上に移すと良いでしょう。
長くなってきたので、この話題は次回へまわします。

Programming ElixirでHttpoisonを使う例が古かったのでメモ。

mix.exsを修正する。

1
2
3
4
5

defp deps do
  [
    { :httpoison, "~> 0.8.0" }
  ]
end

issues/github_issues.exsも修正する

1
2
3

def handle_response({:ok, %HTTPoison.Response{status_code: 200, body: body}}), do: { :ok, body }
def handle_response({:ok, %HTTPoison.Response{status_code: ___, body: body}}), do: { :error, body }
def handle_response({:error, %HTTPoison.Error{reason: reason}}), do: { :error, reason }

余談

尚、PragProgのサポートサイトには#77904に該当するエラッタが登録されており、
mix.exsにて

1
2
3
4
5

defp deps do
  [
    { :httpoison, "~> 0.4.0" }
  ]
end

とすればissues/github_issues.exs側を修正せずに動くとあります。

cf. The Pragmatic Bookshelf | Errata for Programming Elixir

が、手元環境(Elixir 1.1.1, OTP 18.0)だと依存パッケージのhackneyがコンパイルできなくなる問題があったため諦めました。指示されるコマンドを実行しても解決せず。

1
2
3
4
5
6
7

[3100]$ iex -S mix
Erlang/OTP 18 [erts-7.1] [source] [64-bit] [smp:8:8] [async-threads:10] [hipe] [kernel-poll:false]

==> hackney (compile)
ERROR: OTP release 18 does not match required regex R15|R16|17
ERROR: compile failed while processing /home/3100/learn/elixir/issues/deps/hackney: rebar_abort
** (Mix) Could not compile dependency :hackney, "/home/3100/.mix/rebar" command failed. You can recompile this dependency with "mix deps.compile hackney", update it with "mix deps.update hackney" or clean it with "mix deps.clean hackney"

どうも下のイシューと同じ現象のように見えます。

cf. (Mix) Could not compile dependency idna, /root/.mix/rebar command failed. If you want to recompile this dependency, please run: mix deps.compile idna · Issue #3857 · elixir-lang/elixir

ElixirのI18N対応について。すぐ出てくるライブラリは下の2つあたり。

chrismccord/linguist
https://github.com/chrismccord/linguist

elixir-lang/gettext
https://github.com/elixir-lang/gettext

前者はProgramming Phoenixという来年1月発売予定の本の執筆者が作ってるライブラリで、
Rubyのi18nに近い使い方ができそうです。辞書ファイルはyamlで定義するやつ。

後者は古き良きgettext(cf. Wikipedia)といった感じです。こちらは.poファイルという形式の辞書ファイルを利用します。
今回はあるライブラリへの提案をするという背景もあり、gettextを試してみました。
Phoenix製Webアプリの開発だったら前者を試すかも。

導入

mixを利用している前提です。mix.exsにgettextを追加します。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

defp deps do
  [
    {:gettext, "~> 0.7"}
  ]
end

# アプリケーション起動前に:getetxtが立ち上がるようにする。必須
def application do
  [
    applications: [:gettext, :logger]
  ]
end

# オプション: 指定しておくと`.po`ファイルが更新されるたびにコンパイルされます。
def project do
  [
    compilers: [:gettext] ++ Mix.compilers
  ]
end

モジュールの定義

1
2
3

defmodule YourLibraryName.Gettext do
  use Gettext, otp_app: :your_library_name
end

辞書ファイルの定義

例えば日本語(ja_JP)に対応する辞書ファイル(.po)の初期パスは
priv/gettext/ja_JP/LC_MESSAGES/default.poとなります。

.poファイルは以下のような感じに記述します。

1

msgid "Hello, gettext"
msgstr "こんにちは、ゲットテクスト"

msgid "Hello, %{name}"
msgstr "こんにちは、%{name}"

利用方法

これを利用するには、ソースコード内で

1
2
3
4

import YourLibraryName.Gettext

def hello_gettext, do: gettext "Hello, gettext"
def hello(name), do: gettext "Hello, %{name}", name: name

のようにgettextを呼び出します。
他にも、単数/複数への対応といった英語圏ぽい機能もありますので、気になる方は以下をどうぞ。

Gettext – gettext v0.7.0

ロケールについて

デフォルトのロケールはconfig/config.exsあたりに記述するのが良さそうです。

1

config :your_library_name, YourLibraryName.Gettext, default_locale: "ja_JP"

また、コード中でロケールを変更することもできます。

1
2
3
4
5

# 取得
locale = Gettext.get_locale(YourLibraryName.Gettext)

# 設定
old_locale = Gettext.put_locale(YourLibraryName.Gettext, "en")

おまけ1: 既存のコードから辞書ファイルの雛形を作る

例えば既にあるライブラリに対してI18N対応を行う場合などを考えてみます。

まずは既存コードのリテラル文字列などをすべてgettext関数経由で呼ぶように変更します。

1
2
3
4
5

# "Hello, Elixir"
gettext "Hello, Elixir"

# "Hello, #{name}"
gettext "Hello, %{name}", name: name

次に、mixに追加されたタスクを実行します。

1

$ mix gettext.extract

これでpriv/gettext/default.potというテンプレートファイルが生成されます。

おまけ2: 気になる速度について

Gettextは可能な処理はランタイム時ではなくコンパイル時に行うように作られているそうです。
Elixirのコンパイル時間についてGettext開発者がElixirConf 2015で話した内容が閲覧できますので
興味のある方は聴いてみてください。

まとめ

駆け足ですが、ざっくりとElixirでのI18N対応方法について見ていきました。
ちょっとしたライブラリならgettextの仕組みで十分対応できそうですね。

実際に、これを利用してelixircnx/comeoninというライブラリをI18N化しました。
comeoninはパスワードのダイジェストを生成するためのライブラリで、簡易的なバリデーションのような仕組みを備えています。
例えばパスワード強度が足りない時に、I18N化されたメッセージが得られるという感じです。

元々英語だったのですが、日本語辞書を皮切りに、フランス語やドイツ語が追加されているようです。興味がある方は使ってみてください。

あと、Phoenix本、いい感じです。comeoninもこの本で知りました。β版ですが既に販売していますよ。

The Pragmatic Bookshelf | Programming Phoenix

PadrinoアプリでActiveRecordを介してMySQLに接続しているのですが
これをCircleCIで用意しているMySQLにつなげる方法のメモ。

基本設定となるcircle.ymlは以下の様になっています。

1

machine:
  timezone:
    Asia/Tokyo
  ruby:
    version:
      2.2.0
  environment:
    RACK_ENV: test
  services:
    - mysql
dependencies:
  override:
    - bundle install
database:
  override:
    - mv config/database.yml.ci config/database.yml
    - bundle exec rake ar:create ar:schema:load
test:
  post:
    - bundle exec rake test

• mysqlを利用させてもらう
• 各種bundle系コマンドを指定

といった部分は特に説明がいらなそうですが
データベース用ymlファイル(後述)をCircleCI用に用意しておいて、CIを回す際に置き換えるのがポイントです。

続いて、config/database.rbの設定。
必要な設定ではありませんが、Railsなどと融通しやすくするためにconfig/database.ymlを読む設定にしています。

1

ActiveRecord::Base.configurations = YAML.load(ERB.new(File.read(Padrino.root('config', 'database.yml'))).result).with_indifferent_access

cf. Padrinoでアプリ作る時もdatabase.ymlを作った方がよかった - くりにっき

最後に、config/database.yml.ci。CircleCIが用意してくれるMySQL環境への接続は以下の設定でOKです。

1

test:
  adapter: mysql2
  encoding: utf8
  database: app_test
  pool: 5
  username:
  password:

ここまでの設定で、無事にCircleCIでテストコードが実行されるようになりました。

毎回よくわからなくなるPythonの導入方法。
あまり考えなくても良いかもしれないけど、複数バージョンを使い分ける可能性を考慮すると
pyenvを入れるのが簡単かも。OSXならhomebrewで簡単。

1
2
3

$ brew install pyenv
$ pyenv --version
pyenv 20151006

shimsにパスを追加するやつ。

1
2
3

$ echo 'export PYENV_ROOT="$HOME/.pyenv"' >> ~/.zshenv
$ echo 'export PATH="$PYENV_ROOT/bin:$PATH"' >> ~/.zshenv
$ echo 'if which pyenv > /dev/null; then eval "$(pyenv init -)"; fi' >> ~/.zshenv

pyenv install -lとして表示された最新のCPythonを導入する。

1
2
3
4
5

$ pyenv install 3.5.0
Downloading Python-3.5.0.tgz...
-> https://yyuu.github.io/pythons/584e3d5a02692ca52fce505e68ecd77248a6f2c99adf9db144a39087336b0fe0
    Installing Python-3.5.0...
    Installed Python-3.5.0 to /Users/zero/.pyenv/versions/3.5.0

1
2
3

$ pyenv global 3.5.0
$ python --versions
Python 2.7.9

。。。。whichしたらhomebrew経由で昔いれたPythonが優先されてた。

1
2
3

$ brew uninstall python
$ python --versions
Python 3.5.0

無事完了。基本的にrbenvと似たAPIぽい。

久々にbrew updateを実行した際に

1
2
3
4
5
6
7
8
9
10
11

brew update
Error: uninitialized constant Formulary::HOMEBREW_CORE_FORMULA_REGEX
Please report this bug:
    https://git.io/brew-troubleshooting
    /usr/local/Library/Homebrew/formulary.rb:260:in `loader_for'
    /usr/local/Library/Homebrew/formulary.rb:205:in `factory'
    /usr/local/Library/Homebrew/cmd/update.rb:173:in `block in report'
    /usr/local/Library/Homebrew/cmd/update.rb:159:in `each_line'
    /usr/local/Library/Homebrew/cmd/update.rb:159:in `report'
    /usr/local/Library/Homebrew/cmd/update.rb:24:in `update'
    /usr/local/Library/brew.rb:140:in `<main>'

のようなエラーが出てしまった。

結論から言えば、もう一度brew updateすると無事処理が完了した。

cf. Error: uninitialized constant Formulary::HOMEBREW_CORE_FORMULA_REGEX · Issue #42553 · Homebrew/homebrew · GitHub