寻找具有删除功能的快速过滤器()

Question

我正在尝试编写一个相当快的快速排序，但它在许多其他应用程序中都有使用。

内置过滤器(函数，迭代)函数返回迭代中的项列表，在传递给函数时返回true，并且比传统的for循环要快得多，因为您只需要检查一个列表的一个条件。

我正在寻找的是一个非常快的函数(像过滤器)，它不仅将构造一个新列表，而且会从旧列表中删除它所获取的项。在单枢轴快速排序的应用中，这将允许删除过滤器语句，并可能使分区例程加速近2倍。

有没有内置到python中的这样一个函数？那小矮子呢？如果没有，实现它的最快方法是什么？

作为参考，下面是当前的分区代码：

def partition(u):
    lesser = singleQuicksort(filter(lambda num: num <= u[0], u[1:]))
    greater = singleQuicksort(filter(lambda num: num > u[0], u[1:]))
    return lesser, greater

Answer 1

使用布尔掩码：

def partition(u):
    mask = u[1:] <= u[0]
    return u[1:][mask], u[1:][~mask]

Answer 2

在numpy里，差不多。这是数组索引。当您想要“过滤”出inf时，考虑以下情况

a=array([1,2,3,4,inf])
a[isfinite(a)]

或小于3的数值

a=array([1,2,3,4,5])
a[a>3]

为什么是“那种”？因为索引仍然会创建一个新数组：

>>> a=array([1,2,3,4,inf])
>>> a[isfinite(a)]
array([ 1.,  2.,  3.,  4.])
>>> id(a)
40165288 #your result will differ
>>> id(a[1])
40253288
>>> id(a[isfinite(a)][1])
39747512
>>> a[1]
2.0
>>> a[isfinite(a)][1]
2.0