データフォーマットはどうあるべきか

　データパイプラインを作るときにデータのフォーマットはどうあるべきかについて、技術系のブログをいくつか読みつつ考えてみた。

Part of the problem is performance — text formats have to be parsed every time they are processed. Data is typically written once but processed many times; text formats add a significant overhead to every data query or analysis.

But the worst problem by far is the fact that with CSV and JSON data, the data has a schema, but the schema isn’t stored with the data. For example, CSV files have columns, and those columns have meaning. They represent IDs, names, phone numbers, etc. Each of these columns also has a data type: they can represent integers, strings, or dates. There are also some constraints involved — you can dictate that some of those columns contain unique values or that others will never contain nulls. All this information exists in the head of the people managing the data, but it doesn’t exist in the data itself.

The people who work with the data don’t just know about the schema; they need to use this knowledge when processing and analyzing the data. So the schema we never admitted to having is now coded in Python and Pig, Java and R, and every other application or script written to access the data.

引用元: The problem of managing schemas
https://www.oreilly.com/ideas/the-problem-of-managing-schemas

•  データフォーマットはデータ分析のパフォーマンスに影響をあたえる（パースするためのオーバーヘッド）。
• データはwriteの一度だけだが、readは複数回であるということを意識するのが重要。多少面倒でもwriteするときによいフォーマットでデータを出力しておけば、readするときに多くの人がhappyになるという 意味。
• CSV、JSONにスキーマ情報を定義することはできるが、データそのものの中にスキーマ情報を格納できない。
• データの中に格納されなかったスキーマ情報に関する処理はそのデータを利用する各アプリケーション内のコードに書かれることになる。つまり同じロジックがいろいろな場所にいろいろな言語で書かれることになる。

One of the key design decisions of Yelp’s Data Pipeline is schematizing all data. In other words, the pipeline forces all the data flowing through it to conform to predefined schemas, instead of existing in a free form. Standardizing the data format is crucial to the Yelp Data Pipeline because we want the data consumers to have an expectation about what type of data they are getting, as well as being able to avoid immediate impact when the upstream data producers decide to change the data they publish. Having a uniform schema representation also gives the Data Pipeline a really easy way to integrate and support various systems that use different data formats.

引用元：More Than Just a Schema Store
https://engineeringblog.yelp.com/2016/08/more-than-just-a-schema-store.html 

• データパイプライン上を流れるデータにあらかじめ定義されたスキーマ制約を課しておくことはとても重要
• フォーマットを標準化しておくことでconsumerはどのような形式のデータを取得するのか予測できる
• 統一的なスキーマ表現は異なる形式のデータをもつ多様なシステムを統合する際にも重要 

A common pain point that every data pipeline must address is how to deal with upstream schema changes. Often times such an event requires a lot of communication and coordination between upstream data producers and downstream data consumers. Yelp is not immune to this problem. We have batch jobs and systems that ingest data coming from other batch jobs and systems. It has become a painful problem every time the upstream data changes because it may cause the downstream batch jobs or systems to crash or necessitate a backfill. The entire process is pretty labor-intensive.

引用元：More Than Just a Schema Store
https://engineeringblog.yelp.com/2016/08/more-than-just-a-schema-store.html 

• アップストリームでのスキーマ変更にどのように対処するかはデータパイプラインの共通的な悩み
• あるバッチの出力が別のバッチの入力となっている場合、アップストリーム側のデータが変わるとダウンストリーム側のバッチに影響を及ぼす
• スキーマ変更が生じると、producer、consumer間のコミュニケーション、調整に多大な工数がかかる 

ここまでがデータフォーマットを統一することの重要性、データ内にスキーマ情報をもつことの重要性に関する話。ここからは、どのフォーマットがいいのか、スキーマの進化に強いフォーマットは無いのかという話。YelpではAvroを使っているらしい。

Apache Avro, a data serialization system, has some really nice properties, and is ultimately what we selected. Avro is a space-efficient binary serialization format that integrates nicely with dynamic languages like Python, without requiring code generation. The killer feature of Avro, for our system, is that it supports schema evolution. That means that a reader application and a writer application can use different schema versions to consume and produce data, as long as the two are compatible. This decouples consumers and producers nicely - producers can iterate on their data format, without requiring changes in consumer applications.

