pandas - 使用 Cython 查找数组中所有唯一元素的最快方法

Question

我试图找到最高效的方法来从 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

我还尝试了 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)

讨论

因此，pandas 比 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_set来自 C++

@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

性能

创建一个由 100 万个字符串组成的数组，其中包含 1,000 个不同的值

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)

讨论

因此，对于 unicode 字符串，Python 的集合似乎优于 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

Pandas - 5 毫秒

Python 列表集 - 10 毫秒

Cython 集 - 13 毫秒

整数“作弊” - 1.2 毫秒

字符串 1,000 唯一，共 1,000,000

Cython 集 - 60 毫秒

Python 列表集 - 63 毫秒

Pandas - 98 毫秒

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

Answer 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)

使用集合 ( O(n) ) 的 pandas 方法比使用 numpy 的排序方法 ( O(nlogn) ) 快约 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 -functions 返回 numpy 数组，它由低级 c 整数组成。这个返回一组成熟的 Python 整数。完全不同的事情!

这意味着对于 numpy-array 中的每个元素，我们必须首先创建一个 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 整数更复杂，因此处理它们的成本更高。使用 pd.unique在 C-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 集复制到 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 data structures .

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

这取决于设置实现需要多少内存开销，并且总是关于内存和速度之间的权衡。例如 std::unordered_set至少需要 32字节保存 8 - 字节整数。一些google的数据结构可以做得更好。

运行 /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)

numpy 显示 1.2 GB和 2.0GB 用于 pandas .

实际上，在我的 Windows 机器上 np.unique比 pd.unique 快如果数组中只有(旁边)唯一的元素，即使是“仅” 10^6元素(可能是因为随着使用集的增长需要重新哈希)。然而，这不是我的 Linux 机器的情况。

另一个场景是 pandas当哈希函数的计算不便宜时，不会发光:将长字符串(比如 1000 个字符)视为对象。

要计算哈希值，需要考虑所有 1000字符(这意味着很多数据-> 很多散列未命中)，两个字符串的比较主要是在一两个字符之后进行的-那么概率已经非常高了，我们知道字符串是不同的。所以 log n numpy 的因子 unique看起来不再那么糟糕了。

在这种情况下，最好使用树集而不是散列集。

改进 cpp 无序集:

使用cpp的无序集的方法可以改进，因为它的方法 reserve() ，这将消除重新散列的需要。但是没有导入到cython中，所以从Cython中使用起来比较麻烦。

然而，保留不会对只有 50 个唯一元素的数据的运行时间产生任何影响，对于几乎所有元素都是唯一的数据，最多只有因子 2(由于使用的调整大小策略而摊销成本)。
ints 的哈希函数是身份(至少 for gcc )，所以在这里获得的好处不多(我认为在这里使用更花哨的哈希函数不会有帮助)。

我看不出如何调整 cpp 的无序集以击败 Pandas 使用的 khash 实现，这似乎非常适合此类任务。

这里是例如 these pretty old benchmarks ，这表明 khash比 std::unordered_map 快一些只有 google_dense 更快。

使用谷歌密集 map :

在我的实验中，谷歌密集 map (来自 here)能够击败 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%)，但需要更多的测试来确定是否真的如此。

我不确定我的回答是否对您有帮助。我的收获是:

如果我们需要一组 Python 整数，set(pd.unique(...))似乎是一个很好的起点。

在某些情况下，numpy 的排序解决方案可能更好(更少的内存，有时哈希计算太昂贵)

通过更好地权衡(例如，使用更少/更多内存/预分配，因此我们不需要重新散列或使用位集进行查找)，可以使用对数据的更多了解来调整解决方案。

Pandas 解决方案似乎对某些常见情况进行了很好的调整，但对于其他情况，另一种权衡可能会更好 - 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