Самый быстрый способ найти все уникальные элементы в массиве с Cython

Я пытаюсь найти наиболее эффективный метод для поиска уникальных значений из массива NumPy. Функция NumPy unique работает очень медленно и сначала сортирует значения перед поиском уникальной. Pandas хэширует значения, используя klib C library, которая намного быстрее. Я ищу решение Cython.

Простейшее решение похоже просто перебирает массив и использует набор Python для добавления каждого элемента следующим образом:

from numpy cimport ndarray
from cpython cimport set

@cython.wraparound(False)
@cython.boundscheck(False)
def unique_cython_int(ndarray[np.int64_t] a):
    cdef int i
    cdef int n = len(a)
    cdef set s = set()
    for i in range(n):
        s.add(a[i])
    return s

Я также попробовал unordered_set из С++

from libcpp.unordered_set cimport unordered_set
@cython.wraparound(False)
@cython.boundscheck(False)
def unique_cpp_int(ndarray[np.int64_t] a):
    cdef int i
    cdef int n = len(a)
    cdef unordered_set[int] s
    for i in range(n):
        s.insert(a[i])
    return s

Производительность

# create array of 1,000,000
a = np.random.randint(0, 50, 1000000)

# Pure Python
%timeit set(a)
86.4 ms ± 2.58 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

# Convert to list first
a_list = a.tolist()
%timeit set(a_list)
10.2 ms ± 74.8 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

# NumPy
%timeit np.unique(a)
32 ms ± 1.17 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

# Pandas
%timeit pd.unique(a)
5.3 ms ± 257 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

# Cython
%timeit unique_cython_int(a)
13.4 ms ± 1.02 ms per loop (mean ± std. dev. of 7 runs, 100 loops each)

# Cython - c++ unordered_set
%timeit unique_cpp_int(a)
17.8 ms ± 158 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

Обсуждение

Итак, Pandas примерно в 2,5 раза быстрее, чем набор cythonized. Его свинец увеличивается, когда есть более четкие элементы. Удивительно, но чистый набор python (в списке) превосходит набор cythonized.

Мой вопрос здесь - есть ли более быстрый способ сделать это в Cython, чем использовать метод add повторно? А можно ли улучшить С++ unordered_set?

Использование строк Unicode

История меняется, когда мы используем строки unicode. Я считаю, что мне нужно преобразовать массив numpy в тип данных object, чтобы правильно добавить его тип для Cython.

@cython.wraparound(False)
@cython.boundscheck(False)
def unique_cython_str(ndarray[object] a):
    cdef int i
    cdef int n = len(a)
    cdef set s = set()
    for i in range(n):
        s.add(a[i])
    return s

И снова я попробовал unordered_set из С++

@cython.wraparound(False)
@cython.boundscheck(False)
def unique_cpp_str(ndarray[object] a):
    cdef int i
    cdef int n = len(a)
    cdef unordered_set[string] s
    for i in range(n):
        s.insert(a[i])
    return s

Производительность

Создайте массив из 1 миллиона строк с 1000 различными значениями

s_1000 = []
for i in range(1000):
    s = np.random.choice(list('abcdef'), np.random.randint(5, 50))
    s_1000.append(''.join(s))

s_all = np.random.choice(s_1000, 1000000)

# s_all has numpy unicode as its data type. Must convert to object
s_unicode_obj = s_all.astype('O')

# c++ does not easily handle unicode. Convert to bytes and then to object
s_bytes_obj = s_all.astype('S').astype('O')

# Pure Python
%timeit set(s_all)
451 ms ± 5.94 ms per loop (mean ± std. dev. of 7 runs, 1 loop each) 

%timeit set(s_unicode_obj)
71.9 ms ± 5.91 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

# using set on a list
s_list = s_all.tolist()
%timeit set(s_list)
63.1 ms ± 7.38 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

# NumPy
%timeit np.unique(s_unicode_obj)
1.69 s ± 97.5 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

%timeit np.unique(s_all)
633 ms ± 3.99 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

# Pandas
%timeit pd.unique(s_unicode_obj)
97.6 ms ± 6.61 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

# Cython
%timeit unique_cython_str(s_unicode_obj)
60 ms ± 5.81 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

# Cython - c++ unordered_set
%timeit unique_cpp_str2(s_bytes_obj)
247 ms ± 8.45 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

Обсуждение

