エンジニア日記（1）工数見積をミスった

工数の見積を誤ってしまった。

一日の労働時間 = 一日の実作業時間

という前提で工数を見積もってしまったのだ。
これは大きな間違いだった。

一日8時間労働する人がいたとする。8時間のうちの1時間はメールを見たり、報告書を書いたりなどの雑務の時間になる。さらに、１時間働いて5-10分程度休憩すると考えると、なんだかんだで1時間である。

一日の労働時間 が8時間なら、実質的な作業に充てられる時間は6時間。
さらに、朝礼とか定例会議とかあるような場合だと、実作業時間は更に減ってしまう。

正確な見積をする場合は、

一日の労働時間 != 一日の実作業時間

をしっかりと認識しておかなければならない。定時に帰れるようにしたいなら、一日の実作業時間 = 6時間で見積らなければならない。

Fight for liberty!

かっこいいCMを見た。ディクテーションしてみた。

To those who can hear me, I say "Do not despair."
And so long as men die, liberty will never perish.
You are not machines, you are not cattle, you are men.
You, the people, have the power -- the power to create machines, the power to create happiness.
You, the people, have the power to make this life free and beautiful, to make this life a wonderful adventure.
Fight for liberty!

C#入門（11）マルチスレッド

　C#でマルチスレッド処理を書いて遊んでみました。
Javaの場合は、Threadクラスの子クラスや、Runnableインターフェースの実装クラスといったように別スレッドで実行したい処理をクラス単位で指定しますが、C#の場合はデリゲートを使ってメソッド単位で指定できます。

　今回は、以下の４つのサンプルを書きました。

1. 別スレッドで処理を実行する
2. Mutexを使って排他制御を行う
3. Semaphoreを使って同時実行スレッド数を制御する
4. Timerを使ってスレッド毎のステータスを表示する

[4.の実行結果]

以下、サンプルのソースコードです。

1. 別スレッドで処理を実行する

インスタンスメソッドをThreadStartデリゲートとして使用すると、インスタンス固有のパラメータをメソッド内から参照できるというのがポイントです。

using System;
using System.Threading;

class Task 
{

    private string code;

    public Task(string code)
    {
        this.code = code;
    }

    public void Start()
    {
        Thread thread = new Thread(new ThreadStart(DoIt));
        thread.Start();
    }

    private void DoIt() 
    {
        for (int i = 0; i < 10; i++) 
        {
            Thread.Sleep(100);
            Console.WriteLine("working on the task: {0}.", code);
        }
    }

}

public class Sample
{
    public static void Main()
    {
        Task task1 = new Task("task-1");
        Task task2 = new Task("task-2");

        task1.Start();
        task2.Start();
    }
}

2. Mutexを使って排他制御を行う

リソースに複数のスレッドが同時にアクセスしないようにするには、Mutexを使います。ロックには所有権があり、ロックを取得したスレッドのみがロックを開放できるというのがポイントです。
以下の例では、ユニークなシーケンスを割り振る機能を持つクラスのインスタンスに対して排他制御を行います。

using System;
using System.Threading;

class Sequence 
{

    private int seq;

    private Mutex mutex = new Mutex();

    public Sequence()
    {
        this.seq = 0;
    }

    // what would happen without a mutex?
    public int Next() 
    {
        mutex.WaitOne();

        int curSeq = seq;
        Thread.Sleep(100);
        seq = ++curSeq;

        mutex.ReleaseMutex();

        Thread.Sleep(150);
        return curSeq;
    }
}

class Task 
{

    private string name;
    private Sequence seq;

    public Task(string name, Sequence seq)
    {
        this.name = name;
        this.seq = seq;
    }
    
    public void Start()
    {
        Thread thread = new Thread(new ThreadStart(DoIt));
        thread.Start();
    }
    
    private void DoIt() 
    {
        for (int i = 0; i < 10; i++) 
        {
            Console.WriteLine("{0} got {1}.", this.name, seq.Next());
        }
    }
    
}

