Page List

Search on the blog

2016年1月24日日曜日

redis入門

redisとは?
  • NoSQLデータベース
  • Key-Value型のデータストア
  • Cで実装されている
  • インメモリで動作するDB

インストール
Mac OSの場合は、homebrewからインストールできます。
$ brew install redis

起動
LaunchAgentsに登録して起動。
$ ln -sfv /usr/local/opt/redis/*.plist ~/Library/LaunchAgents
$ launchctl load ~/Library/LaunchAgents/homebrew.mxcl.redis.plist
サーバがListenしていることを確認。
$ lsof -i -nP | grep $(pgrep redis)

サンプル
CRUD処理のサンプルです。
処理はredisクライアントを使って実行します。
$ redis-cli

まずは、Create処理から。
127.0.0.1:6379> HMSET user:0001 name "Taro Yamada" email "taro_yama@test.com"
OK

次に、Read処理。
ハッシュ全体のRead、ハッシュのフィールドを指定したReadができます。
127.0.0.1:6379> HGETALL user:0001
1) "name"
2) "Taro Yamada"
3) "email"
4) "taro_yama@test.com"
127.0.0.1:6379> 
127.0.0.1:6379> HMGET user:0001 name
1) "Taro Yamada"

それから、Update処理。
emailフィールドを更新します。
127.0.0.1:6379> HSET user:0001 email "taro_yama@test.co.jp"
(integer) 0
127.0.0.1:6379> HMGET user:0001 email
1) "taro_yama@test.co.jp"

最後にDelete処理。
フィールドの削除、キーの削除を行ってみます。
127.0.0.1:6379> HDEL user:0001 email
(integer) 1
127.0.0.1:6379> HGETALL user:0001
1) "name"
2) "Taro Yamada"
127.0.0.1:6379> DEL user:0001
(integer) 1
127.0.0.1:6379> HGETALL user:0001
(empty list or set)

2016年1月23日土曜日

MongoDB入門

mongoDBとは?
  • NoSQLのデータベース
  • Document指向データベース
  • C++で記述されている
  • データをJSONライクな形式で管理する
  • RDBのように固定的なフィールド定義をもたない
インストール
Mac OSにインストールします。
$ brew update
$ brew install mongodb

起動
$ ln -sfv /usr/local/opt/mongodb/*.plist ~/Library/LaunchAgents
$ launchctl load ~/Library/LaunchAgents/homebrew.mxcl.mongodb.plist
mongdデーモンがlistenしていることを確認。
$ lsof -i -nP | grep $(pgrep mongod)
mongod    2074 kenjih    6u  IPv4 0xc2212eb1f557f05      0t0  TCP 127.0.0.1:27017 (LISTEN)

語句
基本的な語句をRDBとの対比で。
MongoDB RDB
コレクション テーブル
ドキュメント レコード

サンプル実行
基本的なCRUD処理のサンプル。
$ mongo
> // ドキュメント登録
> db.employees.save({name:"Taro Yamada",age:20,job:"Engineer",email:"taro_yamada@test.co.jp"})
WriteResult({ "nInserted" : 1 })
> db.employees.save({name:"Hanako Suzuki",age:30,job:"Manager",email:"hanako_suzuki@test.co.jp"})
WriteResult({ "nInserted" : 1 })
>
> // コレクション内の全ドキュメント取得
> db.employees.find() 
{ "_id" : ObjectId("56a327228881c1ea39a5e261"), "name" : "Taro Yamada", "age" : 20, "job" : "Engineer", "email" : "taro_yamada@test.co.jp" }
{ "_id" : ObjectId("56a327308881c1ea39a5e262"), "name" : "Hanako Suzuki", "age" : 30, "job" : "Manager", "email" : "hanako_suzuki@test.co.jp" }
>
> // キーワード指定検索(完全一致)
> db.employees.find({name:"Taro Yamada"})
{ "_id" : ObjectId("56a327228881c1ea39a5e261"), "name" : "Taro Yamada", "age" : 20, "job" : "Engineer", "email" : "taro_yamada@test.co.jp" }
>
> // キーワード指定検索(Like)
> db.employees.find({email:/test.co.jp/})
{ "_id" : ObjectId("56a327228881c1ea39a5e261"), "name" : "Taro Yamada", "age" : 20, "job" : "Engineer", "email" : "taro_yamada@test.co.jp" }
{ "_id" : ObjectId("56a327308881c1ea39a5e262"), "name" : "Hanako Suzuki", "age" : 30, "job" : "Manager", "email" : "hanako_suzuki@test.co.jp" }
>
> // 1件のみ取得
> db.employees.findOne({email:/test.co.jp/})
{
 "_id" : ObjectId("56a327228881c1ea39a5e261"),
 "name" : "Taro Yamada",
 "age" : 20,
 "job" : "Engineer",
 "email" : "taro_yamada@test.co.jp"
}
>
> // ドキュメント件数取得
> db.employees.count({age: {$lt: 30}})  // 30歳未満
1
>
> // ドキュメント更新
> db.employees.update({'name':'Taro Yamada'}, {$set: { age: 21}})
WriteResult({ "nMatched" : 1, "nUpserted" : 0, "nModified" : 1 })
>
> // ドキュメント削除
> db.employees.remove({})
WriteResult({ "nRemoved" : 2 })
>
> // コレクション削除
> db.employees.drop()
true
> 

2016年1月21日木曜日

メモ化再帰のキャッシュは処理の最初でやる

 メモ化再帰で答えをキャッシュする場合、
  1. 処理の最後にキャッシュする
  2. 処理の最初にキャッシュする
という2つの書き方がある。自分はだいたい前者の書き方で書いていた。

このような感じ。
int dp[100][100];

int rec(int x, int y) {
  if (dp[x][y] != -1)
    return dp[x][y];

  int ret = 0;
  // do some calculation                                                                                                       

  return dp[x][y] = ret;
}
しかし上のような書き方だと、// do some calculationの中でx, yの値を書き換えてしまうとバグってしまう。
まあ落ち着いていればそのようなミスはないかもしれないが、コンテスト本番で慌てているとそのようなミスが発生するかもしれない。// do some calculationの処理が長くて複雑な場合はすぐにバグの原因を発見できないかもしれない。

このようなバグを予防するには、以下のような後者の書き方の方が良さそうだ。
int dp[100][100];

int rec(int x, int y) {
  int &ret = dp[x][y];
  if (ret != -1)
    return ret;

  ret = 0;
  // do some calculation                                                                                                       

  return ret;
}
というちょいTIPSな話でした。

2016年1月17日日曜日

中国料理店過程

中国料理店過程とは?
  • 離散時刻で確率的に変化する過程
  • 中国料理店に客がやってきたときに、どの円卓に座るかを考える
  • 店には無数の円卓があり、円卓には無数の人が座れるものとする
  • 最初の客は空の円卓に座る
  • 2番目以降の客はランダムに円卓を選ぶが、座っている人の数が多い円卓を好む
  • 数学的には[1,2,3,...,n]のpartitionがランダムに作成されることになり、数学者はこのpartitionの確率分布に興味を持つらしい
  • ノンパラメトリックなベイズメソッドに応用される
モデリング
より一般化されたモデルもあるみたいだが、一番簡単なモデルを考える。

最初の客は空の円卓に座る。
n番目(n > 1)の客は、|b_i|/nの確率で円卓b_iに座る。もしくは、1/nの確率で空の円卓に座る。ただし、|b_i|は円卓b_iに座っている客の人数を表す。

サンプルプログラム
これだけだと何が嬉しいかわからない。ベイズにどうやって応用するか勉強したい。
from random import random
from bisect import bisect_left
import numpy as np

n = 100       # number of customers
block = []    # partition

for i in range(n):
    if not block:
        block.append([i])
    else:
        x = random()
        p = np.cumsum([1.0*len(b)/(i+1) for b in block])
        pos = bisect_left(p, x)
        if pos >= len(block):
            block.append([i])
        else:
            block[pos].append(i)
    print block

2016年1月16日土曜日

Jukedeckで無料でBGMを作成する

Jukedeckとは?
 無料でBGMを作成することができるサービス。TechCrunch Disrupt London 2015の優勝サービス。Royalty-Freeなので、著作権関連の問題を気にせず自由に使える。また、作成したBGMはダウンロードすることができ、月5回のダウンロードまでは無料。
 作成したビデオにちょっとしたBGMを付けたいときに使えそうだ。

何曲か作ってみた
 作ってみたと言っても、以下の3つを選択してボタンをポチっとするだけ。
  • 曲のジャンル
  • 曲調
  • 曲の長さ
Red Approval
まずはロックっぽい曲。Rock - Angry - 1:00とした。
激しいギターバッキングからリードギターが入ってくる。ドラムとベースもいい感じに入ってくる。

Receding Works
Ambient - Sparse - 1:00とした。 落ち着く感じの環境音楽が出来上がった。

Impossible Path
Folk - Melancholic - 1:00とした。注文どおり哀愁漂うフォークが出来上がった。

Music from Jukedeck - create your own at jukedeck.com

2016年1月13日水曜日

Codeforces Round #338 Multipliers

問題概要
とても大きな数nがある。
nの素因数が与えられるので、nの約数の総積をmod 1000000007で求めよ。

制約
nの素因数の個数 <= 200,000
2 <= nの素因数 <= 200,000

解き方
数論の知識が必要。
  1. d(x)をxの約数の個数とすると、gcd(a, b) = 1のとき、d(ab) = d(a) d(b)となる。
  2. nの約数の総積は、n^(d(n)/2)となる。
  3. gcd(a, n) = 1のとき、a^x = a^(x % (n-1)) (mod n)となる。
1. はdivisor関数はmultiplicativeという有名な話。因数分解された数の約数の個数を高速に数える方法を理解していれば確かにそうだと分かる。

2. は最近知った。これは、約数を昇順に列挙したものと、降順に列挙したものを上下に並べて、上下の積を取ればそうなることが分かる。

3. は知らなかった。modで計算するとき冪乗の右肩の数は%取っていけないのは知っていたけど、mod nのときは% (n-1)を計算すればいいらしい。これはフェルマーの小定理から導ける。

サンプル解
上の3つを組み合わせて解く。詳しい式変形はeditorial参照。
#include <iostream>
#include <map>

using namespace std;

const long long MOD = 1e9 + 7;

long long mpow(long long x, long long p, long long mod) {
  long long ret = 1;
  while (p) {
    if (p & 1)
      ret = ret * x % mod;
    x = x * x % mod;
    p >>= 1;
  }
  return ret;
}

int main(int argc, char *argv[])
{
  int m;
  cin >> m;
  map<long long, int> p;

  for (int i = 0; i < m; i++) {
    long long x;
    cin >> x;
    ++p[x];
  }

  long long ret = 1;
  long long d = 1;
  for (const auto& pr : p) {
    long long x = pr.first;
    long long k = pr.second;

    long long f = mpow(x, k*(k+1)/2, MOD);
    ret = mpow(ret, k+1, MOD) * mpow(f, d, MOD) % MOD;
    d = d * (k+1) % (MOD-1);
  }
  
  cout << ret << endl;
  
  return 0;
}

2016年1月10日日曜日

Dockerメモ

 Dockerの勉強をした。オフィシャルサイトのどこを見ると何が載っているかをメモしておく。

Macにdockerをインストール

コンテナの実行(インタラクティブコンテナ)
コンテナの実行(デーモナイズドコンテナ)

Python Flaskアプリケーションの実行
port binding(自動設定、port番号指定)
コンテナで動作するアプリケーションのログ確認
コンテナで動いているプロセスの確認
コンテナの停止
コンテナの再起動
コンテナの削除

ローカルのhostにあるdocker imageの確認
docker imageの取得
docker imageの検索
docker imageの作成
Dockerfileを使ったimageの作成
既存imageへのタグ設定
Docker Hubにimageをpush
docker imageの削除

コンテナに名前をつける
ネットワークの作成
ネットワークを指定してコンテナを起動
起動中のコンテナのシェルを開く
同一ネットワークで動作するコンテナへの接続

Data volumeの追加
ホストディレクトリをdata volumeとしてマウント
OS X, windowsでDocker Machineを使っている場合のマウント方法
Data Volume Containerを使ったコンテナ間のデータ共有
Data volumeを使ったバックアップ、リストア、マイグレイーション

Dockerコマンドを使ったDocker Hubへのアクセス
Automated BuildsによるGitHubとのsync

2016年1月1日金曜日

[TED] Regina Hartley: Why the best hire might not have the perfect resume


 Silver Spoon(エリート大学出身の成績優秀な人)とScrapper(三流大学出身のジョブホッパー)どちらを選ぶべきかという話。

  Scrapperは不採用となることが多いが、彼らには逆境を乗り越えるために必要なエネルギー、対処法などが備わっている可能性もある。例えばスティーブ・ジョブズは未婚の両親から生まれ、生まれてすぐ養子に出された。大学を中退しているし、ジョブホッパーだ。その上、失読症だった。しかし、彼は偉大なビジネスリーダーだ。
 アメリカでは調査を行った企業家のうち35%が失読症を持っていることがわかった。彼らは、失読症というハンディキャップを回避するため、人の話をよく聴き細部まで注意を払うという企業家にとって必須となるスキルを身につけたのだ。
 多様な人材を採用する企業はパフォーマンスがすぐれているということも明らかになった。調査によると、多様な人材を採用する企業のうちトップ50社は、S&P500よりも25%効率的な成果を上げているという。

graph-toolでグラフのビジュアライズ

 Pythonのgraph-toolというライブラリを使うとグラフ(ネットワーク)の美しいビジュアライズが出来る。公式サイトを見るとアニメーションなども作れるようでなかなか面白そう。
 とりあえずサンプルとして、Warshall Floydで有向グラフを強連結成分分解して色分けするということをやってみた。

インストール
homebrewでインストールできる。
brew tap homebrew/science
brew install graph-tool

有向グラフの作成
from graph_tool.all import *

v_num = 8
edges = [
    [0,1,0,0,0,0,0,0],
    [0,0,1,0,0,0,0,0],
    [1,0,0,1,0,0,0,0],
    [0,0,0,0,1,0,0,0],
    [0,0,0,0,0,1,0,0],
    [0,0,0,0,0,0,1,0],
    [0,0,0,0,1,0,0,1],
    [0,0,0,0,1,0,0,0]
]

g = Graph()
v = g.add_vertex(v_num)
for i in xrange(v_num):
    for j in xrange(v_num):
        if edges[i][j] == 1:
            g.add_edge(i, j)

graph_draw(g, vertex_text=g.vertex_index, vertex_font_size=15,
            output_size=(600, 600), output="directed_graph.png")
以下が作成された画像。


強連結成分分解
dp = [edge[:] for edge in edges]
for k in xrange(v_num):
    for i in xrange(v_num):
        for j in xrange(v_num):
            dp[i][j] |= dp[i][k] & dp[k][j]

scc_grp = g.new_vertex_property("int")
for i in xrange(v_num):
    if g.vertex(i) in scc_grp.__dict__: continue
    scc_grp[g.vertex(i)] = i
    for j in xrange(v_num):
        if dp[i][j] & dp[j][i]:
            scc_grp[g.vertex(j)] = i

graph_draw(g, vertex_text=g.vertex_index, vertex_font_size=15, 
           vertex_fill_color = scc_grp, output_size=(600, 600), output="directed_graph_scc.png")
以下が作成された画像。成分ごとに色分けされている。

参考ページ
Quick start using graph-tool(公式ページ)
graph_tool.draw - Graph drawing and layout(公式ページ)