Итак, похоже, что набор Python превосходит Pandas для строк unicode, но не для целых чисел. И снова, итерация через массив в Китоне действительно не помогает нам вообще.

Обман с целыми числами

Можно обойти множества, если вы знаете, что диапазон ваших целых чисел не слишком сумасшедший. Вы можете просто создать второй массив всех нулей / False и повернуть свою позицию True, когда вы столкнетесь с каждым, и добавьте это число в список. Это очень быстро, поскольку хеширование не выполняется.

Следующее работает для целых положительных массивов. Если у вас есть отрицательные целые числа, вам нужно будет добавить константу, чтобы сдвинуть числа до 0.

@cython.wraparound(False)
@cython.boundscheck(False)
def unique_bounded(ndarray[np.int64_t] a):
    cdef int i, n = len(a)
    cdef ndarray[np.uint8_t, cast=True] unique = np.zeros(n, dtype=bool)
    cdef list result = []
    for i in range(n):
        if not unique[a[i]]:
            unique[a[i]] = True
            result.append(a[i])
    return result

%timeit unique_bounded(a)
1.18 ms ± 21.3 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

Недостатком является, конечно же, использование памяти, так как наибольшее целое число может привести к чрезвычайно большому массиву. Но этот метод мог бы работать и для float, если бы вы точно знали, сколько значительных цифр было у каждого номера.

Резюме

Целые числа 50 уникальных из 1 000 000 общих

  • Pandas - 5 мс
  • Набор Python списка - 10 мс
  • Набор Cython - 13 мс
  • "Обман" с целыми числами - 1,2 мс

Строки 1000 уникальные из 1 000 000 всего

  • Комплект Cython - 60 мс
  • Набор Python списка - 63 мс
  • Pandas - 98 мс

Оцените всю помощь, сделав это быстрее.

Ответы

Ответ 1

Я думаю, что ответ на ваш вопрос "какой самый быстрый способ найти уникальные элементы" - это "это зависит". Это зависит от вашего набора данных и от вашего оборудования.

Для ваших сценариев (я в основном рассматривал целочисленный случай) pandas (и используется khash) делает довольно приличную работу. Я не смог сопоставить эту производительность с помощью std::unordered_map.

Однако google::dense_hash_set в моих экспериментах был немного быстрее, чем pandas -решение.

Пожалуйста, прочтите более подробное объяснение.

Я хотел бы начать с объяснения результатов, которые вы наблюдаете, и использовать эти идеи позже.

Я начинаю с вашего int-example: в массиве есть только 50 уникальные элементы, но 1,000,000:

import numpy as np
import pandas as pd
a=np.random.randint(0,50, 10**6, dtype=np.int64)

В качестве базового значения времени np.unique() и pd.unique() для моей машины:

%timeit np.unique(a)
>>>82.3 ms ± 539 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
%timeit pd.unique(a)
>>>9.4 ms ± 110 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

pandas подход с набором (O(n)) примерно в 10 раз быстрее, чем метод numpy с сортировкой (O(nlogn)). log n = 20 для n=10**6, поэтому коэффициент 10 примерно соответствует ожидаемой разности.

Другое отличие состоит в том, что np.unique возвращает отсортированный массив, поэтому можно было бы использовать бинарный поиск для поиска элементов. pd.unique возвращает несортированный массив, поэтому нам нужно либо его сортировать (что может быть O(n log n), если в исходных данных не так много дубликатов) или преобразовать его в структуру типа.

Посмотрим на простой Python-Set:

%timeit set(a)
>>> 257 ms ± 21.9 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

Первое, что мы должны знать здесь: мы сравниваем яблоки и апельсины. Предыдущие unique -функции возвращают массивы numpy, которые состоят из низких c-целых чисел. Этот возвращает набор полных Python-целых чисел. Совершенно другое дело!

Это означает, что для каждого элемента в numpy-массиве мы должны сначала создать объект python - достаточно накладные расходы, и только тогда мы можем добавить его в набор.

Преобразование в целые числа Python может быть выполнено на этапе предварительной обработки - ваша версия с list:

A=list(a)
%timeit set(A)
>>> 104 ms ± 952 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
%timeit set(list(a))
>>> 270 ms ± 23.3 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

Для создания целых чисел Python требуется более 100 мс. Тем не менее, целые числа python более сложны, чем слабые C-int и, следовательно, их обработка стоит дороже. Использование pd.unique в C-int и продвижение к Python-множеству происходит намного быстрее.