public class Sample
{
    public static void Main()
    {
        Sequence seq = new Sequence();

        Task task1 = new Task("task1", seq);
        Task task2 = new Task("task2", seq);
        
        task1.Start();
        task2.Start();
    }
}

3. Semaphoreを使って同時実行スレッド数を制御する

Mutexを使うと、リソースに同時アクセスするスレッド数を１個にすることが出来ました。N個にしたい場合は、Semaphoreを使います。Mutexと違ってロックの所有という概念が無いため、ロックを取得していないスレッドがロックを開放するという処理を行うことが出来ます。
以下の例では、サイズ=3のプールを持つリソースに複数のスレッドがアクセスします。

using System;
using System.Threading;

class Resource 
{
    private Semaphore pool;

    public Resource(int poolSize)
    {
        pool = new Semaphore(poolSize, poolSize);
    }

    public void doSomething(int complexity) 
    {
        pool.WaitOne();
        Console.WriteLine("{0} {1} started the task.", DateTime.Now, Thread.CurrentThread.Name);
        Thread.Sleep(complexity * 1000);
        Console.WriteLine("{0} {1} completed the task, increasing semaphore to {2}.", 
                          DateTime.Now, Thread.CurrentThread.Name, 1+pool.Release());
    }
}

class Task 
{
    private int complexity;
    private Resource resource;

    public Task(int complexity, Resource resource)
    {
        this.complexity = complexity;
        this.resource = resource;
    }
    
    public void Start()
    {
        Thread thread = new Thread(new ThreadStart(DoIt));
        thread.Name = "Task" + this.complexity.ToString();
        thread.Start();
    }
    
    private void DoIt() {
        resource.doSomething(this.complexity);
    }
    
}

public class Sample
{
    public static void Main()
    {
        Resource resource = new Resource(3);

        for (int i = 0; i < 10; i++)
        {
            new Task(i+1, resource).Start();
        }

    }
}

4. Timerを使ってスレッド毎のステータスを表示する

サンプル3. の出力をもう少しかっこよくできないかと考えて、作ったのがこのサンプルです。
Timerを使うと、一定間隔で特定の処理を別スレッドで呼び出すことが出来ます。

using System;
using System.Threading;

class Resource 
{
    private int size;
    private Semaphore pool;

    public Resource(int poolSize)
    {
        this.size = poolSize;
        this.pool = new Semaphore(0, poolSize);
    }

    public void Connect()
    {
        pool.Release(size);
    }

    public void doSomething(int taskId) 
    {
        pool.WaitOne();

        for (int i = 0; i < 30; i++)
        {
            Task.UpdateStatus(taskId);
            Thread.Sleep((taskId + 1) * 10);
        }

        pool.Release();
    }
}

class Task 
{

    public const int TASK_NUM = 20;

    private static int[] Status = new int[TASK_NUM];

    private int id;
    private Resource resource;

    public Task(int id, Resource resource)
    {
        this.id = id;
        this.resource = resource;
    }

    public static void DisplayStatus(Object obj)
    {
        Console.CursorLeft = 0;
        Console.CursorTop = 0;
        Console.WriteLine("{0}: ", DateTime.Now.ToString());

        for (int i = 0; i < TASK_NUM; i++)
        {
            string line = string.Empty;
            for (int j = 0; j <= Status[i]; j++)
            {
                line += '*';
            }
            Console.WriteLine(line);
        }
    }

    public static void UpdateStatus(int taskId)
    {
        ++Status[taskId];
    }

    public void Start()
    {
        Thread thread = new Thread(new ThreadStart(DoIt));
        thread.Start();
    }
    
    private void DoIt() {
        resource.doSomething(this.id);
    }
    
}

public class Sample
{
   
