Tech Tips: 6月 2016

2016年6月27日月曜日

便利なPythonライブラリ（７）Cerberus

Pythonでバリデーション処理を書くときは、Cerberusというライブラリが便利そう。

インストール

pipで。

$ pip install cerberus

サンプル
バリデーションの定義をdictで定義して、Validatorのコンストラクタに渡す。

from cerberus import Validator

schema = {
    "url": {'required': True, 'type': 'string'},
    "title": {'required': True, 'type': 'string'},
    "links" : {'type': 'list', 'schema': {'type': 'string'}},
    "imgs": {'type': 'list', 'schema': {'type': 'dict', \
                 'schema': {'tag': {'type': 'string'}, 'url': {'type': 'string'}}}},
    "pv": {'required': True, 'type': 'integer', 'min': 0}
}
validator = Validator(schema)

これで、validatorができた。

上から説明すると、
urlは必須項目。型はstring。
titleは必須項目。型はstring。
linksはオプション項目。型はstringのリスト。
imgsはオプション項目。型はtag, urlというキーをもつdictのリスト。ただし、tag、url共にstring。
pvは必須項目。型はinteger。最小値は0。

データを作ってバリデーションしてみる。

document = {
    "url": "http://example.com/validator/test.html",
    "links": ['http://example.com/test1.html', 'http://example.com/test2.html'],
    "imgs": [{'tag': 'pic1', 'url': 'img/pic1.png'}],
    "pv": 10
}

if validator.validate(document):
    print ("success!")
else:
    print ("fail!")
    print (validator.errors)

実行結果。

fail!
{'title': 'required field'}

という風になかなか直感的で使い易い。もちろん拡張して自前のバリデーション定義も作成できる。

2016年6月25日土曜日

Codeforces Round #359 (Div. 2) D. Kay and Snowflake

問題概要
ノード数nの木が与えられる。
q個のクエリが飛んでくる。
クエリの入力vに対して、ノードvのcentroidを出力せよ。

解法
自分のすべての子のcentroidが分かっているとする。
すると自分のcentroidは、自分と、最大の部分木を持つ自分の子のパス上にあることが分かる。

実装
dfs1回で書けそうな気もするが、素直に2回に分けて書いた方がよい。

#pragma comment(linker, "/STACK:256000000")

using namespace std;

#define ALL(x) (x).begin(), (x).end()
#define EACH(itr,c) for(__typeof((c).begin()) itr=(c).begin(); itr!=(c).end(); itr++)
#define FOR(i,b,e) for (int i=(int)(b); i<(int)(e); i++)
#define MP(x,y) make_pair(x,y)
#define REP(i,n) for(int i=0; i<(int)(n); i++)

int n, q;
vector<int> ch[300000];
int par[300000];
int maxc[300000];
int centroid[300000];
int sz[300000];

void dfs(int v) {
  sz[v] = 1;
  maxc[v] = 0;
  for (auto &w: ch[v]) {
    dfs(w);
    sz[v] += sz[w];
    maxc[v] = max(maxc[v], sz[w]);
  }
}

bool check(int v, int c) {
  return 2 * (sz[v] - sz[c]) <= sz[v] && 2 * maxc[c] <= sz[v];
}

void centroid_dfs(int v) {
  if (!ch[v].size())
    centroid[v] = v;
  else {
    int c = -1;
    for (auto &w: ch[v]) {
      centroid_dfs(w);
      if (sz[w] == maxc[v])
        c = w;
    }
    c = centroid[c];
    while (!check(v, c))
      c = par[c];
    centroid[v] = c;
  }
}

int main() {
  scanf(" %d %d", &n, &q);
  int v;
  REP (i, n-1) {
    scanf(" %d", &v);
    --v;
    par[i+1] = v;
    ch[v].push_back(i+1);
  }
  dfs(0);
  centroid_dfs(0);
  REP (i, q) {
    scanf(" %d", &v);
    printf("%d\n", centroid[--v]+1);
  }
  return 0;
}

2016年6月24日金曜日

load averageとは

load averageとは？

load = システムが実行しているワークの単位。CPUリソースを使用している or CPUリソースを待っているプロセスの数。
load average = ある時間単位でのloadの平均。