引用元：Billions of Messages a Day - Yelp's Real-time Data Pipeline
https://engineeringblog.yelp.com/2016/07/billions-of-messages-a-day-yelps-real-time-data-pipeline.html

• Avroは容量効率がとても優れているバイナリシリアライゼーションフォーマット
• スキーマの進化をサポート
• スキーマに互換性があれば、producerが書くデータ、consumerが読むデータが異なるバージョンであってもよい
• つまり、consumerとproducerの結合度が弱まる
• producer側はconsumer側の影響を意識せずにデータフォーマットを継続的に改良することができる

まとめ

• データパイプラインを流れるデータはフリー形式ではなく、なんらかのフォーマットに統一するべき
• フォーマット形式は
• データ圧縮率が高いものがよい
• データ内にスキーマ情報を持てるものがよい
• スキーマの進化をサポートしているものがよい
• 適切なフォーマット形式を選ぶことで以下のメリットがえられる
• データ分析処理のパフォーマンスが向上
• producer/consumer間のコミュニケーションコストが減る
• アップストリーム側の変更がダウンストリーム側に及びにくくなる
• スキーマ情報に関する処理コード（型変換、デフォルト値の設定、単純なパース処理）の記述量が減る

集合族とは

　グラフィカルモデルの勉強をしていたら、集合族という聞きなれない言葉に遭遇したので調べてみた。

集合族とは、集合のあつまりのこと。
特に、ある集合Sの部分集合族とは、Sの部分集合のあつまりのことである。

具体的な例を考えてみる。
集合SをS = {1,2,3,4}と定義する。
以下にSの部分集合族をいくつか列挙してみる。

Sのべき集合は、Sの部分集合族である。
べき集合とは、以下のようにSの考えられる部分集合をすべて列挙したものである。
{{}, {1}, {2}, {3}, {4}, {1,2}, {1,3}, {1,4}, {2,3}, {2,4}, {3,4}, {1,2,3}, {1,3,4}, {1,2,4}, {2,3,4}, {1,2,3,4}}

Sのk-元部分集合からなる集合は、Sの部分集合族である。
k-元部分集合とは要素数がkの部分集合のこと。
例えば以下のようなSの1-元部分集合は、Sの部分集合族である。
{{1}, {2}, {3}, {4}}

適当にSから部分集合を選んでそれを要素とする集合を作ると、それはSの部分集合族である。
例えば、{{1,2}, {1,2,3}, {3,4}, {4}}など。

デフォルト文字コードを変えてavroのserialize結果を確認した

　ちょっと気になったので実験してみた。
Javaでは、Charset.defaultCharset().name()とやると、JVMのデフォルトの文字コードを取得できる。この文字コードはOSのロケールや文字コードに依存して決まるらしい。
EclipseだとProject-Propertiesから文字コードを変更できるので、このへんをいろいろ変えてどうなるか見てみた。

実験コード

package com.kenjih.sample;

import java.io.ByteArrayOutputStream;
import java.io.IOException;
import java.nio.charset.Charset;

import org.apache.avro.Schema;
import org.apache.avro.SchemaBuilder;
import org.apache.avro.generic.GenericData;
import org.apache.avro.generic.GenericDatumWriter;
import org.apache.avro.generic.GenericRecord;
import org.apache.avro.io.DatumWriter;
import org.apache.avro.io.EncoderFactory;
import org.apache.avro.io.JsonEncoder;

public class Main {

