Search on the blog

2016年10月24日月曜日

IndeedのTech Talkに行ってきた

 先週の木曜日、IndeedのTech Talkに行ってきた。「データに基づく意思決定のアンチパターン」というテーマでトークが行われた。内容自体も大変興味深いものだったが、発表、質疑応答から垣間見えるIndeedのカルチャーに感銘を受けた。それはデータドリブンでものごとが進むということと、失敗に寛容であるということだ。

 質疑応答の時間に、「間違った分析をしたとき、どのようにマネジャーに伝えますか?」というような質問がなされた。自分だったらいろいろと言い訳を考えるかもしれない。間違った分析をしてしまったのはしょうがないと主張するための理由を必死に探すかもしれない。

 この質問に対するIndeedのデータサイエンティストの回答はシンプルなものだった。「間違えをおかしてしまいました。この分析結果は誤りです。」あまりにシンプルな回答に会場には笑いが起きた。そのあと彼はこのように付け加えた。「間違えが許されない職場だったら僕は今日ここに立っていない。今までたくさんの間違えをしてきた。」

 これは失敗を正当化するものではない。エンジニアは失敗が起きないように真摯に課題に取り組むべきだ。しかし失敗は必ず起こる。失敗無くして成功はありえない。失敗を繰り返して成功したのなら、それは成功以外の何物でもない。

 彼は次のような話もしていた。「これまで失敗をしたことがないという人間には二種類の人間がいる。一つは本当に失敗をしたことがない人間。もう一つは失敗をしたことに気づいていない人間。」

 このような文化が日本のIT企業にも広まるといいなと思った。

2016年10月10日月曜日

Lombokを使ってみた

Lombokとは?
Javaのボイラーテンプレートを排除するためのライブラリ。
gettter、setter、toString、...などなどの毎回書かないといけないお決まりのコードをアノテーションから自動生成してくれる。

インストール
gradleの場合は以下をdependenciesに追加。
compile 'org.projectlombok:lombok:1.16.10'

サンプル
getter/setterの定義
package com.kenjih.lombok;

import lombok.Getter;
import lombok.Setter;

public class User {
    @Getter
    @Setter
    private String name;
    
    @Getter
    @Setter
    private int age;
}

toString, equals, hashCodeの定義
package com.kenjih.lombok;

import lombok.EqualsAndHashCode;
import lombok.ToString;

@ToString
@EqualsAndHashCode
public class User {
    private String name;
    private int age;    
}

コンストラクタの定義
package com.kenjih.lombok;

import lombok.AllArgsConstructor;

@AllArgsConstructor
public class User {
    private String name;
    private int age;    
}

他にもいろいろできる。

2016年10月2日日曜日

直線型グラフのマッチング数

 以下のような直線型グラフのマッチングについて考える。
一般にノード数nの直線型グラフからk個のマッチングを選ぶパターン数はn-kCkとなる。

例えば上のグラフの場合(n=6)は、
k = 1なら6-1C= 5、
k = 2なら6-2C= 6、
k = 3なら6-3C= 1
となり、実際に個数を数えてみると正しいことが分かる。

何をやってるかというと、マッチングに使われる枝の左側のノードを選んでいるわけである。普通にノードを選ぶだけだと一つのノードが複数のマッチングに属してしまうかもしれないので、あらかじめ右側の端点に使われるノードを除いておく。

すると左側のノードの選び方により一意にマッチングが決定する。逆にマッチングの選び方に対して、左側のノードの選び方は一意に決まる。よって一対一の対応にあるのでこの方法で数え上げができることが分かる。




モンモール数を包除原理で計算する

 モンモール数を計算するときは漸化式を使えば計算できるが、実は包除原理を使っても計算できるのではないかと思ったので試してみた。

 予想どおり包除原理でも計算できるようだ。
計算量は漸化式を使うとO(N)、包除原理を使うとO(N2)なので漸化式の方が高速。

#include <iostream>
#include <cassert>

using namespace std;

const long long MOD = 1e9 + 7;
const int N = 1000;
long long f[N];
long long comb[N][N];
long long x[N];
long long y[N];

// 漸化式で解く
void solveWithRec() {
  x[0] = 1, x[1] = 0;
  for (int i = 2; i < N; i++)
    x[i] = (i-1) * (x[i-1] + x[i-2]) % MOD;
}

// 包除原理で解く
void solveWithIncExc() {
  f[0] = 1;
  for (int i = 1; i < N; i++)
    f[i] = i * f[i-1] % MOD;

  comb[0][0] = 1;
  for (int i = 1; i < N; i++) {
    comb[i][0] = comb[i][i] = 1;
    for (int j = 1; j < i; j++)
      comb[i][j] = (comb[i-1][j] + comb[i-1][j-1]) % MOD;
  }
  for (int i = 0; i < N; i++) {
    y[i] = f[i];
    for (int j = 1; j <= i; j++) {
      if (j % 2)
        y[i] -= comb[i][j] * f[i-j] % MOD;
      else
        y[i] += comb[i][j] * f[i-j] % MOD;
      y[i] = (y[i] % MOD + MOD) % MOD;
    }
  }
}

int main(int argc, char *argv[])
{
  solveWithRec();
  solveWithIncExc();

  for (int i = 0; i < N; i++)
    assert(x[i] == y[i]);

  cout << "same!" << endl;
  
  return 0;
}

2016年10月1日土曜日

Message QueueとPublish-Subscribeの違い

Messaging Systemには大きく二つの種類がある。
一つがMessage Queueで、もう一つがPublish-Subscribe。