    public static void Main()
    {

        TimerCallback tcb = new TimerCallback(Task.DisplayStatus);
        Timer timer = new Timer(tcb, null, 1000, 100);

        Resource resource = new Resource(5);

        Task[] tasks = new Task[Task.TASK_NUM];
        for (int i = 0; i < Task.TASK_NUM; i++)
        {
            tasks[i] = new Task(i, resource);
            tasks[i].Start();
        }

        Thread.Sleep(2000);
        resource.Connect();

        Console.ReadLine();
        timer.Dispose();
    }

}

Gale-Shapleyアルゴリズム

　最近、安定結婚問題に基づいてパートナーを決める出会い系アプリに関する記事を読みました。安定結婚問題を解くGale-Shapleyアルゴリズムが面白そうだったので勉強してみました。

安定結婚問題とは?

N人の男とN人の女がいる。N組のカップルを作りたい。
ただし、駆け落ちする人が現れないようにカップルを作りたい。

「駆け落ち」が起こりえる条件は、

1. 自分のパートナーよりも、好きな人（A）が別にいる
2. Aさんも、Aさん自身のパートナーより自分のことを好きでいてくれる

である。

Gale-Shapleyアルゴリズムとは?

安定結婚問題を解くためのアルゴリズムで、以下のような手続きをパートナーのいない男がいなくなるまで繰り返します。

1. パートナーがいない男（X）は、まだプロポーズをしたことのない相手の中で一番好きな人にプロポーズをする。
2. プロポーズされた女は、
1. フリーの場合、そのプロポーズを受け入れる。
2. すでに婚約中の場合、
1. 今の婚約相手よりもXの方が魅力的であれば、今の婚約相手を振って、Xのプロポーズを受け入れる。
2. Xよりも今の婚約相手の方が魅力的であれば、Xのプロポーズを断る。

このアルゴリズムが本当に正しく動作するのか考えてみました。

ーまず、このアルゴリズムは停止するのか？

アルゴリズムは、パートナーがいない男が存在する間は停止しない。パートナーという関係は男集合から女集合へのbijectiveな写像なので、「パートナーがいない男が存在する」と「パートナーがいない女が存在する」は同値。

女は、一度でもプロポーズされると、それ以降はうまく男をキープすることで常にパートナーのいる状態を継続できる。よって、すべての女が一度でもプロポーズをされたことがある状態になるとこのアルゴリズムは停止する。

男はN人いて、それぞれの男には１位からN位まで女をランク付けしたリストがあり、それにしたがってプロポーズしていくので、プロポーズという行為が全体でN * N回行われた時点でアルゴリズムは停止する。

よって計算量はO(N²)。

ーアルゴリズムが停止したときのマッチングには、ブロッキングペア（駆け落ちが発生するようなペア）が存在しないか？

m1はf1よりf2の方が好き、かつ、f2はm2よりm1の方が好きであるにも関わらず、アルゴリズムが停止したとき、(m1, f1)、(m2, f2)というペアがえられたと仮定する。

しかしこの場合、m1はf1にプロポーズする前にf2にプロポーズしているはずで、f2はそのプロポーズを受け入れているはずである。よってそのようなペアは存在しない。

ソースコード

C++で書いたソースコードを貼りつけておきます。Gale-Shapleyアルゴリズムの処理は関数process()で行なっています。

#include <iostream>
#include <vector>
#include <queue>
#include <cassert>

using namespace std;

const int N = 100;

int male[N][N];    // j-th favorite of i-th male is male[i][j]
int female[N][N];  // j-th favorite of i-th female is female[i][j]

int rmale[N][N];   // for i-th male, j-th female is rmale[i][j]-th place
int rfemale[N][N]; // for i-th female, j-th male is rfemale[i][j]-th place

int match[N];      // i-th female is engaged to match[i]-th male

void read() {

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> male[i][j];
            rmale[i][male[i][j]] = j;
        }
    }

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> female[i][j];
            rfemale[i][female[i][j]] = j;
        }
    }

}

