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

Untuk memberikan idea, perkara yang kami cari ialah nombor telefon yang sama dalam dua tatasusunan. Kemudian kita membina pokok kamus daripada nombor telefon dalam tatasusunan pertama.
Untuk kali kedua, cuma cari terus dalam pokok kamus. Kerumitan keseluruhan ialah O(N * 11) = O(N). 11 digit setiap nombor telefon. Jumlah kerumitan hanya O(N).
Rujukan Zhihu: https://zhuanlan.zhihu.com/p/...

public class TrieTree {
    private class Node {
        char ch;
        TreeMap<Character, Node> node;
        int count;

        public Node(char ch) {
            ch = this.ch;
            node = new TreeMap<>();
            count = 0;
        }
    }

    public class StringCount implements Comparable{
        public String str;
        public int count;

        public StringCount(String str, int count) {
            this.str = str;
            this.count = count;
        }

        @Override
        public int compareTo(Object o) {
            StringCount t = (StringCount) o;
            if(this.count > t.count){
                return -1;
            }
            if(this.count < t.count){
                return 1;
            }
            return 0;
        }
    }

    private int indexStringCount;
    private StringCount[] stringCounts;
    private Node root;
    private int size;
    private static boolean DEBUG = true;
    
    public TrieTree() {
        root = new Node('$');
        size = 0;
    }

    public int insert(String str) {
        int res = 0;
        Node temp = root;
        for (int i = 0; i < str.length(); i++) {
            char ch = str.charAt(i);
            if (temp.node.get(ch) == null) temp.node.put(ch, new Node(ch));
            temp = temp.node.get(ch);
        }
        if(temp.count == 0) size ++;
        res = ++temp.count;
        return res;
    }
    
    public StringCount[] getStringCount(){
        indexStringCount = 0;
        stringCounts = new StringCount[this.size];
        ergodic(root, "");
        Arrays.sort(stringCounts);
        {
            for(StringCount s : stringCounts){
                System.out.println(s.str + " " + s.count);
            }
        }
        return stringCounts;
    }
    private void ergodic(Node foo, String str){
        if(foo.count != 0){
            stringCounts[indexStringCount ++] = new StringCount(str, foo.count);
        }
        for(Character ch:foo.node.keySet()){
            ergodic(foo.node.get(ch), str + ch);
        }
    }
    
    private void show(Node foo, String str) {
        if (foo.count != 0) {
            System.out.println(str + " : " + foo.count);
        }
        for(Character ch:foo.node.keySet()){
            show(foo.node.get(ch), str + ch);
        }
    }
    public void showALL() {
        show(root, "");
    }
    public int size(){
        return size;
    }
    
    public static void main(String[] args) {
        TrieTree tree = new TrieTree();
        String[] strs = { "a", "aa", "a", "b", "aab", "bba" };
        for (int i = 0; i < strs.length; i++) {
            tree.insert(strs[i]);
        }
        tree.showALL();
        System.out.println(tree.size);
        tree.getStringCount();
    }
}

Answer 2

Saya baru sahaja menemui kaedah, masa pelaksanaan adalah kira-kira 2s:

public class TestB {
    static long count;

    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 - 3; i++) {
            b[i] = num2 + i;
        }
        b[9999999] = 13000000000l;
        b[9999998] = 13000000002l;
        b[9999997] = 13000000002l;

        long start = System.currentTimeMillis();
  
        Arrays.sort(a);
        int flag = -1;
        for (int i = 0; i < b.length; i++) {
            count = b[i];
            flag = Arrays.binarySearch(a, count);
            if (flag <= 50000000 && flag >= 0) {
                System.out.println(count + "   " +flag);
            }
        }
        System.out.println(System.currentTimeMillis() - start);
    }
}

Idea utama kaedah ini adalah untuk mengisih dahulu, kemudian gunakan kaedah Arrays.binarySearch() untuk melaksanakan pertanyaan binari dan mengembalikan subskrip tatasusunan yang sepadan.

---

Saya mengubah suai kaedah mendapatkan sumber data dan mendapati bahawa jika sumber data rawak digunakan, masa yang digunakan adalah kira-kira 8s Masa ralat digunakan terutamanya dalam kaedah pengisihan () Peraturan sumber data masih menjejaskan kerumitan masa algoritma pengisihan.
Kod diubah suai seperti berikut:

UjianB kelas awam {

static long count;

public static void main(String[] args) {
    System.out.println(random());
    long[] a = new long[50000000];
    for (int i = 0; i < a.length; i++) {
        a[i] = random();
    }

    long[] b = new long[10000000];
    for (int i = 0; i < b.length; i++) {
        b[i] = random();
    }
    long start = System.currentTimeMillis();
    Arrays.sort(b);
    Arrays.sort(a);
    int flag = -1;
    int cc =0;
    for (int i = 0; i < b.length; i++) {
        count = b[i];
        flag = Arrays.binarySearch(a, count);
        if (flag <= 50000000 && flag >= 0) {
            System.out.println(count + "   " + flag);
            cc++;
        }
    }
    System.out.println("相同数据的数量："+cc);
    System.out.println(System.currentTimeMillis() - start);
}

public static long random() {
    return Math.round((new Random()).nextDouble()*10000000000L+10000000000L);
}

}

