java - 算法问题，2个数组，数组a保存1000W条手机号，数组b保存5000W条，找出两个数组相同的手机号，执行时间需要 <2s

Question

有人说用归并算法，但是执行下来时间远远不止2s。
在下实在想不出还有什么好办法，希望各位能给个提示或者解法，谢谢。

下面是我的测试代码：

  public class TestA {

    public static void main(String[] args) {
        long[] a = new long[50000000];
        long num = 13000000000l;
        for (int i = 0; i < a.length; i++) {
            a[i] = (num + i);
        }
        long[] b = new long[10000000];
        long num2 = 14000000000l;
        for (int i = 0; i < b.length - 2; i++) {
            b[i] = (num2 + i);
        }
        b[9999999] =  13000000000l;
        b[9999998] =  13000000001l;

        long[] c = new long[a.length+b.length];
        long start = System.currentTimeMillis();
        for (int i = 0; i < a.length; i++) {
            c[i] = a[i];
        }
        for (int i = 0; i < b.length; i++) {
            c[i + a.length] = b[i];
        }
        System.out.println("start");
        sort(c, 0, c.length-1);
        long end = System.nanoTime();
        System.out.println(System.currentTimeMillis() - start);
        for (int i = 0; i < c.length; i++) {
            
            System.out.println(c[i]);
        }

    }

    public static void sort(long[] data, int left, int right) {
        if (left < right) {
            // 找出中间索引
            int center = (left + right) / 2;
            // 对左边数组进行递归
            sort(data, left, center);
            // 对右边数组进行递归
            sort(data, center + 1, right);
            // 合并
            merge(data, left, center, right);
        }
    }

    public static void merge(long[] data, int left, int center, int right) {
        long[] tmpArr = new long[data.length];
        int mid = center + 1;
        // third记录中间数组的索引
        int third = left;
        int tmp = left;
        while (left <= center && mid <= right) {

            // 从两个数组中取出最小的放入中间数组
            if (data[left] <= data[mid]) {
                if(data[left] == data[mid]){
                    System.out.println(data[left]);
                }
                tmpArr[third++] = data[left++];
             
            } else {
                tmpArr[third++] = data[mid++];
            }
        }
        // 剩余部分依次放入中间数组
        while (mid <= right) {
            tmpArr[third++] = data[mid++];
        }
        while (left <= center) {
            tmpArr[third++] = data[left++];
        }
        // 将中间数组中的内容复制回原数组
        while (tmp <= right) {
            data[tmp] = tmpArr[tmp++];
        }
    }

}

Answer 1

아이디어를 제공하기 위해 우리가 찾고 있는 것은 두 배열의 동일한 전화번호입니다. 그런 다음 첫 번째 배열의 전화번호로 사전 트리를 만듭니다.
두 번째부터는 사전트리에서 직접 검색해 보세요. 전체적인 복잡도는 O(N * 11) = O(N)입니다. 전화번호당 11자리입니다. 전체 복잡도는 O(N)에 불과합니다.
참고자료 지후: https://zhuanlan.zhihu.com/p/...

으아아아

Answer 2

방금 메서드를 찾았는데 실행 시간은 약 2초입니다.

으아악

이 방법의 주요 아이디어는 먼저 정렬한 다음 Arrays.binarySearch() 메서드를 사용하여 바이너리 쿼리를 수행하고 일치하는 배열 첨자를 반환하는 것입니다.

---

데이터 소스를 얻는 방법을 수정해 보니, 임의의 데이터 소스를 사용할 경우, 데이터 소스의 정렬 방식에서 오류 시간이 주로 8초 정도 소모되는 것으로 나타났습니다. 여전히 정렬 알고리즘의 시간 복잡도에 영향을 미칩니다.
코드는 다음과 같이 수정됩니다.

공개 클래스 TestB {

으아악

}

Answer 3

考虑bitmap, 参考https://github.com/RoaringBit...
RoaringBitmap aBM = new RoaringBitmap()
for (int i = 0; i < a.length; i++) {

으아악

}
...
RoaringBitmap 상호 작용BM = RoaringBitmap.and(aBM, bBM)
for (int 항목: 상호 작용BM) {

으아악

}

Answer 4

으아악

위 코드를 사용하면 내 컴퓨터에서는 8s입니다

Answer 5

http://tieba.baidu.com/p/3866...

Answer 6

C#, 로컬로 실행, 릴리스, 611ms

으아악

Answer 7

redis SINTER(주어진 모든 집합의 교집합인 집합의 모든 구성원을 반환합니다.)

Answer 8

이 작업을 배열에서만 수행할 수 있다면 최소한 더 작은 배열을 순회해야 하며 정렬도 불가피합니다. 그리고 배열 내용을 다른 데이터 구조로 내보낼 수 있다면 질문의 원래 의도에 어긋나는 것 같습니다. 질문자는 배열 작업을 테스트하고 싶었습니까?

Answer 9

MBP에서 약 200ms밖에 걸리지 않는 더 간단한 방법을 생각해 보겠습니다. 일반 Pentium G2020은 250ms 밖에 걸리지 않습니다
글쎄, 이 알고리즘은 완전히 불가능합니다.

Answer 10

사실 이 질문의 핵심은 알고리즘입니다.
Programming Pearls의 첫 번째 장을 읽어 보시기 바랍니다. 좋은 아이디어를 제공하겠습니다.
우선 질문을 좀 더 다듬어 보아야 합니다. 즉, 휴대전화번호는 꼭 중국 휴대전화번호여야만 합니까? 그렇지 않으면 숫자가 훨씬 더 높아질 것입니다.
프로그래밍 주지에서 전화번호가 어떻게 저장되는지 간단히 설명드리겠습니다.
그는 이진수만을 사용하여 모든 휴대폰 번호를 저장합니다. 이진수는 매우 길 수 있습니다. 길이는 가능한 가장 큰 전화번호와 같습니다. 예를 들어 13999999999는 실제로 13을 생략할 수 있는 숫자입니다. 우리의 숫자는 999999999자리의 이진수입니다.
각 자릿수에서 이 전화번호가 있으면 1로, 없으면 0으로 표시합니다.
간단하게 하기 위해 휴대전화번호의 범위는 0으로 가정하겠습니다. -9, 10자리 이진수 0000000000을 준비해보자.
첫 번째 배열에 3개의 전화번호(1, 5, 7)가 있다고 가정하자. 그러면 이 배열을 저장하는 이진수는 0010100010이다. 1, 5 , 이 숫자의 7자리는 1이고 나머지 비트는 0이다.
두 번째 배열에 6개의 전화번호, 즉 1, 2, 3, 4, 7, 8이 있다고 가정합니다. 그러면 이 배열을 저장하는 이진수는 0110011110, 즉 1, 2, 3, 4, 7입니다. 8번째 비트는 1이고 나머지 비트는 0이다.
그렇다면 이 두 배열에서 동일한 전화번호를 어떻게 찾을 수 있을까요?
비트 연산에서는 "비트 AND"(AND) 연산만 하면 됩니다. 동일한 비트가 모두 1이면 여전히 1입니다. 둘 중 하나가 0이면 0입니다.
0010100010 & 0110011110 = 0010000010

첫 번째와 일곱 번째 자리가 1인 이진수라는 것을 단번에 알아냈습니다.