比较两个排序的int数组
我有数百万个固定大小（100）的int数组。 每个数组都已排序并具有唯一元素。 对于每个数组，我想找到所有具有70％公共元素的数组。 现在我每秒进行大约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)); }
输出：
真正
假
过早优化™
我现在尝试优化上面的代码。 请检查代码块是否标记为
/* optimization */
有明显的区别。 在优化之后，我会重构代码以将其归结为一个或两个return语句。
您可以进行两种快速优化。
如果数组A的start元素大于B的end元素，则它们通常不能具有公共元素。
另一个是三角不等式的东西：
f(B,C) <= 100 - |f(A,B)-f(A,C)|
其原因是（假设f(A,B) > f(A,C) ）至少有f(A,B) - f(A,C)元素同时存在于A和B中但不存在于C.这意味着它们不能成为B和C的共同元素。
你可以尝试合并排序忽略重复。 这是排序数组的O（n）操作。 如果两个数组共有70％的元素，则生成的集合将具有130个或更少的唯一整数。 在您的情况下，您不需要结果，因此您只需计算唯一条目的数量，并在达到131或两个数组的末尾时立即停止。
编辑（2）以下代码可以使用4个核心在大约47秒内完成~176亿次比较。 使用4 cours使代码multithreading仅快70％。
仅当int值的范围相当小时，才使用BitSet。 否则你必须比较int []（如果你需要，我已经把代码留了下来）
在47.712秒内进行了176,467,034,428次比较，结果为444,888次
public static void main(String... args) throws InterruptedException { int length = 100; int[][] ints = generateArrays(50000, length); final BitSet[] bitSets = new BitSet[ints.length]; for(int i=0;i rawValues = new ArrayList(170); for (int i = 0; i < 170; i++) rawValues.add(i); int[][] ints = new int[count][length]; Random rand = new Random(1); for (int[] ia : ints) { Collections.shuffle(rawValues, rand); for (int i = 0; i < ia.length; i++) ia[i] = (int) (int) rawValues.get(i); Arrays.sort(ia); } return ints; } private static int compare(int[] ia, int[] ja) { int count = 0; int i=0,j=0; while(i jv) { j++; } else { count++; // duplicate i++; j++; } } return ia.length + ja.length - count; } private static int compare(BitSet ia, BitSet ja) { BitSet both = new BitSet(Math.max(ia.length(), ja.length())); both.or(ia); both.or(ja); return both.cardinality(); }