void process() {

    fill(match, match + N, -1);

    queue<pair<int, int> > q;
    
    for (int i = 0; i < N; i++) {
        // i-th male is trying to propose his first favorite
        q.push(make_pair(i, 0));
    }
    
    while (!q.empty()) {
        int m = q.front().first;
        int order = q.front().second;
        q.pop();

        int f = male[m][order];

        // The proposed female is free.
        if (match[f] == -1) {
            match[f] = m;
        } 
        // The proposed female is engaged but switches over to him.
        else if (rfemale[f][m] < rfemale[f][match[f]]) {
            int dumped = match[f];
            match[f] = m;
            q.push(make_pair(dumped, rmale[dumped][f] + 1));
        } 
        // The proposed female is engaged and rejects him.
        else {
            q.push(make_pair(m, order + 1));
        }
    }

}

void write() {

    for (int i = 0; i < N; i++) {
        cout << i << " th female is engaged to " << match[i] << " th male." << endl;
    }

}

void check() {

    for (int f1 = 0; f1 < N; f1++) {

        int m1 = match[f1];

        for (int f2 = 0; f2 < N; f2++) {

            if (f1 == f2)
                continue;

            int m2 = match[f2];

            // m1 won't elope with another female.
            assert(rmale[m1][f1] < rmale[m1][f2] || rfemale[f2][m2] < rfemale[f2][m1]);

            // f1 won't elope with another male.
            assert(rfemale[f1][m1] < rfemale[f1][m2] || rmale[m2][f2] < rmale[m2][f1]);
            
        }
    }

}

int main(int argc, char **argv) {

    read();

    process();

    write();
    
    check();
    
    return 0;
}

鳩ノ巣原理

　鳩ノ巣原理の面白い動画を見つけたのでメモ。
動画では、以下の問題の解法を女の子（イモトアヤコではない）が説明してくれます。

1. 表面に5つの点が付けられた球がある。この球を2つの半球にカットする。片方の半球に点が少なくとも4つあるようなカットの仕方が必ず存在することを証明せよ。（※但し、切り口上に存在する点は両方の半球に属していると考える。）
2. 長さnの整数列Aがある。この整数列から連続する区間からなる部分列を選び、その部分列の要素の和をsとする。任意のAに対して、sがnで割れるような部分列の選び方が必ず存在することを証明せよ。

Covariance、Contravariance、Invariance

　JavaとかC#とか使ってたらたまに見かける言葉。
理解が曖昧だったので、調べてみました。

定義

以下では、クラスAがクラスBの子クラスであるという関係を A ≦ Bのように表します。

今、A ≦ Bであるとする。
このときクラスの写像fは、

1. f(A) ≦ f(B)を満たすならば、covariantである。
2. f(B) ≧ f(A)を満たすならば、contravariantである。
3. どちらも満たさないならば、invariantである。

これだけだと抽象的なので、Javaを例に考えてみます。

配列はcovariant

Javaの場合、配列はcovariantです。
配列を型Tから型T[]への写像fであると考えると、定義の条件1が成り立ちます。
具体例を挙げると、Integer[] は Number[] の小クラスです。
よって以下のようなプログラムを書くことが出来ます。

package com.kenjih.sample;

public class Sample1 {
 
 public static void main(String[] args) {
  // 配列はcovariant
  Number[] numbers = new Integer[10];
  Object[] objects = new Integer[10];
 }

}

genericsはinvariant

genericタイプのコレクションはinvariantです。
以下のようなプログラムはコンパイルエラーになります。配列はcovariantなのに、genericsはinvariantというのはなかなか厄介です。

package com.kenjih.sample;

import java.util.ArrayList;

public class Sample2 {
 
 public static void main(String[] args) {
  // genericsはinvariant

  // Type mismatch: cannot convert from ArrayList<Integer> to ArrayList<Number>
  ArrayList<Number> numbers = new ArrayList<Integer>();
  
  // もちろんcontravariantでもない。
  // Type mismatch: cannot convert from ArrayList<Number> to ArrayList<Integer>
  ArrayList<Integer> integers = new ArrayList<Number>();
 }
 
}

メソッドの引数はcontravariant、メソッドの戻り値はcovariant