    public void run() throws IOException {
        // set default encoding
        System.out.println("default encoding=" + Charset.defaultCharset().name());

        // create avro record
        Schema schema = SchemaBuilder.record("test").namespace("hoge.fuga")
                .fields()
                .name("keyword").type().stringType().noDefault().endRecord();

        String keyword = "あいうえお";
        GenericRecord record = new GenericData.Record(schema);
        record.put("keyword", keyword);

        // serialize with json encoder
        DatumWriter<GenericRecord> writer = new GenericDatumWriter<GenericRecord>(schema);
        ByteArrayOutputStream out = new ByteArrayOutputStream();
        JsonEncoder encoder = EncoderFactory.get().jsonEncoder(schema, out);
        writer.write(record, encoder);
        encoder.flush();
        
        // see bytes of keyword
        byte[] bytes = keyword.getBytes();
        for (int i = 0; i < bytes.length; i++) {
            System.out.print(bytes[i] + ",");
        }
        System.out.println();
        
        // see bytes of serialize message
        bytes = out.toByteArray();
        for (int i = 0; i < bytes.length; i++) {
            System.out.print(bytes[i] + ",");
        }
        System.out.println();
        
        // bytes are encoded with UTF-8
        System.out.println(out.toString("UTF-8"));        
    }

    public static void main(String[] args) throws IOException {
        new Main().run();
    }

}

結果

以下のようにavroのserializerは、JVMのデフォルト文字コードが何であれ、UTF-8エンコーディングで結果を返すらしい。ということでシリアライズ結果を文字列に格納したい場合は、toString("UTF-8")しておけばOKっぽい。

UTF-8のとき

default encoding=UTF-8

-29,-127,-126,-29,-127,-124,-29,-127,-122,-29,-127,-120,-29,-127,-118,

123,34,107,101,121,119,111,114,100,34,58,34,-29,-127,-126,-29,-127,-124,-29,-127,-122,-29,-127,-120,-29,-127,-118,34,125,

{"keyword":"あいうえお"}

UTF-16のとき

default encoding=UTF-16

-2,-1,48,66,48,68,48,70,48,72,48,74,

123,34,107,101,121,119,111,114,100,34,58,34,-29,-127,-126,-29,-127,-124,-29,-127,-122,-29,-127,-120,-29,-127,-118,34,125,

{"keyword":"あいうえお"}

Shift_jisのとき

default encoding=Shift_JIS

-126,-96,-126,-94,-126,-92,-126,-90,-126,-88,

123,34,107,101,121,119,111,114,100,34,58,34,-29,-127,-126,-29,-127,-124,-29,-127,-122,-29,-127,-120,-29,-127,-118,34,125,

{"keyword":"あいうえお"}

SLF4Jでロギング

SLF4Jとは？
Simple Logging Facade for Java。ロギングフレームワークのFacade的なやつ。
SLF4Jを使うことで、特定のロギングフレームワークの実装に依存することなく、ロギング処理が書ける。

準備
gradleでプロジェクトを作成すると、

gradle init --type java-library

デフォルトでslf4j-apiがdependenciesに入ってた。

dependencies {
    compile 'org.slf4j:slf4j-api:1.7.13'
    testCompile 'junit:junit:4.12'
}

使ってみる

package com.kenjih.logging;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

public class Sample {

    public void run() {
        Logger logger = LoggerFactory.getLogger(Sample.class);
        logger.info("Hello, world!");
    }

    public static void main(String[] args) {
        new Sample().run();
    }

}

このままで実行するとエラーになる。

SLF4J: Failed to load class "org.slf4j.impl.StaticLoggerBinder".
SLF4J: Defaulting to no-operation (NOP) logger implementation
SLF4J: See http://www.slf4j.org/codes.html#StaticLoggerBinder for further details.

ここで注目すべきは、コード自体はコンパイルできること。
エラー内容は実行するときにロガー実装が見つかりませんでした的な内容。つまり特定のロガー実装に依存することなくロギングコードが書けて、このソースの使用者が使用するロガーを決めることができるということ。これはライブラリを書くときに非常に便利。なぜなら特定のロガー実装をエンドユーザーに強制する必要がなくなるから。

ということで以下ロガー実装との組み合わせを試していく。

log4j2を使う
ロガー実装としてlog4j2を使うことにする。

build.gradleに以下のdependencyを追記。

compile group: 'org.apache.logging.log4j', name: 'log4j-api', version: '2.7'  
compile group: 'org.apache.logging.log4j', name: 'log4j-core', version: '2.7'
compile group: 'org.apache.logging.log4j', name: 'log4j-slf4j-impl', version: '2.7'

クラスパスに以下のファイルをlog4j2.xmlという名前で置く。