И теперь ваша версия Cython:

%timeit unique_cython_int(a)
31.3 ms ± 630 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

Что я действительно не понимаю. Я бы ожидал, что он будет работать аналогично set(a) -cython вырезает интерпретатор, но это не объяснит фактор 10. Однако у нас есть только 50 различных целых чисел (которые даже в пуле целых чисел, потому что они меньше, чем 256), поэтому существует определенная оптимизация, которая играет роль/разницу.

Попробуйте другой набор данных (теперь есть 10**5 разные номера):

b=np.random.randint(0, 10**5,10**6, dtype=np.int64)
%timeit unique_cython_int(b)
>>> 236 ms ± 31.1 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
%timeit set(b)
>>> 388 ms ± 15.3 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

Ускорение менее 2 - это то, чего я ожидал бы.

Посмотрим на cpp-версию:

%timeit unique_cpp_int(a)
>>> 25.4 ms ± 534 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
%timeit unique_cpp_int(b)
>>> 100 ms ± 4.8 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

Есть некоторые накладные расходы при копировании данных из cpp-набора в набор Python (как указывал DavidW), но в остальном поведение, как я ожидал бы, дало бы мой опыт: std::unordered_map несколько быстрее, чем Python, но не самая большая реализация вокруг - panda, кажется, превзошла его:

%timeit set(pd.unique(b))
>>> 45.8 ms ± 3.48 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

Итак, похоже, что в ситуации, когда есть много дубликатов, а хеш-функция дешевая, решение pandas трудно превзойти.

Возможно, вы можете попробовать структуры данных Google.

Однако, когда данные имеют только очень мало дубликатов, решение сортировки numpy может стать более быстрым. Основная причина заключается в том, что numpy unique требуется только в два раза больше памяти - исходные данные и вывод, в то время как pandas хэш-набор-решение требует гораздо больше памяти: исходные данные, набор и вывод. Для огромных наборов данных это может стать разницей между достаточным объемом оперативной памяти и отсутствием достаточного объема оперативной памяти.

В зависимости от набора-реализации зависит от того, сколько оперативной памяти требуется, и это всегда связано с компромиссом между памятью и скоростью. Например, std::unordered_set требуется, по крайней мере, 32 байт, чтобы сохранить целое число 8 -byte. Некоторые структуры данных google могут работать лучше.

Запуск /usr/bin/time -fpeak_used_memory:%M python check_mem.py с pandas/numpy unique:

#check_mem.py
import numpy as np
import pandas as pd
c=np.random.randint(0, 2**63,5*10**7, dtype=np.int64)
#pd.unique(c)  
np.unique(c)

показывает 1,2 ГБ для numpy и 2,0 ГБ для pandas.

На самом деле, на моей машине с Windows np.unique работает быстрее, чем pd.unique, если в массиве есть (только рядом) только уникальные элементы, даже для элементов "only" 10^6 (возможно, из-за необходимых повторений в качестве используемый набор растет). Однако это не относится к моей машине Linux.

Другой сценарий, в котором pandas не блистает, заключается в том, что вычисление хеш-функции не является дешевым: рассмотрите длинные строки (например, 1000 символы) как объекты.

Для вычисления хеш-значения нужно учитывать все 1000 символы (что означает, что много данных → много промахов хэша), сравнение двух строк в основном выполняется после одного или двух символов - вероятность тогда уже очень высока, мы знаем, что строки разные. Таким образом, коэффициент log n numpy unique больше не выглядит таким.

В этом случае лучше использовать древовидный набор вместо хеш-набора.

Улучшение в cpp-неупорядоченном наборе:

Метод, использующий неупорядоченный набор cpp, может быть улучшен благодаря его методу reserve(), что избавит от необходимости переименования. Но он не импортируется на cython, поэтому использование довольно громоздко от Cython.

Однако резервирование не повлияло бы на время выполнения данных с использованием только 50 уникальных элементов и не более 2 (амортизируемые затраты из-за используемой стратегии изменения размера) для данных, имеющих почти все уникальные элементы.

Хеш-функция для ints является тождеством (по крайней мере для gcc), поэтому не так много, чтобы получить здесь (я не знаю, t думаю, что использование более причудливой хэш-функции поможет здесь).