A ≦ Bであるとします。クラスAでクラスBのメソッドをoverrideします。 このとき、型TからTのメソッドの引数への写像、型TからTのメソッドの戻り値への写像がどのような性質をみたすべきか考えます。
以下のソースコードから、

• 子クラスのメソッドの引数の型 ≧ 親クラスのメソッドの引数の型
• 子クラスのメソッドの戻り値の型 ≦ 親クラスのメソッドの戻り値の型

ということが分かります。子クラスのメソッドはポリモフィズムを実現するために親クラスの参照を通して呼ばれることがよくあります。ポリモフィズムできるようにするには引数の型、戻り値の型をどうすればいいか考えると、上の性質がイメージしやすいと思います。
実際のJavaではオーバーライドに関する型指定はより厳密で、Java 1.4の場合は引数、戻り値の型ともに完全一致でなければならず、Java 1.5以降ではcovariantな戻り値の型でもオーバーライド出来るらしいです。

package com.kenjih.sample;

public class Sample3 {
 
 public static Number doit(Number x) {
  return x;
 }
 
 public static void main(String[] args) {
  
  Integer x = Integer.valueOf(0);
  Number y = x;
  Object z = x;
  
  // parameter type test
  Number ret3 = doit(x);    // f: Integer -> Number   OK
  Number ret4 = doit(z);    // f: Object -> Number    Compile Error

  // return type test
  Integer ret1 = doit(y);   // f: Number -> Integer   Compile Error
  Object ret2 = doit(y);    // f: Number -> Object    OK
  
 }
}

連分数

　連分数関連の処理をC++で書いて遊んでみました。

　連分数の基本については、Continued Fraction By Kardi Teknomo, PhD が分かりやすかったです。
　冪級数展開が発散するときでも連分数展開は収束する場合があり、かつ、どちらも収束するようなケースでは連分数展開の方が収束が早い場合が多いらしく、実用的なトピックです。黄金比やネイピア数を連分数展開すると綺麗な形になるというのもまた興味を唆られます。

分数を連分数展開する

p/qを連分数展開する場合を考えます。

p/q = [p/q] + (p%q)/q = [p/q] + 1/(q/(p%q))

となります。
ただし、[]はfloor関数です。

a₀ = [p/q], a₁ = [q/(p%q)], ....となるのでこれを再帰的に考えていくとユークリッドの互除法と同じパターンになることが分かります。

#include <iostream>
#include <vector>

using namespace std;

/*
 * p/q を連分数展開する
 */
void expand(int p, int q, vector<int> &terms) {
    if (q == 0)
        return;

    terms.push_back(p / q);
    expand(q, p % q, terms);

}

template <typename T>
void dump(const vector<T> &vs) {
    for (size_t i = 0; i < vs.size(); i++)
        cout << vs[i] << " ";
    cout << endl;
}

int main() {
    vector<int> terms;
    expand(109, 48, terms);
    dump(terms);  // 2 3 1 2 4 

    return 0;
}

連分数を分数に変換する

ボトムアップに計算する方法（右結合則を使って項数を減らしていくようなイメージ）もありますが、トップダウンに計算する方法の方が面白そうだったのでそちらをやってみます。

p₀ = a₀,  q₀ = 1,
p₁ = a₁ a₀ + 1,  q₁ = a_1, 
p_k = a_kp_k-1 + p_k-2(k > 1),
q_k = a_kq_k-1 + q_k-2(k > 1).

とすると、

[a₀; a₁, a₂, ..., a_k] = p_k / q_k

が成り立ちます（帰納法で証明できます）。

これを使えば連分数を分数に変換出来ます。
因みにa_kがすべて1の場合は、p_kとq_kが隣り合うフィボナッチ数になるため、連分数[1; 1,1,1,1,1,1,...]は黄金比になります。

#include <iostream>
#include <vector>
#include <iomanip>

using namespace std;

/*
 * 連分数を分数に変換する
 */
