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

Pour donner une idée, ce que nous recherchons, c'est le même numéro de téléphone dans les deux tableaux. Ensuite, nous construisons un arbre de dictionnaire à partir des numéros de téléphone du premier tableau.
Dans un deuxième temps, recherchez-le directement dans l'arborescence du dictionnaire. La complexité globale est O(N * 11) = O(N). 11 chiffres par numéro de téléphone. La complexité totale n’est que O(N).
Référence 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

Je viens de trouver une méthode, le temps d'exécution est d'environ 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);
    }
}

L'idée principale de cette méthode est de trier d'abord, puis d'utiliser la méthode Arrays.binarySearch() pour effectuer une requête binaire et renvoyer l'indice du tableau correspondant.

---

J'ai modifié la méthode d'obtention de la source de données et j'ai constaté que si une source de données aléatoire est utilisée, le temps consommé est d'environ 8 s. Le temps d'erreur est principalement consommé dans la méthode de tri sort() Les règles de la source de données. affectent toujours la complexité temporelle de l'algorithme de tri.
Le code est modifié comme suit :

classe publique TestB {

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()
for (int i = 0; i < a.length; i++) {

aBM.add(a[i])

}
...
RoaringBitmap interactionBM = RoaringBitmap.and(aBM, bBM)
for (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);

En utilisant le code ci-dessus, sur ma machine, c'est 8s

Answer 5

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

Answer 6

C#, exécution locale, version, 611 ms

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(Renvoie tous les membres d'un ensemble qui est l'intersection de tous les ensembles donnés.)

Answer 8

Si cette opération ne peut être effectuée que dans un tableau, il n'y a pas d'astuce. Au moins, le plus petit tableau doit être parcouru, et même le tri est inévitable. Et si le contenu du tableau peut être exporté vers d’autres structures de données, cela semble violer l’intention initiale de la question. La personne qui pose la question voulait-elle tester les opérations sur les tableaux ?

Answer 9

Prenons une méthode plus simple, qui ne prend qu'environ 200 ms sur MBP. Le Pentium G2020 ordinaire ne prend que 250 ms
Eh bien, cet algorithme est complètement impossible.

Answer 10

En fait, l'algorithme est la clé de cette question.
Je vous propose de lire le premier chapitre de Programming Pearls. Fournira de bonnes idées.
Tout d'abord, la question doit être affinée, c'est-à-dire : le numéro de téléphone portable doit-il être uniquement un numéro de téléphone portable chinois ? Sinon, le chiffre serait bien plus élevé.
Permettez-moi de vous expliquer brièvement comment les numéros de téléphone sont stockés dans Programming Zhuji.
Il utilise uniquement un nombre binaire pour stocker tous les numéros de téléphone portable. Un chiffre binaire peut être très long. La longueur est égale au plus grand numéro de téléphone possible. Par exemple, 13999999999, en fait, 13 peut être omis. Notre numéro est un nombre binaire à 999999999 chiffres.
Dans chaque chiffre, s'il y a ce numéro de téléphone, il est marqué comme 1, sinon, il est marqué comme 0.
Par souci de simplicité, je supposerai que la plage des numéros de téléphone portable est 0. -9, préparons un nombre binaire à 10 chiffres 0000000000.
Supposons que le premier tableau ait 3 numéros de téléphone, qui sont 1, 5 et 7. Ensuite, le nombre binaire stockant ce tableau est 0010100010. Le 1, 5 , et 7 chiffres de ce nombre valent 1, les autres bits valent 0.
Supposons que le deuxième tableau comporte 6 numéros de téléphone, à savoir 1, 2, 3, 4, 7 et 8. Le nombre binaire stockant ce tableau est alors 0110011110, soit 1, 2, 3, 4, 7. Le Le 8ème bit est 1 et les autres bits sont 0.
Alors comment retrouver le même numéro de téléphone dans ces deux tableaux ?
Il vous suffit d'effectuer l'opération "ET au niveau du bit" (ET) dans les opérations sur les bits. Si les deux mêmes bits sont 1, c'est toujours 1. Tant que l'un d'eux est 0, c'est 0.
0010100010 & 0110011110 = 0010000010

J'ai tout de suite découvert qu'il s'agissait d'un nombre binaire avec 1 dans le 1er et le 7ème chiffre.