<?xml version="1.0" encoding="UTF-8"?>
<Configuration status="WARN">
  <Appenders>
    <Console name="Console" target="SYSTEM_OUT">
      <PatternLayout pattern="%d{yyyy/MM/dd HH:mm:ss} %-5level - %msg%n"/>
    </Console>
  </Appenders>
  <Loggers>
    <Root level="info">
      <AppenderRef ref="Console"/>
    </Root>
  </Loggers>
</Configuration>

実行。

2016/11/03 19:40:51 INFO  - Hello, world!

log4jを使う
log4j 1系でやってみる。

依存ライブラリは以下のものを使う。

compile group: 'org.slf4j', name: 'slf4j-log4j12', version: '1.7.13'
compile group: 'log4j', name: 'log4j', version: '1.2.17'

設定ファイルは、log4j.xmlという名前でクラスパスに置く。

<?xml version="1.0" encoding="UTF-8" ?>
<!DOCTYPE log4j:configuration SYSTEM "log4j.dtd">
<log4j:configuration xmlns:log4j="http://jakarta.apache.org/log4j/" >

  <appender name="stdout" class="org.apache.log4j.ConsoleAppender">
     <param name="Target" value="System.out" /> 
     <layout class="org.apache.log4j.PatternLayout">
        <param name="ConversionPattern" value="%m%n" />
     </layout>
  </appender>
  <root>
    <appender-ref ref="stdout"/>
  </root>
</log4j:configuration>

実行。

Hello, world!

IndeedのTech Talkに行ってきた

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

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

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

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

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

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

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;    
}

他にもいろいろできる。

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

　以下のような直線型グラフのマッチングについて考える。

一般にノード数nの直線型グラフからk個のマッチングを選ぶパターン数は_n-kC_kとなる。

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

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

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

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

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

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

#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;
}

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
• 構成管理ツール
• サーバのプロビジョニングを効率化できる

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

• Vagrant: https://www.vagrantup.com/downloads.html
• VirtualBox: https://www.virtualbox.org/wiki/Downloads
• Ansible: brew install 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;
}

xorshiftの周期を調べてみた

 xorshiftは擬似乱数ジェネレータの一つであり、2³²-1という周期を持つらしい。
これはなかなか便利そうだ。さっそく仕事で使えそう（というか仕事で教えてもらったのだった...）。

本当に周期が2³²-1なのか気になったので試したみた。

#include <iostream>

using namespace std;

const uint32_t x0 = 2463534242;

uint32_t xorshift() {
  static uint32_t x = x0;
  x = x ^ (x << 13);
  x = x ^ (x >> 17);
  return x = x ^ (x << 5);
}

int main(int argc, char *argv[])
{
  uint32_t i = 1;
  while (xorshift() != x0)
    ++i;
  cout << i << endl;
  return 0;
}

実行結果

4294967295

本当！

Builderパターンでオブジェクトの生成制御

　オブジェクトを作成したときに、

• 必須フィールドを設けたい
• あるフィールドには自動で値を入れたい
• 中途半端なオブジェクトを利用者に使わせたくない

みたいなことをしたくて、オブジェクトの生成制御するデザインパターンあったよなぁと思って調べてたらBuilderパターンだった。

やりたかったのは以下のようなこと。

package com.kenjih.sample;

public class User {

    private String name;
    private int age;
    private int id;

    private User(Builder builder) {
        this.name = builder.name;
        this.age = builder.age;
        this.id = 1234;  // TODO: Assign unique ID
    }

    public void sayHello() {
        System.out.printf("Hello! I am %s, %d years lod!\n", name, age);
    }

    static class Builder {
        private String name;
        private Integer age;

        Builder() {}

        Builder(String name, Integer age) {
            this.name = name;
            this.age = age;
        }

        Builder setName(String name) {
            this.name = name;
            return this;
        }

        Builder setAge(int age) {
            this.age = age;
            return this;
        }

        User build() {
            if (name == null || age == null)
                throw new NullPointerException();
            return new User(this);
        }
    }

    public static void main(String[] args) {
        User u1 = new User.Builder("Taro", 20).build();
        u1.sayHello();

        User u2 = new User.Builder().setName("Hanako").setAge(15).build();
        u2.sayHello();
        
        User u3 = new User.Builder().setName("Jiro").build();  // NullPointerException
        u3.sayHello();
    }
}

