Cool Badges for GitHub Projects

GitHubで貼っておきたいバッジあれこれ

 

ライセンス表示

• shields.io で自分で作る
• 上記の例は license - MIT - blue で指定
• リンク先はChooseALicense.com を指定するとよい

Read the Docs

• Read the Docs
• ドキュメント生成ツール Sphinx のホスティングサービス
• 完全無料
• 参考
  • ReadTheDocsでSphinxホスティングは磐石（になる予定） - YAMAGUCHI::weblog
  • ae35 / docs / ソース / readthdocs.rst — Bitbucket

Travis CI

• Travis CI
• ユニットテストのホスティングサービス
• 対応言語
  • C, C++, Clojure, Erlang, Go, Groovy, Haskell, Java, JavaScript & Node.js, Objective-C, Perl, PHP, Python, Ruby, Scala
• オープンソースであれば無料、それ以外は月額 $129〜 の有料プランあり => Travis CI: Plans

Coveralls

• Coveralls - Test Coverage History & Statistics
• コードカバレッジ可視化のホスティングサービス
• 対応言語
  • C, C++, Go, Haskell, Java, JavaScript & Node.js, Lua, PHP, Python, Ruby, Scala, OCaml
• オープンソースであれば無料、それ以外は月額 $4.99〜 => Coveralls - Pricing

Scrutinizer

• Scrutinizer
• ソースコードの静的解析
• 対応言語
  • PHP, Python, Ruby (Java, Scala は検討中の模様)
• トライアル期間14日は無料、その後、月額 $19〜 => Plans & Pricing

 

 

Related Posts

• mog project: Integrating Your Python Projects with Travis-CI and Coveralls

Scala: error: forward reference extends over definition of value

Scala: Stream の再帰的な定義でエラー

 

自分自身を参照するような Stream を定義したら、エラーが出た。

 

エラーが発生する例

1 2 3 4 5 6 7

