残業したくないあなたに：データ構造とアルゴリズム

#WHY

私が学生の時代や研修ではデータ構造やアルゴリズムのやり方は習いましたが実際にどのようなシチュエーションで使用してどのような欠点、利点があるかまで言及して教わった経験がありません。

”必要は発明の母”という言葉があるように現実的に使える形にしないと丸暗記して終わりです。

そこで今回のタイトルは”残業したくない”を押し出してみました。

実際のところデータ構造とアルゴリズムを把握することで計算量やメモリの使用量が大幅に変わってきます。

つまりこれを習得するだけでコストダウンや無駄な残業の抑制につながりハッピーになれる可能性を秘めているわけです。
今の時代はググれば手法自体はでてきます。ただどのような状況でどのデータ構造、どのアルゴリズムが良いかは状況によって変わります。その選択の指標になればと思いこの記事を書きました。

この記事によって一人でも多くの方の時間を作れて幸せになってくれると幸いです。

注意：筆者の知識で分かる範囲で記述しています。知見のある詳しい方が見て間違いが分かれば面倒かもしれませんが指摘して頂けると幸いです。私だけでなく私以外のこの記事を見た人のためになると思います。

#WHAT

本質的に大事になってくる考え方が扱うデータの大きさ、種類、必要とされる処理によって選択すべきデータ構造とアルゴリズムが変わってきます。具体的に確認すべき手順は下記です。

• 現状の処理のボトルネックがデータ構造またはアルゴリズムに関連していそうか調査
• 扱うデータの大きさ、種類を確認
• データ構造を選択
• アルゴリズムを選択(データ構造に依存して実装するかしないか決まる)
• データ構造とアルゴリズムを実装（場合によってはデータ構造のみ実装）
• 計測
• リソースの消費度合いの比較
• 問題なければ採用

高速化のためにはボトルネックの解消が必要です。アルゴリズムやデータ構造以外に時間がかかっている部分があればその部分に引きづられて速度が落ちます。
それを防ぐために最初に各モジュールごとの速度を計測しておきましょう。

単純に高速なアルゴリズムを使用しても計測した際に遅くなっている場合があります。これはスワップと呼ばれる物理メモリ空間に入りきらなかったデータをHDDなどに退避させる処理が頻繁に起こると発生します。
そのためリソースの消費具合の確認は必須になります。

扱うデータの見るべき指標

• データの種類
• データサイズ（メモリを大量に使用しそうか）
• 挿入・削除・更新の頻度
• 検索頻度

上記の指標によって扱うべきデータ構造が決まってきます。
挿入・削除、更新は基本的にデータの末尾ではなくデータの中間部を想定しています。

データ構造

• Array
• メリット：インデックスを通して高速にアクセス可能。末尾のデータ挿入、削除は高速
• デメリット：データが大きい場合に大量のメモリを消費する。インデックス中間部分へのデータの挿入、削除が遅い
• Linked List
• メリット：データをどの部分であっても挿入、削除が容易なためリサイズが容易
• デメリット： リンクを辿ってアクセスするためデータのアクセスが遅い。次のデータのアドレスを保持するためデータのサイズがその分大きくなる。
• Binary Tree
• メリット：挿入、更新がLinked Listのように高速にでき、なおかつ検索も早い。
• デメリット：深さが平衡していないと性能に悪影響を与える
• Trie
• メリット：辞書など大量のデータパターンを高速に扱いたい場合に使用
• デメリット：メモリ消費量が多い
• Graph
• メリット：TreeやTrieでは扱えない循環型のデータを扱う時に使用。nodeごとのコストを割り振ることもできるので最適なルートやコストを求める問題にも適用可能。
• デメリット： 複雑な為、扱うのが難しい
• Stack
• メリット：データの取得は高速。再帰的な処理などと相性が良い
• デメリット：何も考えずに使うとStack Over Flowのようなメモリリークを起こす。中間のデータにはアクセス不可
• Queue
• メリット：データの取得は高速。ファイルの入出力やWEBからのデータ入出力などと相性が良い
• デメリット：スタックと同様で何も考えずに使うとメモリリークを起こす。中間のデータにはアクセス不可

