2017-02-27

Go 変数宣言についてのまとめ

仕事で Goを使う機会があったので、基本から勉強していて、変数宣言について気になった点についてメモがてらまとめます。

Golangにおける変数宣言において、 varをつかって変数宣言をするのが一般的

package main

import (
  "fmt"
)

func main() {

  // int型で宣言 初期値指定なし
  var i int

  // iとjをint型で宣言 初期値指定なし
  var i, j int

  // iとjをint型で宣言 初期値指定あり
  var i, j int = 1, 2

}

上記の方法だと変数毎に型を指定しましたが、 := をつかえば、型を指定せずに、暗黙的に変数宣言ができます。

package main

import "fmt"

func main() {
  var i, j int = 1, 2

  // := は暗黙の型変形
  k := 3
  c, python, java := true, false, "no !"

  // 1 2 3 true false no ! と表示される
  fmt.Println(i, j, k, c, python ,java)

  var i int = 1
  j := "1"  // string
  k := 1    // int

  // 変数型の確認
  fmt.Println(reflect.TypeOf(i))
  fmt.Println(reflect.TypeOf(j))
  fmt.Println(reflect.TypeOf(k))
}

ただし、:= をつかった暗黙的宣言は、基本的に関数スコープ内でのみの利用が可能で、関数宣言外では利用できません。

package main

import "fmt"

// 関数外での暗黙的宣言
l := 1
func main() {
  t := 1
  fmt.Println(t)
}

// コンパイルエラーが出る
$go run test-type.go
./test-type.go:7: syntax error: non-declaration statement outside function body

2017-02-05

mongod replicaSet セカンダリノードを起動後に[RS102 too stale to catch up]が出たときの対処法

mongo replicaSet

mongoでレプリカセットを組んでいて、たまに障害でセカンダリノードのサーバなどが死んで、
セカンダリノードのmongodプロセスを起動した後に、プライマリのデータをsyncできずに下記のエラーが出る場合があります

[rsBackgroundSync] replSet error RS102 too stale to catchup, at least from....

このエラーは、セカンダリノードが数時間とか長い間死んだ状態になっていて、syncの状態がstale(古い)な状態で再起動した場合に発生します。

原因

原因としては、セカンダリノードのoplogの情報が古すぎてsyncできないことが挙げられます。
mongoの仕組みとして、プライマリノードにデータが書き込まれるときのオペレーション情報をoplogに保持しています。
oplogコレクションは capped size collectionのため、一定サイズを超えた場合に古いものから消されていきます。セカンダリノードはこのプライマリノードのoplogをtailしてsyncを行うのですが、セカンダリノードが死んだままだと、
syncに必要なoplogの状態が更新されずに、プライマリのデータとsyncさせるためのデータが欠損してしまうために、このエラーが出ます。

対策

対策としては、セカンダリノードで持っているデータは古すぎて使えないため、一回まっさらな状態にした後にmongodを起動させると、初期状態からsyncが始まり、復旧できます

問題が起きたセカンダリノードのmongodプロセスを停止する
セカンダリノードのデータディレクトリ(/data/mongodb とか、設定していたデータディレクトリ)を削除する。
再度mongodをリセットする

これで再度初期状態からsyncが始まり、完了すると再びセカンダリノードとして復旧できます。

参考

stackoverflow.com

2017-02-02

ソフトマックス関数についてのまとめ

ニューラルネットワーク機械学習

前回の記事でニューラルネットワークの出力に対する活性化関数にシグモイド関数を使うことを紹介しました。今回では、分類問題をニューラルネットワークをつかって解く際に、活性化関数としてよく使われるソフトマックス関数についてまとめます。

ソフトマックス関数とは

数式で表すと以下のとおりになります。

${\large y_k = \frac {exp(a_k)} {\sum_{i=0}^n exp(a_i)}}$

ソフトマックス関数の利点と特徴

ソフトマックス関数の特徴としては、大きく２つにわけられます。
- 出力の各要素の値域が $0 \leq y_i \leq 1$ となる
- 出力の総和が1となる

この２つのうち、2番目がニューラルネットワークで使う上で重要となります。なぜならば、出力値の各要素の総和が1になるので、出力層の各ユニットの値を確率として解釈することができます。
これにより、問題に対して確率的アプローチを取れるようになります。

ソフトマックス関数の注意点

