Tech Tips: 1月 2016

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日木曜日

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を作成することができるサービス。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

解き方
数論の知識が必要。

d(x)をxの約数の個数とすると、gcd(a, b) = 1のとき、d(ab) = d(a) d(b)となる。
nの約数の総積は、n^(d(n)/2)となる。
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の勉強をした。オフィシャルサイトのどこを見ると何が載っているかをメモしておく。

https://docs.docker.com/engine/installation/mac/

Macにdockerをインストール

https://docs.docker.com/engine/userguide/dockerizing/

コンテナの実行（インタラクティブコンテナ）

コンテナの実行（デーモナイズドコンテナ）

https://docs.docker.com/engine/userguide/usingdocker/

Python Flaskアプリケーションの実行

port binding（自動設定、port番号指定）

コンテナで動作するアプリケーションのログ確認

コンテナで動いているプロセスの確認

コンテナの停止

コンテナの再起動

コンテナの削除

https://docs.docker.com/engine/userguide/dockerimages/

ローカルのhostにあるdocker imageの確認

docker imageの取得

docker imageの検索

docker imageの作成

Dockerfileを使ったimageの作成

既存imageへのタグ設定

Docker Hubにimageをpush

docker imageの削除

https://docs.docker.com/engine/userguide/networkingcontainers/

コンテナに名前をつける

ネットワークの作成

ネットワークを指定してコンテナを起動

起動中のコンテナのシェルを開く

同一ネットワークで動作するコンテナへの接続

https://docs.docker.com/engine/userguide/dockervolumes/

Data volumeの追加

ホストディレクトリをdata volumeとしてマウント

OS X, windowsでDocker Machineを使っている場合のマウント方法

Data Volume Containerを使ったコンテナ間のデータ共有

Data volumeを使ったバックアップ、リストア、マイグレイーション

https://docs.docker.com/engine/userguide/dockerrepos/

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（公式ページ）

登録: 投稿 (Atom)

Tech Tips

Page List

Search on the blog