|データ構造 | データの種類 | データのサイズ |中間データに対する挿入・削除・更新の頻度 |中間データに対する検索頻度 |
|:-----------|------------:|------------:|------------:|------------:|:------------:|
| Array | プログラム内 | メモリのサイズに依存（中程度） |少ない |多い |
| Linked List | プログラム内 | メモリのサイズに依存（中程度） |多い |少ない |
| Binary Tree | プログラム内 | メモリのサイズに依存（中程度） |多い |多い |
| Stack | プログラム内 | メモリのサイズに依存（少ない） |無し |無し |
| Queue | 外部入出力 | メモリのサイズに依存（中程度） |無し |無し |
| Trie | プログラム内 | メモリのサイズに依存（大きい） |無し |無し |

Graphは大規模なデータや用途が特殊な場合に使用するので上記の指標とは別で定義します。

Graph：飛行機のルートやコスト計算など巡回型かつ各node間にコストを振りたい問題に使用

選択すべきアルゴリズム

• 扱うデータ構造
• 使用できるリソース

データ構造によってはソートしておくと恩恵をうけられるデータ構造があるためです。

• ソートによる恩恵が受けられるデータ構造
• Array

アルゴリズム

• Binary Treeで使用されるアルゴリズム

• 木構造の操作

• Graphで使用されるアルゴリズム

• 深さ優先探索

• 幅優先探索

• Arrayの作成前で使用されるアルゴリズム
  ソートアルゴリズムはクイックソートが基本的に使用されることが多いです。
  ただし条件によっては他のソートアルゴリズムを使用する場合もあります。

• クイックソート

  • 一般的に高速なアルゴリズムのため使用される機会が多い

• マージソート

  • 並列で処理が可能なため、メモリとCPUの並列数が豊富な場合に使用。

• 挿入ソート

  • マージソートやクイックソートに比べ、データの状態に依存していないため安定的にソート可能。主に小さなデータやすでにほとんどソート済みのデータに使用

• カウンティングソート

  • シンプルかつ高速なソート。メモリが豊富で扱うデータとマッチしていればこの手法が一番良い

• 高速化のためのテクニック

• 動的計画法

#HOW

ここで重要になるのが実際に記述できることです。その理由は実際に記述できないと中身が分からず、自分の環境に合わせたチューニングができないからです。早く帰るためにこの手間を惜しまないようにしましょう。
またアルゴリズムは汎用性が高いため一度マスターすれば言語関係なく利用できるため応用範囲が広いのも利点です。
著者は勉強のためにC++で記述しています。
Arrayは簡単なのでソートと合わせて記述しています。

Array

マージソート

マージソートのポイントは

• 中間の値を作成すること
• 中間の値を利用して2つ配列を作成すること
• それらを昇順にするために交換すること

void Merge(int *data_array, int left, int mid, int right){
	int n1 = mid - left;
	int n2 = right - mid;
	int *L = new int[n1];
	int *R = new int[n2];
	for(int i = 0; i < n1; i++){
		L[i] = data_array[left + i];
	}
	for(int i = 0; i < n2; i++){
		R[i] = data_array[mid + i];
	}
	L[n1] = ENDNUMBER;
	R[n2] = ENDNUMBER;
	int i = 0;
	int j = 0;
	for(int k = left; k < right - 1 ; k++){
		if(L[i] < R[j]){
			data_array[k] = L[i];
			i = i + 1;
		}else{
			data_array[k] = R[j];
			j = j + 1;
		}
	}
}

void merge_sort::merge_method(int *data_array, int left, int right){
	int mid = (left + right) / 2;
	if(left + 1 < right){
		merge_method(data_array, left, mid);
		merge_method(data_array, mid, right);
		Merge(data_array, left, mid , right);
	}
}

クイックソート

クイックソートのポイントは

• 中間の値を作成すること
• 中間の値に近い値同士を比較し昇順に入れ替え
• 中間の値を利用して再帰的に処理

int med3(int x, int y, int z){
	if(x < y){
		if(y < z){
			return y;
		}else {
			if(z < x){
				return x;
			}else{
				return z;
			}
		}
	}else{
		if(z < y){
			return y;
		}else {
			if(x < z){
				return x;
			}else{
				return z;
			}
		}
	}
}

