搜索彼此之间的差异小于固定值的数字的算法？

Question

假设存在一个巨大的真实数据集：A1,A2,A3,...,Ai,...An（其中 n 是一个非常大的数。）。我想找到这些子数据集，其中这些子集中每个数字之间的差异小于一个固定值 B。它必须花费尽可能少的时间和内存。有什么想法吗？

Answer 1

不清楚您的意思是多少数据 - 是否足够小以将所有数据加载到 RAM 中，是否为 32 位整数，数据中重复的可能性有多大，是否使用多台机器或不 and/or 使用 map-reduce 作业等。尽管缺乏信息，我可以盲目地建议您使用 Radix sort。它的线性时间排序算法。

编辑 1

正如您提到的，数据已经按升序排序，因此我们可以对每个元素使用二进制搜索（上限）找到所有子集。

假设数据容器为A[i]，大小为n，粗略的伪代码如下：

upper_bound(start, end, key):
    indx := end + 1
    while start <= end do
        mid := start + (end - start) / 2
        if A[mid] >= key:
            indx := mid
            end := mid - 1
        else
            start := mid + 1

     return indx
end


subsets := [] // list of subsets
for i = n - 1 to i = 0 do
    indx := upper_bound(0, i - 1, A[i] - B)
    set := [ elements from A[indx] to A[i] ]
    subsets.push(set)
end

print subsets

对于每个元素arr[i]，你必须找到上限；整体时间复杂度为O(n logn).

如果需要，我可以提供 C++ 或 Java 工作代码段。

编辑 2

这是Java代码

import java.util.ArrayList;
import java.util.Arrays;

/**
 *
 * @author kaidul
 */
public class Test {

    private static int upperBound(int left, int right, int key, Integer[] A) {
        int indx = right + 1;
        while(left <= right) {
            int mid = left + (right - left) / 2;
            if(A[mid] > key) {
                indx = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return indx;
    }

    public static void main(String[] args) {
        Integer[] A = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        int B = 4;
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        for(int i = A.length - 1; i > 0; --i) {
            int startIndx = upperBound(0, i - 1, Math.min(A[i] - B, A[i] - A[0]), A);
            if(startIndx < i) {
                ArrayList<Integer> solutionSet = new ArrayList<>( Arrays.asList( Arrays.copyOfRange(A, startIndx, i + 1) ) );
                result.add(solutionSet);
            }
            if(startIndx == 0) {
                break;
            }
        }
        result.stream().forEach((subset) -> {
            System.out.println(subset);
        });
    }

}

输出：

[7, 8, 9, 10]
[6, 7, 8, 9]
[5, 6, 7, 8]
[4, 5, 6, 7]
[3, 4, 5, 6]
[2, 3, 4, 5]
[1, 2, 3, 4]

Answer 2

如评论中所述，集合已经排序。让我们称第 i 个元素为 a[i]。一个简单的线性传递找到所有子集（伪代码，不检查数据的结尾——这很容易添加，但会模糊算法的思想）：

low = 0;
high = 0;
repeat {
    while (a[high] - a[low] <= B) {
        high = high + 1;
    }
    output set a[low .. high-1];
    while (a[high] - a[low] > B) {
        low = low + 1;
    }
}

请注意，一次只有 low 和 high 之间的部分需要在内存中。因此可以流式传输数据而无需将其全部存储在内存中。

该算法也将输出一个元素子集。如果不需要，可以很容易地抑制它。

搜索彼此之间的差异小于固定值的数字的算法？

Algorithm to search the numbers whose difference between each other is smaller than a fixed value?

algorithm

difference

编辑 1

编辑 2