nginxでリバースプロキシ使ってnode.jsのSocket.IOを使う

nginxの比較的新しいバージョンではWebSocketのリバースプロキシに対応しているので、試して見ました。

今回はsocket.ioを使い、
nginxのバージョンは1.4.3を使いました。

nginxのプロキシの設定を設定ファイルに加えます。
/etc/nginx/conf.d/default.conf

    location /socket.io/ {
        proxy_pass ＜socket.ioのサーバ＞;
        # 例) proxy_pass http://localhost:1234;
        proxy_http_version 1.1;
        proxy_set_header Upgrade $http_upgrade;
        proxy_set_header Connection "upgrade";
    }

設定を変えたら。
チェックをします。

$ sudo /etc/init.d/nginx configtest
nginx: the configuration file /etc/nginx/nginx.conf syntax is ok
nginx: configuration file /etc/nginx/nginx.conf test is successful

問題がなければnginxの再起動

$ sudo /etc/init.d/nginx restart
nginx を停止中:                                            [  OK  ]
nginx を起動中:                                            [  OK  ]

C++ boost ライブラリ インストール (Visual Studio 2012)

C++ boost ライブラリ　インストール

Visual Studio2012でBoostライブラリを入れた時のメモです。

この記事を書いた時点での最新バージョンは
Version 1.53.0
です。

下記サイトから最新バージョンをダウンロードします。
http://www.boost.org/

windowsであればzipファイルのものをダウンロードすればおｋです。

そのファイルを適当なところに展開します

自分はD直下にboostというフォルダを作りそこに展開しました

D:\boost

次にVisualStudioのコマンドプロンプトを開き作業フォルダを今展開したファイルのところにします。

>cd D:\boost\

そして次のコマンドを実行

>\bootstrap

このコマンドは32bit版のVSのコマンドプロンプトじゃないと動かないみたいです。

上記のコマンドを実行したら次のコマンドを実行します。

>b2 --build-dir=build\x86 --stagedir=stage/x86 address-model=32 -j 4
>b2 --build-dir=build\x64 --stagedir=stage/x64 address-model=64 -j 4

今回はboostを32bitと64bitの両方入れたかったため、 address-modelオプションで指定しています。
stagedirを指定することで32bitと64bitを分けています。

• j 4 というオプションは -j Nと指定することでN並列でビルドできます。　つまりマルチコアならビルドが早くなります。

このあとしばらく時間がかかりますがこれでインストールは完了です。

今回の実行では
インクルードパスは

D:\boost\boost_1_53_0

ライブラリパスは
32bit

D:\boost\boost_1_53_0\stage\x86\lib

64bit

D:\boost\boost_1_53_0\stage\x64\lib

という風になります。

このパスをVisualStudioのプロジェクトの設定でパスを追加すればboostが使えるようになります。

vectorのメモ その１

C++でvector使っててちょっと気づいたことのメモ。
タイトルにその１とかついてるけどまたなんかあったらその２とか作るかもしれないからです。

VisualStudioのDebugビルドだとvectorのアクセスは遅い

saxpyをやってみて比較してみました。
saxpyというのは
数式で表すと
Y = a * X + Y
となります。（Y,Xはベクトル、aはスカラ)
単精度の場合はsaxpyですが倍精度の場合はdaxpyと言ったりします。

問題サイズ（要素数）は10000000です。

最適化オプションなし

	Debugビルド	Releaseビルド
配列	0.0202452（秒）	0.0236787（秒）
vector	0.827819（秒）	0.0493195（秒）

Debugビルド時にvectorがものすごく遅いのがわかります。
Releaseビルドでは使えるレベルですが、配列を使た時の半分の性能しか出ていません。

Releaseビルドでは最適化を行うと思うので、VSのO2オプションをつけて計測してみました。
O2オプション

	Releaseビルド
配列	0.00778593（秒）
vector	0.00793234（秒）

ちゃんと最適化を行えば配列もvectorもあまり大差ない結果になるみたいです。

同様の実験をg++でもやってみました。
上述のものとは違う端末を使っているので速度は上のものとは異なっています。

g++

	最適化なし	O3
配列	0.0412589(秒)	0.0097611(秒)
vector	0.080672(秒)	0.0137689(秒)

最適化オプションなしの場合でも、最適化オプションをO3にした場合でもvectorが遅くなっているのがわかります。

vectorって便利ですがやはり配列よりは遅いんですかね。

vectorの2次元配列は連続メモリ配列にならない

意外と忘れてしまったまま使いそうなので一応メモ。

vectorの2次元配列を作る場合に、次のような書き方をすることがあると思います。

vector< vector<float> > array(10, vector<float>(10));

こうすることで10*10の二次元配列ができるわけですがメモリ連続にはなりません。

