我有数百万个固定大小 (100) 的 int 数组。每个数组都经过排序并具有唯一的元素。对于每个数组,我想找到所有具有 70% 公共(public)元素的数组。现在我每秒进行大约 100 万次比较(使用 Arrays.binarySearch()),这对我们来说太慢了。
谁能推荐一个更好的搜索算法?
最佳答案
像这样的东西应该可以完成这项工作(前提是数组已排序并包含唯一元素):
public static boolean atLeastNMatchingElements(final int n,
final int[] arr1,
final int[] arr2){
/* check assumptions */
assert (arr1.length == arr2.length);
final int arrLength = arr2.length;
{ /* optimization */
final int maxOffset = Math.max(arrLength - n, 0);
if(arr1[maxOffset] < arr2[0] || arr2[maxOffset] < arr1[0]){
return false;
}
}
int arr2Offset = 0;
int matches = 0;
/* declare variables only once, outside loop */
int compResult; int candidate;
for(int i = 0; i < arrLength; i++){
candidate = arr1[i];
while(arr2Offset < arrLength - 1){
compResult = arr2[arr2Offset] - candidate;
if(compResult > 0){
break;
} else{
arr2Offset++;
if(compResult == 0){
matches++;
break;
}
}
}
if(matches == n){
return true;
}
/* optimization */
else if(matches < n - (arrLength - arr2Offset)){
return false;
}
}
return false;
}
示例用法:
public static void main(final String[] args){
final int[] arr1 = new int[100];
final int[] arr2 = new int[100];
int x = 0, y = 0;
for(int i = 0; i < 100; i++){
if(i % 10 == 0){
x++;
}
if(i % 12 == 0){
y++;
}
arr1[i] = x;
arr2[i] = y;
x++;
y++;
}
System.out.println(atLeastNMatchingElements(70, arr1, arr2));
System.out.println(atLeastNMatchingElements(95, arr1, arr2));
}
输出:
true
false
过早优化™
我现在已经尝试优化上面的代码。请检查代码块是否标记为
/* optimization */
明显不同。优化后,我会重构代码,将其简化为一两个 return 语句。
关于java - 比较两个排序的 int 数组,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/4758118/