scala> def f(x: Int) = {      |   val xs: Stream[Int] = x #:: xs.map(_ + 1)      |   xs.tail      | } :17: error: forward reference extends over definition of value xs          val xs: Stream[Int] = x #:: xs.map(_ + 1)                                      ^

 

対応方法

lazy val にすれば OK。

1 2 3 4 5 6 7 8

scala> def f(x: Int) = {      |   lazy val xs: Stream[Int] = x #:: xs.map(_ + 1)      |   xs.tail      | } f: (x: Int)scala.collection.immutable.Stream[Int]   scala> f(3).take(10).toList res8: List[Int] = List(4, 5, 6, 7, 8, 9, 10, 11, 12, 13)

 

 

References

• scala - When does a Stream need to be lazy? - Stack Overflow

AdTech x Scala x Performance Tuning

アドテク×Scala meetup で登壇してきました

 

ありがたいことに、ひょんなことから声を掛けていただき、去る 11月20日
サイバーエージェント社で行われた『アドテク×Scala meetup』で少しだけお話をさせていただきました。

 

tl;dr

• イベントページ => アドテク×Scala meetup - connpass
• CA社イベントレポート => アドテク×Scala勉強会を開催しました！ | AdTech Studio Tech Blog
• スライド
• アドテクを支えるScala - Ad Generationの場合
  
  2014 11-20 adtechxscala-meetup from Yoshihiro Nomura
• Dynalystが広告配信で使っている技術(Spray×Akka×Kamon×Zabbix)
  
  アドテク×Scala @Dynalyst from Sangwon Han
• アドテク×Scala×パフォーマンスチューニング
  
  アドテク×Scala×パフォーマンスチューニング from Yosuke Mizutani
• 軽量言語メインの 文系エンジニアだった自分が Scalaのシステム開発に携わることになった経緯
  
  軽量言語メインの 文系エンジニアだった自分が Scalaのシステム開発に携わることになった経緯 @shigemk2 from Michihito Shigemura

 

感想

• アドテクを支えるScala - Ad Generationの場合
• アドジェネさん、Spray/Actor ベースで動いているのかー。
• Dynalystが広告配信で使っている技術(Spray×Akka×Kamon×Zabbix)
• 公式ドキュメントをきちんと読む事、当たり前だけどとても大事。
• scalaのFutureの並列に実行されない書き方とされる書き方 - Qiita
  TLで話題になっていた。どちらが適しているかは用途によると思うけど。
• kamon-io/Kamon のことは知らなかった。
• 抽象的な Future | eed3si9n Abstract Future って何だ? 要勉強。
• アドテク×Scala×パフォーマンスチューニング
• 緊張しました。 200人もの大人数の前で話したのは初めてです。
• インフラ目線の内容も織り交ぜ、自分自身が普段心がけていることをまとめました。
• アドテク以外の開発でも参考になる部分はあると思います。
• 軽量言語メインの 文系エンジニアだった自分が Scalaのシステム開発に携わることになった経緯
• 馬の人だー。
• 座談会
• OE(@OE_uia)さん の貫禄の回し。
• あのベテラン司会者のような落ち着きは、どこから生まれるのだろうか。
• ご質問くださった皆様、どうもありがとうございました。

 

全体を通して



• 与えられた発表時間はプレゼンに集中し、後で質問を受け付けるというスタイル。
  発表者側としてはとてもやりやすかった。
• Spray/Actor ベースのシステム、十分に枯れてきた感がある。
  早いところプロダクションで作ってみたい。
• 無料で振る舞われたビール & 寿司に感動。さすがサイバーエージェントさんや。
  (こちらはスタッフ & 登壇者専用) 
   
• 人気沸騰中の Scala ガール (AdTech Studio Girls Blog) に会えました！
• 当日だけでなくイベントの準備に奔走されたCA社の皆様、当日ご来場くださった皆様、
  本当にありがとうございました！
  (こちらは開場前の準備風景)
   

 

Integrating Your Python Projects with Travis-CI and Coveralls

Python: GitHub 上のプロジェクトを Travis-CI, Coveralls と連携する

 

GitHub でパブリックなプロジェクトを作ったら、無料でCI環境とカバレッジ環境を手に入れることが可能。
これを利用しない手はない。

以下、具体例として一つの小さなプロジェクトを作りながら説明する。

 

Step 1: GitHub リポジトリ作成

setup.py で管理された Python プロジェクトを作る。

ディレクトリ構成

構成の一例。

. ├── .gitignore ├── .travis.yml ├── LICENSE ├── README.md ├── setup.py ├── src │   └── yourpackage │       ├── __init__.py │       └── yourmodule.py └── tests     ├── __init__.py     └── test_yourmodule.py

 

アプリケーション/ライブラリの実装

ソースコードは src ディレクトリ配下にまとめる。

ここでは例として yourpackage というパッケージと、適当な数値計算を行うyour_function という関数を用意した。

__init__.py にインポート対象(クラス/関数)を書くのを忘れずに。

src/__init__.py

1	from .yourmodule import your_function

src/yourmodule.py

1 2 3 4 5 6 7 8 9 10 11 12 13

def your_function(x):     ret = 0     if x % 2:         ret |= 1     if x < 10000:         ret |= 2     if x == 10000:         ret |= 4     if x % 9 == 7:         ret |= 8     if x / 2000 == 6:         ret |= 16     return ret

テストコードの実装

テストコードは tests ディレクトリ配下にまとめる。

tests 自体もパッケージとして管理したほうが利便性がよいので、空の __init__.py を作る。
そして以下のようなテストコードを書いた。

tests/test_yourmodule.py

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

import unittest from yourpackage import your_function     class TestYourModule(unittest.TestCase):     def setUp(self):         pass       def test_your_function_zero(self):         self.assertEqual(your_function(0), 2)       def test_your_function_odd(self):         self.assertEqual(your_function(1), 3)       def test_your_function_greater_than_10000(self):         self.assertEqual(your_function(10006), 8)       def test_your_function_12345(self):         self.assertEqual(your_function(12345), 17)

カバレッジ結果をわかりやすくするため、あえてカバレッジ率は 100% にならないようにしている。

setup.py セットアップスクリプトの記述

今回は必要ないが、他の Python ライブラリに依存があればここで記述する。

setup.py

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

from setuptools import setup, find_packages   setup(     name='your-project-name',     version='0.0.1',     description='description for your project',     author='your name',     author_email='your email address',     url='your url',     install_requires=[         # list your dependencies     ],     tests_require=[         # dependencies for unit testing     ],     package_dir={'': 'src'},     packages=find_packages('src'),     include_package_data=True,     test_suite='tests', )

テストの実行

setup.py を使ってテストを実行する。以下のように表示されれば OK。

$ python ./setup.py test running test running egg_info creating src/your_project_name.egg-info writing src/your_project_name.egg-info/PKG-INFO writing top-level names to src/your_project_name.egg-info/top_level.txt writing dependency_links to src/your_project_name.egg-info/dependency_links.txt writing manifest file 'src/your_project_name.egg-info/SOURCES.txt' reading manifest file 'src/your_project_name.egg-info/SOURCES.txt' writing manifest file 'src/your_project_name.egg-info/SOURCES.txt' running build_ext test_your_function_12345 (tests.test_yourmodule.TestYourModule) ... ok test_your_function_greater_than_10000 (tests.test_yourmodule.TestYourModule) ... ok test_your_function_odd (tests.test_yourmodule.TestYourModule) ... ok test_your_function_zero (tests.test_yourmodule.TestYourModule) ... ok   ---------------------------------------------------------------------- Ran 4 tests in 0.000s   OK

ここまでできたら、一旦 GitHub に公開リポジトリとして push する。

 

Step 2: Travis-CI の登録

• https://travis-ci.org/ にアクセス
• メニュー右上の Sign in with GitHub をクリックし、GitHub OpenID認証を承認
• ログイン後、アカウント名 -> Accounts -> Repositories の画面で
  連携したいプロジェクトをチェック・オン
  

 

Step 3: Coveralls の登録

• https://coveralls.io/ にアクセス
• メニュー右上の SIGN IN ボタンをクリックし、GitHub OpenID認証を承認
• ログイン後、REPOS -> ADD REPOS ボタンをクリック
• リストに対象リポジトリが表示されていなかったら、画面上部の SYNC GITHUB REPOS ボタンをクリック
• 連携したいプロジェクトをチェック・オン
  

 

Step 4: .travis.yml の設置

プロジェクトルートに、.travis.yml という名前の設定ファイルを作れば
Travis-CI がそのファイルを読み取ってテストを走らせてくれる。

こちら (Travis CI: Building a Python Project) を参考に、以下のような内容で記述。

1 2 3 4 5 6 7 8 9 10 11

--- language: python python:   - "2.6"   - "2.7" install:   - pip install coveralls script:   - coverage run --source=src setup.py test after_success:   - coveralls

install, script, after_success に Coveralls 連携のための記述を追加していることに注意。

この状態で GitHub に push を行えば、ほどなく(数分以内に)自動的に Travis-CI, Coverall の処理が開始される。

 

Step5: 結果確認

Travis-CI, Coverall ともに GUI ですぐに結果を確認できる。
またテストに失敗した場合は、自動的に通知メールが飛んでくる。 

• Travis-CI
  
• Coveralls
  
  
  ファイル単位のカバレッジももちろん閲覧可能。
  

 

Step 6: バッジの登録

Travis-CI, Coveralls ともに公式のバッジが用意されている。

• Travis-CI
  
• Coveralls
   

これらを README に貼り付ければ、GitHub 訪問者にとってもステータスが一目瞭然だ。
 

さいごに

今回は Python プロジェクトの例を挙げたが、setup.py やテストコードの準備さえ済めば、実に簡単に連携できる。

まさに朝飯前。『Web系エンジニアにとってテストコードを書くのは朝起きて歯磨きをするように当たり前のこと』との言もあったが、これらのサービスはさながら無料の朝食サービスのようなものだ。

より高度な使い方もできるので、詳細は各サービスのドキュメントを参照。以下はその一例。

• master 以外のブランチと連携
• pull request との連携 (マージする前に結果を確認できるので便利)
• 通知先の拡張 (チャットサービス等と連携)
• プライベートリポジトリとの連携 (有償)

Travis-CI, Coveralls ともに他の言語でも利用可能なので、今後も積極的に活用していきたい。

 

今回使用したコード

• mogproject/skeleton-python

 

References

• TravisCI - CI環境構築 ~ Python編 ~ - Qiita
• 今回参考にしたプロジェクト: zaneli/docomocvpy

Cheat Sheets for My Sake

自分向け各種チートシートまとめ

 

自分が忘れがち or 使用頻度の高い事柄だけ書いておく。

Shell Script Cheat Sheet

原則、Bourne Shell 互換のものを書く

• 実行中のスクリプトがあるディレクトリをフルパスで取得

SCRIPT_DIR=$( cd "$( dirname "$0" )" && pwd -P )

この場合、実行スクリプト自身がシンボリックリンクだと正しい判定ができない。以下のような実装が必要。

function __readlink_f {
    local t="$1"; local n=
    (while [ "$t" ]; do cd $(dirname "$t"); n=$(basename "$t"); t=$(readlink "$n"); done; echo "$(pwd -P)/$n")
}

SCRIPT_PATH=$(__readlink_f "$0")
SCRIPT_DIR=$(dirname "${SCRIPT_PATH}")

• 変数が未定義または空文字だった場合にデフォルト値を代入

NAME=${NAME:-"default_value"}

• 特定ディレクトリ配下の条件を満たすファイルを削除

/usr/bin/find $PATH_TO_FIND -type f -name '*.gz' -mtime +$PRESERVE_DAYS -delete

• パラメータの2個目以降を取得

$ f() { echo "${@:2}" }
$ f 1 2 3 4 5
2 3 4 5

• シェルスクリプト終了時に一時ファイルを削除

TMP_FILE="/tmp/$(basename "$0").$$.tmp"
trap "rm -f ${TMP_FILE}" EXIT

• [Linux] サーバに接続されているディスクのマウントポイントを列挙

df --output=source,target | grep ^/dev | awk '{print $2}'

• コマンドの存在をチェック

# assert that all required commands exist
assert_command_exists() {
    while [ -n "$1" ]; do
        command -v $1 >/dev/null 2>&1 || {
            echo "Command '$1' is required but not installed. Aborting."
            exit 1
        }
        shift
    done
}

• Yes/No プロンプト

# print prompt and return yes/no
prompt_yesno() {
    local prompt=$1
    read -p "$prompt [y/N]: " yn
    case "$yn" in
        [Yy]) return 0;;
        *) return 1;;
    esac
}

• シェルスクリプト中のコマンドで失敗した場合に即終了とする

  • シェルの中で　set -e
  • or シェル起動時に bash -e

• ファイルの内容を入力と同時に書き換える (一時ファイルなし)

  • (rm -f -- "${FILEPATH}" && COMMAND > "${FILEPATH}") < "${FILEPATH}"
  • 参考: シェルスクリプトを極める

Bash 配列の操作

• 標準入力から読み込んだ内容を 1行ずつ配列に格納する

IFS=$'\n' lines=($(cat))

または

declare -a lines    ### lines=() でも可
while IFS= read line; do
    lines+=("$line")
done

• 配列の要素を全て削除

unset arr[@]

• 配列のコピー

dst_arr=("${src_arr[@]}")

• 配列の内容を表示

printf '%s\n' "${arr[@]}"

view raw ShellScriptCheatSheet.md hosted with ❤ by GitHub

AWK Cheat Sheet

• shebang

#!/usr/bin/env awk -f

• 先頭の n 個の要素を除外

# Join all tokens except first n ones with a space
function drop(n) {
  s = "";
  for (i = n + 1; i <= NF; ++i) {
    s = (s == "" ? s : s " ") $i
  }
  return s;
}

実行例

$ echo '1 2 3 4 5' | awk 'function drop(n){s="";for(i=n+1;i<=NF;++i){s=(s==""?s:s" ")$i}return s} {print drop(2)}'
3 4 5

view raw AWKCheatSheet.md hosted with ❤ by GitHub

Git Cheat Sheet

• リモートブランチをローカルに取得してチェックアウト

git checkout -t -b branch_name origin/branch_name

• 直前コミットの author を修正

git commit --amend --author="Your Name <your_address@example.com>"

• git push の時に、自動的に現在のブランチが対象になるようにする

git config --global push.default current

• リモートブランチの削除

git push --delete origin branch_name

• コマンドのエイリアスを設定する (checkout => co の例)

git config --global alias.co checkout

• アップストリームの確認と設定

git branch -vv

git push -u [origin branch_name]
  or
git branch --set-upstream-to=origin/branch_name branch_name

view raw GitCheatSheet.md hosted with ❤ by GitHub

MySQL Cheat Sheet

確認

• データベース一覧

show databases

• テーブル一覧

use <db_name>
show tables

• テーブル定義

desc <db_name>;

• ユーザ一覧

select host, user, password from mysql.user;

• ユーザ権限

show grants for <user>@<host>

• レプリケーション状態

スレーブノード上で

show slave status \G

• サーバパラメータ

show variables like '%host';

変更

• カラム名変更

alter table <table_name> change <old_column_name> <new_column_name> <type> <option>;

• カラム削除

alter table <table_name> drop column <column_name>;

• サーバパラメータ

set global <variable_name>=<value>

or modify /etc/my.cnf

• AUTO_INCREMENTの値をリセット

ALTER TABLE <table_name> AUTO_INCREMENT = 1;

• TIMESTAMP型の値を変更

UPDATE <table_name> SET <column_name> = 'YYYY-MM-DD hh:mm:ss' WHERE <condition>

• パスワード変更

set password for 'root'@'localhost' = password('root');

バックアップ

• DB全体

mysqldump -u root -x --all-databases > 出力ファイル名

• 特定DB

mysqldump -u root データベース名 > 出力ファイル名

• 特定テーブル

mysqldump -h ホスト名 -u ユーザ名 -p -t データベース名 テーブル名 > 出力ファイル名

view raw MySQLCheatSheet.md hosted with ❤ by GitHub

Redshift Cheat Sheet

接続

• psql で接続

psql -h <エンドポイントURL> -U <接続ユーザ> -d <データベース名> -p <ポート番号>

例: psql -h xxxxxx.xxxxxxxxxxxx.ap-northeast-1.redshift.amazonaws.com -U awsuser -d xxxxxx -p 5439

環境変数 PGPASSWORD=<パスワード> を指定すればパスワードの入力を省略可能。

プロンプト文字列を変える場合は -v PROMPT1='%m:%/# ' のように変数指定オプションを追加。

テーブル情報確認

• テーブル一覧

\dt

クエリを直接実行する場合

SELECT DISTINCT tablename FROM pg_table_def WHERE schemaname = 'public' ORDER BY tablename;

• テーブル定義の確認

\d+ <テーブル名>

クエリを直接実行する場合

SELECT * FROM pg_table_def WHERE tablename = '<テーブル名>' AND schemaname = 'public';

テーブル定義変更

• カラムの型を変更

新しいカラムを定義し、データを全てコピーし、そしてそのカラム名を変更するより方法がない。

ALTER TABLE <テーブル名> ADD COLUMN <一時的なカラム名> <正しいカラム定義>;
UPDATE <テーブル名> SET <一時的なカラム名> = <カラム名>;
ALTER TABLE <テーブル名> DROP COLUMN <カラム名>;
ALTER TABLE <テーブル名> RENAME COLUMN <一時的なカラム名> TO <カラム名>;

クエリの実行

• ミリ秒単位の Unix time から DATETIME に変換

SELECT TIMESTAMP 'epoch' + <カラム名> * INTERVAL '0.001 s' AS time_stamp FROM <テーブル名>

• 日本時間で表示

SELECT CONVERT_TIMEZONE('JST', TIMESTAMP 'epoch' + <カラム名> * INTERVAL '0.001 s') AS time_stamp FROM <テーブル名>

トラブルシューティング

• データロードエラーの調査

SELECT DISTINCT
  name AS tablename,
  raw_line,
  query,
  starttime,
  filename,
  line_number,
  colname,
  err_code,
  err_reason
FROM
  stl_load_errors error,
  stv_tbl_perm perm
WHERE
  error.tbl = perm.id
ORDER BY
  starttime DESC
LIMIT 20;

参考

• Redshiftの調査系クエリ3選 | Librabuch

view raw RedshiftCheatSheet.md hosted with ❤ by GitHub

Ansible Cheat Sheet

• コマンド結果によって処理の要否を判断する
  • register を使ってコマンド実行結果を変数に格納。
  • ignore_errors は必須。changed_when, failed_when は表示を見やすくするために。

- name: check if YOUR_MODULE is installed
  command: /usr/bin/test -e PATH_TO_THE_FILE
  ignore_errors: True
  changed_when: False
  failed_when: False
  register: is_installed
  tags: YOUR_MODULE

- name: install YOUR_MODULE
  ANSIBLE_MODULE: PARAMS
  when: is_installed | failed
  tags: YOUR_MODULE

- name: check if YOUR_PIP_MODULE is installed
  command: pip show YOUR_PIP_MODULE
  ignore_errors: True
  changed_when: False
  failed_when: False
  register: check_installed
  tags: YOUR_PIP_MODULE

- name: install YOUR_PIP_MODULE
  pip: name={{ item }} state=present
  with_items: YOUR_PIP_MODULE_URL
  when: check_installed.stdout == ''
  tags: YOUR_PIP_MODULE

view raw AnsibleCheatSheet.md hosted with ❤ by GitHub

Ansible: Visualizing CloudWatch Metrics with Grafana

Ansible: Grafana で CloudWatch のメトリクスを可視化するための Playbook

 

tl;dr

Grafana に触れてみたいなら、まずは Grafana Play Home

 

目的

• AWS CloudWatch の各種メトリクスを Grafana で見たい
• Grafana の URL は SSL + ベーシック認証で保護したい
• これらのセットアップ作業を Ansible で自動化したい

 

使ったもの

• Amazon CloudWatch: AWS 標準の監視コンソール。メトリクスデータが蓄積している前提
• Amazon EC2
• Amazon Linux: インスタンスを1台立ち上げ、この中に全てをインストールする
• Nginx: フロントエンドの Web サーバ。BASIC認証 + 自己署名証明書によるSSL通信を設定。
• Grafana: メトリクスデータの可視化ツール
• Elasticsearch: Grafana のデータストアとして使う
• Graphite: メトリクスデータ管理システム
• uWSGI: フロントエンド連携用に必要
• MySQL: Graphite のデータストアとして使う
• cloudwatch-dump: CloudWatch のメトリクスデータを取得し、Graphite に流し込むために使用
• Ansible: セットアップ(プロビジョニング)の自動化

 

コード

こちらのリポジトリに Vagrant + Ansible コード一式と再現手順を書いた。

• mogproject/example-ansible-grafana

必要なソフトウェア/プラグインをインストール後、vagrant up を行えば以下のような Grafana の画面に触れられるようになる。

Grafana のロゴが表示されないのは https 通信をしているためで、表示させるにはソースコードに手を入れる必要がありそう。

 

はじめに

システム監視の目的は大きく「異常検知」と「トレンド分析」の2つに分けられる。

また一般に、「トレンド分析」がその対象者に応じて、例えば「システム利用者向け分析」「システム管理者向け分析」「経営判断層層向け分析」の3つのように分類できると、スッキリとしたシステムになりやすい。

 

今回の構成ではメトリクスデータは一旦 CloudWatch に集約される想定である。

異常検知は CloudWatch が持ち合わせている Alarm 機能で対応する。
Simple Notification Service を使うことでメール送信だけではなく、携帯端末にpush通知を行ったり、特定のURLにhttpリクエストを投げたり、オートスケールを実現したりなど工夫次第でできることは多い。

次に、そのメトリクスデータを一式 Graphite に投入する。
これを Grafana のようなフロントエンドで可視化することにより、異なる対象者に向けたダッシュボードを簡単に作ることができる。
生成されたグラフを週次レポートのような形で定期的に発信するのもよい。

 

構成イメージ

解説

 

Vagrantfile

• プラグイン dotenv を使うことでアカウント固有の定義を別ファイル(.env)に分離
• (コスト節約のため)米国東部リージョンに t2.micro インスタンスを1個新規構築する
• Ansible のロールの中で使う変数は、extra_vars として引き渡す

Role: aws-scripts-mon

• これは本来監視される側のセットアップである
• CloudWatch の標準機能だけは取得できない Linux 内部の情報(メモリ/スワップ/ディスクスペース使用状況)を CloudWatch に送信する
• 今回は、ec2-user の ~/aws-scripts-mon ディレクトリ配下にモジュール一式を配置し、Cron で 5分おきにレポーティングが実行されるよう仕掛けた
• CloudWatch API のアクセスには、EC2 構築時とは別の IAM ユーザ (cloudwatch) を準備した

Role: nginx

• もちろん Grafana は Apache でも動作する(その方が簡単だ)が、今回は Web サーバとして Nginx を採用する
• このロールの中で自己署名証明書を作成し、/etc/nginx/cert ディレクトリ配下に配置した
• 実際のSSLサイトの設定は、Grafana のインストール後に実施する

Role: mysql

• デフォルトの SQLite でも動作するが、運用を考えるなら MySQL 等のほうが堅い
• Amazon Linux はデフォルトで利用可能な EPEL リポジトリに対して yum install するだけ  

Role: graphite

• jsmartin/ansible-graphite を参考にした
• python-carbon を yum でインストールしたのは、起動スクリプトの有り物を使いたかったので
• 最初は graphite-web も yum で導入したのだが、/opt/graphite/bin 以下のモジュールがインストールされずエラーが出て面倒なことになったので、最終的にこちらは pip で入れることにした
• そのため、carbon 関係はFHS準拠っぽいディレクトリ構成なのに graphite の場所は /opt/graphite 配下という状態になっている
• コマンドによって処理の要否を判定する雛形はこちらにも書いた
• Whisper のデフォルトのデータ間隔・保持期間を 5分・2年 に書き換えている。(storage-schemas.conf)
  こうすることで長期間の分析をしてもデータが重くならない。(逆に1分単位の分析はできなくなる)
• 起動がうまくいかない場合は、大抵 /var/log/graphite-web.log を見れば原因がわかるはず 

Role: cloudwatch-dump

• 自作のダンプツールを pip でインストール
• ec2-user の ~/cloudwatch-dump ディレクトリ配下にシェルを置き、Cron で 1時間に1回(*:05)、graphite にデータを流し込む
• 何かあった時でもデータを再投入できるよう、~/cloudwatch-dump/logs に直近のログを残している
  (ローテーションは logrotate を使ったほうが良かったかも)
• シェルスクリプトの中で、メトリクスパス中に含まれるEC2インスタンスIDをニックネームへの変換している

Role: elasticsearch

• RPM のダウンロード先を指定して、yum install するだけ

Role: grafana

• Grafana 自体は独立したツールなので、インストールは素直に終わる
• カスタマイズは config.js をテンプレートエンジンに乗せて行う。Grafana のバージョンによって微妙に項目が変わっているので注意
• 最後に Nginx の SSL サイト設定と、BASIC認証用のファイルを作って完了

 

References

• jsmartin/ansible-graphite
• graphite with nginx and uwsgi

Related Posts

• mog project: cloudwatch-dump - Dump All the CloudWatch Metrics Statistics

Mac: Upgrading to OS X Yosemite

Mac: OS X Yosemite にアップグレードした際のメモ

 

reattach-to-user-namespace のアップデート

HomeBrew でインストールした reattach-to-user-namespace で警告が出た。

warning: reattach-to-user-namespace: unsupported new OS, trying as if it were 10.6-10.9 warning: _vprocmgr_move_subset_to_user failed warning: reattach-to-user-namespace: unable to reattach

reattach-to-user-namespace の最新版をインストールすればよい。

$ brew upgrade reattach-to-user-namespace

 

テキストエディタなどで Ctrl-N (カーソルを一行下へ移動) が効かなくなる

なぜか、システム環境設定 Keyboard -> Input Sources -> Japanese -> Windows-like shortcuts に
チェックが入っていると、Emacs ライクなキーバインドである Ctrl-N が効かなくなるようだ。

チェックオフにして解決。

ハードウェアドライバの更新

• Roland QUAD-CAPTURE:
  Mac OS X への対応状況 (OS X Yosemite... :: QUAD-CAPTURE :: お知らせ :: サポート :: ローランド

cloudwatch-dump - Dump All the CloudWatch Metrics Statistics

Python: CloudWatch のメトリクスデータを全て出力するスクリプト

 

概要

• mogproject/cloudwatch-dump

1. 特定リージョンの AWS CloudWatch からメトリクスの一覧を取得し、
2. その全てのメトリクスに対して、ある期間を一定の単位時間で「平均」「合計」の統計値を取得し、
3. その結果(メトリクス、数値、タイムスタンプ)を Graphite に投入可能な形式で出力する

そんな Python スクリプトを作成。

 

モチベーション

やりたいことは、CloudWatch のデータを Grafana で見たいだけ。

はじめは Fluentd + fluent-plugin-cloudwatch + fluent-plugin-graphite を使って流し込んでいたのだが、

• メトリクスと統計方法(Average, Sum, Maximum)を1個1個指定しなければいけなかったり (将来にわたってメンテが必要)
• ちらほらデータの欠落が見られたり
• バッファリングの関係か、データが更新されるタイミングを制御しづらかったり
• 特定期間だけリトライしたい場合に難しかったり

といったことがあったので、1時間おきのバッチ処理で一括インポートをすることにした。

 

とはいえ悩みどころなのが統計方法。
CloudWatch では各サービス・各メトリクスごとに推奨の(意味のある)統計方法が異なっている。

しかし今回は割り切って、全メトリクスについて 平均(Average)、合計(Sum) を取得することにした。
物によっては Maximum を得たい場合もあるが、一旦は目を瞑る。

 

今後の課題

• CloudWatch の APIリクエストも決して無制限で使えるわけではないので、極力無駄なリクエストは減らしたい。
  (現時点では100万件/月まで無料, それ以降は1,000件ごとに0.01USDの課金)
  CPU使用率の Sum など、結局個別に指定する他ないのか。
• 個別のメトリクス統計方法の指定 (DynamoDB の ItemCount の Maximum など) をできるようにするか
• 並列化をして高速に
• ユニットテストを充実させる

 

導入方法、注意事項についてはリポジトリの README参照。

Python: How to Parse DateTime with Local Timezone

Python: ローカルのタイムゾーン情報付きで日時表記文字列を読み込む

 

Python の datetime クラスは、"naive" と "aware" の 2種類の顔を持つ。

• 8.1. datetime — 基本的な日付型および時間型 — Python 2.7ja1 documentation

"aware" な datetime はタイムゾーンの情報を持ち、"naive" は持たない。

プログラム内部では "aware" な datetime を利用し、"naive" は入出力境界のみにとどめるのがセオリーだ。

 

タイムゾーンの自動認識には、dateutil.tz.tzlocal を使うのが最も適当な様子。

たとえば datetime.strptime を使って日時を認識するコードは以下のようになる。

1 2 3 4 5

>>> from datetime import datetime >>> from dateutil.tz import tzlocal >>> t = datetime.strptime('201410281234', '%Y%m%d%H%M').replace(tzinfo=tzlocal()) >>> t datetime.datetime(2014, 10, 28, 12, 34, tzinfo=tzlocal())

datetime#astimezone を使ってタイムゾーンを変更する。

1 2 3

>>> import pytz >>> t.astimezone(pytz.utc) datetime.datetime(2014, 10, 28, 3, 34, tzinfo=<UTC>)

epoch time への変換には一手間かかる。calendar.timegm を使うのがベストプラクティスのようだ。

1 2 3 4 5

>>> import calendar >>> calendar.timegm(t.timetuple()) 1414499640 >>> calendar.timegm(t.astimezone(pytz.utc).timetuple()) 1414467240

Ansible: Playbook for AWS CloudWatch Monitoring Scripts

Ansible: CloudWatch 用 Linux 監視スクリプトをインストールする Playbook

 

前提

• EC2 インスタンスの OS は Amazon Linux とする
• 認証情報はファイルに保存する
• インスタンス作成前であれば、IAM Role の設定により認証情報の保持が不要となる
• CloudWatch API 専用の IAM ユーザの作成を推奨
• 各種パラメータについては vars/main.yml を参照
• 課金が発生する可能性があるので注意

 

コード

aws-scripts-mon/tasks/main.yml

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 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48

--- - name: install additional perl modules   yum: name={{ item }} state=present   with_items:     - perl-Switch     - perl-Sys-Syslog     - perl-LWP-Protocol-https   tags: aws-scripts-mon   - name: check if script is installed   command: /usr/bin/test -e {{ path_to_script }}   ignore_errors: True   changed_when: False   register: is_installed   tags: aws-scripts-mon   - name: download scripts from AWS server   get_url: url={{ download_url }} dest={{ path_to_download }}   when: is_installed | failed   tags: aws-scripts-mon   - name: unzip downloaded file   unarchive: copy=no src={{ path_to_download }} dest={{ home_dir }}   when: is_installed | failed   tags: aws-scripts-mon   - name: create credential file   template: src={{ item }}.j2 dest={{ script_dir }}/{{ item }} owner={{ user }} group={{ user }} mode="0600"   with_items:     - awscreds.conf   tags: aws-scripts-mon   - name: set directory owner   file: path={{ script_dir }} state=directory owner={{ user }} group={{ user }} recurse=yes   tags: aws-scripts-mon   - name: remove downloaded file   file: path={{ path_to_download }} state=absent   tags: aws-scripts-mon   - name: set cron   cron: user={{ user }}         state=present         name="CloudWatch monitoring script"         minute="{{ cron.minute }}"         hour="{{ cron.hour }}"         job="{{ cron.job }}"   tags: aws-scripts-mon

aws-scripts-mon/templates/awscreds.conf.j2

1 2	AWSAccessKeyId={{ access_key }} AWSSecretKey={{ secret_key }}

aws-scripts-mon/vars/main.yml

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

--- user: ec2-user version: 1.1.0 filename: CloudWatchMonitoringScripts-v{{ version }}.zip download_url: http://ec2-downloads.s3.amazonaws.com/cloudwatch-samples/{{ filename }}   path_to_download: "/tmp/{{ filename }}"   home_dir: "/home/{{ user }}" script_dir: "{{ home_dir }}/aws-scripts-mon" path_to_script: "{{ script_dir }}/mon-put-instance-data.pl"   access_key: "{{ aws_cloudwatch_agent_access_key_id }}" secret_key: "{{ aws_cloudwatch_agent_secret_access_key }}"   cron:   hour: "*"   minute: "*/5"   job: "{{ path_to_script }} --mem-util --mem-used --mem-avail --swap-util --swap-used --disk-path=/ --disk-space-util --disk-space-used --disk-space-avail --aws-credential-file={{ script_dir }}/awscreds.conf --from-cron"

credential 情報 (aws_cloudwatch_agent_xxx) は、extra-vars などで渡す想定。

 

 

References

• Amazon Web Services ブログ: 【AWS発表】Linux用CloudWatch監視スクリプトに3つの新機能を追加
• Amazon CloudWatch Monitoring Scripts for Linux : Sample Code & Libraries : Amazon Web Services
• AWS運用監視ノウハウ CloudWatch 〜作ってからが本番です！〜

Scala: How to Limit DynamoDB's Range Query

Scala: AWS DynamoDB のテーブルに対して件数制限付きのレンジクエリを実行する

 

DynamoDB の range クエリについて、理解が足りなかったので整理しておく。

今回は例として、食事の記録を以下の項目とともに DynamoDB に格納し、
ユーザごとの最新 n 件の食事を調べるクエリを投げるようなアプリケーションを考えてみる。

DynamoDB: FoodLog

• UserId [ハッシュキー]: ユーザID (文字列)
• Timestamp [レンジキー]: タイムスタンプ(epoch からの経過時間をミリ秒単位で格納) (整数値)
• Food: 食事した内容 (文字列)
• Calorie: 摂取カロリー (整数値)

 

テーブル作成

aws-cli で以下のコマンドを実行し、FoodLog テーブルを作成する。
(aws-cli および認証情報はセットアップ済みの前提)

$ aws dynamodb create-table \ --table-name FoodLog \ --attribute-definitions \ AttributeName=UserId,AttributeType=S \ AttributeName=Timestamp,AttributeType=N \ --key-schema AttributeName=UserId,KeyType=HASH AttributeName=Timestamp,KeyType=RANGE \ --provisioned-throughput ReadCapacityUnits=1,WriteCapacityUnits=1

 

ベース部分実装

Java のライブラリと O/R マッパーを使って FoodLog クラスを実装。
接続情報は環境変数(AWS_ACCESS_KEY, AWS_SECRET_KEY)より与えられる想定である。

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 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46

package com.github.mogproject.example.dynamodb   import com.amazonaws.auth.BasicAWSCredentials import com.amazonaws.regions.RegionUtils import com.amazonaws.services.dynamodbv2.AmazonDynamoDBClient import com.amazonaws.services.dynamodbv2.datamodeling._   import scala.annotation.meta.beanGetter import scala.beans.BeanProperty import scala.collection.JavaConverters._   trait DynamoDBClient {   private[this] val accessKeyId = sys.env("AWS_ACCESS_KEY")   private[this] val secretAccessKey = sys.env("AWS_SECRET_KEY")   private[this] val region = RegionUtils.getRegion("ap-northeast-1")   private[this] val endpoint = region.getServiceEndpoint("dynamodb")     private[this] val credentials = new BasicAWSCredentials(accessKeyId, secretAccessKey)   private[this] val client = {     val ret = new AmazonDynamoDBClient(credentials)     ret.setRegion(region)     ret.setEndpoint(endpoint)     ret   }   protected val mapper = new DynamoDBMapper(client)     def batchSave(xs: FoodLog*) = mapper.batchSave(xs.asJava)     def batchDelete(xs: FoodLog*) = mapper.batchDelete(xs.asJava)     def batchWrite(toWrite: Seq[FoodLog], toDelete: Seq[FoodLog]) = mapper.batchWrite(toWrite.asJava, toDelete.asJava) }   @DynamoDBTable(tableName = "FoodLog") case class FoodLog(                     @(DynamoDBHashKey@beanGetter)(attributeName = "UserId") @BeanProperty var userId: String,                     @(DynamoDBRangeKey@beanGetter)(attributeName = "Timestamp") @BeanProperty var timestamp: Long,                     @DynamoDBAttribute(attributeName = "Food") @BeanProperty var food: String,                     @DynamoDBAttribute(attributeName = "Calorie") @BeanProperty var calorie: Int                     ) {   def this() = this(null, 0, null, 0) }   object FoodLog extends DynamoDBClient {   def readRecent(userId: String, limit: Int): Seq[FoodLog] = ??? }

 

テストデータ投入

REPL を使い、2ユーザx10件ずつのランダムなテストデータを投入する。

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

$ export AWS_ACCESS_KEY="xxxxxx" $ export AWS_SECRET_KEY="xxxxxx" $ sbt console   scala> import com.github.mogproject.example.dynamodb.FoodLog import com.github.mogproject.example.dynamodb.FoodLog   scala> import scala.util.Random import scala.util.Random   scala> val item1 = (1 to 10).map(i => FoodLog("user-1", Random.nextInt(100000), s"food-$i", Random.nextInt(2000))) item1: scala.collection.immutable.IndexedSeq[com.github.mogproject.example.dynamodb.FoodLog] = Vector(FoodLog(user-1,78548,food-1,1911), FoodLog(user-1,67632,food-2,974), FoodLog(user-1,34756,food-3,1639), FoodLog(user-1,15595,food-4,937), FoodLog(user-1,77366,food-5,158), FoodLog(user-1,9615,food-6,393), FoodLog(user-1,64601,food-7,429), FoodLog(user-1,6847,food-8,1834), FoodLog(user-1,55271,food-9,1434), FoodLog(user-1,74394,food-10,885))   scala> val item2 = (1 to 10).map(i => FoodLog("user-2", Random.nextInt(100000), s"food-$i", Random.nextInt(2000))) item2: scala.collection.>immutable.IndexedSeq[com.github.mogproject.example.dynamodb.FoodLog] = Vector(FoodLog(user-2,15618,food-1,1356), FoodLog(user-2,27456,food-2,123), FoodLog(user-2,62137,food-3,1122), FoodLog(user-2,43501,food-4,673), FoodLog(user-2,80906,food-5,577), FoodLog(user-2,96682,food-6,1112), FoodLog(user-2,40193,food-7,1961), FoodLog(user-2,44857,food-8,1064), FoodLog(user-2,88767,food-9,1618), FoodLog(user-2,42126,food-10,761))   scala> FoodLog.batchSave(item1 ++ item2: _*) res0: java.util.List[com.amazonaws.services.dynamodbv2.datamodeling.DynamoDBMapper.FailedBatch] = []

 

クエリ部分(仮)実装

件数制限付きのクエリを素直に書くと、以下のようになる。

1 2 3 4 5 6 7 8

def readRecent(userId: String, limit: Int): Seq[FoodLog] = {   val query = new DynamoDBQueryExpression[FoodLog]()     .withHashKeyValues(FoodLog(userId, 0, null, 0))     .withScanIndexForward(false)     .withLimit(limit)     .withConsistentRead(false)   mapper.query(classOf[FoodLog], query).asScala }

そして limit=5 としてクエリを実行すると、結果は …… 10個ある!?

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

$ sbt console scala> import com.github.mogproject.example.dynamodb.FoodLog import com.github.mogproject.example.dynamodb.FoodLog   scala> FoodLog.readRecent("user-1", 5) res0: Seq[com.github.mogproject.example.dynamodb.FoodLog] = Buffer(FoodLog(user-1,78548,food-1,1911), FoodLog(user-1,77366,food-5,158), FoodLog(user-1,74394,food-10,885), FoodLog(user-1,67632,food-2,974), FoodLog(user-1,64601,food-7,429), FoodLog(user-1,55271,food-9,1434), FoodLog(user-1,34756,food-3,1639), FoodLog(user-1,15595,food-4,937), FoodLog(user-1,9615,food-6,393), FoodLog(user-1,6847,food-8,1834))   scala> res0.size res1: Int = 10   scala> res0 foreach println FoodLog(user-1,78548,food-1,1911) FoodLog(user-1,77366,food-5,158) FoodLog(user-1,74394,food-10,885) FoodLog(user-1,67632,food-2,974) FoodLog(user-1,64601,food-7,429) FoodLog(user-1,55271,food-9,1434) FoodLog(user-1,34756,food-3,1639) FoodLog(user-1,15595,food-4,937) FoodLog(user-1,9615,food-6,393) FoodLog(user-1,6847,food-8,1834)

 

これはどういうことなのか

sbt run で実行可能なプログラムを作成し、build.sbt に以下の記述を行って http-wire ログを出力してみる。

1 2 3 4 5 6 7

javaOptions in run ++= Seq(   "-Dorg.apache.commons.logging.Log=org.apache.commons.logging.impl.SimpleLog",   "-Dorg.apache.commons.logging.simplelog.showdatetime=true",   "-Dorg.apache.commons.logging.simplelog.log.org.apache.http.wire=DEBUG" )   fork in run := true

すると、以下のように DynamoDB との通信が 2回発生していることがわかる。

[error] 2014/10/20 01:09:19:440 JST [DEBUG] wire - >> "POST / HTTP/1.1[\r][\n]" [error] 2014/10/20 01:09:19:441 JST [DEBUG] wire - >> "Host: dynamodb.ap-northeast-1.amazonaws.com[\r][\n]" (snip) [error] 2014/10/20 01:09:19:442 JST [DEBUG] wire - >> "{"TableName":"FoodLog","Limit":5,"ConsistentRead":false,"KeyConditions":{"UserId":{"AttributeValueList":[{"S":"user-1"}],"ComparisonOperator":"EQ"}},"ScanIndexForward":false}" [error] 2014/10/20 01:09:19:468 JST [DEBUG] wire - << "HTTP/1.1 200 OK[\r][\n]" (snip) [error] 2014/10/20 01:09:19:478 JST [DEBUG] wire - << "{"Count":5,"Items":[{"UserId":{"S":"user-1"},"Timestamp":{"N":"78548"},"food":{"S":"food-1"},"calorie":{"N":"1911"}},{"UserId":{"S":"user-1"},"Timestamp":{"N":"77366"},"food":{"S":"food-5"},"calorie":{"N":"158"}},{"UserId":{"S":"user-1"},"Timestamp":{"N":"74394"},"food":{"S":"food-10"},"calorie":{"N":"885"}},{"UserId":{"S":"user-1"},"Timestamp":{"N":"67632"},"food":{"S":"food-2"},"calorie":{"N":"974"}},{"UserId":{"S":"user-1"},"Timestamp":{"N":"64601"},"food":{"S":"food-7"},"calorie":{"N":"429"}}],"LastEvaluatedKey":{"Timestamp":{"N":"64601"},"UserId":{"S":"user-1"}},"ScannedCount":5}" [info] FoodLog(user-1,78548,food-1,1911) [info] FoodLog(user-1,77366,food-5,158) [info] FoodLog(user-1,74394,food-10,885) [info] FoodLog(user-1,67632,food-2,974) [info] FoodLog(user-1,64601,food-7,429) [error] 2014/10/20 01:09:19:504 JST [DEBUG] wire - >> "POST / HTTP/1.1[\r][\n]" [error] 2014/10/20 01:09:19:504 JST [DEBUG] wire - >> "Host: dynamodb.ap-northeast-1.amazonaws.com[\r][\n]" (snip) [error] 2014/10/20 01:09:19:505 JST [DEBUG] wire - >> "{"TableName":"FoodLog","Limit":5,"ConsistentRead":false,"KeyConditions":{"UserId":{"AttributeValueList":[{"S":"user-1"}],"ComparisonOperator":"EQ"}},"ScanIndexForward":false,"ExclusiveStartKey":{"UserId":{"S":"user-1"},"Timestamp":{"N":"64601"}}}" [error] 2014/10/20 01:09:19:533 JST [DEBUG] wire - << "HTTP/1.1 200 OK[\r][\n]" (snip) [error] 2014/10/20 01:09:19:533 JST [DEBUG] wire - << "{"Count":5,"Items":[{"UserId":{"S":"user-1"},"Timestamp":{"N":"55271"},"food":{"S":"food-9"},"calorie":{"N":"1434"}},{"UserId":{"S":"user-1"},"Timestamp":{"N":"34756"},"food":{"S":"food-3"},"calorie":{"N":"1639"}},{"UserId":{"S":"user-1"},"Timestamp":{"N":"15595"},"food":{"S":"food-4"},"calorie":{"N":"937"}},{"UserId":{"S":"user-1"},"Timestamp":{"N":"9615"},"food":{"S":"food-6"},"calorie":{"N":"393"}},{"UserId":{"S":"user-1"},"Timestamp":{"N":"6847"},"food":{"S":"food-8"},"calorie":{"N":"1834"}}],"ScannedCount":5}" [info] FoodLog(user-1,55271,food-9,1434) [info] FoodLog(user-1,34756,food-3,1639) [info] FoodLog(user-1,15595,food-4,937) [info] FoodLog(user-1,9615,food-6,393) [info] FoodLog(user-1,6847,food-8,1834)

改めてAPIマニュアル(DynamoDBQueryExpression (AWS SDK for Java - 1.9.1))を読む。

Sets the maximum number of items to retrieve in each service request to DynamoDB and returns a pointer to this object for method-chaining.

Note that when calling DynamoDBMapper.query, multiple requests are made to DynamoDB if needed to retrieve the entire result set. Setting this will limit the number of items retrieved by each request, NOT the total number of results that will be retrieved. Use DynamoDBMapper.queryPage to retrieve a single page of items from DynamoDB.

つまるところ、withLimit で指定しているのはクエリ全体の取得件数ではなく、
1回のリクエストで取得するサイズ (サービスリクエストにおける1ページのサイズ) なのである。

DynamoDBMapper.query メソッドは(ページ単位で遅延評価となる)全体の結果セットを返すため、
その結果に map や size などの横断的な処理を適用すると結果セット全体がスキャンされてしまう。

求める結果が最初のページだけでよければ、DynamoDBMapper.queryPage を利用するのが正解だ。

 

クエリ部分の正しい実装

ハイライト部分を修正。

1 2 3 4 5 6 7 8

def readRecent(userId: String, limit: Int): Seq[FoodLog] = {   val query = new DynamoDBQueryExpression[FoodLog]()     .withHashKeyValues(FoodLog(userId, 0, null, 0))     .withScanIndexForward(false)     .withLimit(limit)     .withConsistentRead(false)   mapper.queryPage(classOf[FoodLog], query).getResults.asScala }

結果は想定通り、5個のみとなった。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

scala> import com.github.mogproject.example.dynamodb.FoodLog import com.github.mogproject.example.dynamodb.FoodLog   scala> FoodLog.readRecent("user-1", 5) res0: Seq[com.github.mogproject.example.dynamodb.FoodLog] = Buffer(FoodLog(user-1,78548,food-1,1911), FoodLog(user-1,77366,food-5,158), FoodLog(user-1,74394,food-10,885), FoodLog(user-1,67632,food-2,974), FoodLog(user-1,64601,food-7,429))   scala> res0.size res1: Int = 5   scala> res0 foreach println FoodLog(user-1,78548,food-1,1911) FoodLog(user-1,77366,food-5,158) FoodLog(user-1,74394,food-10,885) FoodLog(user-1,67632,food-2,974) FoodLog(user-1,64601,food-7,429)

DynamoDBのスキャンが想定外に繰り返されると、応答が遅くなるだけでなく
読み込みキャパシティの限界突破のリスクも非常に高くなる。
このような落とし穴にはよくよく注意が必要である。

 

さいごに、簡単なベンチマークを行った。

100件のデータを用意し、「limit=5 の全ページスキャン」「limit=5 の最初のページのみスキャン」「limit=100 の最初のページのみスキャン」の所要時間を測定したところ、結果は以下のようになった。

• limit=5 の全ページスキャン                    : 340msec
• limit=5 の最初のページのみスキャン      :  19msec
• limit=100 の最初のページのみスキャン  :  28msec

やはり、DynamoDBに対してHTTP通信を繰り返す(上記の例では20回)のは非常にコストが高い。
全ページのスキャンを行うくらいなら、最初から limit を引き上げたほうが得策だろう。

 

 

Source code

• mogproject/example-dynamodb

 

References

• Understanding Auto-Paginated Scan with DynamoDBMapper - AWS Developer Blog - Java
• AWS Developer Forums: Set limit on number of records fetched ...
  2013年の時点で、話題になっていたようだ。

Scala: Property-Based Testing with ScalaTest and ScalaCheck

Scala: ScalaTest + ScalaCheck を使ってプロパティベースのユニットテストを行う

• ScalaTest とは
  多くの Scala プロジェクトで採用されているユニットテスト・フレームワークのデファクトの一つ。
  双璧をなす Specs2 とどちらを使うかは好みの問題。
• ScalaCheck とは
  Haskell の QuickCheck から派生したツール。
  実行時にランダムな入力を自動的に生成し、振る舞いをテストすることができる。
  テスト仕様とテストデータを分離できるようになるのが嬉しい。
  ScalaTest/Specs2 には ScalaCheck を透過的に扱うための仕組みが標準で組み込まれている。

 

sbt の設定

ScalaTest/ScalaCheck を使うにはsbt プロジェクトを作るのが一番簡便だろう。

build.sbt などに、以下のように依存ライブラリを追加する。

libraryDependencies ++= Seq(   "org.scalatest" %% "scalatest" % "2.2.0" % "test",   "org.scalacheck" %% "scalacheck" % "1.11.6" % "test" )

 

REPL で ScalaCheck を試す

sbt test:console で REPL を立ち上げれば、すぐに ScalaCheck の動作に触れることができる。

はじめての ScalaCheck

任意のInt型整数に対して、2 を掛けるのと自分自身を足し合わせた結果が同じになることを確かめる。
ランダムな入力 100個に対するテストが行われ、結果「OK」が表示される。

1 2 3 4 5 6 7 8

scala> import org.scalacheck.Prop.forAll import org.scalacheck.Prop.forAll   scala> val prop = forAll { x: Int => x * 2 == x + x } prop: org.scalacheck.Prop = Prop   scala> prop.check + OK, passed 100 tests.

テストに失敗する例。x * 2 でオーバーフローする場合、その値を 2 で割っても x には戻らない。

1 2 3 4 5 6

scala> val prop = forAll { x: Int => x * 2 / 2 == x }   scala> prop.check ! Falsified after 4 passed tests. > ARG_0: 1073741824 > ARG_0_ORIGINAL: 1461275699

Int 以外の組み込み型も、そのまま直感的に扱える。

1 2 3 4 5 6 7 8 9 10 11 12 13 14

scala> val prop =      |   forAll { (x: String, y: String, n: Int) => (x + y).startsWith(x.take(n)) } prop: org.scalacheck.Prop = Prop   scala> prop.check + OK, passed 100 tests.   scala> val prop =      |   forAll { xss: List[List[Int]] => xss.map(_.length).sum == xss.flatten.length } prop: org.scalacheck.Prop = Prop   scala> prop.check   OK, passed 100 tests.

ランダムに生成される String や List の長さ(サイズ)は、デフォルトでは 0以上 100以下となる。

• ScalaTest 2.2.0 - Checkers - ScalaTest 2.2.0 - org.scalatest.prop.Checkers

 

入力値の制約

入力に対して制約を与えるには、以下2種類の方法がある。

1. ジェネレータ(Gen)を与える

1 2 3 4 5 6 7 8

scala> import org.scalacheck.Gen import org.scalacheck.Gen   scala> val prop = forAll(Gen.choose(-10000, 10000)){ x: Int => x * 2 / 2 == x } prop: org.scalacheck.Prop = Prop   scala> prop.check + OK, passed 100 tests.

2. テストの内部でフィルタリングする (マッチしない場合のテストを放棄)

1 2 3 4 5 6 7 8

scala> import org.scalacheck.Prop.BooleanOperators import org.scalacheck.Prop.BooleanOperators   scala> val prop = forAll{ x: Int => (-10000 <= x && x <= 10000) ==> (x * 2 / 2 == x) } prop: org.scalacheck.Prop = Prop   scala> prop.check + OK, passed 100 tests.

ただし後者の場合、制約が強すぎるとテストが全く行われない可能性があるので注意。

1 2 3 4 5

scala> val prop = forAll{ x: Int => (x == 12345) ==> (x * 2 / 2 == x) } prop: org.scalacheck.Prop = Prop   scala> prop.check ! Gave up after only 0 passed tests. 101 tests were discarded.

 

ScalaTest の一部として ScalaCheck を使う

BDD スタイルの FlatSpec を使う場合の例。

単純なテストであれば、org.scalatest.prop.Checkers.check を使うだけでよい。

ExampleSpec.scala

1 2 3 4 5 6 7 8

import org.scalatest.prop.Checkers.check import org.scalatest.{MustMatchers, FlatSpec}   class ExampleSpec extends FlatSpec with MustMatchers {   "multiplying integer with two" should "be same as adding itself" in check { x: Int =>     x * 2 == x + x   } }

sbt test を流せば以下のような結果が表示される。

[info] ExampleSpec: [info] multiplying integer with two [info] - should be same as adding itself

GeneratorDrivenPropertyChecks トレイトをミックスインすれば、より複雑なテストケースを書けるようになる。

例えばこのような平面座標の距離を求める簡単な関数に対して、

Coord.scala

1 2 3

case class Coord(x: Double, y: Double) {   def distance(c: Coord) = math.sqrt(math.pow(c.x - x, 2) + math.pow(c.y - y, 2)) }

ScalaCheck を使ってみる。

CoordSpec.scala

1 2 3 4 5 6 7 8 9 10

import org.scalatest.prop.GeneratorDrivenPropertyChecks import org.scalatest.{MustMatchers, FlatSpec}   class CoordSpec extends FlatSpec with MustMatchers with GeneratorDrivenPropertyChecks {   "Coord#distance" should "be same as norm when one side is origin" in forAll { (x: Double, y: Double) =>     val norm = math.sqrt(x * x + y * y)     Coord(x, y).distance(Coord(0, 0)) mustBe norm     Coord(0, 0).distance(Coord(x, y)) mustBe norm   } }

 

独自のクラスに対してテストを行う

組み込み型以外のクラスを任意に生成するには、独自のジェネレータを作ればよい。

ジェネレータの実装例

1 2 3 4 5

def genCoord: Gen[Coord] =   for {     x <- Gen.choose(-100.0, 100.0)     y <- Gen.choose(-100.0, 100.0)   } yield Coord(x, y)

Gen.choose, Gen.oneOf, Gen.someOf がよく使われる。
Gen.frequency で出現頻度を調整したり、Gen.suchThat で制約を付けたり
org.scalacheck.Arbitrary.arbitrary で任意の値を選んだりもできる。(参考: User Guide · rickynils/scalacheck Wiki)

テストコードはこのような形になった。

CoordSpec.scala

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 32 33 34 35 36 37 38

import org.scalacheck.Gen import org.scalacheck.Arbitrary.arbitrary import org.scalatest.prop.GeneratorDrivenPropertyChecks import org.scalatest.{MustMatchers, FlatSpec}   class CoordSpec extends FlatSpec with MustMatchers with GeneratorDrivenPropertyChecks {   def genCoord: Gen[Coord] =     for {       x <- Gen.choose(-100.0, 100.0)       y <- Gen.choose(-100.0, 100.0)     } yield Coord(x, y)     "Coord#distance" should "be norm when one side is origin" in forAll { (x: Double, y: Double) =>     val norm = math.sqrt(x * x + y * y)     Coord(x, y).distance(Coord(0, 0)) mustBe norm     Coord(0, 0).distance(Coord(x, y)) mustBe norm   }     it should "be zero with same coordinates" in forAll(genCoord) { (a: Coord) =>     a.distance(a) mustBe 0.0   }   it should "be positive or zero" in forAll(genCoord, genCoord) { (a: Coord, b: Coord) =>     a.distance(b) must be >= 0.0   }   it should "be less than 300" in forAll(genCoord, genCoord) { (a: Coord, b: Coord) =>     a.distance(b) must be < 300.0   }   it should "not change after swapping parameters" in forAll(genCoord, genCoord) { (a: Coord, b: Coord) =>     a.distance(b) mustBe b.distance(a)   }   it should "not change after parallel shift" in forAll(     genCoord, genCoord, Gen.choose(-100.0, 100.0), arbitrary[Int], minSuccessful(500), maxDiscarded(2000)) {       (a: Coord, b: Coord, dx: Double, dy: Int) => whenever(-10000 <= dy && dy <= 10000) {       a.distance(b) mustBe (Coord(a.x + dx, a.y + dy).distance(Coord(b.x + dx, b.y + dy)) +- 1.0E-8)     }   } }

最後の例は、whenever で入力を制限したり、+- を使うことで浮動小数点数の誤差を吸収している。

 

 

Source code

• mogproject/example-scalacheck

 

References

• User Guide · rickynils/scalacheck Wiki
• Scalaのユニットテスト入門 - seratch's weblog in Japanese
• Scala逆引きレシピ - 翔泳社の本
  <= テストデータをTableで持たせる方法など、より詳細が書かれています
• ScalaCheck: The Definitive Guide
  <= どのようなプロパティを考えるべきかなどの指針も書かれており、実用的な内容

Counting Number of Trailing Zeros in Scala

Scala: 末尾から続く0の個数を数える

 

与えられた64ビット整数値に対して、それを2進数にしたときに末尾から0が何個連続するかを求めたい。

たとえば十進数 88 の場合、2進数にすると 1011000 となるので、答えは 3 となる。

これは、ntz (number of trailing zeros) として知られる典型的なビット操作の問題である。

 

今回はそれを Scala で解くコードをいくつか準備し、その性能を比較してみた。

 

環境

• CPU: 1.8 GHz Intel Core i5
• OS: Mac OS X 10.9.4
• Scala: 2.11.2
• sbt: 0.13.5
• sbt-jmh: 0.1.6

 

Scala での実装

 

1ビットずつシフトして数える

いかにもコストが重そうだが、find を使って最初にビットの立った位置を探す方法。
x は負数をとることもあるので、符号なしの右シフト(>>>)が必要な点に注意。

1 2	def ntzNaive(x: Long): Int =   (0 until 64).find(i => ((x >>> i) & 1L) != 0L).getOrElse(64)

var を使って工夫 (2種類)

1 2 3 4 5 6 7 8 9 10 11 12 13

def ntzLoop1(x: Long): Int = {   var y = ~x & (x - 1)   var n = 0   while (y != 0) {n += 1; y >>>= 1}   n }   def ntzLoop2(x: Long): Int = {   var y = x   var n = 64   while (y != 0) {n -= 1; y <<= 1}   n }

二分探索木を用いた方法 (3種類)

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 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130

def ntzBinarySearch1(x: Long): Int = {   if (x == 0L) {     64   } else {     var n = 1     var y = x     if ((y & 0x00000000ffffffffL) == 0L) {n += 32; y >>>= 32}     if ((y & 0x000000000000ffffL) == 0L) {n += 16; y >>>= 16}     if ((y & 0x00000000000000ffL) == 0L) {n += 8; y >>>= 8}     if ((y & 0x000000000000000fL) == 0L) {n += 4; y >>>= 4}     if ((y & 0x0000000000000003L) == 0L) {n += 2; y >>>= 2}     n - (y & 1L).toInt   } }   def ntzBinarySearch2(x: Long): Int = {   if (x == 0L) {     64   } else {     var n = 63     var y = 0L     var z = x << 32; if (z != 0) {n -= 32; y = z}     z = y << 16; if (z != 0) {n -= 16; y = z}     z = y << 8; if (z != 0) {n -= 8; y = z}     z = y << 4; if (z != 0) {n -= 4; y = z}     z = y << 2; if (z != 0) {n -= 2; y = z}     z = y << 1; if (z != 0) n -= 1     n   } }   def ntzBinarySearch3(x: Long): Int = {   if (x == 0L)     64   else     if ((x & 0xffffffffL) != 0L)       if ((x & 0xffffL) != 0L)         if ((x & 0xffL) != 0L)           if ((x & 0xfL) != 0L)             if ((x & 3L) != 0L)               if ((x & 1L) != 0L) 0 else 1             else               if ((x & 4L) != 0L) 2 else 3           else             if ((x & 0x30L) != 0L)               if ((x & 0x10L) != 0L) 4 else 5             else               if ((x & 0x40L) != 0L) 6 else 7         else           if ((x & 0xf00L) != 0L)             if ((x & 0x300L) != 0L)               if ((x & 0x100L) != 0L) 8 else 9             else               if ((x & 0x400L) != 0L) 10 else 11           else             if ((x & 0x3000L) != 0L)               if ((x & 0x1000L) != 0L) 12 else 13             else               if ((x & 0x4000L) != 0L) 14 else 15       else         if ((x & 0xff0000L) != 0L)           if ((x & 0xf0000L) != 0L)             if ((x & 30000L) != 0L)               if ((x & 10000L) != 0L) 16 else 17             else               if ((x & 40000L) != 0L) 18 else 19           else             if ((x & 0x300000L) != 0L)               if ((x & 0x100000L) != 0L) 20 else 21             else               if ((x & 0x400000L) != 0L) 22 else 23         else           if ((x & 0xf000000L) != 0L)             if ((x & 0x3000000L) != 0L)               if ((x & 0x1000000L) != 0L) 24 else 25             else               if ((x & 0x4000000L) != 0L) 26 else 27           else             if ((x & 0x30000000L) != 0L)               if ((x & 0x10000000L) != 0L) 28 else 29             else               if ((x & 0x40000000L) != 0L) 30 else 31     else       if ((x & 0xffff00000000L) != 0L)         if ((x & 0xff00000000L) != 0L)           if ((x & 0xf00000000L) != 0L)             if ((x & 0x300000000L) != 0L)               if ((x & 0x100000000L) != 0L) 32 else 33             else               if ((x & 0x400000000L) != 0L) 34 else 35           else             if ((x & 0x3000000000L) != 0L)               if ((x & 0x1000000000L) != 0L) 36 else 37             else               if ((x & 0x4000000000L) != 0L) 38 else 39         else           if ((x & 0xf0000000000L) != 0L)             if ((x & 0x30000000000L) != 0L)               if ((x & 0x10000000000L) != 0L) 40 else 41             else               if ((x & 0x40000000000L) != 0L) 42 else 43           else             if ((x & 0x300000000000L) != 0L)               if ((x & 0x100000000000L) != 0L) 44 else 45             else               if ((x & 0x400000000000L) != 0L) 46 else 47       else         if ((x & 0xff000000000000L) != 0L)           if ((x & 0xf000000000000L) != 0L)             if ((x & 3000000000000L) != 0L)               if ((x & 1000000000000L) != 0L) 48 else 49             else               if ((x & 4000000000000L) != 0L) 50 else 51           else             if ((x & 0x30000000000000L) != 0L)               if ((x & 0x10000000000000L) != 0L) 52 else 53             else               if ((x & 0x40000000000000L) != 0L) 54 else 55         else           if ((x & 0xf00000000000000L) != 0L)             if ((x & 0x300000000000000L) != 0L)               if ((x & 0x100000000000000L) != 0L) 56 else 57             else               if ((x & 0x400000000000000L) != 0L) 58 else 59           else             if ((x & 0x3000000000000000L) != 0L)               if ((x & 0x1000000000000000L) != 0L) 60 else 61             else               if ((x & 0x4000000000000000L) != 0L) 62 else 63 }

対数計算を利用

1 2 3 4 5 6 7 8 9

private[this] val ln2 = math.log(2)   def ntzLogarithm(x: Long): Int =   if (x == 0L)     64   else if (x == 0x8000000000000000L)     63   else     (math.log(x & -x) / ln2).toInt

ハッシュを利用 (黒魔術)

1 2 3 4 5 6

private[this] val ntzHash = 0x03F566ED27179461L private[this] lazy val ntzTable: Array[Int] =   (0 until 64).map(i => (ntzHash << i >>> 58).toInt -> i).sorted.map(_._2).toArray   def ntzHash(x: Long): Int =   if (x != 0L) ntzTable((((x & -x) * ntzHash) >>> 58).toInt) else 64

 

ネイティブでの実装

C++ のインラインアセンブリを使って x86-64の命令を直接呼び出す。
それを JNI/JNA でラップして Scala から呼び出した。




JNI (Java Native Interface)

• C++ コード

1 2 3 4 5 6 7 8 9 10 11 12

#include <jni.h>   extern "C" JNIEXPORT jint JNICALL Java_com_github_mogproject_util_BitOperation_ntzJni   (JNIEnv *env, jobject obj, jlong x) {   if (x == 0) return 64;   int pos = 0;   __asm__(     "bsf %1,%q0;"     :"=r"(pos)     :"rm"(x));   return pos; }

• ビルド

$ g++ -dynamiclib -O3 \ -I/usr/include -I$JAVA_HOME/include -I$JAVA_HOME/include/darwin \ bitops_jni.cpp -o libbitops_jni.dylib

• Scala コード

1 2 3 4 5 6 7 8 9 10 11 12 13

package com.github.mogproject.util   class BitOperation {   @native def ntzJni(x: Long): Int }   object BitOperation {   System.load("/path/to/libbitops_jni.dylib")     private[this] val bitop = new BitOperation     def ntzJni(x: => Long) = bitop.ntzJni(x) }

JNA (Java Native Access)

• C++ コード

1 2 3 4 5 6 7 8 9

extern "C" int ntz(unsigned long long x) {   if (x == 0) return 64;   int pos = 0;   __asm__(     "bsf %1,%q0;"     :"=r"(pos)     :"rm"(x));   return pos; }

• ビルド

$ g++ -dynamiclib -O3 bitops_jna.cpp -o libbitops_jna.dylib

• Scala コード

1 2 3 4 5 6

private[this] val lib =   com.sun.jna.NativeLibrary.getInstance("/path/to/libbitops_jna.dylib")   private[this] val func = lib.getFunction("ntz")   def ntzJna(x: Long): Int = func.invokeInt(Array(x.asInstanceOf[Object]))

 

テスト

とりあえず REPL でランダムなLong型整数を与え、全てのメソッドの結果が一致することを確認。

scala> import com.github.mogproject.util.BitOperation._ import com.github.mogproject.util.BitOperation._   scala> def f(x: Long) = Seq(ntzNaive(x), ntzLoop1(x), ntzLoop2(x),      | ntzBinarySearch1(x), ntzBinarySearch2(x), ntzBinarySearch3(x), ntzLogarithm(x),      | ntzHash(x), ntzJni(x), ntzJna(x)) f: (x: Long)Seq[Int]   scala> f(0) res0: Seq[Int] = List(64, 64, 64, 64, 64, 64, 64, 64, 64, 64)   scala> f(-1) res1: Seq[Int] = List(0, 0, 0, 0, 0, 0, 0, 0, 0, 0)   scala> f(0x8000000000000000L) res2: Seq[Int] = List(63, 63, 63, 63, 63, 63, 63, 63, 63, 63)   scala> Seq.fill(1000)(scala.util.Random.nextLong) forall (f(_).toSet.size == 1) res3: Boolean = true

 

ベンチマーク

sbt-jmh でベンチマークを取る。

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

import com.github.mogproject.util.BitOperation import org.openjdk.jmh.annotations.{Benchmark, Scope, State => JmhState}   import scala.util.Random     @JmhState(Scope.Thread) class BitOperationBench {   val random = new Random(12345)     @Benchmark def ntzNaive(): Unit = BitOperation.ntzNaive(random.nextLong())     @Benchmark def ntzLoop1(): Unit = BitOperation.ntzLoop1(random.nextLong())   @Benchmark def ntzLoop2(): Unit = BitOperation.ntzLoop2(random.nextLong())     @Benchmark def ntzBinarySearch1(): Unit = BitOperation.ntzBinarySearch1(random.nextLong())   @Benchmark def ntzBinarySearch2(): Unit = BitOperation.ntzBinarySearch2(random.nextLong())   @Benchmark def ntzBinarySearch3(): Unit = BitOperation.ntzBinarySearch3(random.nextLong())     @Benchmark def ntzLogarithm(): Unit = BitOperation.ntzLogarithm(random.nextLong())   @Benchmark def ntzHash(): Unit = BitOperation.ntzHash(random.nextLong())     @Benchmark def ntzJni(): Unit = BitOperation.ntzJni(random.nextLong())   @Benchmark def ntzJna(): Unit = BitOperation.ntzJna(random.nextLong()) }

測定結果

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

[info] Running org.openjdk.jmh.Main -i 10 -wi 10 -f1 -t1 .*BitOperation.*   (snip)   [info] Benchmark                                          Mode  Samples         Score  Score error  Units [info] c.g.m.m.u.b.BitOperationBench.ntzBinarySearch1    thrpt       10  35184555.294   147974.730  ops/s [info] c.g.m.m.u.b.BitOperationBench.ntzBinarySearch2    thrpt       10  35130401.937   234705.330  ops/s [info] c.g.m.m.u.b.BitOperationBench.ntzBinarySearch3    thrpt       10  29846819.149   352975.842  ops/s [info] c.g.m.m.u.b.BitOperationBench.ntzHash             thrpt       10  35127105.013   127143.455  ops/s [info] c.g.m.m.u.b.BitOperationBench.ntzJna              thrpt       10   1396115.477    16139.308  ops/s [info] c.g.m.m.u.b.BitOperationBench.ntzJni              thrpt       10  25644475.628   231921.707  ops/s [info] c.g.m.m.u.b.BitOperationBench.ntzLogarithm        thrpt       10  35144781.544    92927.496  ops/s [info] c.g.m.m.u.b.BitOperationBench.ntzLoop1            thrpt       10  30099013.164   308642.730  ops/s [info] c.g.m.m.u.b.BitOperationBench.ntzLoop2            thrpt       10  15183889.536   142090.869  ops/s [info] c.g.m.m.u.b.BitOperationBench.ntzNaive            thrpt       10  14309678.759   317520.811  ops/s

飛び抜けて良いものがある、という訳ではなく
BinarySearch1, BinarySearch2, Logarithm, Hash が先頭グループとしてほぼ同等の成績。

JNI はやはり関数コールのペナルティが大きいのか、実用には厳しいレベル。
JNA は一つだけ桁違いに性能が悪かった。

やはり計測あるのみ。
"Trust no one, bench everything." を実感した。

 

References

• 404 Blog Not Found:C - でも一番右端の立っているビット位置を求めてみた
• chessprogramming - BitScan
• A Simple Java Native Interface (JNI) example in Java and Scala

 

 

Related Posts

• mog project: Micro Benchmark in Scala - Using sbt-jmh

Micro Benchmark in Scala - Using sbt-jmh

Scala でマイクロベンチマーク - sbt-jmh を使ってみる

 

sbt-jmh は、sbt コンソールの中で、Java のマイクロベンチマークツールである jmh を扱えるようにする
sbt プラグインである。

Scala のマイクロベンチマークにデファクトスタンダードが存在するかどうかは分からないが、

• scala.testing.Benchmark は Scala 2.11 で廃止
• Google Caliper は最近メンテナンスがされていない?

といった経緯もあり、今回触れてみることにした。

 

環境

• OS: Mac OS X 10.9.4
• Scala: 2.11.2
• sbt: 0.13.5
• sbt-jmh: 0.1.6

 

sbt 定義ファイルの設定

まずは sbt の各種設定ファイルにプラグインの追加設定を行う。

• plugins.sbt
  

  addSbtPlugin("pl.project13.scala" % "sbt-jmh" % "0.1.6")

• build.sbt (利用時のみ)
  

  jmhSettings

• Build.scala (利用時のみ/一例)
  

  import pl.project13.scala.sbt.SbtJmh._   sbt.Project(...).settings(jmhSettings: _*)

 

ベンチマーク対象コードの記述

src/main/scala 配下の任意の .scala ファイルに適当なクラスを作って(objectではダメ）、
測定したいメソッドにアノテーション @org.openjdk.jmh.annotations.Benchmark を付けるだけでよい。

• 例: 数値の Set/List を作成し、contains メソッドを実行するまでの所要時間を計測
  

  1 2 3 4 5 6 7 8 9

  import org.openjdk.jmh.annotations.Benchmark   class ContainsBench {   @Benchmark   def setContains(): Unit = (1 to 100000).toSet.contains(100001)     @Benchmark   def listContains(): Unit = (1 to 100000).toList.contains(100001) }

• クラス内で状態を保持したり、パラメータ付きのメソッドを定義したい場合は
  @State など他のアノテーションの利用が必要
  

  1 2 3 4 5 6 7 8 9 10 11 12 13

  import org.openjdk.jmh.annotations.{Benchmark, Scope, State}   @State(Scope.Thread) class ContainsBench {   val xs = (1 to 100000).toSet   val ys = (1 to 100000).toList     @Benchmark   def setContains(): Unit = xs.contains(100001)     @Benchmark   def listContains(): Unit = ys.contains(100001) }

 

ベンチマークの実行

コードの準備が終わったら、sbt を起動。(マルチプロジェクトの場合は対象プロジェクトへ移動)

run -l でベンチマーク一覧、run -h でヘルプが表示される (オプションは非常に豊富)。

• 全てのベンチマークの実行
  

  run -i 3 -wi 3 -f1 -t1

  
  -i でイテレーション回数、
  -wi でウォームアップイテレーション(測定前に実行される繰り返し)回数を指定。
  正確な測定を行うためには、それぞれ最低でも10〜20回を指定すべきとのこと。
  
  -f はフォークする数の指定。この回数だけウォームアップ+実測が繰り返される。
  -t はスレッド数。とりあえずは 1 を指定すれば良さそうだ。
  
  また、いくつかの測定モードが用意されているが、デフォルトではスループット計測モードとなる。
• 特定のベンチマークの実行
  公式ドキュメントに載っていた例。ワイルドカードを使えるようだ。

  run -i 3 -wi 3 -f1 -t1 .*FalseSharing.*

• 実行結果の例
  

  [info] Running org.openjdk.jmh.Main -i 3 -wi 3 -f1 -t1 [info] # VM invoker: /Library/Java/JavaVirtualMachines/1.7.0.jdk/Contents/Home/jre/bin/java [info] # VM options: <none> [info] # Warmup: 3 iterations, 1 s each [info] # Measurement: 3 iterations, 1 s each [info] # Timeout: 10 min per iteration [info] # Threads: 1 thread, will synchronize iterations [info] # Benchmark mode: Throughput, ops/time [info] # Benchmark: com.github.mogproject.util.ContainsBench.listContains [info] [info] # Run progress: 0.00% complete, ETA 00:00:12 [info] # Fork: 1 of 1 [info] # Warmup Iteration   1: 35.322 ops/s [info] # Warmup Iteration   2: 40.904 ops/s [info] # Warmup Iteration   3: 46.665 ops/s [info] Iteration   1: 39.450 ops/s [info] Iteration   2: 42.116 ops/s [info] Iteration   3: 41.535 ops/s [info] [info] [info] Result: 41.033 ±(99.9%) 25.573 ops/s [Average] [info]   Statistics: (min, avg, max) = (39.450, 41.033, 42.116), stdev = 1.402 [info]   Confidence interval (99.9%): [15.461, 66.606] [info] [info] [info] # VM invoker: /Library/Java/JavaVirtualMachines/1.7.0.jdk/Contents/Home/jre/bin/java [info] # VM options: <none> [info] # Warmup: 3 iterations, 1 s each [info] # Measurement: 3 iterations, 1 s each [info] # Timeout: 10 min per iteration [info] # Threads: 1 thread, will synchronize iterations [info] # Benchmark mode: Throughput, ops/time [info] # Benchmark: com.github.mogproject.util.ContainsBench.setContains [info] [info] # Run progress: 50.00% complete, ETA 00:00:07 [info] # Fork: 1 of 1 [info] # Warmup Iteration   1: 4.550 ops/s [info] # Warmup Iteration   2: 6.826 ops/s [info] # Warmup Iteration   3: 6.980 ops/s [info] Iteration   1: 6.730 ops/s [info] Iteration   2: 6.901 ops/s [info] Iteration   3: 6.798 ops/s [info] [info] [info] Result: 6.810 ±(99.9%) 1.569 ops/s [Average] [info]   Statistics: (min, avg, max) = (6.730, 6.810, 6.901), stdev = 0.086 [info]   Confidence interval (99.9%): [5.241, 8.380] [info] [info] [info] # Run complete. Total time: 00:00:15 [info] [info] Benchmark                              Mode  Samples   Score  Score error  Units [info] c.g.m.u.ContainsBench.listContains    thrpt        3  41.033       25.573  ops/s [info] c.g.m.u.ContainsBench.setContains     thrpt        3   6.810        1.569  ops/s

  contains メソッド自体は Set のほうが圧倒的に速いものの、toSet のコストが大きいため List バージョンのほうが良いスループットが出ることがわかった。

より高度な使い方は公式ドキュメントや以下を参照。

 

 

References

• sbt-jmhを使って、Scalaでマイクロベンチマーク - Starlight
• Javaのマイクロベンチマークツール「JMH」 - Taste of Tech Topics

Scala: How to define initial commands of REPL in SBT

Scala: SBTのREPL起動時に自動で実行されるコマンドを定義する

 

sbt console (マルチプロジェクトの場合は sbt project_name/console)を実行すると
プロジェクトの実行環境が完全にセットアップされた状態で REPL が立ち上がる。

このとき sbt の Key である initialCommands を定義すれば、
その内容がREPL初期化時に自動的に実行されるようになる。

• Configure and use Scala — sbt Documentation

毎回手で打つと面倒な import 文や、ちょっと試すためのデータなどを定義すると非常に捗る。

initialCommands in console := "import your.package.name._"

 

参考: initialCommands を駆使した例

• scalikejdbc/build.sbt at master · scalikejdbc/scalikejdbc
  REPL起動時にテスト用DBが自動でセットアップされる。とてもユーザーライクな作りだ。

Cogito ergo sum

常々思うこと。

 

この世界は、私の認識によって成り立っている。

 

私が認識できないもの、すなわち知覚できないもの、知識として得られない有象無象は

そこに存在していないことと何一つ変わらない。

 

私は、私の死後の世界を認識することはできない。

その時、私という自我が失われることを、知識として身につけているからだ。

したがって、私の死後の世界は、私にとって存在しないものである。

 

ゆえに、私が死ぬことはない。

永遠に生き続けねばならないのだ。

 

 

何処に矛盾があるだろうか。

C++: How to Get Per-Core CPU Usage in Mac

C++: Mac環境でコア単位のCPU使用率を測定する

 

環境

• OS X: 10.9

 

コード

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 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77

#include <stdio.h> #include <unistd.h> #include <mach/mach_host.h> #include <mach/processor_info.h> #include <iostream>   using namespace std;   class CpuUsage {  public:   CpuUsage(int core): core_(core) {     prev = updated_ticks_(core);   }     float get() {     Ticks t = updated_ticks_(core_);     unsigned long long int used = t.used() - prev.used();     unsigned long long int total = t.total() - prev.total();     prev = t;     return (float)used / (float)total * 100.0f;   }    private:   struct Ticks {     unsigned long long int usertime;     unsigned long long int nicetime;     unsigned long long int systemtime;     unsigned long long int idletime;       unsigned long long int used() { return usertime + nicetime + systemtime; }     unsigned long long int total() { return usertime + nicetime + systemtime + idletime; }   } prev;     int core_;     Ticks updated_ticks_(int core) {     unsigned int cpu_count;     processor_cpu_load_info_t cpu_load;     mach_msg_type_number_t cpu_msg_count;       int rc =  host_processor_info(       mach_host_self( ),       PROCESSOR_CPU_LOAD_INFO,       &cpu_count,       (processor_info_array_t *) &cpu_load,       &cpu_msg_count     );     if (rc != 0) {       printf("Error: failed to scan processor info (rc=%d)\n", rc);       exit(1);     }       if (core < 0 || cpu_count <= core) {       printf("Error: invalid core number: %d\n", core);       exit(1);     }     unsigned long long int usertime = cpu_load[core].cpu_ticks[CPU_STATE_USER];     unsigned long long int nicetime = cpu_load[core].cpu_ticks[CPU_STATE_NICE];     unsigned long long int systemtime = cpu_load[core].cpu_ticks[CPU_STATE_SYSTEM];     unsigned long long int idletime = cpu_load[core].cpu_ticks[CPU_STATE_IDLE];       Ticks t = {usertime, nicetime, systemtime, idletime};     return t;   }   };   int main() {   CpuUsage a(0), b(1), c(2), d(3);   sleep(1);   printf("%6.2f, %6.2f, %6.2f, %6.2f\n", a.get(), b.get(), c.get(), d.get());   sleep(1);   printf("%6.2f, %6.2f, %6.2f, %6.2f\n", a.get(), b.get(), c.get(), d.get());   sleep(1);   printf("%6.2f, %6.2f, %6.2f, %6.2f\n", a.get(), b.get(), c.get(), d.get());   return 0; }

(need improvement)

 

実行例

78.00,  72.73,  85.00,  72.00 78.00,  57.00,  72.00,  56.57 82.00,  83.00,  90.00,  88.00

 

 

References

• htop-osx/ProcessList.c at master · max-horvath/htop-osx

Scala: Tackling with sbt-assembly

Scala: sbt-assembly を使う

Scala プロジェクト全体の jar ファイルを作るツールは色々あるが
ここ最近は sbt-assembly がデファクトスタンダードの座を確立したという感が強い。

導入

• project/assembly.sbt の作成
  

  README に従い、以下の内容をのファイルを project/assembly.sbt として保存する。

  addSbtPlugin("com.eed3si9n" % "sbt-assembly" % "0.11.2")

• Build.scala の編集
  

  build.sbt ではなく project/Build.scala に sbt の設定を書く場合の例。
  インポート文を以下のように書き、Project の settings に assemblySettings を追加する。

  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 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46

  import sbt._ import sbt.Keys._ import sbtassembly.Plugin._ import AssemblyKeys._   object Build extends Build {   lazy val buildSettings = Seq(     organization := "your.organization",     version := "0.1.0",     scalaVersion := "2.11.2",     scalacOptions ++= Seq(       "-encoding", "utf-8",       "-target:jvm-1.7",       "-deprecation",       "-unchecked",       "-Xlint",       "-feature"     ),     javacOptions ++= Seq(       "-encoding", "utf-8",       "-source", "1.7",       "-target", "1.7"     )   )     lazy val dependencySettings = Seq(     resolvers ++= Seq(       // your resolvers     ),     libraryDependencies ++= Seq(       // your library dependencies     )   )     // configure prompt to show current project   override lazy val settings = super.settings :+ {     shellPrompt := { s => s"${Project.extract(s).currentProject.id}> " }   }     lazy val root = Project(     id = "projectname",     base = file("."),     settings = super.settings ++ buildSettings ++       dependencySettings ++ assemblySettings   ) }

  プロンプト文字列を変える設定は、spray/Build.scala at master · spray/spray から拝借した。

実行

sbt プロンプトの中で assembly と打つだけ。

projectname> assembly

OS のシェルから実行する場合は

$ sbt assembly

target/scala-X.X/projectname-assembly-X.X.X.jar が作成される。

jar ファイルの実行例

$ java $JAVA_OPTIONS -jar target/scala-X.X/projectname-assembly-X.X.X.jar

 

コンフリクトの解決

sbt-assembly に限らないが、jar 作成にあたって大半の時間は「依存関係スパゲッティ」との格闘に奪われる。

application.conf

例えば、複数プロジェクトでそれぞれ別の application.conf を利用している場合、デフォルトでは以下のようなエラーが出る。

java.lang.RuntimeException: deduplicate: different file contents found in the following: application.conf application.conf         at sbtassembly.Plugin$Assembly$.sbtassembly$Plugin$Assembly$$applyStrategy$1(Plugin.scala:253)         at sbtassembly.Plugin$Assembly$$anonfun$15.apply(Plugin.scala:270)         at sbtassembly.Plugin$Assembly$$anonfun$15.apply(Plugin.scala:267)   *snip*   [error] (projectname/*:assembly) deduplicate: different file contents found in the following: [error] application.conf [error] application.conf

この場合、適切な mergeStrategy を作りこむ必要がある。

例えば、以下のように。
MergeStrategy.concat を指定すれば、application.conf という名前のファイルはその内容が全て結合される。

1 2 3 4 5 6 7 8 9 10 11 12 13 14

lazy val assemblyAdditionalSettings = Seq(   mergeStrategy in assembly ~= { (old) => {     case "application.conf" => MergeStrategy.concat     case x => old(x)   }   } )   lazy val root = Project(   id = "projectname",   base = file("."),   settings = super.settings ++ buildSettings ++     dependencySettings ++ assemblySettings ++ assemblyAdditionalSettings )

同様のファイルが複数あるなら、以下のように指定すればよい。

case "application.conf" | "settings.conf" => MergeStrategy.concat

 

slf4j + logback

例えば、libraryDependencies に以下のように記述すると、assembly 実行時に class ファイルのコンフリクトが発生する。

"ch.qos.logback" % "logback-classic" % "1.1.2", "org.slf4j" % "slf4j-simple" % "1.7.7", "org.slf4j" % "slf4j-api" % "1.7.7", "org.slf4j" % "slf4j-ext" % "1.7.7",

[error] (projectname/*:assembly) deduplicate: different file contents found in the following: [error] /Users/xxxxxx/.ivy2/cache/ch.qos.logback/logback-classic/jars/logback-classic-1.1.2.jar:org/slf4j/impl/StaticLoggerBinder.class [error] /Users/xxxxxx/.ivy2/cache/org.slf4j/slf4j-simple/jars/slf4j-simple-1.7.7.jar:org/slf4j/impl/StaticLoggerBinder.class

• そもそも、必要なライブラリは何かを確認
  

  上記の例の場合、そもそも logback-classic と slf4j-simple を両方使っているのが間違い。
  slf4j-simple の記述を消せばよい。 => 参考

• 依存ライブラリの除外設定
  

  複数のライブラリが、バージョンの異なる同じライブラリに依存している場合、libraryDependencies に exclude を指定する。

  Exclude specific transitive deps

  libraryDependencies ++= Seq(   ("org.apache.spark" %% "spark-core" % "0.8.0-incubating").     exclude("org.mortbay.jetty", "servlet-api").     exclude("commons-beanutils", "commons-beanutils-core").     exclude("commons-collections", "commons-collections").     exclude("commons-collections", "commons-collections").     exclude("com.esotericsoftware.minlog", "minlog") )

• それでもダメなら、mergeStrategy に手を付ける
  

  パスに対してパターンマッチを適用し、適切なマージ方法を設定。

  Merge Strategy

  mergeStrategy in assembly <   {     case PathList("javax", "servlet", xs @ _*)         => MergeStrategy.first     case PathList(ps @ _*) if ps.last endsWith ".html" => MergeStrategy.first     case "application.conf" => MergeStrategy.concat     case "unwanted.txt"     => MergeStrategy.discard     case x => old(x)   } }

 

その他の便利設定

テスト中は assembly を無効に

test in assembly := {}

エントリポイントの指定

明示したほうが可読性が上がりそう。

mainClass in assembly := Some("your.app.Boot")

scala-library を含めない

jar ファイルをダイエットさせたい場合。

assemblyOption in assembly ~= { _.copy(includeScala = false) }

ただ scala-library.jar 自体は 6MB 程度しかないので、含めておいたとしてもそんなに気にならないと思う。

最終的にはこのような形になった。

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 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56

import sbt._ import sbt.Keys._ import sbtassembly.Plugin._ import AssemblyKeys._    object Build extends Build {   lazy val buildSettings = Seq(     organization := "your.organization",     version := "0.1.0",     scalaVersion := "2.11.2",     scalacOptions ++= Seq(       "-encoding", "utf-8",       "-target:jvm-1.7",       "-deprecation",       "-unchecked",       "-Xlint",       "-feature"     ),     javacOptions ++= Seq(       "-encoding", "utf-8",       "-source", "1.7",       "-target", "1.7"     )   )      lazy val dependencySettings = Seq(     resolvers ++= Seq(       // your resolvers     ),     libraryDependencies ++= Seq(       // your library dependencies     )   )     lazy val assemblyAdditionalSettings = Seq(     test in assembly := {},     mainClass in assembly := Some("your.app.Boot"),     mergeStrategy in assembly ~= { (old) => {       case "application.conf" => MergeStrategy.concat       case x => old(x)     }     }   )     // configure prompt to show current project   override lazy val settings = super.settings :+ {     shellPrompt := { s => s"${Project.extract(s).currentProject.id}> " }   }      lazy val root = Project(     id = "projectname",     base = file("."),     settings = super.settings ++ buildSettings ++       dependencySettings ++ assemblySettings ++ assemblyAdditionalSettings   ) }

Top N Sorter in Scala

Scala: トップNソートの実装

 

比較可能な大きな集合 $M$ に対して上位 $N$ 件のソート結果を取得したい。

この局面では一般にヒープソートが有効なので、PriorityQueue を使ってみる。

 

1 2 3 4 5 6 7 8 9 10 11 12

import scala.collection.mutable.PriorityQueue   class TopNSorter[A](n: Int)(ord: Ordering[A]) {   private[this] val data = PriorityQueue()(ord.reverse)     def insert(item: A): Unit = {     data += item     if (data.size > n) data.dequeue   }     def result(): Seq[A] = data.dequeueAll.reverse }

insert は $O(\log N)$ になるはず。(要素の追加は $O(\log N)$, サイズ取得と先頭要素へのアクセスは$O(1)$)
$M$ 件挿入すれば $O(M\log N)$。
result は $O(N)$ だが、$N$ が小さい前提なので問題ない。

1 2 3 4 5 6 7

scala> val x = new TopNSorter[Int](100)(Ordering.Int) x: TopNSorter[Int] = TopNSorter@520f1862   scala> (1 to 10000000) foreach x.insert   scala> x.result res1: Seq[Int] = Vector(10000000, 9999999, 9999998, 9999997, 9999996, 9999995, 9999994, 9999993, 9999992, 9999991, 9999990, 9999989, 9999988, 9999987, 9999986, 9999985, 9999984, 9999983, 9999982, 9999981, 9999980, 9999979, 9999978, 9999977, 9999976, 9999975, 9999974, 9999973, 9999972, 9999971, 9999970, 9999969, 9999968, 9999967, 9999966, 9999965, 9999964, 9999963, 9999962, 9999961, 9999960, 9999959, 9999958, 9999957, 9999956, 9999955, 9999954, 9999953, 9999952, 9999951, 9999950, 9999949, 9999948, 9999947, 9999946, 9999945, 9999944, 9999943, 9999942, 9999941, 9999940, 9999939, 9999938, 9999937, 9999936, 9999935, 9999934, 9999933, 9999932, 9999931, 9999930, 9999929, 9999928, 9999927, 9999926, 9999925, 9999924, 9999923, 9999922, 9999921, 9999920, 9999919, 9999918, 9999917, 9999916, 9999915...

単に

1	scala> (1 to 10000000).sorted.reverse.take(100)

とするよりはずっと速い。

もう少しスマートに書けそうなものだけど。。。

IVA Reading: Chapter 02, Section 06 Exercises

IVA読書会 chap02-sect06 宿題

 

No.5

lex順序でS多項式を求める計算問題。

RECAP

$$S(f, g) = \frac{x^\gamma}{{\scriptstyle \text{LT}}(f)}\cdot f - \frac{x^\gamma}{{\scriptstyle \text{LT}}(g)}\cdot g$$
where $$x^\gamma = \text{LCM}({\scriptstyle \text{LM}}(f), {\scriptstyle \text{LM}}(g))$$

計算には PARI/GP を利用。
ただ Leading Term を返す関数が見つからなかったので、LM, LC を手で計算して与えた。

1 2 3 4 5 6 7 8 9 10

? spol(f, g, lm_f, lm_g, lc_f, lc_g) = lcm(lm_f, lm_g)/(lm_f * lc_f) * f - lcm(lm_f, lm_g)/(lm_g * lc_g) * g %11 = (f,g,lm_f,lm_g,lc_f,lc_g)->lcm(lm_f,lm_g)/(lm_f*lc_f)*f-lcm(lm_f,lm_g)/(lm_g*lc_g)*g ? spol(4*x^2*z - 7*y^2, x*y*z^2 + 3*x*z^4, x^2*z, x*y*z^2, 4, 1) %12 = -3*z^4*x^2 - 7/4*z*y^3 ? spol(x^4*y - z^2, 3*x*z^2 - y, x^4*y, x*z^2, 1, 3) %18 = 1/3*y^2*x^3 - z^4 ? spol(x^7*y^2*z + 2*i*x*y*z, 2*x^7*y^2*z + 4, x^7*y^2*z, x^7*y^2*z, 1, 2) %17 = 2*i*z*y*x - 2 ? spol(x*y + z^3, z^2 - 3*z, x*y, z^2, 1, 1) %15 = 3*z*y*x + z^5

a.
$\begin {eqnarray*} S(4x^2z - 7y^2, xyz^2 + 3xz^4) &=& \frac{x^2yz^2}{4x^2z}\cdot (4x^2z - 7y^2) - \frac{x^2yz^2}{xyz^2}\cdot (xyz^2 + 3xz^4)\\ &=& \frac{1}{4}yz \cdot (4x^2z - 7y^2) - x \cdot (xyz^2 + 3xz^4) \\ &=& x^2yz^2 - \frac{7}{4}y^3z - x^2yz^2 - 3x^2z^4 \\ &=& -3x^2z^4-\frac{7}{4}y^3z \end {eqnarray*}$

以下、途中式は省略。

b.
$S(x^4y - z^2, 3xz^2 - y) = \frac{1}{3}x^3y^2 - z^4$

c.
$S(x^7y^2z + 2ixyz, 2x^7y^2z + 4) = 2ixyz - 2$

d.
$S(xy+z^3, z^2-3z) = 3xyz + z^5$

 

No.11




左辺を変形

$$\begin {eqnarray*} S(x^\alpha f, x^\beta g) &=& \frac{\text{LCM}({\scriptstyle \text{LM}}(x^\alpha f), {\scriptstyle \text{LM}}(x^\beta g))}{{\scriptstyle \text{LT}}(x^\alpha f)}\cdot x^\alpha f - \frac{\text{LCM}({\scriptstyle \text{LM}}(x^\alpha f), {\scriptstyle \text{LM}}(x^\beta g))}{{\scriptstyle \text{LT}}(x^\beta g)}\cdot x^\beta g \\ &=& \frac{\text{LCM}(x^\alpha {\scriptstyle \text{LM}}(f), x^\beta {\scriptstyle \text{LM}}(g))}{x^\alpha {\scriptstyle \text{LT}}(f)}\cdot x^\alpha f - \frac{\text{LCM}(x^\alpha {\scriptstyle \text{LM}}(f), x^\beta {\scriptstyle \text{LM}}(g))}{x^\beta {\scriptstyle \text{LT}}(g)}\cdot x^\beta g \\ &=& \frac{\text{LCM}(x^\alpha {\scriptstyle \text{LM}}(f), x^\beta {\scriptstyle \text{LM}}(g))}{{\scriptstyle \text{LT}}(f)}\cdot f - \frac{\text{LCM}(x^\alpha {\scriptstyle \text{LM}}(f), x^\beta {\scriptstyle \text{LM}}(g))}{{\scriptstyle \text{LT}}(g)}\cdot g \end {eqnarray*}$$

右辺を変形

$$\begin {eqnarray*} x^\gamma S(f,g) &=& x^\gamma \cdot \Bigl(\frac{\text{LCM}({\scriptstyle \text{LM}}(f), {\scriptstyle \text{LM}}(g))}{{\scriptstyle \text{LT}}(f)}\cdot f - \frac{\text{LCM}({\scriptstyle \text{LM}}(f), {\scriptstyle \text{LM}}(g))}{{\scriptstyle \text{LT}}(g)}\cdot g\Bigr) \\ &=& \frac{\text{LCM}(x^\alpha {\scriptstyle \text{LM}}(f), x^\beta {\scriptstyle \text{LM}}(g))}{\text{LCM}({\scriptstyle \text{LM}}(f), {\scriptstyle \text{LM}}(g))} \cdot \Bigl(\frac{\text{LCM}({\scriptstyle \text{LM}}(f), {\scriptstyle \text{LM}}(g))}{{\scriptstyle \text{LT}}(f)}\cdot f - \frac{\text{LCM}({\scriptstyle \text{LM}}(f), {\scriptstyle \text{LM}}(g))}{{\scriptstyle \text{LT}}(g)}\cdot g\Bigr) \\ &=& \text{LCM}(x^\alpha {\scriptstyle \text{LM}}(f), x^\beta {\scriptstyle \text{LM}}(g)) \cdot \Bigl(\frac{1}{{\scriptstyle \text{LT}}(f)}\cdot f - \frac{1}{{\scriptstyle \text{LT}}(g)}\cdot g\Bigr) \\ &=& \frac{\text{LCM}(x^\alpha {\scriptstyle \text{LM}}(f), x^\beta {\scriptstyle \text{LM}}(g))}{{\scriptstyle \text{LT}}(f)}\cdot f - \frac{\text{LCM}(x^\alpha {\scriptstyle \text{LM}}(f), x^\beta {\scriptstyle \text{LM}}(g))}{{\scriptstyle \text{LT}}(g)}\cdot g \end {eqnarray*}$$

したがって、$S(x^\alpha f, x^\beta g) = x^\gamma S(f,g)$

□

 

また、
$\text{LCM}(x^\alpha {\scriptstyle \text{LM}}(f), x^\beta {\scriptstyle \text{LM}}(g)) = \text{LCM}({\scriptstyle \text{LM}}(x^\alpha f), {\scriptstyle \text{LM}}(x^\beta g))$
${\scriptstyle \text{LM}}(f) \mid {\scriptstyle \text{LM}}(x^\alpha f)$
${\scriptstyle \text{LM}}(g) \mid {\scriptstyle \text{LM}}(x^\alpha g)$
より、
$\text{LCM}({\scriptstyle \text{LM}}(f), {\scriptstyle \text{LM}}(g)) \mid \text{LCM}(x^\alpha {\scriptstyle \text{LM}}(f), x^\beta {\scriptstyle \text{LM}}(g))$

$x^\alpha$, $x^\beta$, ${\scriptstyle \text{LM}}(f)$, ${\scriptstyle \text{LM}}(g)$ はいずれも単項式であるから、$x^\gamma$ もまた単項式である。

How to Make a Transpose of 2D-Array in Scala

Scala: 2次元配列を転置する方法

 

要素数 $M \times N$ の 2次元配列 $A$ に対して、$A_{ij} = B_{ji} \, (1 \le i \le M,\, 1 \le j \le N)$ となるような
$N \times M$ の2次元配列 $B=A^T$ を作成したい。

Scala の Array クラスには、そのものズバリ transpose というメソッドがある。

• Scala Standard Library 2.11.2 - Array - Scala Standard Library 2.11.2 - scala.Array

1 2 3 4 5

scala> val a = Array(Array(1,2,3),Array(4,5,6),Array(7,8,9),Array(10,11,12)) a: Array[Array[Int]] = Array(Array(1, 2, 3), Array(4, 5, 6), Array(7, 8, 9), Array(10, 11, 12))   scala> a.transpose res0: Array[Array[Int]] = Array(Array(1, 4, 7, 10), Array(2, 5, 8, 11), Array(3, 6, 9, 12))

これを利用すれば、文字列を区切って縦に結合するような処理もシンプルに記述できる。

1 2 3 4 5 6 7 8 9 10 11 12

scala> val s = """      | abc 123      | def 456      | """ s: String = " abc 123 def 456 "   scala> s.split('\n').withFilter(!_.isEmpty).map(_.split("[ ]+")).transpose map (_.mkString) res1: Array[String] = Array(abcdef, 123456)

　

　

References

• Matrix transposition - Rosetta Code

Scala: How to Merge Two Maps with Summing Values

Scala: Map の値を加算しながらマージする

 

Scalaz を使うとシンプル。

sbt 設定例

libraryDependencies += "org.scalaz" %% "scalaz-core" % "7.0.6"

実行例

1 2 3 4 5

scala> import scalaz.Scalaz._ import scalaz.Scalaz._   scala> Map('a -> 10, 'b -> 20, 'c -> 30) |+| Map('a -> 5, 'c -> 7, 'd -> 9) res0: scala.collection.immutable.Map[Symbol,Int] = Map('a -> 15, 'c -> 37, 'd -> 9, 'b -> 20)

引き算をするなら、こんな感じだろうか。

1 2	scala> Map('a -> 10, 'b -> 20, 'c -> 30) |+| Map('a -> 5, 'c -> 7, 'd -> 9).mapValues(-_) res1: scala.collection.immutable.Map[Symbol,Int] = Map('a -> 5, 'c -> 23, 'd -> -9, 'b -> 20)

 

 

References

• Nimrod's Tech Blog » Scala Map Merge

Scala: Getting Started with Akka-HTTP

Scala: Akka-HTTP を試してみる

 

Akka-HTTP とは、Spray++ という位置づけの新進気鋭の HTTPサーバ フレームワーク。
Reactive Stream を使って実装されているのが大きな特徴。

Spray は ベンチマーク で Finagle や wai (Haskell) に圧勝している。
Akka-HTTP もその流れを引き継ぎ、ハイパフォーマンスサーバに適したフレームワークになるだろうと期待している。

これまで Spray すら使ったことがなかったのだが、少しだけ Akka-HTTP に触れてみる。

 

Hello World with Akka-HTTP


/ping にアクセスすると "PONG" を返すシンプルな Webサーバを作る。

project/Build.scala

Build.scala

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 32 33 34 35 36 37 38 39 40 41 42 43

import sbt._ import sbt.Keys._   object ApplicationBuild extends Build {   lazy val buildSettings = Seq(     organization := "com.github.mogproject",     version      := "0.1.0-SNAPSHOT",     scalaVersion := "2.11.1",     scalacOptions ++= Seq(       "-deprecation",       "-unchecked",       "-feature",       "-encoding", "utf-8"     ),     javacOptions ++= Seq(       "-source", "1.7"     )   )     lazy val resolverSettings = Seq(     resolvers ++= Seq(       "Sonatype OSS Releases" at "http://oss.sonatype.org/content/repositories/releases",       "Sonatype OSS Snapshots" at "http://oss.sonatype.org/content/repositories/snapshots",       "Typesafe Repository" at "http://repo.typesafe.com/typesafe/releases/"     ),     libraryDependencies ++= Seq(       "org.scalatest" %% "scalatest" % "2.2.0" % "test",       "com.typesafe" % "config" % "1.2.1",       "com.typesafe.akka" %% "akka-http-core-experimental" % "0.4",       "com.typesafe.akka" %% "akka-stream-experimental" % "0.4"     )   )     lazy val testSettings = Seq(     parallelExecution in Test := true   )     lazy val root = Project(     id = "akka-http-example",     base = file("."),     settings = super.settings ++ buildSettings ++ resolverSettings ++ testSettings   ) }

src/main/resources/application.conf

application.conf

akka {   loglevel = INFO }

src/main/scala/Boot.scala

• Scala Days 2014 資料のサンプルコード そのままでは型推論周りでコンパイルエラーとなった。

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

import akka.io.IO import akka.http.Http   import akka.actor.ActorSystem import akka.pattern.ask import akka.util.Timeout import akka.http.model._ import akka.http.model.HttpMethods._ import scala.concurrent.duration._ import akka.stream.scaladsl.Flow   object Boot extends App {   import system.dispatcher   implicit val system = ActorSystem()   implicit val askTimeout: Timeout = 500.millis     val bindingFuture = IO(Http) ? Http.Bind("localhost", 8080)     bindingFuture foreach { binding =>     Flow(binding.connectionStream) foreach { connection =>       Flow(connection.requestProducer).map {         case HttpRequest(GET, Uri.Path("/ping"), _, _, _) =>           HttpResponse(entity = "PONG!")         case _ => HttpResponse(404, entity = "Unknown resource!")       }.produceTo(connection.responseOut)     }   } }

[error] akka-http-example/src/main/scala/Boot.scala:20: value connectionStream is not a member of Any [error]     Flow(binding.connectionStream) foreach { connection ⇒ [error]                  ^ [error] one error found [error] (compile:compile) Compilation failed

• 以下のように修正したら、動いた

Boot.scala

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

import akka.io.IO import akka.http.Http   import akka.actor.ActorSystem import akka.pattern.ask import akka.util.Timeout import akka.stream.{MaterializerSettings, FlowMaterializer} import akka.http.model._ import akka.http.model.HttpMethods._ import scala.concurrent.duration._ import akka.stream.scaladsl.Flow   object Boot extends App {   import system.dispatcher   implicit val system = ActorSystem()   implicit val askTimeout: Timeout = 500.millis     val materializer = FlowMaterializer(MaterializerSettings())   val bindingFuture = IO(Http) ? Http.Bind("localhost", 8080)     bindingFuture foreach { case Http.ServerBinding(localAddress, connectionStream) =>     Flow(connectionStream).foreach { case Http.IncomingConnection(remoteAddress, requestProducer, responseConsumer) =>       Flow(requestProducer).map {         case HttpRequest(GET, Uri.Path("/ping"), _, _, _) =>           HttpResponse(entity = "PONG!")         case _ => HttpResponse(404, entity = "Unknown resource!")       }.produceTo(materializer, responseConsumer)     }.consume(materializer)   } }

$ curl http://localhost:8080/ping PONG! $ curl http://localhost:8080/pin Unknown resource!

 

ルーティング

ロードマップによると、spray-routing に相当する DSLライブラリが akka-http (akka-http-core ではない) に組み込まれる予定とのこと。

現時点ではまだ無いのでパターンマッチで何とかするしかなさそう。

• 公式ドキュメントにかかれていたサンプル

1 2 3 4 5 6 7 8 9 10 11 12

import HttpMethods._   val requestHandler: HttpRequest ⇒ HttpResponse = {   case HttpRequest(GET, Uri.Path("/"), _, _, _) ⇒     HttpResponse(       entity = HttpEntity(MediaTypes.`text/html`,         "<html><body>Hello world!</body></html>"))     case HttpRequest(GET, Uri.Path("/ping"), _, _, _) ⇒ HttpResponse(entity = "PONG!")   case HttpRequest(GET, Uri.Path("/crash"), _, _, _) ⇒ sys.error("BOOM!")   case _: HttpRequest ⇒ HttpResponse(404, entity = "Unknown resource!") }

 

References

• Parleys.com - akka-http: (un)REST for your Actors by Mathias Doenitz
• Scala Documentation — Akka Documentation
• API ドキュメント
• Sprayの簡単な紹介 - アドファイブ日記