解決策としては
1次元配列を2次元配列のように使えば大丈夫ですね。
実際この方法を使うのが多いかもです。
10*10のvectorを作りたい場合は

vector<float> array(10*10);

のように必要なサイズを1次元配列でとってしまいます。
アクセスするときは
たとえば3行目0列目にアクセスしたいときは
array[3*10 + 0]
5行目8列目にアクセスしたいときは
array[5*10 + 8]
といった感じにアクセスできます。

もう一つの解決策としては
boostライブラリのboost::multi_arrayなどを使えばメモリ連続に領域確保もでき、array[i][j]のようなアクセスも可能になります。

まとめ

・vectorは配列よりも遅い
・VisualStudioを使うときはDebugビルドだとかなり遅い
・vectorの二次元配列はメモリ連続にならない
　　解決策としては
　　　　・1次元配列で一括で領域を確保して２次元配列のように扱う
　　　　・boostライブラリのboost::multi_arrayを使う

AOJでの入出力メモ C++

AOJで問題を解くときに入出力の仕方を時間が開くと忘れちゃうのでメモ

入力の終わりまで処理する時

入力の終わりまで処理や、EOFまでといった場合です。AOJの問題はこのタプの入力が多そうです。
次の書き方で入力を取れます。

int a;
while(cin>>a){
    //処理;
}

EOFの時にループから抜けます。

たまに入力の終わりが0みたいな問題もありますがそういう場合は次のようにすればよい。

int a;
while(cin>>a&&a){
}

複数の入力

スペースで区切られた以下のような複数の入力

10 13

こういう場合は

while(cin>>a>>b){
}

こんなかんじで

文字列

文字列の入力はスペースのところまでとる場合は

string s;
cin>>s;

１行取る場合はgetline関数を使います。

string s;
getline(cin,s);

カンマで区切られてる時

5,3
6,4
1,6

こんなかんじの時です。
cin行を文字列としてとって1文字目と３文字目を数値に変換して読み取るとかすればできるかもしれませんがscanfを使うと楽です。

int a,b;
scanf("%d,%d",&a,&b);

桁数が決まった出力をする時

coutでも桁数の指定ができると思いますが、なんかうまくできなかったので、printfを使った方法を書いておきます。
少数第３位まで出力したい場合は以下の様にします。

printf("%.3f %.3f\n",a,b);

整数部分の桁数を指定したい場合は

printf("%3d",a);

と言った感じです。
ちなみにprintfで制度指定した場合は四捨五入されるようです。
coutを使った方法は結構めんどくさそうなので気が向いたらまたメモすると思います。

エラトステネスのふるい

プログラミングメモ
エラトステネスのふるいというアルゴリズムを初めて使ってみたので、忘れないようにメモ

AOJ 0009 Prime Number

AOJ 0009 の問題
整数n以下の素数の数を出力するという問題です。

はじめは試し割りみたいな感じでやってみたんですが、TimeLimitになってしまったので。エラトステネスのふるいというアルゴリズムを使ってみました。

とりあえず書いてみたプログラムが以下のもの

エラトステネスのふるい

#include <iostream>
using namespace std;
#define MAX 10000000
bool prime[MAX]={true};

int countPrime(int n){
	if(n<2) return 0;
	if(n==2) return 1;
	int ret=0;
	for(int i=0;i<MAX;i++) prime[i]=true;
	for(int i=2;i*i<=n;i++){
		if(prime[i]){
			for(int j=i*i;j<=n;j=j+i){
				prime[j]=false;
			}
		}
	}
	for(int i=2;i<=n;i++){
		if(prime[i]) ret++;
	}
	return ret;
}

int main(){
	int n;
	while(cin>>n){
		cout <<countPrime(n) <<endl;		
	}
	return 0;
}

エラトステネスのふるいはO(n)らしいのでかなり高速です。

アルゴリズムについてはwikipediaをみるとわかりやすかったです。

このブログを書いてて気づきましたがこの問題の場合複数の入力があり、入力されるnは６桁という制約があるので、入力されたnに対して毎回数え直すのではなく、
1000000まで一度ループを回して素数を決めてしまって、その後に入力されたnまでの素数を数えるっていう風にしたほうがよさそうですね。

AOJ登録してみた

いまさらですけどAOJに登録してみました。
AOJっていうのはAIZU ONLINE JUDGEという競技プログラミングのサイトです。

今まで競技プログラミングはTopCoderは登録していましたが、TopCoderは英語だったりするので、ほとんどやっていませんでした。

AOJは問題が日本語のものもあるのでとっつきやすいです。
簡単な問題もあって、自分にあった問題が選べるので、
「なんかプログラミングしたいけど今特に作りたいものがない」
みたいなときにお世話になりそうです。

やってみると意外とはまってしまって楽しいです！

