Baike.dev
Log in
Back to tool/Back to issues
#8307·cupy

cp.unique without sorting

Author: essocaCreated Apr 24, 2024Updated Sep 12, 2026
Labelscat:numpy-compatprio:medium

Description

There are use cases where one wants to find unique rows in a 2D array without having to sort the outputs. This is already recognized by the implementation of unique by pandas. They claim it to be significantly faster than numpy's for long enough sequences.

I wanted to try the differences by implementing such functionality, keeping numpy's API. So I tried:

python
@numba.njit('Tuple((int64[::1], int64[::1], int32[::1]))(int64[::1])')
def _unique1d_with_no_sort_cpu_kernel(arr):
    uniques = dict()
    counts = dict()
    INF64 = np.iinfo(np.int64).max
    ind = np.ones(arr.size, dtype=np.int64) * INF64
    inv = np.empty(arr.size, dtype=np.int64)
    count_unique = -1
    for i, row in enumerate(arr):
        if row not in uniques:
            count_unique += 1
            uniques[row] = count_unique
            counts[row] = 1
            ind[count_unique] = i
        else:
            counts[row] += 1
        inv[i] = uniques[row]
    counts = np.asarray(list(counts.values()), dtype=np.int32)
    return ind[ind != INF64], inv, counts

and then wrap it by

python
def unique_no_sort_cpu_axis0(arr):
    arr_hashed = np.asarray([hash(row.tobytes()) for row in arr])
    return _unique1d_with_no_sort_cpu_kernel(arr_hashed)

Write a test case:

python
arr = np.random.randint(0, 2, (1000000, 10))
a1, b1, c1 = unique_no_sort_cpu_axis0(arr)
_, a2, b2, c2 = np.unique(
  arr,
  return_index=True,
  return_inverse=True,
  return_counts=True,
  axis=0
)

Asserting equality:

python
>>> all([np.all(a1==a2), np.all(b1==b2), np.all(c1==c2)])
True

Compare performance:

python
>>> %timeit unique_no_sort_cpu_axis0(arr)
273 ms ± 452 µs per loop (mean ± std. dev. of 7 runs, 1 loop each)
>>> %timeit np.unique(arr, return_index=True, return_inverse=True, return_counts=True, axis=0)
2.27 s ± 49.6 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

This implementation is then ~8x faster than numpy.

Since finding unique rows using cupy is also of interest (e.g. see the latest post requesting such a feature, which is btw already possible by sorting), I am very interested in the possibility of a faster implementation without sorting. Could you please consider it?

Many thanks in advance.

Additional Information

No response

Source: cupy/cupy

View original on GitHubView discussion on GitHub