Answer 3

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

aBM.add(a[i])

}
...
RoaringBitmap interactionBM = RoaringBitmap.and(aBM, bBM)
untuk (int item: interactionBM) {

System.out.println(item)

}

Answer 4

        long start = System.currentTimeMillis();
        HashSet<Long> alongs = new HashSet<>();

        for (long l : b) {
            alongs.add(l);
        }

        ArrayList<Long> sames = new ArrayList<>();
        for (long l : a) {
            if (alongs.contains(l)) {
                sames.add(l);
            }
        }

        long end = System.currentTimeMillis();
        System.out.println(end - start);

Menggunakan kod di atas, pada mesin saya, ia adalah 8s

Answer 5

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

Answer 6

C#, berjalan secara setempat, keluaran, 611ms

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;
var hashSetB = new HashSet<long>(b);

var matches = new List<long>();
var timer = new System.Diagnostics.Stopwatch();
Console.WriteLine("Starts...");
timer.Start();
for (var i = 0; i < a.Length; i++)
{
    if (hashSetB.Contains(a[i]))
    {
        matches.Add(a[i]);
    }
}
timer.Stop();
Console.WriteLine(timer.ElapsedMilliseconds);
Console.WriteLine("Found match: " + string.Join(", ", matches));
Console.ReadLine();

Answer 7

redis SINTER(Mengembalikan semua ahli set yang merupakan persilangan semua set yang diberikan.)

Answer 8

Jika operasi ini hanya boleh dilakukan dalam tatasusunan, tiada muslihat Sekurang-kurangnya tatasusunan yang lebih kecil mesti dilalui, malah pengisihan tidak dapat dielakkan. Dan jika kandungan tatasusunan boleh dieksport ke struktur data lain, ia seolah-olah melanggar niat asal soalan. Adakah penyoal ingin menguji operasi tatasusunan?

Answer 9

Mari kita ambil kaedah yang lebih mudah, yang hanya mengambil masa kira-kira 200ms pada MBP. Pentium G2020 biasa hanya mengambil masa 250ms
Nah, algoritma ini sama sekali mustahil.

Answer 10

Malah, algoritma adalah kunci kepada soalan ini.
Saya cadangkan anda membaca bab pertama Programming Pearls. Akan memberikan idea yang baik.
Pertama sekali, soalan mesti diperhalusi, iaitu, adakah nombor telefon bimbit mesti nombor telefon bimbit Cina sahaja? Jika tidak jumlahnya akan lebih tinggi.
Biar saya terangkan secara ringkas cara nombor telefon disimpan dalam Pengaturcaraan Zhuji.
Dia hanya menggunakan nombor binari untuk menyimpan semua nombor telefon bimbit. Satu digit binari boleh menjadi sangat panjang. Panjangnya adalah sama dengan nombor telefon terbesar yang mungkin. Sebagai contoh, 13999999999, sebenarnya, 13 boleh diabaikan Nombor kami ialah nombor binari dengan 999999999 digit.
Dalam setiap digit, jika terdapat nombor telefon ini, ia ditandakan sebagai 1, jika tidak, ia ditandakan sebagai 0.
Demi kesederhanaan, saya akan menganggap bahawa julat nombor telefon bimbit ialah 0 -9, mari kita sediakan Nombor binari 10 digit 0000000000.
Andaikan tatasusunan pertama mempunyai 3 nombor telefon, iaitu 1, 5, dan 7. Kemudian nombor binari yang menyimpan tatasusunan ini ialah 0010100010. 1, 5 , dan 7 digit nombor ini ialah 1, bit lain ialah 0.
Andaikan tatasusunan kedua mempunyai 6 nombor telefon iaitu 1, 2, 3, 4, 7, dan 8. Maka nombor binari yang menyimpan tatasusunan ini ialah 0110011110, iaitu 1, 2, 3, 4, 7. Bit ke-8 ialah 1 dan bit lain ialah 0.
Jadi bagaimana untuk mencari nombor telefon yang sama dalam dua tatasusunan ini?
Anda hanya perlu melakukan operasi "bitwise AND" (AND) dalam operasi bit Jika kedua-dua bit yang sama adalah 1, ia masih 1. Selagi salah satu daripadanya adalah 0, ia adalah 0.
0010100010 & 0110011110 = 0010000010

Saya mendapati sekali gus ia adalah nombor binari dengan 1 dalam digit pertama dan ke-7.