ソート速度比較

最近C言語にあまり触っておらず、忘れそうだったのでCを使ったのと、
これから卒業研究でもおそらくCを使うので、リハビリとしていろいろなソートを実装してみました。
ついでに速度比較も。

選択ソート

#include <stdio.h>
#include <time.h>
#include <stdlib.h>

#define SIZE 10
int main(){
	
	int *array;
	int i,j;
	int tmp;
	int min;

	array = (int*)malloc(sizeof(int)*SIZE);

	srand((unsigned)time(NULL));
	for( i=0; i < SIZE; i++){
		array[i] = rand();				
	}

	for( i=0; i<SIZE;i++){
		min=i;
		for(j=i+1;j<SIZE;j++){
			if(array[min]>array[j]){
				min = j;
			}
		}
		tmp = array[i];
		array[i] = array[min];
		array[min] = tmp;
	}

	for( i=0; i < SIZE; i++)
			printf("%d \n",array[i]);	
}

バブルソート

#include <stdio.h>
#include <time.h>
#include <stdlib.h>

#define SIZE 10

int main(){
	
	int *array;
	int i,j;
	int tmp;
	int flag;

	array = (int*)malloc(sizeof(int)*SIZE);
	srand((unsigned)time(NULL));
	for( i=0; i < SIZE; i++){
		array[i] = rand();				
	}
	
	for( i=0; i<SIZE;i++){
		flag=0;
		for(j=0;j<SIZE-i-1;j++){
			if(array[j]>array[j+1]){
				tmp = array[j];
				array[j] = array[j+1];
				array[j+1] = tmp;
				flag=1;
			}
		}
		if(!flag)
				break;
	}

	for( i=0; i < SIZE; i++)
			printf("%d \n",array[i]);
				
}

シェーカーソート

バブルソートを改良したようなものです。

#include <stdio.h>
#include <time.h>
#include <stdlib.h>

#define SIZE 10
int main(){
	
	int *array;
	int i,j;
	int right,left,last_swap_index;
	int tmp;

	array = (int*)malloc(sizeof(int)*SIZE);
	srand((unsigned)time(NULL));
	for( i=0; i < SIZE; i++){
		array[i] = rand();				
	}

	right=SIZE-1; left=0;
	while(right>left){
		for(i=left;i<right;i++){
			if(array[i]>array[i+1]){
				tmp = array[i];
				array[i] = array[i+1];
				array[i+1] = tmp;
				last_swap_index=i;
			}
		}
		right = last_swap_index;

		for(i=right;i>left;i--){
			if(array[i]<array[i-1]){
				tmp=array[i];
				array[i] = array[i-1];
				array[i-1] = tmp;
				last_swap_index=i;
			}
		}
		left = last_swap_index;
	}
		
	for( i=0; i < SIZE; i++)
			printf("%d \n",array[i]);
				
}

挿入ソート

#include <stdio.h>
#include <time.h>
#include <stdlib.h>

#define SIZE 10
int main(){
	
	int *array;
	int i,j;
	int tmp;

	array = (int*)malloc(sizeof(int)*SIZE);

	srand((unsigned)time(NULL));
	for( i=0; i < SIZE; i++){
		array[i] = rand();				
	}
		
	for( i=1; i<SIZE;i++){
		tmp=array[i];
		if(array[i-1]>tmp)
		{
			j=i;
			do{
				array[j]=array[j-1];
				j--;
			}while(j>0 && array[j-1] > tmp);
			array[j] = tmp;
		}
	}

	for( i=0; i < SIZE; i++)
			printf("%d \n",array[i]);
				
}

ヒープソート

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define SIZE 10

void HeapSort(int *, int);
void DownHeap(int * , int , int );

int main()
{
	int *array;
	int i;

	array = (int*)malloc(sizeof(int)*SIZE);

	srand((unsigned)time(NULL));
	for(i=0;i<SIZE;i++)
		array[i] = rand();

	HeapSort(array,SIZE-1);

	for(i=0;i<SIZE;i++)
		printf( "%d\n",array[i]);
	
	return 0;
}

void HeapSort(int *array, int n){
	int leaf,root;
	int tmp;

	leaf = n;
	root = n/2;

	while(root>=0){
		DownHeap(array,leaf,root);
		root--;
	}

	while(leaf>=0){
		tmp = array[0];
		array[0] = array[leaf];
		array[leaf] = tmp;
		leaf--;
		DownHeap(array,leaf,0);
	}
}

void DownHeap(int *array,int leaf , int root){
	int i;
	int tmp;

	i = root*2+1;
	while(i <=leaf){
		if(i<leaf && array[i+1]>array[i])
			i++;
		if(array[root] >= array[i])
			break;
		tmp = array[root];
		array[root] = array[i];
		array[i]=tmp;

		root = i;
		i=root*2+1;
	}
}