Jacksonを使ってみた

　Pythonではよくやるけど、Javaでオブジェクトをjson化したことが無かった。
Jacksonというライブラリがよく使われるらしい。

インストール
build.gradleのdependenciesに以下を追記。

compile group: 'com.fasterxml.jackson.core', name: 'jackson-databind', version: '2.8.3'

サンプル

package com.kenjih.jackson;

import com.fasterxml.jackson.core.JsonProcessingException;
import com.fasterxml.jackson.databind.ObjectMapper;

class User {
    int id;
    String name;

    User(int id, String name) {
        this.id = id;
        this.name = name;
    }

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }
}

public class Main {
    public void run() throws JsonProcessingException {
        User user = new User(1, "taro");
        ObjectMapper mapper = new ObjectMapper();
        String json = mapper.writeValueAsString(user);
        System.out.println(json);
    }

    public static void main(String[] args) {
        try {
            new Main().run();
        } catch (JsonProcessingException e) {
            e.printStackTrace();
        }
    }
}

実行結果

{"id":1,"name":"taro"}

sparseなindicator vectorからユーザの類似度を測る

　ユーザがadをclickした/しないでindicator vectorを作ってユーザ間の類似度を測りたかった。僕の直感だと{0, 1}のベクトルの距離なのでハミング距離だろうと思ったけど、コサイン距離のほうがいいらしい。

　確かにハミング距離だと全く嗜好の違うユーザだろうが、嗜好がほとんど同じユーザだろうが、x個の次元が異なると距離がx/|dim|になって嬉しくない。これに対してコサイン距離を使うと、嗜好が似ているユーザの場合は似ている方向に角度が寄るので距離が緩和される。

　直感的にもそうなるのは理解できるが、実際に計算して確かめてみた。

from scipy.spatial.distance import hamming, cosine

x1 = [1,1,1,0,0,0,0,0,0,0]
y1 = [0,1,1,1,0,0,0,0,0,0]

y2 = [0,1,0,0,0,0,0,0,0,0]
x2 = [1,0,0,0,0,0,0,0,0,0]

print(hamming(x1, y1))  # 0.2
print(hamming(x2, y2))  # 0.2

print(cosine(x1, y1))  # 0.333333333333
print(cosine(x2, y2))  # 1.0

Centroid Decompositionの問題

Centroid Decompositionを使う問題をいくつか解いてみた。
Centroidが何なのか知らない人はこちら。

Codeforces Round #190 Ciel the Commander

問題
木の各ノードにアルファベット（A-Z）を1つ書きたい。
ただし、同じアルファベットが書かれた2つのノードv, w間のパス上には、2つのノードに書かれたアルファベットより小さい文字が書かれたノードが存在しなければならない。
このようなアルファベットの書き方を求めよ。

解法
Centroid Decompositionして分解されたときの再帰の深さの順に小さい文字を割り振っていけばOK。

ソースコード

#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()

int n;
vector<int> edges[100000];
int rk[100000];
int sz[100000];

void szdfs(int v, int par = -1) {
  sz[v] = 1;
  for (auto &w: edges[v]) {
    if (rk[w] || w == par) continue;
    szdfs(w, v);
    sz[v] += sz[w];
  }
}

int centroid(int v, int par, int total) {
  for (auto &w: edges[v]) {
    if (rk[w] || w == par) continue;
    if (2 * sz[w] > total)
      return centroid(w, v, total);
  }
  return v;
}

void solve(int v, int r) {
  szdfs(v);
  v = centroid(v, -1, sz[v]);
  rk[v] = r;
  for (auto &w: edges[v]) {
    if (rk[w]) continue;
    solve(w, r+1);
  }
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n;
  REP (i, n-1) {
    int a, b;
    cin >> a >> b;
    --a, --b;
    edges[a].push_back(b);
    edges[b].push_back(a);
  }
  solve(0, 1);
  REP (i, n) {
    char c = 'A' + rk[i] - 1;
    cout << c << " ";
  }
  cout << endl;
  
  return 0;
}

Codeforces Round #199 Xenia and Tree

