WQUPC reduces time from 30 years to 6 seconds

Потрясающий факт: добавлением пары строчек в алгоритм, мы сокращаем время выполнения с 30 лет до 6 секунд!

Было

    public void union(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        parent[rootP] = rootQ; 
    }

    public int find(int p) {
        while (p != parent[p])
            p = parent[p];
        return p;
    }

Стало

    public void union(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        if (size[rootP] < size[rootQ]) {
            parent[rootP] = rootQ;
            size[rootQ] += size[rootP];
        }
        else {
            parent[rootQ] = rootP;
            size[rootP] += size[rootQ];
        }
    }

    public int find(int p) {
        while (p != parent[p]) {
            parent[p] = parent[parent[p]];
            p = parent[p];
        }
        return p;
    }

Это из проблемы Union-Find, где надо определять/задавать принадлежность объектов одному/разным наборам.

http://algs4.cs.princeton.edu/15uf/

Если взять миллиард (10^9) объектов и выполнить над ними 10^9 операций Union-Find, то в первом случае (Quick-Union UF) ждать придется 30 лет.

А во втором случае (Weighted Quick-Union with Path Compression UF) задача будет выполнена через 6 секунд.

Потрясающе.

Вот так всю жизнь используешь алгоритмы/структуры и знать не знаешь, какие страшные тайны скрыты под поверхностью.

А ведь я помню, как радовался народ, когда я чутка переписал алгоритм рассчета полигонов (древняя ГИС на древнем Автокаде) и вместо часов ожидания мы получали результат через секунды.

Но с 30 лет до 6 секунд парой строк? Это потрясающе.

original post http://vasnake.blogspot.com/2016/01/wqupc-reduces-time-from-30-years-to-6.html