使用Cython查找数组中所有独特元素的最快方法

Question

我试图找到最有效的方法来从NumPy数组中查找唯一值.NumPy的unique功能非常慢,在找到唯一值之前先对值进行排序.Pandas使用klib C库来散列值,这个库要快得多.我正在寻找一个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

我也试过c ++中的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)

讨论

因此,大熊猫比cythonized集快2.5倍.当有更多不同的元素时,它的领先优势会增加 令人惊讶的是,一个纯粹的python集(在列表中)击败了一个cythonized集.

我的问题是 - 在Cython中有更快的方法来add重复使用该方法吗？并且可以改进c ++ 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_setc ++

@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,000个不同值的100万个字符串的数组

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的集合优于unicode字符串的pandas而不是整数.再一次,在Cython中迭代数组并没有真正帮助我们.

欺骗整数

如果你知道你的整数范围不是太疯狂,那么绕过集合是可能的.您可以简单地创建所有零的第二个数组/ 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)

缺点当然是内存使用,因为你的最大整数可能会强制一个非常大的数组.但是,如果您确切地知道每个数字有多少有效数字,这种方法也适用于浮点数.

摘要

整数50个独特的1,000,000总计

• 熊猫 - 5毫秒
• Python列表 - 10毫秒
• Cython设置 - 13毫秒
• 用整数'作弊' - 1.2毫秒

字符串1,000独特,总计1,000,000

• Cython设置 - 60毫秒
• Python列表 - 63毫秒
• 熊猫 - 98毫秒

感谢所有帮助使这些更快.

Answer 1

我认为你回答的问题是"找到独特元素的最快方法是什么"是"它取决于".这取决于您的数据集和硬件.

对于你的场景(我主要看整数情况)pandas(和使用khash)做了相当不错的工作.我无法使用这个性能std::unordered_map.

然而,google::dense_hash_set我的实验比熊猫解决方案略快.

请继续阅读以获得更详细的解释.

我想首先解释您正在观察的结果,然后再使用这些见解.

我从你的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)

使用set(O(n))的pandas方法比使用sorted(O(nlogn))的numpy方法快10倍.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-array中的每个元素,我们必须首先创建一个python-object - 相当大的开销,然后才能将它添加到set中.

转换为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-integers比低C-int更复杂,因此处理它们的成本更高.使用pd.uniqueC-int而不是提升到Python-set要快得多.

现在你的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-version:

%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-set复制到Python集有一些开销(正如DavidW所指出的那样),但是根据我对它的体验,我所期望的行为:std::unordered_map比Python快一些,但不是最好的实现周围 - 熊猫似乎打败了它:

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

所以看起来,在这种情况下,有许多重复且哈希函数便宜,大熊猫解决方案很难被击败.

有人可能会试用谷歌数据结构.

但是,当数据只有很少的重复数据时,numpy的排序解决方案可能会变得更快.主要原因是,numpy unique只需要内存的两倍 - 原始数据和输出,而pandas hash-set-solution需要更多内存:原始数据,集合和输出.对于庞大的数据集,它可能成为拥有足够RAM和没有足够RAM的区别.

它取决于set-implementation需要多少内存开销,而且总是关于内存和速度之间的权衡.例如std::unordered_set,至少需要32byte来保存一个8字节的整数.一些谷歌的数据结构可以做得更好.

/usr/bin/time -fpeak_used_memory:%M python check_mem.py使用pandas/numpy独特运行:

#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 GB numpy和2.0 GB pandas.

实际上,在我的Windows机器np.unique上比pd.unique没有(旁边)数组中的唯一元素更快,即使对于"仅" 10^6元素(可能是因为所使用的集合增长时所需的重新组合).然而,我的Linux机器不是这种情况.

另一种pandas不发光的情况是散列函数的计算不便宜:考虑长字符串(比如1000字符)作为对象.

要计算哈希值,需要考虑所有1000字符(这意味着大量数据 - >大量哈希未命中),两个字符串的比较主要是在一个或两个字符之后完成 - 然后概率已经非常高,我们知道字符串是不同的.因此log nnumpy的因素unique不再那么糟糕了.

在这种情况下,最好使用树集而不是哈希集.

改进cpp-unordered集合:

使用cpp的无序集的方法可以通过其方法得到改进reserve(),这将消除重新散列的需要.但它并没有导入到cython中,所以Cython的使用非常繁琐.

然而,对于具有仅50个唯一元素且最多因子2(由于使用的调整大小策略而导致的摊销成本)的数据的运行时,对于几乎所有元素都是唯一的,对于数据的运行时没有任何影响.

哈希函数ints是身份(至少对于gcc),所以在这里获得的并不多(我不认为使用更花哨的哈希函数会对此有所帮助).

我看不出cpp的无序集如何能够被调整以击败熊猫使用的khash实现,这对于这类任务来说似乎相当不错.

例如,这些相当旧的基准测试表明,这khash比 std::unordered_map仅仅更快的google_dense要快一些.

使用谷歌密集地图:

在我的实验中,谷歌密集地图(从这里)能够击败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使用的内存可能比khash更多(最多20%),但是需要更多的测试才能确定是否真的如此.

我不确定我的回答对你有帮助.我的外卖是:

1. 如果我们需要一组Python整数,set(pd.unique(...))似乎是一个很好的起点.
2. 在某些情况下,numpy的排序解决方案可能更好(内存更少,有时哈希计算太昂贵)
3. 通过更好的权衡(例如,使用更少/更多的内存/预分配,因此我们不需要重新散列或使用bitset进行查找),可以使用了解有关数据的更多信息来调整解决方案.
4. 对于一些常见情况,熊猫解决方案似乎调整得相当不错,但在其他情况下,另一种权衡可能会更好 - google_dense是最有希望的候选人.

谷歌测试的列表:

#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脚本后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

修复后的C++版本:

%%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