問題
木のノードに色を塗る。はじめノード1は赤色に、それ以外のノードは青色に塗られている。以下のクエリを高速に処理せよ。
1. ある青いノードを赤色に塗る
2. あるノードから赤色のノードまでの最短距離を求める

解法
Centroid Decompositionを使って、バランスした木に構築する。
1. のクエリに対しては指定されたノードを赤く塗り、そのノードからルート方向へ登りながら、 通過したノードにそのノードからそのノード以下の赤ノードまでの最短距離を更新する。
2. のクエリに対してはそのノードからルート方向へ登りながら1.のときに更新した値を用いて最短距離を計算する。
木がバランスしているので、訪れるノード数がlog(n)個程度になるのがポイント。

Centroid Decompositionで作った木と元の木のノード集合は同じだが、枝集合は異なることに注意。ノード間の距離を求める場合は元の木における距離を使わないといけない。

ソースコード

#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()

class LCA {
  int V, logV;
  vector<int> depth;
  vector<vector<int> > parent;
  
  void build() {
    for (int k = 0; k + 1 < logV; k++) {
      for (int v = 0; v < V; v++) {
        if (parent[k][v] < 0) parent[k+1][v] = -1;
        else parent[k+1][v] = parent[k][parent[k][v]];
      }
    }
  }
public:
  LCA(int V) {
    this->V = V;
    logV = 0;
    while (V > (1LL<<logV)) logV++;
    this->depth = vector<int>(V);
    this->parent = vector<vector<int> >(logV, vector<int>(V));
  }
  
  void init(int N, int p[], int d[]) {
    for (int i = 0; i < N; i++) {
      parent[0][i] = p[i];
      depth[i] = d[i];
    }
    this->build();
  }
  
  int query(int u, int v) {
    if (depth[u] > depth[v]) swap(u, v);
    for (int k = 0; k < logV; k++) {
      if ((depth[v] - depth[u]) >> k & 1)
        v = parent[k][v];
    }
    if (u == v) return u;
    
    for (int k = logV-1; k >= 0; k--) {
      if (parent[k][u] != parent[k][v]) {
        u = parent[k][u];
        v = parent[k][v];
      }
    }
    return parent[0][u];
  }
};

const int INF = 1<<28;
int n, m;
vector<int> edges[100000];
bool vis[100000];
int p[100000];
int sz[100000];
bool red[100000];
int dist[100000];
int lcap[100000];
int lcad[100000];
LCA lca(100000);

void szdfs(int v, int par = -1) {
  sz[v] = 1;
  for (auto &w: edges[v]) {
    if (vis[w] || w == par) continue;
    szdfs(w, v);
    sz[v] += sz[w];
  }
}

int centroid(int v, int par, int total) {
  for (auto &w: edges[v]) {
    if (vis[w] || w == par) continue;
    if (2 * sz[w] > total)
      return centroid(w, v, total);
  }
  return v;
}

void balanceTree(int v, int par = -1) {
  szdfs(v);
  v = centroid(v, -1, sz[v]);
  p[v] = par;
  vis[v] = true;
  for (auto &w: edges[v]) {
    if (vis[w]) continue;
    balanceTree(w, v);
  }
}

void lcadfs(int v, int par, int d) {
  lcap[v] = par;
  lcad[v] = d;
  for (auto &w: edges[v]) {
    if (w == par) continue;
    lcadfs(w, v, d+1);
  }
}

void paint(int v) {
  red[v] = true;
  int w = v;
  while (w != -1) {
    int u = lca.query(v, w);
    int cost = lcad[v] + lcad[w] - 2 * lcad[u];
    dist[w] = min(dist[w], cost);
    w = p[w];
  }
}

int query(int v) {
  int ret = INF;
  int w = v;
  while (w != -1) {
    int u = lca.query(v, w);
    int cost = lcad[v] + lcad[w] - 2 * lcad[u];
    ret = min(ret, dist[w] + cost);
    w = p[w];
  }
  return ret;
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m;
  REP (i, n-1) {
    int a, b;
    cin >> a >> b;
    --a, --b;
    edges[a].push_back(b);
    edges[b].push_back(a);
  }
  balanceTree(0);

  fill(dist, dist+n, INF);
  lcadfs(0, -1, 0);
  lca.init(n, lcap, lcad);
  paint(0);
  REP (i, m) {
    int t, x;
    cin >> t >> x;
    --x;
    if (t == 1)
      paint(x);
    else
      cout << query(x) << endl;
  }
  
  return 0;
}