上記のように、ニューラルネットワークでソフトマックス関数を使うことで、出力層の各ユニットの値を確率として表現でき、統計的アプローチが取れる様になるのですが、
コンピュータ上でソフトマックス関数を使う際に注意点があります。
注意点は、ソフトマックス関数で $exp(a_i)$ を使うのですが、指数関数は入力値が増えると、出力の増加率も大きいので、値によっては桁数がたりずにオーバーフローしてしまいます。

どう解決するか

上記のオーバーフローの問題を解決するために、ソフトマックス関数の数式を、logと指数の性質を利用して変形していきます。

${\large y_k = \frac {exp(a_k)} {\sum_{i=0}^n exp(a_i)}}$ (1)

分母と分子に定数Cをかけて
${\large = \frac {Cexp(a_k)} {C \sum_{i=0}^n exp(a_i)}}$ (2)

$Cexp(x) = exp(x + logC)$ なので

${\large = \frac {exp(a_k + logC)} {\sum_{i=0}^n exp(a_i + logC)}}$ (3)

$logC = C1$ として、さらに別の定数を用いて
${\large = \frac {exp(a_k + C1)} {\sum_{i=0}^n exp(a_i + C1)}}$ (4)

と表すことができる。ニューラルネットワークにおいては、上記の $C1$ は入力信号の中で最大の値を用いるのが一般的です。
正負のどちらでも問題ないので、最大値を取得した上で、それを引くことでオーバーフローを回避できます。

import numpy as np
a = np.array([0.3, 2.9, 4.0])

def softmax_imp(a):
    # 入力値の中で最大値を取得
    c = np.max(a)
    # オーバーフロー対策として、最大値cを引く。こうすることで値が小さくなる
    exp_a = np.exp(a - c);
    sum_exp_a = np.sum(exp_a)

    y = exp_a / sum_exp_a
    return y

print(softmax_imp(a))

numpyを使えば、配列に対して最大値を求めたり、各要素に対して同じ処理を行うことが容易にできるので、かなり楽にかけます。

2017-01-23

php mysql でコネクションプールを貼る

php mysql

phpからmysqlを使う際に、拡張モジュールであるmysqliを使って mysqlサーバとの接続、クエリ実行を行う場合コネクションプールを貼る事ができます。公式ドキュメントによると、phpでのコネクションプールはphp5.3から対応されています。

PHP: mysqli 拡張モジュールでの持続的接続 - Manual

コネクションプールを貼ることによって、クライアント接続毎に新たにコネクションを張り直す必要がなく、再利用することができます。