pair<int, int> compute(const vector<int> &terms) {
    int p[] = {terms[0], 1};
    int q[] = {1, 0};

    int len = terms.size();
    for (int i = 1; i < len; i++) {
        p[i & 1] = terms[i] * p[(i-1) & 1] + p[i & 1]; 
        q[i & 1] = terms[i] * q[(i-1) & 1] + q[i & 1];
    }
    --len;

    return make_pair(p[len & 1], q[len & 1]);
}


int main() {
    
    vector<int> terms(30, 1);
    pair<int, int> frac = compute(terms);
    cout << fixed << setprecision(15);
    cout << 1. * frac.first / frac.second << endl;   // 1.618033988750541

    frac = compute(vector<int> {2, 3, 1, 2, 3, 1});
    cout << fixed << setprecision(15);
    cout << 1. * frac.first / frac.second << endl;   // 2.270833333333333

    return 0;
}

実数を分数に変換する

実は、これをやりたく連分数について勉強したのです。

実数xを分数p/qで近似せよ。

という問題を考えます。

1. xを連分数展開する。
2. 連分数を分数に変換する。

の手順でp/qを導出することが出来ます。かなりテキトーなコードですが、お遊びレベルではそれっぽく動いています。

#include <cstdio>
#include <cmath>

using namespace std;

/*
 * 実数を分数に変換する
 */
void compute(double x, double eps = 1e-9) {

    double y = x;
    int a = (int)y;

    if (abs(a - x) < eps) {
        printf("%d / %d = %.15lf (diff = %.15lf)\n", a, 1, 1.*a, abs(a - x));
        return;
    }

    y = 1 / (y - a);
    int p[] = {a, 1};
    int q[] = {1, 0};

    int i = 0;
    while (i < 30) {
        a = (int)y;
        y = 1 / (y - a);
        ++i;
        p[i & 1] = a * p[(i-1) & 1] + p[i & 1]; 
        q[i & 1] = a * q[(i-1) & 1] + q[i & 1];

        if (abs(1. * p[i & 1] / q[i & 1] - x) < eps)
            break;
    }

    printf("%d / %d = %.15lf (diff = %.15lf)\n", 
           p[i&1], q[i&1], 1. * p[i&1] / q[i&1], abs(1. * p[i & 1] / q[i & 1] - x));
}

int main() {
    
    compute(sqrt(2));  // 47321 / 33461 = 1.414213562057320 (diff = 0.000000000315775)     
    compute(sqrt(3));  // 51409 / 29681 = 1.732050806913514 (diff = 0.000000000655363)  
    compute(M_PI);     // 103993 / 33102 = 3.141592653011902 (diff = 0.000000000577891) 
    compute(1.222);    // 611 / 500 = 1.222000000000000 (diff = 0.000000000000000)      

    return 0;
}

実は昔同じ問題を考察していたのを思い出しました。このときは二分探索/しゃくとり法で解こうとしていたみたいです。
今回連分数を勉強して、より実用的なツールを手に入れたなという感じです。

C#入門（10）拡張メソッド

　拡張メソッド(Extension Method)を使うと、既存のクラスにインスタンスメソッドを追加する（したように見せかける）ことが出来る。

　これはなかなか面白い。
intに、Negate、Add、ToBinaryという拡張メソッドを定義してみた。
ポイントは、thisというキーワードをつけること。

using System;

public static class Extentions
{
    public static int Negate(this int value)
    {
        return -value;
    }

    public static int Add(this int value, int x)
    {
        return value + x;
    }

    public static string ToBinary(this int value)
    {
        string ret = string.Empty;
        while (value > 0)
        {
            ret = (value & 1).ToString() + ret;
            value >>= 1;
        }

        return ret;
    }

}

public class Sample
{
    public static void Main (string[] args)
    {
        new Sample().run();
    }

    public void run() 
    {
        int x = 10;
            
        Console.WriteLine("{0}", x.Negate());
        Console.WriteLine("{0}", x.Add(100));
        Console.WriteLine("{0}", 1000.ToBinary());
    }

}