artkpv

Latency Comparison Numbers Simplified (~2012)
----------------------------------   log2 log10
L1 cache reference                     0    0           0.5   ns
Branch mispredict                      3    1             5   ns
L2 cache reference                     3    1             7   ns 
Mutex lock/unlock                      5    2            25   ns
Main memory reference                  8    2           100   ns                      20x L2 cache, 200x L1 cache
Compress 1K bytes with Zippy          14    4        10,000   ns       10 us
Send 1K bytes over 1 Gbps network     14    4        10,000   ns       10 us
Read 4K randomly from SSD*            18    5       150,000   ns      150 us          ~1GB/sec SSD

artkpv

class UnionFind:
    """Weighted quick-union with path compression and connected components.

    The original Java implementation is introduced at
    https://www.cs.princeton.edu/~rs/AlgsDS07/01UnionFind.pdf

    >>> uf = UnionFind(10)
    >>> for (p, q) in [(3, 4), (4, 9), (8, 0), (2, 3), (5, 6), (5, 9),
    ...                (7, 3), (4, 8), (6, 1)]:
    ...     uf.union(p, q)