実際には、mysqliのインスタンス生成時のホスト名の先頭に「p:」をつければ自動的にやってくれるようです。

  $mysqli = new mysqli('p:127.0.0.1, 'mysql_user', 'mysql_pass', 'mysql_db_name');

2017-01-11

Node.js clusterモジュールについて

Node.js cluster

シングルスレッドで動作するNode.jsにおいて、マルチコアCPUを持っているマシンの能力を最大限引き出すために、
複数のワーカープロセスを起動して処理を分散させたいといったニーズがあると思います。
そのときに重要なclusterモジュールについて、いつも業務で使っていますが、さらなる理解のため、整理してみます。
この記事は、Node.jsバージョンv6.x系を前提とした話となります。

clusterモジュール

clusterモジュールについて、大まかな処理の流れは、ドキュメントやNode.jsユーザグループのブログ(Node.js v0.6時のもので古いです)が非常に参考になります。
blog.nodejs.jp

clusterモジュールによるプロセス間通信には2つの方法があり、それぞれ紹介していきます。

マスタープロセスによるロードバランシング

この方法では、マスタープロセスは指定したポートで待ち受けて、新たなコネクションを受け付けます。
リクエストがあるたびに、マスタープロセスはラウンドロビン方式でワーカープロセスに処理を委譲します。
この方法の場合、リクエストが来るたびにマスタープロセスがロードバランサーとして仕事をするために、同時アクセス数が増加したときに、サーバ全体のスループットが、
マスタープロセスの上限に依存します。
この方法は、上記の問題から、webサーバにおいてあまり利用されることがなく、複数マシン間で処理を分散する場合のリバースプロキシとして用いられることが多いです。

カーネルによるロードバランシング (v0.11.2以降デフォルト)

マスタープロセスからソケットを作成し、ワーカプロセスに接続済みソケットを渡してクライアントとワーカプロセス間で接続を行う方法です。
このアプローチはNode.js v0.11.2からUnix系プラットフォーム(windows以外のこと)でデフォルトになりました。理論的には、この方法が最も良いパフォーマンスを提供します。

clusterモジュールを実際に使ってみる

実際にclusterモジュールを使って動かしてみるのが理解しやすいので、公式ドキュメントのサンプルを参考にwebサーバを作ってみました。

// clusterテスト用
// master workerプロセス共に、このプログラムの上から処理が走る

"use strict";

const cluster = require('cluster');
const http = require('http');

if (cluster.isMaster) {
  // masterプロセスの場合の処理

  // Keep track of http requests
  var numReqs = 0;
  setInterval(() => {
    console.log('numReqs =', numReqs);
  }, 1000);

  // Count requests
  function messageHandler(msg) {
    if (msg.cmd && msg.cmd == 'notifyRequest') {
      numReqs += 1;
    }
  }

  // Start workers and listen for messages containing notifyRequest
  // cpu数を取得し、cpu数分だけ、ワーカープロセスをforkする
  const numCPUs = require('os').cpus().length;
  for (var i = 0; i < numCPUs; i++) {
    cluster.fork();
  }

  Object.keys(cluster.workers).forEach((id) => {
    // クラスター毎にメッセージハンドラー(リクエスト数カウント処理)を設定する
    // messageイベントを受信したときに発火する
    cluster.workers[id].on('message', messageHandler);
  });

  cluster.on('exit', (worker, code, signal) => {
    console.log('worker %d died (%s). restarting...', worker.process.pid, signal || code);
  });
} else {
  // workerプロセスの処理

  // Worker processes have a http server
  http.Server((req, res) => {
    console.error('---Request header.', req.headers)
    res.writeHead(200);
    res.end('hello world \n');

    // notify master about the requests
    process.send({
      cmd: 'notifyRequest'
    });
  }).listen(8000);
}

マスタープロセスでの処理

マスター・ワーカープロセスともに上記のコードを上から実行していくのですが、それぞれのプロセスにおいて cluster.isMasterという値を持っており、この値でマスター・ワーカープロセスを判断しています。

マスタープロセスの場合、CPUコア数分のワーカープロセスをforkする処理をおこなっており、それぞれのワーカープロセスに対して、
プロセス間メッセージを受信したときのmessageイベントと、ワーカープロセスが死んだときのexitイベントに対するハンドラ関数をそれぞれセットしています。

  // masterプロセスの場合の処理

  // Keep track of http requests
  var numReqs = 0;
  setInterval(() => {
    console.log('numReqs =', numReqs);
  }, 1000);

  // Count requests
  function messageHandler(msg) {
    if (msg.cmd && msg.cmd == 'notifyRequest') {
      numReqs += 1;
    }
  }

  // Start workers and listen for messages containing notifyRequest
  // cpu数を取得し、cpu数分だけ、ワーカープロセスをforkする
  const numCPUs = require('os').cpus().length;
  for (var i = 0; i < numCPUs; i++) {
    cluster.fork();
  }

  Object.keys(cluster.workers).forEach((id) => {
    // クラスター毎にメッセージハンドラー(リクエスト数カウント処理)を設定する
    // messageイベントを受信したときに発火する
    cluster.workers[id].on('message', messageHandler);
  });

  cluster.on('exit', (worker, code, signal) => {
    console.log('worker %d died (%s). restarting...', worker.process.pid, signal || code);
  });

ワーカープロセスでの処理

ワーカープロセスでは、8000番ポートでhttpリクエストを受付、hello worldを返すhttpサーバの処理を行っています。このプログラムでは、リクエストを受け付けた際に、 process.sendで、マスタープロセスに対してリクエストを受け付けたことを通知しています。
マスタープロセスでは、このnotifyRequestコマンドを受け取ると、リクエストカウントをインクリメントして、1000ミリ秒毎にリクエストカウントを表示させています。

  // workerプロセスの処理

  // Worker processes have a http server
  http.Server((req, res) => {
    console.error('---Request header.', req.headers)
    res.writeHead(200);
    res.end('hello world \n');

    // notify master about the requests
    process.send({
      cmd: 'notifyRequest'
    });
  }).listen(8000);

サーバの起動

実際にサーバを起動してみて、挙動を確認します。
先程書いたプログラムを/Users/testuser/Documents/nodejs-sandbox配下のcluster-test.jsに作成し、ターミナルで実行します。

$ node cluster-test.js
numReqs = 0     // 1000ミリ秒毎にリクエストカウント表示
numReqs = 0

これでlocalhostの8000番ポートでリクエストを待ち受けている状態になりました。ためしに、起動されているnodeプロセスを確認すると、しっかりとCPUコア数分(8コア)ワーカープロセスが立ち上がっていることが確認できます。

testuser     81767   0.0  0.1  3050252  21320 s003  S+    2:31AM   0:00.15 /Users/testuser/.nodebrew/node/v6.9.2/bin/node /Users/testuser/Documents/nodejs-sandbox/cluster-test.js
testuser     81766   0.0  0.1  3068684  21408 s003  S+    2:31AM   0:00.16 /Users/testuser/.nodebrew/node/v6.9.2/bin/node /Users/testuser/Documents/nodejs-sandbox/cluster-test.js
testuser     81765   0.0  0.1  3041036  20876 s003  S+    2:31AM   0:00.16 /Users/testuser/.nodebrew/node/v6.9.2/bin/node /Users/testuser/Documents/nodejs-sandbox/cluster-test.js
testuser     81764   0.0  0.1  3068684  21580 s003  S+    2:31AM   0:00.16 /Users/testuser/.nodebrew/node/v6.9.2/bin/node /Users/testuser/Documents/nodejs-sandbox/cluster-test.js
testuser     81763   0.0  0.1  3049228  20980 s003  S+    2:31AM   0:00.16 /Users/testuser/.nodebrew/node/v6.9.2/bin/node /Users/testuser/Documents/nodejs-sandbox/cluster-test.js
testuser     81762   0.0  0.1  3068684  21652 s003  S+    2:31AM   0:00.16 /Users/testuser/.nodebrew/node/v6.9.2/bin/node /Users/testuser/Documents/nodejs-sandbox/cluster-test.js
testuser     81761   0.0  0.1  3068684  21604 s003  S+    2:31AM   0:00.15 /Users/testuser/.nodebrew/node/v6.9.2/bin/node /Users/testuser/Documents/nodejs-sandbox/cluster-test.js
testuser     81760   0.0  0.1  3068684  21464 s003  S+    2:31AM   0:00.16 /Users/testuser/.nodebrew/node/v6.9.2/bin/node /Users/testuser/Documents/nodejs-sandbox/cluster-test.js
testuser     81759   0.0  0.1  3059468  21468 s003  S+    2:31AM   0:00.13 node cluster-test.js

この状態のまま、クライアント用にターミナルをもう１つ立ち上げ、curlでhttpリクエストを送るとレスポンスが返ってくるのを確認できます。

$ curl localhost:8000
hello world

さらに、先程から起動していたサーバ側のターミナルには、リクエストカウントが1増えていることが確認できます。

numReqs = 0
---Request header. { 'user-agent': 'curl/7.37.0',
  host: 'localhost:8000',
  accept: '*/*' }
numReqs = 1

以上のように、clusterモジュールを使って、複数プロセスでwebサーバを立ち上げることができました。
clusterはNode.jsにおける負荷分散で欠かせないものなのでしっかりと理解することが重要かと思います。

2017-01-09

シェルソートについて

アルゴリズムシェルソート python

シェルソートは前回紹介した挿入ソートの改良版アルゴリズムです。
挿入ソートは一般的に、配列がほとんどソートされた状態で効率的に機能するもので、それ以外の場合では大きくパフォーマンスが落ちるのですが
シェルソートではその欠点を補う仕組みになっています。

計算量は以下の通りです。
- 最悪時計算量アルゴリズムの間隔関数に依存するが、 $O(nlog^2n)$
- 最良時計算量 $O(n)$
- 空間計算量 $O(1)$

アルゴリズムをpythonで書いてみると、以下の通りになります。

import sys

# シェルソート
def shellSort(aList):
    subListCount = len(aList) // 2
    while subListCount > 0:
        for pos in range(subListCount):
            doGapInsertionSort(aList, pos, subListCount)

        print("After increments of size", subListCount);
        print("The list is", aList);

        subListCount = subListCount // 2

# 挿入ソート ギャップあり版
def doGapInsertionSort(aList, startPos, gap):
    for i in range(startPos + gap, len(aList), gap):
        currentVal = aList[i]
        position = i
        while position >= gap and aList[position - gap] > currentVal:
            aList[position] = aList[position - gap]
            position = position - gap

        aList[position] = currentVal

a = [int(a_temp) for a_temp in input().strip().split(' ')]

#シェルソート実行
shellSort(a)
print(a)

シェルソートと挿入ソートの違い

挿入ソートでは、隣接要素間で比較を行い、2つの要素が逆順になっていたら値を交換していく処理になります。
それと違って、シェルソートでは、離れた要素間の比較と交換を実行できるようにし、アルゴリズムの最終ステップまで隣接要素を比較しないようになります。
挿入ソートでは1だけ離れたものを比較し、シェルソートではhだけ離れた要素を比較します。それによって、ある程度値にばらつきのある配列をソートする際に、並び替え回数が減らせるため処理速度が改善します。

シェルソート分析

一般的にシェルソートは大規模なリストに対しては最適でなく、1000〜10000までの中規模なアルゴリズムにおいて最も効率が良いと言われています。 $O(n^2)$ のアルゴリズムのなかでは最も高速となります。

シェルソートの欠点

欠点としては、アルゴリズムが複雑であり、マージソート・ヒープソート・クイックソートと比べたときに効率的でない点があげられます。

2017-01-07

挿入ソートについて

アルゴリズム

先月、Javascript advent calendarで、v8の配列ソートアルゴリズムにおいて、
配列の要素数に応じて挿入ソートとクイックソートを使い分けているという記事を書きました。
v8における配列ソートについて - kakts-log

今回は、挿入ソートについてまとめてみたいと思います。

挿入ソート

挿入ソートとは、ソートアルゴリズムの一種で、ある値をソート済み配列に追加するときに有効な手法です。
in-placeで、配列を書き換えながら行うので、空間計算量は $O(1)$ ですむためメモリ効率がよく、実装が簡単です。計算量は以下の通りになっています。

最悪計算時間 $О(n^2)$
最良計算時間 $O(n)$
平均計算時間 $О(n^2)$

pythonで書いてみると、以下の通りになります。

import sys

# スペース区切りで配列要素を入力
a = [int(a_temp) for a_temp in input().strip().split(' ')]

for pos in range(1, len(a)):
    # 交換対象の値を保持
    value = a[pos]
    # 配列の要素数 - 1 だけinsertがはしる
    i = pos - 1
    while i >= 0 and a[i] > value:
        # 前方の要素のほうが大きい場合は1つ後ろに値をずらしていく
        a[i + 1] = a[i]
        i = i - 1

    #チェックが終わったら 値を適切な位置に代入する
    a[i + 1] = value

print(a)

使うべき状況

配列の要素数が少ない時(20以下くらい) どれくらいの値をもって”少ない”とするかはマシンスペックやプログラミング言語によって異なりますが、だいたい20以下が望ましいようです。
Javascript エンジンのv8においては10以下のときに挿入ソートを採用しています。
配列がほぼソートされている状態の時配列の要素が、ほぼソートされていて、後ろの数要素だけソートされていない状態の場合、挿入ソートのパフォーマンスは非常に良くなります。
理由としては、配列の前方のほうがソートされているため、比較回数を劇的に減らせるためです。
重複する要素が存在する場合
重複する要素がある場合、データスワッピングの回数が減るため、計算量が減ります。

挿入ソートの利点

ソート時に用いるメモリ量が少ないソートにおいて、与えられた配列を直接書き換えていく仕組みなので、配列の要素以外にメモリを使う必要がありません。

計算量の分析

ベストケースの場合、n要素数の配列の場合計算量は $O(n)$ と、線形時間でソートを行うことができます。
しかし、この状況の配列をソートする可能性はほぼないため、インパクトとしては小さいですが、挿入ソートは、
comparison-basedなソートアルゴリズムの中で、唯一、ベストケースの振る舞いを持つソートアルゴリズムとなります。
そして、ソートする配列が重複なしで、ランダムに要素が並べられている場合は計算量が最悪になります。

平均、最悪な場合の計算量は、どちらも $O(n^2)$ となります。

他のソートアルゴリズムとの比較

要素数が少ない、またはほぼソート済みの配列の場合、クイックソートやマージソートよりも勝るので、要素数が少ないときは挿入ソート、それ以外の場合はクイックソートやマージソートを使うケースが多い。
また、挿入ソートの改良版としてシェルソートというものがある。