Nothing but Programming: Algorithm

Showing posts with label Algorithm. Show all posts

HeapSort (C++ Template関数実装)

久しぶりに、プログラミング。
今日はいままで自分で書いたことなかったヒープソート。


#ifndef __HEAPSORT_H__
#define __HEAPSORT_H__

template 
void MaxHeapify( T* target, unsigned int index , unsigned int length) {
	unsigned int l = index<<1;
	unsigned int r = (index<<1)+1;
	unsigned int max = index;
	if( l < length && target[index] < target[l]	){
		max = l;
	}
	if( r < length && target[max] < target[r] ){
		max = r;
	}
	if( index != max ){
		T tmp = target[index];
		target[index] = target[max];
		target[max] = tmp;
		MaxHeapify( target, max, length );	
	}

	return;
}

template 
void BuildMaxHeap( T* target, unsigned int length ){
	for( unsigned int i = (length-1)/2; true ; i-- ){
		MaxHeapify( target, i, length );
		if( 0 == i ){
			break;
		}
	}
}


template 
void HeapSort( T* target, unsigned int length){
	BuildMaxHeap( target , length );
	while(length != 0 ){
		T tmp = target[length-1]; 
		target[length-1] = target[0];
		target[0] = tmp;
		length--;
		MaxHeapify(target, 0, length );
	}
}

#endif

includeしてから次ように使う。


unsigned char buf[] = {5,7,10,8,11};
HeapSort( buf, 5 );
//ここでbuf内はソート済み。

ヘルニアで寝込んでしまった。早１か月。いまだに10分以上立ったり座ったりはできない。
つらい・・・。

まあ、そんなことを言っていてもどうもならないし、病院に行ってはいるので、そこで言われるようにするしかないということで、勉強をしようと思って、本なりビデオなりを見ている。

そんなとき、以前にFacebookの採用情報欄にパズルが載っていたのを思い出した。プログラミングの問題が載っていて、それを解いて送ると、まあ、採用に少しは考慮してくれるみたいな感じのやつ。
ただし、結構難しい。

というわけで、今回はこれをやってみることにした。
http://www.facebook.com/careers/puzzles.php#!/careers/puzzles.php?puzzle_id=8
Peak Trafficという問題。

いろいろアルゴリズムなどを調べながらやった。
今回はちょっと１日当たりパソコンを触っていられる時間も限られているので、２週間ぐらいかけてちょっとづつ調べたり、プログラム書いたりして完成させた。

Facebookにこのトピックに関しての掲示板があったのでそこも参考にした。すでに解いている人が、テスト用データやどのくらい処理に時間がかかったかなどを載せている。
http://www.facebook.com/careers/puzzles.php#!/topic.php?uid=15325934266&topic=6943

とりあえず、今日Facebookに送ったところ、正解とのこと。扱ったことのないデータ構造やアルゴリズムだったのでそれだけでもかなり勉強になった。

ただ、何日か前に一応答えを出せるプログラムは書いたのだけれど遅いのが気になって少し何とかならないかと挑戦したけど、だめだった。
さっきの掲示板に投稿している人は、あるテストデータ（60MB程度）を処理するのにPythonで書いて、10秒以内だそうだ。ちなみに僕のはRubyで書いて6分；；。お話になりません。

どうしたらいいんだろうと考えたけど、だめだった。まだまだ考えられる余地はあるので、まだがんばる。
PythonとRubyの差も多少はありそうだが、そんなレベルの違いじゃないな。

ちなみに、そんなときに出会ったのが以下のレクチャー
（これ自体はこのとはの直接の答えではないけど、何か得られるものがないかと思って見た。）
この前のMITの授業といい、こんなのが見られるなんて何て素晴らしいんだ。
ほかにもUCBerkleyのStructure and Interpretation of Computer Programを使った授業もYouTubeで見られる。
この辺は、どこかのページにテキストブックとともにまとめておく価値がありそうだ。