numpy 'isin‘性能改进

Question

我有一个有383毫秒行的矩阵，我需要基于一个值列表(index_to_remove)过滤这个矩阵。该函数在1次迭代中执行多次。是否有比以下更快的替代办法：

def remove_from_result(matrix, index_to_remove, inv=True):
    return matrix[np.isin(matrix, index_to_remove, invert=inv)]

Answer 1

更快的实现

这是一个编译版本，使用一组作为列表理解解决方案的@Matt Messersmith。它基本上是对较慢的np.isin方法的替代。在index_to_remove是标量值的情况下，我遇到了一些问题，并为本例实现了一个单独的版本。

码

import numpy as np
import numba as nb

@nb.njit(parallel=True)
def in1d_vec_nb(matrix, index_to_remove):
  #matrix and index_to_remove have to be numpy arrays
  #if index_to_remove is a list with different dtypes this 
  #function will fail

  out=np.empty(matrix.shape[0],dtype=nb.boolean)
  index_to_remove_set=set(index_to_remove)

  for i in nb.prange(matrix.shape[0]):
    if matrix[i] in index_to_remove_set:
      out[i]=False
    else:
      out[i]=True

  return out

@nb.njit(parallel=True)
def in1d_scal_nb(matrix, index_to_remove):
  #matrix and index_to_remove have to be numpy arrays
  #if index_to_remove is a list with different dtypes this 
  #function will fail

  out=np.empty(matrix.shape[0],dtype=nb.boolean)
  for i in nb.prange(matrix.shape[0]):
    if (matrix[i] == index_to_remove):
      out[i]=False
    else:
      out[i]=True

  return out


def isin_nb(matrix_in, index_to_remove):
  #both matrix_in and index_to_remove have to be a np.ndarray
  #even if index_to_remove is actually a single number
  shape=matrix_in.shape
  if index_to_remove.shape==():
    res=in1d_scal_nb(matrix_in.reshape(-1),index_to_remove.take(0))
  else:
    res=in1d_vec_nb(matrix_in.reshape(-1),index_to_remove)

  return res.reshape(shape)

示例

data = np.array([[80,1,12],[160,2,12],[240,3,12],[80,4,11]])
test_elts= np.array((80))

data[isin_nb(data[:,0],test_elts),:]

Tmings

test_elts = np.arange(12345)
data=np.arange(1000*1000)

#The first call has compilation overhead of about 300ms
#which is not included in the timings
#remove_from_result:     52ms
#isin_nb:                1.59ms

Answer 2

过滤函数的运行时看起来是线性的w.r.t。输入matrix的大小。请注意，使用set进行列表理解的筛选绝对是线性的，您的函数运行速度大约是在我的机器上输入相同的列表理解过滤器的两倍。您还可以看到，如果将大小增加X的倍数，运行时也会增加X的倍数：

In [84]: test_elts = np.arange(12345)

In [85]: test_elts_set = set(test_elts)

In [86]: %timeit remove_from_result(np.arange(1000*1000), test_elts)
10 loops, best of 3: 81.5 ms per loop

In [87]: %timeit [x for x in np.arange(1000*1000) if x not in test_elts_set]
1 loop, best of 3: 201 ms per loop

In [88]: %timeit remove_from_result(np.arange(1000*1000*2), test_elts)
10 loops, best of 3: 191 ms per loop

In [89]: %timeit [x for x in np.arange(1000*1000*2) if x not in test_elts_set]
1 loop, best of 3: 430 ms per loop

In [90]: %timeit remove_from_result(np.arange(1000*1000*10), test_elts)
1 loop, best of 3: 916 ms per loop

In [91]: %timeit [x for x in np.arange(1000*1000*10) if x not in test_elts_set]
1 loop, best of 3: 2.04 s per loop

In [92]: %timeit remove_from_result(np.arange(1000*1000*100), test_elts)
1 loop, best of 3: 12.4 s per loop

In [93]: %timeit [x for x in np.arange(1000*1000*100) if x not in test_elts_set]
1 loop, best of 3: 26.4 s per loop

用于过滤非结构化数据，这在算法复杂性方面是尽可能快的，因为您必须触摸每个元素一次。你不能比线性时间做得更好。--一些可能有助于提高性能的事情：

1. 如果你可以访问像pyspark这样的东西(如果你愿意花几块钱的话，你可以在AWS上使用EMR )，你可以做得更快。这个问题相当令人尴尬地平行。您可以将输入分成K块，为每个员工提供需要平放的项和块，让每个工作人员筛选，然后在最后收集/合并。或者您甚至可以尝试使用multiprocessing，但是您必须小心内存(multiprocessing类似于C的fork()，它会生成子进程，但是每个克隆您当前的内存空间)。
2. 如果您的数据具有某种结构(如排序)，您可以更聪明地处理它，并获得次线性算法复杂性。例如，如果您需要从一个大的排序数组中删除相对较少的项，则只需对要删除的每个项执行bin搜索即可。这将在O(m log n)时间内运行，其中m是要删除的项数，n是大数组的大小。如果m是相对较小的(相对于n)，您是在做生意，那么您将接近O(log )。有更聪明的方法来处理这种特殊情况，但我选择这一种，因为它很容易解释。如果你知道你的数据的分布情况，你可能会比线性时间做得更好。

HTH。

Answer 3

如果可能，您应该将正在np.isin中传递的数组转换为整数类型。除此之外，如果可能的话，尝试使比较数组(第二个参数尽可能小)，删除重复项是方法之一。