void quick::quick_method(int *data_array, int left, int right){
	if (left < right){
		int i = left;
		int j = right;
		int tmp;
		int piviot = med3(data_array[i], data_array[i + (j - i) / 2], data_array[j]);
		while(1){
			while (data_array[i] < piviot) i++;
			while (piviot < data_array[j]) j--;
			if(i >= j){
				break;
			}
			tmp = data_array[i];
			data_array[i] = data_array[j];
			data_array[j] = tmp;
			i++;
			j--;
		}
		quick_method(data_array, left, i - 1);
		quick_method(data_array, j + 1, right);
	}
}

挿入ソート

挿入ソートはシンプルなので特にポイントはないです。

配列中の一つ前の値が大きければ交換の処理を行う。

void insert_sort::insert_method(int *data_array){
	int tmp;
	int j;
	for(int i = 1; i < ARRAY_SIZE; i++){
		tmp = data_array[i];
		for(j = i; j > 0 && data_array[j - 1] > tmp; j--){
			data_array[j] = data_array[j - 1];
		}
	        data_array[j] = tmp;
	}
}

カウンティングソート

各値の頻度分布を作成し、その頻度分布に沿ってソートしています。

void counting_sort::counting_sort_method(int *sort_data){
	int *counting_sort_array = new int[ARRAY_SIZE];

	for(int i = 0; i < ARRAY_SIZE; i++){
		counting_sort_array[i] = 0;
	}

	for(int i = 0; i < ARRAY_SIZE; i++){
		counting_sort_array[sort_data[i]]++;
	}
	int output_index = 0;
	// counting_sort_array is zero not add data
	for(int j=0;j < ARRAY_SIZE; j++){
		while(counting_sort_array[j]--){
			sort_data[output_index++] = j;
		}
	}
}

Binary Tree

木構造を定義して各種木の操作を行います。

木構造の定義

struct node{
	int key_value;
	node *p_left;
	node *p_right;
};

木の操作

挿入処理です。再帰的な処理によってシンプルな実装で実現できるのが木の利点です。

node* binary_tree::insert(node *p_tree, int key){

	if(p_tree == NULL){
		node *p_new_tree = new node;
		p_new_tree->key_value = key;
		p_new_tree->p_left = NULL;
		p_new_tree->p_right = NULL;
		return p_new_tree;
	}
	if(key < p_tree->key_value){
		p_tree->p_left = insert(p_tree->p_left, key);
	}
	if(key > p_tree->key_value){
		p_tree->p_right = insert(p_tree->p_right, key);
	}
	return p_tree;
}

探索

検索処理です。これもBinary Treeで作成しているため単純な実装で実現可能になります。

int binary_tree::search(node *p_tree, int key){
	if(p_tree == NULL){
		return NULL;
	}
	if(p_tree->key_value == key){
		return p_tree->key_value;
	}
	else if(key < p_tree->key_value){
		return search(p_tree->p_left, key);
	}else if(key > p_tree->key_value){
		return search(p_tree->p_right, key);
	}
}

###木の削除

node binary_tree::destroy_tree(node *p_tree){
	if(p_tree != NULL){
	    destroy_tree(p_tree->p_left);
	    destroy_tree(p_tree->p_right);
		delete p_tree;
	}
}

最大の要素を探す

int binary_tree::find_max(node *p_tree){
	if(p_tree == NULL){
		return NULL;
	}else if(p_tree->p_right == NULL){
		return p_tree->key_value;
	}else{
		return find_max(p_tree->p_right);
	}
}

最小の要素を探す

int binary_tree::find_min(node *p_tree){
	if(p_tree == NULL){
		return NULL;
	}else if(p_tree->p_left == NULL){
		return p_tree->key_value;
	}else{
		return find_max(p_tree->p_left);
	}
}

要素の削除

要素の削除は木の構造を保つために少し複雑になります。

• 木の中の要素最大のnodeを見つける処理を記述（これは後ほど必要）
• 木と削除したい要素を与える

