线性对比查找与二分法对比查找性能对比

 

 

 

 

package com.cn.ld.util;

 

import java.util.ArrayList;

import java.util.Arrays;

import java.util.List;

import org.apache.commons.lang.StringUtils;

 

public class CollectionUtil extends StringUtils {

 

public static void arrayOper() {

int[] a = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 2, 3, 4, 5, 6, 7,

8, 9, 1, 2 };

int[] b = new int[10];

int d[] = new int[10];

List<Integer> c = new ArrayList<Integer>();

 

System.arraycopy(a, 0, c, 0, 9);

for (int i : c) {

System.out.println(i);

}

 

}

 

/**

* 二分法查找

*/

public static int dichotomy(int num, int[] a) {

int lowerBound = 0;

int uperBound = a.length - 1;

int curNum = 0;

 

while (true) {

curNum = (lowerBound + uperBound) / 2;

if (num == a[curNum]) {

return curNum;

} else if (lowerBound > uperBound) {

return -1;

} else {

if (num > a[curNum]) {

lowerBound = curNum + 1;

} else {

uperBound = curNum - 1;

}

}

}

}

 

/**

* 线性查找

* 

* @param args

*/

public static int linearity(int num, int[] a) {

int index = 0;

for (int i = a.length - 1; i > 0; i--) {

if (a[i] == num) {

index = i;

break;

}

}

return index;

}

 

public static void main(String[] args) {

int a[] = null;

int arrySize[] = new int[] { 1000, 5000, 10000, 100000 };

for (int j = arrySize.length - 1; j > -1; j--) {

test(arrySize, j);

}

}

 

private static void test(int[] arrySize, int j) {

int[] a;

a = new int[arrySize[j]];

for (int i = a.length - 1; i > 0; i--) {

a[i] = i;

}

long l1, l2, l3, l4, l5, l6, l7;

int count1, count2;

count1 = 0;

count2 = 2;

l4 = System.currentTimeMillis();

for (int i = a.length - 1; i > 0; i--) {

l1 = System.currentTimeMillis();

int num = CollectionUtil.dichotomy(i, a);

l2 = System.currentTimeMillis();

l3 = (l2 - l1);

if (l3 > 0) {

// System.out.println("输入要查询的数："+i+" 返回索引："+num+" 该索引对应值为："+a[i]+" 此次二分法查找耗时:"+l3+"毫秒");

count1 = count1 + 1;

}

}

l5 = System.currentTimeMillis();

l6 = l5 - l4;

l4 = System.currentTimeMillis();

for (int i = a.length - 1; i > 0; i--) {

l1 = System.currentTimeMillis();

int num = CollectionUtil.linearity(i, a);

l2 = System.currentTimeMillis();

l3 = (l2 - l1);

if (l3 > 0) {

// System.out.println("输入要查询的数："+i+" 返回索引："+num+" 该索引对应值为："+a[i]+" 此次线性查找耗时:"+l3+"毫秒");

count2 = count2 + 1;

}

}

l5 = System.currentTimeMillis();

l7 = l5 - l4;

System.out.println("元数据共：" + a.length + "条 ; 二分法对比超找次数：" + a.length

+ " 次耗时超过0毫秒次数:" + count1 + "次");

System.out.println("二分法查找对比总共耗时" + l6 + "毫秒");

System.out.println("元数据共：" + a.length + "条 ; 线性对比超找次数：" + a.length

+ " 次耗时超过0毫秒次数:" + count2 + "次");

System.out.println("线性查找对比总共耗时" + l7 + "毫秒");

System.out.println("\n\n");

}

}

 

 

元数据共：100000条 ; 二分法对比超找次数：100000 次耗时超过0毫秒次数:0次

二分法查找对比总共耗时46毫秒

元数据共：100000条 ; 线性对比超找次数：100000 次耗时超过0毫秒次数:574次

线性查找对比总共耗时60657毫秒

 

 

 

元数据共：10000条 ; 二分法对比超找次数：10000 次耗时超过0毫秒次数:1次

二分法查找对比总共耗时15毫秒

元数据共：10000条 ; 线性对比超找次数：10000 次耗时超过0毫秒次数:58次

线性查找对比总共耗时875毫秒

 

 

 

元数据共：5000条 ; 二分法对比超找次数：5000 次耗时超过0毫秒次数:0次

二分法查找对比总共耗时0毫秒

元数据共：5000条 ; 线性对比超找次数：5000 次耗时超过0毫秒次数:17次

线性查找对比总共耗时234毫秒

 

 

 

元数据共：1000条 ; 二分法对比超找次数：1000 次耗时超过0毫秒次数:0次

二分法查找对比总共耗时0毫秒

元数据共：1000条 ; 线性对比超找次数：1000 次耗时超过0毫秒次数:3次

线性查找对比总共耗时16毫秒

 

 

总结：对于后期系统重构对比查找的地方，要考虑数据源数量大小进行处理。如果数量较小没必要优化算法