アルゴリズム 番兵を使った線形探索（Linear Search Sentinel）

Javaで番兵を使った線形探索

番兵を使うことによって、ループ内での条件判断が少なくなり処理効率が良くなるとのこと。

import java.util.Arrays;
import java.util.List;
import java.util.Vector;

public class LinearSearchSentinel {
	public static void main(String[] args) {
		List<Integer> dataList = Arrays.asList(10, 8, 9, 3, 2, 1, 4, 6, 5, 0);
		System.out.println("result index = " + search(dataList, 2));
	}
	
	public static int search(List<Integer> dataes, int valueToFind) {
		int index = -1;
		Vector<Integer> dataList = new Vector<Integer>(dataes);
		dataList.add(valueToFind);
		while (dataList.get(++index) != valueToFind) {
		}
		if (index == (dataList.size() - 1)) {
			return -1;
		} 
		return index;
	}
}

Pythonで番兵を使った線形探索

def linearSearchSentinel(dataes, valueToFind):
    dataes.append(valueToFind)
    index = 0
    while dataes[index] != valueToFind:
        index += 1
    if index == (len(dataes) - 1):
        return -1
    else:
        return index
    
if __name__ == '__main__':
    dataes = [10, 8, 9, 3, 2, 1, 4, 6, 5, 0]
    print 'result index = %s' % linearSearchSentinel(dataes, 2)

番兵を使った場合と使わない場合の処理速度を比較(python)

比較処理実行ソースコード

if __name__ == '__main__':
    setup = 'from algorithms import linearSearch'
    t1 = Timer('linearSearch.search(range(1000), 999)', setup)
    t2 = Timer('linearSearch.searchSentinel(range(1000), 999)', setup)
    print 'search result        = %s' % t1.timeit(10000)
    print 'searchSentinel result= %s' % t2.timeit(10000)

実行結果

search result        = 2.96792609117
searchSentinel result= 3.10446495295

あれれ、番兵使ってるほうが処理速度は速いと思ってたのに番兵使ってるほうが遅いよ！！