node* binary_tree::remove(node *p_tree, int remove_value){
	if(p_tree == NULL){
		return NULL;
	}
	if(p_tree->key_value == remove_value){
	    if(p_tree->p_left == NULL){
	    	node *p_right_sub_tree = p_tree->p_right;
	    	delete p_tree;
	    	return p_right_sub_tree;
	    }
	    if(p_tree->p_right == NULL){
	    	node *p_left_sub_tree = p_tree->p_left;
	    	delete p_tree;
	    	return p_left_sub_tree;
	    }
	    node *p_max_node = find_max(p_tree->p_left);
	    p_max_node->p_left = remove_max_node(p_tree->p_left, p_max_node);
	    p_max_node->p_right = p_tree->p_right;
	    delete p_tree;
	    return p_max_node;
	}else if(p_tree->key_value < remove_value){
		remove(p_tree->p_left, remove_value);
	}else{
		remove(p_tree->p_right, remove_value);
	}
	return NULL;
}

Graph

グラフの作成

深さ優先探索と幅優先探索用のメソッド作成

class graph {
public:
	graph();
	virtual ~graph();
	graph(int V);
	void addEdge(int v, int w);
	void depth_first_search(int v);
	void breadth_first_search(int s);
private:
	int V;
	list<int> *adj;
	void depth_first_search_util(int v, bool visited[]);
};

エッジの追加

void graph::addEdge(int v, int edge){
	adj[v].push_back(edge);
}

作成されたグラフは下記のようなものを想定しています。

深さ優先探索

void graph::depth_first_search_util(int v, bool visited[]){
	visited[v] = true;
	cout << v << " " << endl;
	list<int>::iterator i;
	for(i = adj[v].begin(); i != adj[v].end(); ++i){
		if(!visited[*i]){
			depth_first_search_util(*i, visited);
		}
	}
}

void graph::depth_first_search(int v){
	bool *visited = new bool[V];
	for(int i = 0; i < V; i++){
		visited[i] = false;
	}
	for(int i = 0; i < V; i++){
	    if(visited[i] == false){
	    	depth_first_search_util(i, visited);
	    }
	}
}

幅優先探索

幅優先探索のポイントはQueueを使用している点です。
Queueに探索幅分の値を入れて、順に検索することでQueueの性質であるFirst in First outにより幅優先探索を実現しています。

void graph::breadth_first_search(int s){

	bool *visited = new bool[V];
	for(int i = 0; i < V; i++){
		visited[i] = false;
	}
	list<int> queue;

	visited[s] = true;
	queue.push_back(s);

	list<int>::iterator i;

	while(!queue.empty()){
		s = queue.front();
		cout << s << " " << endl;
		queue.pop_front();
		for(i = adj[s].begin(); i != adj[s].end(); ++i){
			if(!visited[*i]){
				visited[*i] = true;
				queue.push_back(*i);
			}
		}
	}
}

Trie

今回定義したアルファベットのパターン数#define ALPHABETS 26

vectorのint型のデータをヘッダーに定義しています。

vector<int> occurrences;

トライ木の挿入処理です。
トライ木のルートを作成し、それの子ノードにノードを追加
発生回数をindex回数分追加する処理です。

void trie_tree_node::insert(char text[], int index){
	vector<char> word(text, text + strlen(text));
	trie_tree_node *temp = this->root;

	int i = 0;

	while(i < word.size()){
		if(temp->children[word[i] - 'a'] == NULL){
			temp->children[word[i] - 'a'] = new trie_tree_node();
			temp->children[word[i] - 'a']->parent = temp;
		}
		temp = temp->children[word[i] - 'a'];
		++i;
	}
	temp->occurrences.push_back(index);
}

木の値の表示部分です。
アルファベットを順に追っていき、木の子ノードが存在すれば表示用の列に子ノードを追加します。
子ノードに対して再帰的に処理を行います。
発生回数が0でなければ文字の表示とその回数を再帰的に表示しています。

