Получение уникальных значений массива 1D NumPy без сортировки

Question

У меня много больших одномерных массивов, и я хотел бы получить уникальные значения. Как правило, можно сделать:

x = np.random.randint(10000, size=100000000)
np.unique(x)

Однако это выполняет ненужную сортировку массива. В документах на np.unique не упоминается способ извлечения индексов без сортировки. Другие ответы с np.unique включают использование return_index, но, насколько я понимаю, массив все еще сортируется. Итак, я попытался использовать set:

set(x)

Но это намного медленнее, чем сортировка массива с np.unique. Есть ли более быстрый способ получения уникальных значений для этого массива, который позволяет избежать сортировки и быстрее, чем np.unique?

Answer 1

Если ваши значения являются положительными целыми числами в относительно небольшом диапазоне (например, 0 ... 10000), существует альтернативный способ получения списка уникальных значений с использованием масок: (см. unique2() ниже)

import numpy as np

def unique1(x):
    return np.unique(x)

def unique2(x):
    maxVal    = np.max(x)+1
    values    = np.arange(maxVal)
    used      = np.zeros(maxVal)
    used[x]   = 1
    return values[used==1]

# optimized (with option to provide known value range)
def unique3(x,maxVal=None):
    maxVal    = maxVal or np.max(x)+1
    used      = np.zeros(maxVal,dtype=np.uint8)
    used[x]   = 1
    return np.argwhere(used==1)[:,0]

В моих тестах этот метод намного быстрее, чем np.unique, и он не включает сортировку:

from timeit import timeit
count = 3
x = np.random.randint(10000, size=100000000)

t = timeit(lambda:unique1(x),number=count)
print("unique1",t)

t = timeit(lambda:unique2(x),number=count)
print("unique2",t)

t = timeit(lambda:unique3(x),number=count)
print("unique3",t)

t = timeit(lambda:unique3(x,10000),number=count)
print("unique3",t, "with known value range")


# unique1 16.894681214000002
# unique2 0.8627655060000023
# unique3 0.8411087540000004
# unique3 0.5896318829999991 with known value range

Answer 2

На всякий случай, если вы передумаете о зависимостях, вот простая реализация numba.njit:

import numba

@numba.njit
def unique(arr):
    return np.array(list(set(arr)))


%timeit unique(x) #using Alain T.'s benchmark array
2.64 s ± 799 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

%timeit np.unique(x)
5.45 s ± 233 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

Не так быстро, как выше, но также не требует положительных целочисленных входных данных.