確認方法
uptimeコマンドで。左から、直近1min, 直近5min, 直近15minのload average。

$ uptime
 0:51  up 1 day, 46 mins, 3 users, load averages: 2.05 1.87 2.10

数字が意味するものは？
シングルコアシステムの場合
load average 2.50 = 1.50個のプロセスがCPUの空きを待っている。

load average 0.70 = CPUは30%の時間でアイドル状態にある。

マルチコアシステムの場合

例: CPU4つの場合

load average 4.00 = 4つの異なるプロセスが4つの異なるCPUを使っている。

ということで、load averageがCPU数を超えるとヤバイ状態である。

CPU使用率との違い

シングルコアシステムでCPU使用率が100%というとヤバそうに聞こえる。

しかし、これだけだとシステムがヤバイ状態かどうなのかは何とも言えない。

例えばシステムで計算の多いバッチ処理を回していて、このバッチ以外には実行すべきプロセスがない場合。

CPU使用率100%、load average = 1。

これはバッチがCPUリソースを使えるだけ使って計算しているという状態で、ヤバくはない。

これに対して、webアプリケーションなどイベントドリブン系のシステムで、処理すべきイベントが多発したとき。

CPU使用率100%、load average = 5。

これはヤバい。平均して4つのプロセスが待ち状態にあるということなので、システムのスペックアップを考えた方がよい。

あと、CPU利用率は低いけど、load averageは大きいというパターン。

CPU使用率10%、load average = 10。

IOで処理が詰まってCPUリソースが使えてませんという状態。ボトルネックになっているIOを見つけましょう！という状態。もしくはCPUのコア数多いから減らしてもいいんじゃないという状態。

2016年6月14日火曜日

scalaでneologd版kuromojiを使う

依存ライブラリ
scala-sample/build.sbt

以下の2行が対象。
resolvers += "CodeLibs Repository" at "http://maven.codelibs.org/"
"org.codelibs" % "lucene-analyzers-kuromoji-ipadic-neologd" % "6.0.0-20160519"

lucene-analyzers-kuromoji-ipadic-neologdのバージョンは公式レポジトリを見て最新のものを選ぶといい。

サンプルコード

scala-sample/src/main/scala/com/kenjih/Neologd.scala

サンプル実行結果

ぱるる null 名詞-固有名詞-一般
と null 助詞-並立助詞
こじはる null 名詞-固有名詞-一般
と null 助詞-並立助詞
さや姉 null 名詞-固有名詞-一般
と null 助詞-並立助詞
ゆきりん null 名詞-固有名詞-一般

仕事で使うときは製品名や地名、店名などをうまく分かち書きしてくれるので重宝するはず。
ちなみにデフォルト辞書版kuromojiを使うと、以下のように綺麗に分かち書きできない。

ぱるるとこじはるとさや 名詞,一般,*,*
姉 名詞,一般,*,* 姉
と 助詞,並立助詞,*,*
ゆき 名詞,一般,*,*
りん 副詞,助詞類接続,*,*

2016年6月12日日曜日

便利なPythonライブラリ（６）Invoke

Invokeとは？
Pythonのタスク実行ツールです。
ビルドツールのmakeやRubyのRakeのようなものをPythonで実現できます。
公式ページ: http://www.pyinvoke.org/

サンプル
以下のようなPythonスクリプトをtasks.pyという名前で保存しておきます。
ファイル名はtasks.pyでなければなりません。

from invoke import task, run

@task
def startjob(ctx, taskname, verbose=False, iteration=10):
    print ("starting job...")
    print ("taskname = %s" % taskname)
    print ("verbose = %s" % verbose)
    print ("iteration = %d" % iteration)
    run("ls -l | head -n 5")
    print ("completing job...")

実行例
シェルからinvoke（省略してinvでも可）と入力することで、@taskデコレータが付与された処理を呼び出すことができます。

まずは、実行可能なタスク一覧を表示してみる。

$ inv --list
Available tasks:

  startjob

startjobタスクのhelp表示。

$ inv --help startjob
Usage: inv[oke] [--core-opts] startjob [--options] [other tasks here ...]