それぞれの特徴、長所、短所を簡単にまとめておく。

Message Queue Publish-Subscribe
特徴 一つのレコードは一つのConsumerが消費する。 一つのレコードはすべてのConsumerに配信される。
長所 データ処理を複数のConsumerインスタンスで並列化できる。 一つのデータを複数のConsumerで利用することができる。
短所 一つのConsumerがデータを読むと、そのデータは消える。 データ処理を並列化できない。

Vagrant + VirtualBox + Ansible

 Ansible簡単で便利なので使った方がいいよーと勧められたので試してみた。

各ソフトウェアの説明
  • Vagrant
    • 仮想環境構築ソフトウェア
    • 設定ファイルを記述することで、仮想環境の構築・設定を自動化できる
  • VirtualBox
    • 仮想化ソフトウェア
    • あるOS上で別のOSを動かすことができる
  • Ansible
    • 構成管理ツール
    • サーバのプロビジョニングを効率化できる

各ソフトウェアのインストール

サンプル
Ubuntuを入れて、nginxをインストールして、nginxを起動するという流れをVagrant + VirtualBox + Ansibleでやってみた。

サンプルは以下のバージョンで動作確認を行った。
  • Vagrant 1.8.6
  • VirtualBox 5.1.6
  • Ansible 2.0.2.0
Ubuntu 14.04のboxを追加
$ vagrant box add ubuntu14.04 \
https://cloud-images.ubuntu.com/vagrant/trusty/current/trusty-server-cloudimg-amd64-vagrant-disk1.box
$ vagrant box list
ubuntu14.04 (virtualbox, 0)

Vagrantfileのテンプレート作成
適当な作業ディレクトリを作成してcdする。
vagrant initすると、Vagrantfileが自動生成される。
$ mkdir ansible_sample
$ cd ansible_sample
$ vagrant init

Vagrantfileの編集
テンプレートを編集して以下を記述する。
config.vm.box = "ubuntu14.04"
config.vm.network "private_network", ip: "192.168.33.10"

config.vm.provision "ansible" do |ansible|
  ansible.playbook = "provisioning/playbook.yml"
  ansible.inventory_path = "provisioning/hosts"
  ansible.limit = 'sample'
end

inventory fileの編集
inventory fileはAnsibleの管理対象を定義するファイル。
今回の場合はUbuntuのVMなのでそのIPアドレスを書いておく。
[sample]のところは好きな名前でよい。
$ mkdir provisioning
$ emacs provisioning/hosts
[sample]
192.168.33.10

playbook作成
hostsにはinventory fileで定義した名前を書く。
become: yesはsudo実行の意味。
$ emacs provisioning/playbook.yml
---
- hosts: sample
  become: yes
  user: vagrant 
  tasks:      
    - name: install nginx
      apt: name=nginx update_cache=yes
    - name: restart nginx
      service: name=nginx state=restarted

実行
実行前にディレクトリ構造が以下のようになっていることを確認。
$ tree
.
├── Vagrantfile
└── provisioning
    ├── hosts
    └── playbook.yml

問題なければ、VMを起動&プロビジョン実施。
$ vagrant up
$ vagrant provision

確認
ゲストOSにsshしてservice statusを調べる。
$ vagrant ssh
vagrant@vagrant-ubuntu-trusty-64:~$ service nginx status
 * nginx is running

ホストOSからcurlしてみる。
$ curl 192.168.33.10 
Welcome to nginx!の文字が表示されればOK。

Codeforces Round #374 (Div. 2) C. Journey

問題
n個の名所がある。
名所間を移動するのに必要な時間が与えられる。
1つ目の名所からスタートして、時間T以内にn個目の名所に辿りつかないといけない。
なるべく多くの名所を周りたい場合、どのような順番で名所を訪れればよいか出力せよ。

解法
本番はダイクストラをした。
他の人のソース見たら、みんなトポロジカル順序でDPしてて焦った。
絶対落ちたわーと絶望していたら通っていた。
が、この問題はトポロジカル順序DPで解いた方がかっこいい。

ソース

using namespace std;

#define REP(i,n) for(int i=0; i<(int)(n); i++)
#define FOR(i,b,e) for (int i=(int)(b); i<(int)(e); i++)
#define ALL(x) (x).begin(), (x).end()

const int INF = 1<<30;
int n, m, t;
int dp[5050][5050];  // dp[i][j]: at j-th place and visited i+1 place
int pre[5500][5050];
vector<pair<int, int> > edges[5050];

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  
  cin >> n >> m >> t;
  REP (i, m) {
    int v,u,w;
    cin >> v >> u >> w;
    edges[--v].emplace_back(--u, w);
  }

  REP (i, 5050) REP (j, 5050) { dp[i][j] = INF; pre[i][j] = -1; }
  dp[0][0] = 0;

  REP (i, n) REP (j, n) {
    if (dp[i][j] == INF) continue;
    for (auto &e : edges[j]) {
      int k, w;
      tie(k, w) = e;
      if (dp[i][j] + w < dp[i+1][k]) {
        dp[i+1][k] = dp[i][j] + w;
        pre[i+1][k] = j;
      }
    }
  }

  int v = n-1;
  int c = -1;
  REP (i, n) if (dp[i][v] <= t) c = i;

  vector<int> r;
  while (v) {
    r.push_back(v+1);
    v = pre[c--][v];
  }
  r.push_back(1);
  reverse(ALL(r));

  cout << r.size() << endl;
  for (auto &x: r)
    cout << x << " ";
  cout << endl;

  return 0;
}