void trie_tree_node::lexicographPrint(trie_tree_node *trie_tree, vector<char> printUtilVectr){
	int i;
	bool noChild = true;

	for(i = 0; i < ALPHABETS; i++){
		if(trie_tree->children[i] != NULL){
			noChild = false;
			printUtilVectr.push_back('a' + i);
			lexicographPrint(trie_tree->children[i], printUtilVectr);
			printUtilVectr.pop_back();
		}
	}
	if (trie_tree->occurrences.size() == 0){
		return;
	}else{
		for(vector<char>::iterator itr = printUtilVectr.begin(); itr != printUtilVectr.end(); ++itr){
			cout << *itr;
		}
		cout << " -> @ index " ;

		for(vector<int>::iterator counter = trie_tree->occurrences.begin(); counter != trie_tree->occurrences.end(); ++counter){
			cout << *counter << " ";
		}
		cout << endl;
	}

	printUtilVectr.pop_back();
}

トライ木から単語を検索する処理です。
検索を行う単語の最初の位置が一致するかどうかを検索します。
例えば"apple"だとaが見つかればその文字から子ノードをとってきて文字サイズが0になるまで行う形になります。

trie_tree_node* trie_tree_node::searchWord(trie_tree_node* trie_tree_data, char *text){

	vector<char> word(text, text + strlen(text));
	trie_tree_node *temp = trie_tree_data;

	while(word.size() != 0){
		if(temp->children[word[0] - 'a'] != NULL){
			temp = temp->children[word[0] - 'a'];
			word.erase(word.begin());
		} else {
			break;
		}
	}

	if(word.size() == 0 && temp->occurrences.size() != 0) {
		return temp;
	} else {
		return NULL;
	}
}

単語の削除処理です。
削除対象の単語があるノードを探してきます。
そのノードから発生回数分ノードを削除します。
子ノードに対しても削除処理を行います。

void trie_tree_node::removeWord(trie_tree_node *trie_tree_data, char *word){
	trie_tree_node *temp = searchWord(trie_tree_data, word);
	if(temp == NULL){
		return;
	}

	temp->occurrences.pop_back();

	bool noChild = true;

	int childCount = 0;
	int i;

	for(i = 0; i < ALPHABETS; ++i){
		if(temp->children[i] != NULL){
			noChild = false;
			++childCount;
		}
	}
	if(!noChild){
		return;
	}

	trie_tree_node *traverse;

	while(temp->occurrences.size() == 0 && temp->parent != NULL && childCount < 2){
		traverse = temp->parent;

		for(i = 0; i < ALPHABETS; ++i){
			if(temp == traverse->children[i]){
				traverse->children[i] = NULL;
				break;
			}
		}
	    temp = traverse;

	    for(i = 0; i < ALPHABETS; ++i){
	    	if(temp->children[i] != NULL){
	    		++childCount;
	    	}
	    }
	}
}

動的計画法

あらかじめ取得したデータを再利用して効率良く解く手法になります。

int dynamic_programing::lis_bottom_up(int arr[], int n){
	int i, j, max = 0;
	int *lis = new int[n]();

	for(i = 0; i < n; i++){
		lis[i] = 1;
	}

	for(int i = 1; i < n; i++){
	    for(int j = 0; j < i; j++){
	    	if( arr[i] > arr[j] && lis[i] < lis[j] + 1){
	    		lis[i] = lis[j] + 1;
	    	}
	    }
	}

	for(int i = 0; i < n; i++){
		if(max < lis[i]){
			max = lis[i];
		}
	}

	delete lis;

	return max;
}

コードについて

すべてのコードは下記にまとめています。

リソースの計測方法

timeコマンドで単純な実行速度は図れます。
dstatコマンドであればリソースの消費量を下記のように確認することができます。
右からcpuの使用量、ネットワークのIO、ディスクのIO、メモリの使用量が把握できます。

#注意点

大事なのは自分の環境で動作を確認して計測することです。本番でも同様のことが言えます。本番環境で試す場合には他の要因が絡んでくると思うので注意が必要です。

#まとめ

データ構造とアルゴリズム大事だと分かっちゃいるけど手を出していない・・・
そんなあなたも是非チャレンジして自分の大切な時間を増やせるようにしてみてはいかがでしょうか

もっと深くやりたい方は下記がオススメです。

GeeksforGeeks A computer science portal for geeks

参考

Jumping into C++
ソート
トライ木
Data Science Tutorials
Introduction to Graphs and Their Data Structures: Section 1
GeeksforGeeks A computer science portal for geeks
Trie Tree Implementation