Docstring:
  none

Options:
  -i, --iteration
  -t STRING, --taskname=STRING
  -v, --verbose

startjob実行。

$ inv startjob tasks1
starting job...
taskname = tasks1
verbose = False
iteration = 10
total 96
-rw-r--r--  1 kenjih  staff   134  4  2 00:39 counter.py
drwxr-xr-x@ 5 kenjih  staff   170 11 30  2009 examples
-rw-r--r--  1 kenjih  staff   296  4  9 19:46 groupby.py
-rw-r--r--  1 kenjih  staff    95 11 21  2015 hoge.py
completing job...

オプション指定（省略形で指定）。

$ inv startjob tasks1 -v -i 200
starting job...
taskname = tasks1
verbose = True
iteration = 200
total 96
-rw-r--r--  1 kenjih  staff   134  4  2 00:39 counter.py
drwxr-xr-x@ 5 kenjih  staff   170 11 30  2009 examples
-rw-r--r--  1 kenjih  staff   296  4  9 19:46 groupby.py
-rw-r--r--  1 kenjih  staff    95 11 21  2015 hoge.py
completing job...

オプション指定（非省略形で指定）。

$ inv startjob tasks1 --verbose --iteration 300
starting job...
taskname = tasks1
verbose = True
iteration = 300
total 96
-rw-r--r--  1 kenjih  staff   134  4  2 00:39 counter.py
drwxr-xr-x@ 5 kenjih  staff   170 11 30  2009 examples
-rw-r--r--  1 kenjih  staff   296  4  9 19:46 groupby.py
-rw-r--r--  1 kenjih  staff    95 11 21  2015 hoge.py
completing job...

SparkとHadoop MapReduceの違い

-- Apache Hadoop logo and Spark log[1, 2] --

比較まとめ

	Hadoop MapReduce	Spark
速度	高速	MapReduceの10-100倍高速
データ	ディスクに保存ディスクIOに多くの時間を必要とし、レイテンシが大きい	メモリに保存レイテンシが小さい
Real-Time分析	バッチ処理用に設計されているため、得意ではない	ストリーミングデータの分散処理をサポート
Iterative Algorithm	iterationごとに、ディスクからの入力読込、ディスクへの出力書込が必要なため不向き	中間結果をキャッシュし、キャッシュに対して複数のiterationを走らせるため高速
Graph Algorithm	隣接ノードの情報をメッセージングする機構が備わっていない	GraphXというグラフアルゴリズムライブラリが含まれている

速度
MapReduceはHadoopクラスタのメモリを有効活用できていなかった。
SparkではRDD（Resilient Distributed Datasets）を使うことで、データをメモリに保存することができ、必要な場合にのみディスクへの保存を行うことができる。
これにより、SparkはHadoopよりも格段に高速である。

データ
Hadoopはデータをディスクに保存するが、Sparkはメモリに保存する。
SparkはRDD（Resilient Distributed Datasets）とよばれるデータストレージモデルを用いる。RDDはnetwork IOを最小化するフォールトトレランスの機構を提供する。RDDの一部のデータが失われた場合、lineage（データに提供された処理の履歴）を元に再構築が行われる。このためフォールトトレランスのためのレプリケーションが不要となる。
これに対して、Hadoopはフォールトトレランスのためのレプリケーションを必要とする。

Real-timeデータ分析
Twitterのデータを分析する場合などは、毎秒数百万単位で発生するイベントを処理する必要がある。Sparkの利点の一つは、データストリーミングの分散処理をサポートしている点である。標準で提供されるSpark Streamingライブラリを利用することで、バッチジョブを書く場合と同じ方法でストリーミングジョブを書くことができる。
これに対してMapReduceはバッチ分散処理用にデザインされているため、Real-time分析が不得意である。

Iterative Algorithm
多くのデータ分析アルゴリズムはiterative algorithmとよばれる繰り返し処理を必要とする。例えば、k-means、LDA、PageRankなどがその例である。
Hadoopの場合、各iterationでの計算結果をディスクに書き込み、次のiterationで結果をディスクから読み込むという処理が必要なため、iterative algorithmを高速に実行することは困難である。
Sparkではiterationごとの結果をメモリ上に保存しておけるため、高速に計算することができる。またSparkではMLlibというMachine Learning系の処理を行うためのライブラリが標準で提供されている。