Codeforces Round #372 Digit Tree

問題
木のノードに1-9までの数字が書かれている。
v, w間のパスに含まれるノードの数字をつないで10進数表記の数を作る。その数がMで割り切れるようなv, wのペアの数を求めよ。

解法
uがv, wのLCAとなるような場合のv, wの組み合わせを考える。
v -> u -> wという順序に通るので、v -> uとu -> wの組み合わせを列挙して、2つをつなげるとMで割るようなものを数えればよい。
あとはuをすべてのノードでループしないといけないが、Centroid Decompositionしておくと計算量を抑えることができる。

ソースコード

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()

int n;
long long M;
vector<pair<int, int> > edges[100000];
bool vis[100000];
int sz[100000];
map<int, int> upcnt;
long long r1, r2;
long long pw[100000], ipw[100000];

void szdfs(int v, int par = -1) {
  sz[v] = 1;
  for (auto &e: edges[v]) {
    int w = e.first;
    if (w == par || vis[w]) continue;
    szdfs(w, v);
    sz[v] += sz[w];
  }
}

int centroid(int v, int par, int total) {
  REP (i, edges[v].size()) {
    int w = edges[v][i].first;
    if (w == par || vis[w]) continue;
    if (sz[w] * 2 > total)
      return centroid(w, v, total);
  }
  return v;
}

void downdfs(int v, int par, int acc, int d) {
  if (acc == 0) ++r2;
  r1 += upcnt[(M-acc)*ipw[d]%M];
  for (auto &e: edges[v]) {
    int u, w;
    tie(u, w) = e;
    if (u == par || vis[u]) continue;
    downdfs(u, v, (10LL*acc+w)%M, d+1);
  }
}

void updfs(int v, int par, int acc, int d) {
  if (acc == 0) ++r2;
  ++upcnt[acc];
  for (auto &e: edges[v]) {
    int u, w;
    tie(u, w) = e;
    if (u == par || vis[u]) continue;
    updfs(u, v, (acc+pw[d]*w)%M, d+1);
  }
}

void solve(int v) {
  szdfs(v);
  v = centroid(v, -1, sz[v]);
  upcnt.clear();
  REP (i, edges[v].size()) {
    int u = edges[v][i].first;
    int w = edges[v][i].second;
    if (vis[u]) continue;
    downdfs(u, v, w%M, 1);
    updfs(u, v, w%M, 1);
  }

  upcnt.clear();
  REP (i, edges[v].size()) {
    int u = edges[v][edges[v].size()-1-i].first;
    int w = edges[v][edges[v].size()-1-i].second;
    if (vis[u]) continue;
    downdfs(u, v, w%M, 1);
    updfs(u, v, w%M, 1);
  }
  
  vis[v] = true;
  for (auto &e: edges[v]) {
    int w = e.first;
    if (vis[w]) continue;
    solve(w);
  }
}

long long modpow(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;
}

long long totient(long long n) {
  long long ret = n;
  for (long long i = 2; i * i <= n; i++) {
    if (n % i == 0) {
      ret = ret / i * (i - 1);
      while (n % i == 0)
        n /= i;
    }
  }
  if (n != 1) 
    ret = ret / n * (n - 1);
  return ret;
}

void init() {
  pw[0] = ipw[0] = 1;
  long long inv = modpow(10, totient(M)-1, M);
  FOR (i, 1, 100000) {
    pw[i] = pw[i-1] * 10 % M;
    ipw[i] = ipw[i-1] * inv % M;
  }
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> M;
  REP (i, n-1) {
    int u,v,w;
    cin >> u >> v >> w;
    edges[u].emplace_back(v, w);
    edges[v].emplace_back(u, w);    
  }
  r1 = r2 = 0;
  init();
  solve(0);
  cout << r1 + r2/2 << endl;
  
  return 0;
}