Я не вижу способа, чтобы неупорядоченный набор cpp мог быть изменен, чтобы превзойти реализацию khash, используемую pandas, что кажется довольно хорошим для этого типа задач.

Вот, например, эти довольно старые тесты, которые показывают, что khash несколько быстрее, чем std::unordered_map, причем только google_dense является четным Быстрее.

Использование плотной карты google:

В моих экспериментах гуманная карта google (от здесь) смогла победить khash - в конце можно найти контрольный код ответа.

Это было быстрее, если было только 50 уникальных элементов:

#50 unique elements:
%timeit google_unique(a,r)
1.85 ms ± 8.26 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
%timeit pd.unique(a)
3.52 ms ± 33.9 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

но и быстрее, если были только уникальные элементы:

%timeit google_unique(c,r)
54.4 ms ± 375 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
In [3]: %timeit pd.unique(c)
75.4 ms ± 499 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

Мои несколько экспериментов также показали, что google_hash_set использует, возможно, больше памяти (до 20%), чем хаш, но требуется больше тестов, чтобы понять, действительно ли это так.

Я не уверен, что мой ответ помог вам вообще. Мои приемы:

  • Если нам нужен набор Python-целых чисел, set(pd.unique(...)) кажется хорошей отправной точкой.
  • Есть несколько случаев, когда решение сортировки numpy может быть лучше (меньше памяти, иногда хеш-расчет слишком дорог)
  • Зная больше о данных, можно использовать для настройки решения, сделав лучший компромисс (например, используя меньше/больше памяти /preallocating, поэтому нам не нужно перефразировать или использовать битрейт для поиска).
  • pandas решение, похоже, очень хорошо подходит для некоторых обычных случаев, но тогда для других случаев может быть и другой компромисс - google_dense является самым перспективным кандидатом.

Списки для google-тестов:

#google_hash.cpp
#include <cstdint>
#include <functional>
#include <sparsehash/dense_hash_set>

typedef int64_t lli;
void cpp_unique(lli *input, int n, lli *output){

  google::dense_hash_set<lli, std::hash<lli> > set;
  set.set_empty_key(-1);
  for (int i=0;i<n;i++){
     set.insert(input[i]);
  }  

  int cnt=0;
  for(auto x : set)
    output[cnt++]=x;
}

соответствующий pyx файл:

#google.pyx
cimport numpy as np
cdef extern from "google_hash.cpp":
    void cpp_unique(np.int64_t  *inp, int n, np.int64_t *output)

#out should have enough memory:
def google_unique(np.ndarray[np.int64_t,ndim=1] inp, np.ndarray[np.int64_t,ndim=1] out):
    cpp_unique(&inp[0], len(inp), &out[0])

файл setup.py:

from distutils.core import setup, Extension
from Cython.Build import cythonize
import numpy as np

setup(ext_modules=cythonize(Extension(
            name='google',
            language='c++',
            extra_compile_args=['-std=c++11'],
            sources = ["google.pyx"],
            include_dirs=[np.get_include()]
    )))

Ipython-benchmark script, после вызова python setup.py build_ext --inplace:

import numpy as np
import pandas as pd
from google import google_unique

a=np.random.randint(0,50,10**6,dtype=np.int64)
b=np.random.randint(0, 10**5,10**6, dtype=np.int64)
c=np.random.randint(0, 2**63,10**6, dtype=np.int64)
r=np.zeros((10**6,), dtype=np.int64)

%timeit google_unique(a,r
%timeit pd.unique(a)

Другие объявления

Версия Cython после исправлений:

%%cython
cimport cython
from numpy cimport ndarray
from cpython cimport set
cimport numpy as np
@cython.wraparound(False)
@cython.boundscheck(False)
def unique_cython_int(ndarray[np.int64_t] a):
    cdef int i
    cdef int n = len(a)
    cdef set s = set()
    for i in range(n):
        s.add(a[i])
    return s

Версия С++ после исправлений:

%%cython -+ -c=-std=c++11
cimport cython
cimport numpy as np
from numpy cimport ndarray
from libcpp.unordered_set cimport unordered_set
@cython.wraparound(False)
@cython.boundscheck(False)
def unique_cpp_int(ndarray[np.int64_t] a):
    cdef int i
    cdef int n = len(a)
    cdef unordered_set[int] s
    for i in range(n):
        s.insert(a[i])
    return s