Graph Algorithm
グラフ構造のデータに提供するアルゴリズムの多くでは、隣接するノードの情報が必要となる。例えば、PageRankの場合は、自身のノードにリンクを張っているノードのPageRank値が計算に必要になる。
Hadoopの場合、隣接ノードの情報をメッセージするための機能は提供されていない。これに対してSparkではGraphXという標準ライブラリを使うことで、グラフ系のアルゴリズムを効率的に計算することができる。Sparkは、NettyとAkkaのコンビネーションを使ってメッセージの配信を行っている。

参考URL
[1] Apache Hadoop logo, Apache Software Foundation - https://svn.apache.org/repos/asf/hadoop/logos/out_rgb/, Apache License 2.0
[2] Spark Logo, Spark project team - Spark open source project - UC Berkeley, Apache License 2.0
[3] Apache Spark vs Hadoop MapReduce
[4] What is the difference between Apache Spark and Apache Hadoop (Map-Reduce) ? - Quora

2016年6月6日月曜日

SparkのCountVectorizerを使ってみた

NLP系の前処理としてBow行列を作りたい場合、CountVectorizerが便利です。

サンプル

package com.kenjih

import org.apache.spark.{ SparkConf, SparkContext }
import org.apache.spark.ml.feature.CountVectorizer
import org.apache.spark.sql.SQLContext
import org.apache.spark.ml.feature.{ CountVectorizer, CountVectorizerModel }

object CountVectorizerSample {

  def run(sc: SparkContext): Unit = {
    val sqlContext = new SQLContext(sc)
    import sqlContext.implicits._

    val path = "data/sample1.txt"
    val rdd = sc.textFile(path).map { line =>
      val ws = line.split("\t")
      val textId = ws(0)
      val words = ws(1).split(" ")
      (textId, words)
    }
    val df = rdd.toDF("id", "text")

    val cvm: CountVectorizerModel = new CountVectorizer()
      .setInputCol("text")
      .setOutputCol("features")
      .setMinDF(2)
      .fit(df)

    cvm.vocabulary.zipWithIndex.map(_.swap).foreach(println)
    cvm.transform(df).select("features").show()
  }

  def main(args: Array[String]): Unit = {
    val conf = new SparkConf().setAppName("Simple Application")
    val sc = new SparkContext(conf)
    run(sc)
  }
}

実行結果

kenjih$ cat data/sample1.txt 
0 hello hello hello
1 hello world
2 goodbye world
3 I love you
4 you love me% 
kenjih$ 
kenjih$ spark-submit --master local --class com.kenjih.CountVectorizerSample target/scala-2.10/spark-sample.jar
(0,hello)
(1,you)
(2,love)
(3,world)
+-------------------+
|           features|
+-------------------+
|      (4,[0],[3.0])|
|(4,[0,3],[1.0,1.0])|
|      (4,[3],[1.0])|
|(4,[1,2],[1.0,1.0])|
|(4,[1,2],[1.0,1.0])|
+-------------------+

説明

CountVectorizerを適用するcolumnはArray[String]にしておく。
setMinDFでDocument Frequencyの最小値を設定できる。（最小値未満のドキュメントにしか単語はcorpusに含めない）
CountVectorizerModel.vocabularyでcorpusの単語を参照できる。zipWithIndexしておくと、確認のときに便利。

2016年6月5日日曜日

PostgreSQLをコマンドラインから使う

SQLをファイルに保存、ファイル内のSQLを実行、SQL結果をファイルに保存といった頻出処理をコマンドラインから行う方法をまとめた。

設定

~/.zshrc（bashを使う場合は~/.bashrc）に以下を追記して、デフォルトのエディタを設定しておく。

# Postgre SQL
export PSQL_EDITOR="/usr/local/bin/emacs"

追記したら、実行する。

$ source ~/.zshrc

テーブルの作成

例として使うテーブルを作っておく。

