项目背景:
从一个文件获取10万笔字符串类型数据，数据库表中查询出符合条件的5千数字符窜类型数据。把两者匹配的数据查询出来。
结论：
1、如果数量级不大，二种方式速度差不多
2、如果数量级较大
*如果源数据是有序的，则二分查找法效率高
*如果源数据是无序的，则顺序查找法效率高
原因：
1、字符串排序非常耗时
2、二分查找法需要先排序
执行结果
----------------根据顺序查找法查找数字-----start
构建的源数组长度为:10000
从源数组中随机抽取500个构建第二个数组
总共找到的数字个数为：500
总耗时为：14毫秒
end
----------------先对整形数组进行排序，根据二分查找法查找-----start
构建的源数组长度为:10000
从源数组中随机抽取500个构建第二个数组
10000个数字排序耗时:188毫秒
总共找到的数字的个数为：500
总耗时为：189毫秒
end
----------------根据顺序查找法查找字符窜-----start
构建的源数组长度为:10000
从源数组中随机抽取500个构建第二个数组
总共找到的字符窜的个数为：500
总耗时为：42毫秒
end
----------------先对字符串数组进行排序，根据二分查找法查找字符窜-----start
构建的源数组长度为:10000
从源数组中随机抽取500个构建第二个数组
10000个字符串排序耗时:1021
总共找到的字符窜的个数为：500
总耗时为：1021毫秒
end源代码
package test;
import java.util.Random;
import java.util.UUID;
public class A {
/**
* @param 顺序查找法、二分查找法的比较结论
* 1、如果数量级不大，二种方式速度差不多
* 2、如果数量级较大
* *如果源数据是有序的，则二分查找法效率高
* *如果源数据是无序的，则顺序查找法效率高
*/
public static void main(String[] args) throws Exception {
testIntArr2(10000, 500);
testIntArr1(10000, 500);
testStringArr2(10000, 500);
testStringArr1(10000, 500);
}
/**
* 整形：使用顺序查找法搜索数组
* @param oldLength
* @param newLength
* @throws Exception
*/
public static void testIntArr2(int oldLength,int newLength) throws Exception{
System.out.println("----------------根据顺序查找法查找数字-----start");
int[] arr1 = createIntArr(oldLength);//生成一个包含oldLength个字符串的数组
int[] arr2 = getIntArrFromOtherArr(arr1,newLength);//从数组中挑选newLength个字符串组成第二个数组
long t0=(long) System.currentTimeMillis();//开始计时
int searchedNum=0;
for(int i=0;i<arr2.length;i++){
int temp = arr2[i];
for(int j=0;j<arr1.length;j++){
if(temp==arr1[j]){
searchedNum++;
continue;
}
}
}
System.out.println("总共找到的数字个数为："+searchedNum);
long t1=(long) System.currentTimeMillis();
System.out.println("总耗时为："+(t1-t0)+"毫秒");
System.out.println("end");
}
/**
* 整形：使用二分查找法搜索数组
* @param oldLength
* @param newLength
* @throws Exception
*/
public static void testIntArr1(int oldLength,int newLength) throws Exception{
System.out.println("----------------先对整形数组进行排序，根据二分查找法查找-----start");
int[] arr1 = createIntArr(oldLength);//生成一个包含oldLength的数组
int[] arr2 = getIntArrFromOtherArr(arr1,newLength);//从数组中挑选newLength个组成第二个数组
long t0=(long) System.currentTimeMillis();//开始计时
sort(arr1);//使用冒泡排序法对数组1排序
long t1=(long) System.currentTimeMillis();
System.out.println(oldLength+"个数字排序耗时:"+(t1-t0)+"毫秒");
int searchedNum = 0;
for(int i=0;i<arr2.length;i++){
int temp = arr2[i];
if(binarySearch(arr1, temp)>0){
searchedNum++;
}
}
System.out.println("总共找到的数字的个数为："+searchedNum);
long t2=(long) System.currentTimeMillis();
System.out.println("总耗时为："+(t2-t0)+"毫秒");
System.out.println("end");
}
/**
* 字符串：使用顺序查找法搜索数组
* @param oldLength
* @param newLength
* @throws Exception
*/
public static void testStringArr2(int oldLength,int newLength) throws Exception{
System.out.println("----------------根据顺序查找法查找字符窜-----start");
String[] arr1 = createStringArr(oldLength);//生成一个包含oldLength个字符串的数组
String[] arr2 = getStringArrFromOtherArr(arr1,newLength);//从数组中挑选newLength个字符串组成第二个数组
long t0=(long) System.currentTimeMillis();//开始计时
int searchedNum=0;
for(int i=0;i<arr2.length;i++){
String temp = arr2[i];
for(int j=0;j<arr1.length;j++){
if(temp.equals(arr1[j])){
searchedNum++;
continue;
}
}
}
System.out.println("总共找到的字符窜的个数为："+searchedNum);
long t1=(long) System.currentTimeMillis();
System.out.println("总耗时为："+(t1-t0)+"毫秒");
System.out.println("end");
}
/**
* 字符串：使用二分查找法搜索数组
* @param oldLength
* @param newLength
* @throws Exception
*/
public static void testStringArr1(int oldLength,int newLength) throws Exception{
System.out.println("----------------先对字符串数组进行排序，根据二分查找法查找字符窜-----start");
String[] arr1 = createStringArr(oldLength);//生成一个包含oldLength个字符串的数组
String[] arr2 = getStringArrFromOtherArr(arr1,newLength);//从数组中挑选newLength个字符串组成第二个数组
long t0=(long) System.currentTimeMillis();//开始计时
sort(arr1);//使用冒泡排序法对数组1排序
long t1=(long) System.currentTimeMillis();
System.out.println(oldLength+"个字符串排序耗时:"+(t1-t0));
int searchedNum = 0;
for(int i=0;i<arr2.length;i++){
String temp = arr2[i];
if(binarySearch(arr1, temp)>0){
searchedNum++;
}
}
System.out.println("总共找到的字符窜的个数为："+searchedNum);
long t2=(long) System.currentTimeMillis();
System.out.println("总耗时为："+(t2-t0)+"毫秒");
System.out.println("end");
}
/**
*二分查找法：字符窜
* @param arr
* @param num
* @return
*/
public static int binarySearch(String[] arr , String num){
int start =0;
int end = arr.length-1;
while(start<=end){
int mid = (start+end)/2;
if(num.compareTo(arr[mid]) > 0){
start=mid+1;
}else if(num.compareTo(arr[mid]) < 0){
end=mid-1;
}else{
return mid;
}
}
return -1;
}
/**
* 二分查找法：整数
* @param arr
* @param num
* @return
*/
public static int binarySearch(int[] arr , int num){
int low = 0;
int upper=arr.length-1;
while(low<=upper){
int mid = (low+upper)/2;
if(arr[mid] < num){
low = mid+1;
}else if(arr[mid] > num){
upper=mid-1;
}else{
return mid;
}
}
return -1;
}
/**
* 字符窜从小到大排序
* @param arr
*/
public static void sort(String[] arr){
for(int i=0;i<arr.length;i++){
for(int j=0;j<arr.length-i-1;j++){
if(arr[j].compareTo(arr[j+1]) > 0){
String temp = arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
}
// for(String x : arr){
// System.out.println(x);
// }
}
/**
* 整形数组冒泡排序：从小到大
*/
public static void sort(int[] arr){
for(int i=0;i<arr.length;i++){
for(int j=0;j<arr.length-i-1;j++){
if(arr[j]>arr[j+1]){
int temp = arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
}
// for(int x : arr){
// System.out.println(x);
// }
}
/**
* 构建字符串数组---包含num个uuid
* @return
*/
public static String[] createStringArr(int num){
String[] arr = new String[num];
for(int i=0;i<num;i++){
arr[i] = UUID.randomUUID().toString();
}
System.out.println("构建的源数组长度为:"+arr.length);
return arr;
}
/**
* 从源数组中随机选择n个数据，构建第二个数组
* @param source
* @return
* @throws Exception
*/
public static String[] getStringArrFromOtherArr(String[] source,int n) throws Exception{
if(n>source.length){
throw new Exception("不能超过源数组的长度");
}
Random random = new Random();
String[] arr = new String[n];
for(int i=0;i<n;i++){
int index = random.nextInt(source.length-1);
arr[i]=source[index];
}
System.out.println("从源数组中随机抽取"+arr.length+"个构建第二个数组");
return arr;
}
/**
* 构建整形数组---包含num个整形
* @return
*/
public static int[] createIntArr(int num){
Random random = new Random();
int[] arr = new int[num];
for(int i=0;i<num;i++){
arr[i] = random.nextInt();
}
System.out.println("构建的源数组长度为:"+arr.length);
return arr;
}
/**
* 从源数组中随机选择n个数据，构建第二个数组
* @param source
* @return
* @throws Exception
*/
public static int[] getIntArrFromOtherArr(int[] source,int n) throws Exception{
if(n>source.length){
throw new Exception("不能超过源数组的长度");
}
Random random = new Random();
int[] arr = new int[n];
for(int i=0;i<n;i++){
int index = random.nextInt(source.length-1);
arr[i]=source[index];
}
System.out.println("从源数组中随机抽取"+arr.length+"个构建第二个数组");
return arr;
}
}
版权声明：本文为TIANFEIFEIFEI原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。