クイックソート

最速と言われているソートです。

#include <stdio.h>
#include <time.h>
#include <stdlib.h>

#define SIZE 10

void quickSort(int* array ,int ,int );

int main(){
	
	int *array;
	int i;

	array = (int*)malloc(sizeof(int)*SIZE);

	srand((unsigned)time(NULL));
	for( i=0; i < SIZE; i++){
		array[i] = rand();				
	}

	quickSort(array,0,SIZE-1);

	for( i=0; i < SIZE; i++)
			printf("%d \n",array[i]);
	
}

void quickSort(int* array, int min, int max){
	int mid,key,i,j,tmp;
	if(min<max){
		mid = (min+max)/2;
		key = array[mid];
		i = min;
		j = max;
		do{
			while(array[i]<key)
					i++;
			while(array[j]>key)
					j--;
			if(i <=j){
				tmp = array[i];
				array[i++] = array[j];
				array[j--] = tmp;
			}
		}while(i<=j);
		quickSort(array,min,j);
		quickSort(array,i,max);
	}
}

マージソート

#include <stdio.h>
#include <time.h>
#include <stdlib.h>

#define SIZE 10
int* tmp;

void MergeSort(int* array ,int ,int );

int main(){
	
	int *array;
	int i;

	array = (int*)malloc(sizeof(int)*SIZE);
	tmp  = (int*)malloc(sizeof(int)*SIZE);

	srand((unsigned)time(NULL));
	for( i=0; i < SIZE; i++){
		array[i] = rand();				
	}

	MergeSort(array,0,SIZE-1);

	for( i=0; i < SIZE; i++)
			printf("%d \n",array[i]);
	
}

void MergeSort(int* array, int left, int right){
	int mid,i,j,k;
	if(left>=right) return;

	mid = (left+right)/2;
	MergeSort(array,left,mid);
	MergeSort(array,mid+1,right);

	for(i=left; i<=right;i++)
			tmp[i] = array[i];

	i = left;
	j = mid+1;

	for(k=left; k<=right &&i<=mid && j <= right ;k++){
		if(tmp[i] <= tmp[j])
			array[k]=tmp[i++];
		else
			array[k] = tmp[j++];
	}
	while(i <=mid){
		array[k++] = tmp[i++];
	}
}

シェルソート

挿入ソートを改良したアルゴリズムです。

#include <stdio.h>
#include <time.h>
#include <stdlib.h>

#define SIZE 10

int main(){
	int *array;
	int i,j;
	int h;
	int tmp;

	array = (int*)malloc(sizeof(int)*SIZE);

	srand((unsigned)time(NULL));
	for( i=0; i < SIZE; i++){
		array[i] = rand();				
	}

	while(h<SIZE)
		h=2.25*h+1;

	while(h>1){
		h=h/2.25; 
		for(i=h;i<SIZE;i++){
			tmp = array[i];
			if(array[i-h]>tmp){
				j=i;
				do{
					array[j] = array[j-h];
					j-=h;
				}while(j>h && array[j-h] > tmp);
				array[j] = tmp;
			}
		}
	}


	for( i=0; i < SIZE; i++)
			printf("%d \n",array[i]);
				
}

今日はソースだらけですね。
解説はあまり書きませんが、選択ソート、バブルソート、挿入ソート、シェーカーソートはO(N*N)です。
ヒープソート、クイックソート、マージソートはO(N*logN)
シェルソートはO(N^1.25)といわれています。

実行時間の比較のグラフを作ったので見てもらうと速さの違いがわかると思います。

やはりバブルソートが一番遅いです。
挿入ソートも割と早いですね。
同じO（n^2）のアルゴリズムでもかなり差があります。

O（nlogn）とシェルソート(O(n^1.25))のものはこの要素数ではほとんど実行時間がかかりませんでした。

O(nlogn)とO(n^1.25)のアルゴリズムについてはもっと要素数を大きくした物を別にグラフを作りました。

O(n^1.25)のシェルソートがおもったより早いです。
ヒープソートよりも早いという結果に。ヒープソートはもっといいコードの書き方があるかも。

そしてやはりクイックソートは早いですね。

そんなクイックソートも実は要素数が少ない場合は挿入ソートのほうが早いらしい。
そのためクイックソートの途中の部分配列が十分小さくなったら挿入ソートを用いて最適化することもできる。

ヒープソートは少し遅いが最悪時でも計算量はO(n logn)なので、クイックソートの最悪時であるO（n^2）を避けることができる。

ただ並び替えをするアルゴリズムだけでもいろいろな種類があり、速さに差があるのは知っていましたが、実際に書いて自分で実査に速度を測ってみてどの程度の差があるかというのを実感できました。