探索アルゴリズムについて勉強した＋使ってみた

• オーダ記法...アルゴリズムの処理効率の評価方法
• 線形探索...n個のデータを先頭から順番に見る。O(n)
• 二分探索...データを整列し、条件が一致する方向に二分を繰り返す。O(log n)
• ハッシュ表探索...ハッシュ値で格納位置を決定し、それを用いて探索する。基本的にO(1)

線形探索、二分探索を行う

線形探索と二分探索に置けるオーダの差を確認する

package search;

public class search {
	public static void linersearch(int searchdata,int[] list) {
		int number=0;
		int order=0;
		for(int i:list) {
			number++;
			order++;
			if(i==searchdata) {
				break;
			}
		}
		System.out.println("order: "+order);
	}
	public static void binarysearch(int searchdata,int[] list) {
		int order=0;
		int max=list.length-1;
		int min=0;
		int pointer=0;
		while(max!= min && order<100) {
			order++;
			pointer=(max+min)/2;
			if(list[pointer]==searchdata) {
				System.out.println("ヒット\npointer: "+pointer+"\norder: "+order);
				break;
			}else if(list[pointer]>searchdata) {
				max=pointer;
			}else{
				min=pointer;
			}
			if(max==min) {
				System.out.println("ヒットしませんでした");
			}
		}
	}
}

package search;

public class main {
	public static void main(String[] args) {
		int[] list = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100};
		int[] random = {62,2,91,34,55,19,83,7,41,68,99,13,47,26,74,5,88,30,52,79,11,94,4,60,22,86,37,1,71,44,100,58,25,82,16,49,9,66,93,28,77,3,54,39,85,6,64,15,42,20,97,33,70,51,8,46,90,12,75,23,61,31,96,50,17,81,36,65,43,10,59,24,84,69,40,92,27,57,14,73,48,21,95,32,78,56,80,35,63,98,45,18,72,29,53,87,38,67,76,89};
		System.out.println("線形探索&&整列");
		search.linersearch(72, list);
		System.out.println("\n線形探索&&ランダム");
		search.linersearch(51, random);
		System.out.println("\n二分探索");
		search.binarysearch(41, list);
	}
}

出力
二分探索はオーダを大幅に短縮することができるが、データを整列する必要がある

線形探索&&整列
order: 72

線形探索&&ランダム
order: 54

二分探索
ヒット
pointer: 40
order: 6

ハッシュ探索を行う

仮想的なメモリ領域を定義し、ハッシュ値でポインタを決定してハッシュ探索を行う

package hashsarch;
import java.util.ArrayList;

public class memory {
	private ArrayList<Integer>[] memory =  (ArrayList<Integer>[])new ArrayList[10];
	int getpointersize(int pointer) {
		return memory[pointer].size();
	}
	int getdata(int pointer,int number) {
		return memory[pointer].get(number);
	}
	void add(int data) {
		memory[data%10].add(data);
	}
	memory() {
		for (int i = 0; i < memory.length; i++) {
            memory[i] = new ArrayList<Integer>();
		}
	}
}

package hashsarch;

public class search {
	public static void search(int searchdata,memory memory) {
		int order=0;
		order++;
		int pointer = searchdata%10;
		for(int i=0;i<memory.getpointersize(pointer);i++) {
			order++;
			if(searchdata==memory.getdata(pointer,i)) {
				System.out.println("ヒット\nオーダ: "+order+"\nポインタ: "+pointer+"["+i+"]");
				break;
			}
		}
	}
}

package hashsarch;

public class main {
	public static void main(String args[]) {
		int[] data = {62,2,91,34,55,19,83,7,41,68,99,13,47,26,74,5,88,30,52,79,11,94,4,60,22,86,37,1,71,44,100,58,25,82,16,49,9,66,93,28,77,3,54,39,85,6,64,15,42,20,97,33,70,51,8,46,90,12,75,23,61,31,96,50,17,81,36,65,43,10,59,24,84,69,40,92,27,57,14,73,48,21,95,32,78,56,80,35,63,98,45,18,72,29,53,87,38,67,76,89};
		memory memory = new memory();
		for(int i:data) {
			memory.add(i);
		}
		search.search(96, memory);
	}
}

出力
ポインタが衝突した値をリストに格納しそれらを線形探索しているためオーダが2以上だが、ポインタの特定自体はO(n)で行える。

ヒット
オーダ: 8
ポインタ: 6[6]