kenjih=#  create table emp(
 id int primary key,
 name varchar(32),
 sex char(1),
 age int
);
CREATE TABLE

kenjih=# \d
       List of relations
 Schema | Name | Type  | Owner  
--------+------+-------+--------
 public | emp  | table | kenjih
(1 row)

クエリの編集

\e を使うとエディタが起動し、エディタ上でクエリの編集ができる。

select
  id,
  name,
  sex,
  int
from
  emp

上のクエリを入力し保存する。ここでは~/Sql/select_emp.sqlという場所に保存することにする。
クエリの最後にセミコロンをつけておくと、保存した瞬間に実行されてしまう。この挙動が怖い場合（特にWRITE系処理）は、セミコロンはつけないようにしておくとよい。

クエリの実行
先ほど保存したファイルを実行してみる。
\i [ファイル名]
で指定したファイル内のクエリを実行できる。

kenjih-# \i ~/Sql/emp_select.sql 
 id |      name      | sex | age 
----+----------------+-----+-----
  1 | taro yamada    | M   |  25
  2 | jiro tanaka    | M   |  28
  3 | kyoko imai     | F   |  21
  4 | natsumi hoshii | F   |  30
(4 rows)

保存クエリの確認
一度保存したファイルの内容を確認したい場合は、
\e [ファイル名]
とすればよい。
基本的な使い方としては、\e ファイルで保存したクエリ内容を一度確認して、目的のものと合っていれば\i ファイル名で実行とするのがいい気がする。

クエリバッファのクリア
\e、\iを使って作業をしていると稀にクエリバッファに文字列が残って想定外の挙動になってしまうことがある。そのときは、
\r
を使うとクエリバッファをクリアすることができる。

結果表示のフォーマッティング
aligned/unalignedの切替は
\a
で設定できる。
unalignedの場合は、表の形に整形されない状態で表示される。

id|name|sex|age
1|taro yamada|M|25
2|jiro tanaka|M|28
3|kyoko imai|F|21
4|natsumi hoshii|F|30
(4 rows)

unalignedの場合は区切り文字の設定を
\f [文字]
で行うことができる。

kenjih-# \f '\t'
Field separator is " ".
kenjih-# \i ~/Sql/emp_select.sql 
id name sex age
1 taro yamada M 25
2 jiro tanaka M 28
3 kyoko imai F 21
4 natsumi hoshii F 30
(4 rows)

最後の行数の表示はいらないという場合は、
\pset fotter off
とすればよい。

kenjih-# \pset footer off
Default footer is off.
kenjih-# \i ~/Sql/emp_select.sql 
id name sex age
1 taro yamada M 25
2 jiro tanaka M 28
3 kyoko imai F 21
4 natsumi hoshii F 30

ファイル出力
デフォルトではクエリの結果は標準出力に表示される。
\o [ファイル名]
で指定したファイルに出力することができる。

kenjih-# \o /tmp/test.out
kenjih-# \i ~/Sql/emp_select.sql

ファイルに出力されたことを確認してみる。 \! でpsql内からシェルを起動することができる。

kenjih-# \!
kenjih$ cat /tmp/test.out 
id name sex age
1 taro yamada M 25
2 jiro tanaka M 28
3 kyoko imai F 21
4 natsumi hoshii F 30

2016年6月4日土曜日

Sparkのテンプレートプロジェクトを作る

giter8のtemplatesのリストを参照すると、Sparkのテンプレートがあるようだ。

これを使うと、Sparkのsbtプロジェクトを簡単に作成することができる。

テンプレート生成

$ g8 nttdata-oss/basic-spark-project.g8

A basic spark application project 

name [Basic Spark]: spark-sample
package [com.example]: com.kenjih
version [0.0.1]: 0.0.1
context [anonymous] 3:18 attribute organization isn't defined
context [anonymous] 25:28 attribute organization isn't defined

Template applied in ./spark-sample

生成されたファイルの確認

