Быстрое удаление дубликатов в numpy и python

Question

Есть ли какой-нибудь быстрый способ получить уникальные элементы в numpy? У меня есть код, похожий на этот (последняя строка)

tab = numpy.arange(100000000)

indices1 = numpy.random.permutation(10000)
indices2 = indices1.copy()
indices3 = indices1.copy()
indices4 = indices1.copy()

result = numpy.unique(numpy.array([tab[indices1], tab[indices2], tab[indices3], tab[indices4]]))

Это просто пример, и в моей ситуации indices1, indices2,...,indices4 содержит различный набор индексов и имеет различный размер. Последняя строка выполняется много раз и Inoticed, что это на самом деле узкое место в моем коде ({numpy.core.multiarray.arange}, чтобы быть упреждающим). Кроме того, порядок не важен и элемент в массиве индексов имеет тип int32. Я думал об использовании хеш-таблицы со значением элемента в качестве ключа и попытался:

seq = itertools.chain(tab[indices1].flatten(), tab[indices2].flatten(), tab[indices3].flatten(), tab[indices4].flatten())
myset = {}
map(myset.__setitem__, seq, [])
result = numpy.array(myset.keys())

но было еще хуже.

Есть ли способ ускорить это? Я предполагаю, что снижение производительности происходит из-за «причудливой индексации», которая копирует массив, но мне нужен только полученный элемент для чтения (я ничего не изменяю).

Answer 1

[То, что следует, фактически частично неверно (см. PS):]

Следующий способ получения уникальных элементов во всех подмассивах очень быстрый:

seq = itertools.chain(tab[indices1].flat, tab[indices2].flat, tab[indices3].flat, tab[indices4].flat)
result = set(seq)

Примечаниечто flat (который возвращает итератор) используется вместо flatten() (который возвращает полный массив), и что set() можно вызывать напрямую (вместо использования map() и словаря, как во втором методе)).

Вот результаты синхронизации (полученные в оболочке IPython):

>>> %timeit result = numpy.unique(numpy.array([tab[indices1], tab[indices2], tab[indices3], tab[indices4]]))
100 loops, best of 3: 8.04 ms per loop
>>> seq = itertools.chain(tab[indices1].flat, tab[indices2].flat, tab[indices3].flat, tab[indices4].flat)
>>> %timeit set(seq)
1000000 loops, best of 3: 223 ns per loop

Таким образом, метод set / flat в этом примере в 40 раз быстрее.

PS : время set(seq) на самом деле не является репрезентативным.Фактически, первый цикл синхронизации очищает итератор seq, а последующие оценки set() возвращают пустой набор!Правильный временной тест - следующий

>>> %timeit set(itertools.chain(tab[indices1].flat, tab[indices2].flat, tab[indices3].flat, tab[indices4].flat))
100 loops, best of 3: 9.12 ms per loop

, который показывает, что метод set / flat на самом деле не быстрее.

PPS : здесь (неудачное) исследованиепредложения mtrw;поиск уникальных индексов заранее может быть хорошей идеей, но я не могу найти способ реализовать его, который быстрее, чем описанный выше подход:

>>> %timeit set(indices1).union(indices2).union(indices3).union(indices4)
100 loops, best of 3: 11.9 ms per loop
>>> %timeit set(itertools.chain(indices1.flat, indices2.flat, indices3.flat, indices4.flat))
100 loops, best of 3: 10.8 ms per loop

Таким образом, поиск набора всех различных индексов сам по себедовольно медленно.

PPPS : numpy.unique(<concatenated array of indices>) на самом деле в 2-3 раза быстрее, чем set(<concatenated array of indices>).Это ключ к ускорению, полученному в ответе Баго (unique(concatenate((…)))).Вероятно, причина в том, что позволить NumPy самостоятельно обрабатывать свои массивы, как правило, быстрее, чем связывать чистый Python (set) с массивами NumPy.

Заключение : поэтому этот ответ только документирует неудачные попытки, которыене следует полностью следовать, а также, возможно, полезное замечание о временном коде с итераторами ...

Answer 2

Извините, я не совсем понимаю ваш вопрос, но я сделаю все возможное, чтобы помочь.

Fist {numpy.core.multiarray.arange} - это numpy.arange, а не необычная индексация, к сожалению, необычная индексация не отображается как отдельная позиция в профилировщике. Если вы вызываете np.arange в цикле, вы должны посмотреть, сможете ли вы переместить его наружу.

In [27]: prun tab[tab]
     2 function calls in 1.551 CPU seconds

Ordered by: internal time

ncalls  tottime  percall  cumtime  percall filename:lineno(function)
    1    1.551    1.551    1.551    1.551 <string>:1(<module>)
    1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler'    objects}

In [28]: prun numpy.arange(10000000)
     3 function calls in 0.051 CPU seconds

Ordered by: internal time

ncalls  tottime  percall  cumtime  percall filename:lineno(function)
    1    0.047    0.047    0.047    0.047 {numpy.core.multiarray.arange}
    1    0.003    0.003    0.051    0.051 <string>:1(<module>)
    1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}

Во-вторых, я предполагаю, что tab - это не np.arange(a, b) в вашем коде, потому что, если это tab[index] == index + a, но я предполагаю, что это было только для вашего примера.

В-третьих, np.concatenate примерно в 10 раз быстрее, чем np.array

In [47]: timeit numpy.array([tab[indices1], tab[indices2], tab[indices3], tab[indices4]])
100 loops, best of 3: 5.11 ms per loop

In [48]: timeit numpy.concatenate([tab[indices1], tab[indices2], tab[indices3],     tab[indices4]])
1000 loops, best of 3: 544 us per loop

(Также np.concatenate дает массив (4 * n,), а np.array - массив (4, n), где n - длина индексов [1-4]. Последний будет работать только в том случае, если все индексы 1-4 имеют одинаковую длину.)

И, наконец, вы также можете сэкономить еще больше времени, если сможете сделать следующее:

indices = np.unique(np.concatenate((indices1, indices2, indices3, indices4)))
result = tab[indices]

Делать это в таком порядке быстрее, потому что вы уменьшаете количество индексов, которые вы должны искать на вкладке, но это будет работать, только если вы знаете, что элементы табуляции уникальны (в противном случае вы можете получить повторы даже в результате если индексы уникальны).

Надеюсь, что поможет