$ find spark-sample 
spark-sample
spark-sample/assembly.sbt
spark-sample/build.sbt
spark-sample/project
spark-sample/project/assembly.sbt
spark-sample/project/plugins.sbt
spark-sample/README.rst
spark-sample/src
spark-sample/src/main
spark-sample/src/main/scala
spark-sample/src/main/scala/com
spark-sample/src/main/scala/com/kenjih
spark-sample/src/main/scala/com/kenjih/GroupByTest.scala
spark-sample/src/main/scala/com/kenjih/RandomTextWriter.scala
spark-sample/src/main/scala/com/kenjih/SparkHdfsLR.scala
spark-sample/src/main/scala/com/kenjih/SparkLR.scala
spark-sample/src/main/scala/com/kenjih/SparkLRTestDataGenerator.scala
spark-sample/src/main/scala/com/kenjih/SparkPi.scala
spark-sample/src/main/scala/com/kenjih/WordCount.scala
spark-sample/src/main/scala/com/kenjih/Words.scala
spark-sample/src/test
spark-sample/src/test/scala
spark-sample/src/test/scala/com
spark-sample/src/test/scala/com/kenjih
spark-sample/src/test/scala/com/kenjih/SparkPiSpec.scala

設定ファイルの中身を見ておく。
PROJECT_DIR/project/plugins.sbt
sbtプラグインの設定
　- eclipse
　- idea

PROJECT_DIR/project/assembly.sbt

sbtプラグインの設定

　- sbt-assembly

※ sbt-assemblyはプロジェクトと依存ライブラリをまとめてJARにする機能を提供するプラグイン。

PROJECT_DIR/build.sbt

sbtのビルド設定。
　- spark
　- hadoop

PROJECT_DIR/assembly.sbt

sbt-assemblyの定義。jarのファイル名とか。

このファイルの中には以下の記述がある。

run in Compile <<= Defaults.runTask(fullClasspath in Compile, mainClass in (Compile, run), runner in (Compile, run))

これは、"provided"スコープのライブラリもjarに含めるという設定。
これを書かないと"provided"スコープのライブラリはjarファイルには含まれない。
"provided"スコープは、コンテナ（Sparkなど）側で提供されるライブラリなのでアセンブルされるjarからは除外するという意味。
jarファイルはspark-submitするときに使うだけだという場合は、この行は不要なので削除していい気がする。

実行

まずはユニットテストから。

$ sbt test

テストは円周率の計算を乱択で行うもので稀に失敗するので注意。　

次にJarにアセンブルして、spark上で実行してみる。

sbt assembly

PROJECT_DIR/target/scala-2.10/spark-sample.jarが生成される。

このjarをspark-submitして実行する。

spark-submit --master local --class com.kenjih.SparkPi target/scala-2.10/spark-sample.jar

pi: 3.146のように計算された円周率が標準出力に表示される。

sbtプロジェクトをEclipseにインポート

sbteclipseを使うとsbtプロジェクトをEclipseにインポートできる。

sbteclipseとは？
Eclipseのプロジェクト定義を生成してくれるsbtのプラグイン。
https://github.com/typesafehub/sbteclipse

プラグインの定義
PROJECT_DIR/project/plugins.sbtに以下を書く。

addSbtPlugin("com.typesafe.sbteclipse" % "sbteclipse-plugin" % "4.0.0")

プラグインの実行

$ sbt eclipse

プロジェクトファイルが生成されていることを確認。

$ ls -la
total 24
drwxr-xr-x  9 kenjih  staff   306  6  4 17:41 .
drwxr-xr-x  4 kenjih  staff   136  6  4 17:27 ..
-rw-r--r--  1 kenjih  staff  1006  6  4 17:41 .classpath
-rw-r--r--  1 kenjih  staff   360  6  4 17:41 .project
drwxr-xr-x  3 kenjih  staff   102  6  4 17:41 .settings
-rw-r--r--  1 kenjih  staff   339  6  4 17:27 build.sbt
drwxr-xr-x  5 kenjih  staff   170  6  4 17:41 project
drwxr-xr-x  4 kenjih  staff   136  6  4 17:27 src
drwxr-xr-x  4 kenjih  staff   136  6  4 17:41 target

Eclipseへのインポート
File> import> Existing Project into Workspaceからインポート。

giter8でScalaプロジェクトのテンプレートを作る