代码之家 › 专栏 › 技术社区 › Arty

NumPy-1D数组的懒惰字典比较

lazy-evaluation comparison numpy arrays python

Arty · 技术社区 · 4 年前

我有两个NumPy 1D数组 a 和 b .

我该如何比较它们 lexicographically 这意味着1D数组的比较方式应该与Python比较元组的方式相同。

最重要的是,这应该延迟完成,即函数应该在已知结果的最左侧出现时立即返回结果。

此外,我还在为numpy数组寻找最快的解决方案。对于某些矢量化实现,可能会使用其他numpy函数。

否则,非懒惰的简单实现可能如下:

i = np.flatnonzero((a < b) != (a > b))
print('a ' + ('==' if i.size == 0 else '<' if a[i[0]] < b[i[0]] else '>') + ' b')

或者懒惰的简单变体,但由于使用纯Python类型而速度较慢:

ta, tb = tuple(a), tuple(b)
print('a ' + ('<' if ta < tb else '==' if ta == tb else '>') + ' b')

另一种解决方案是使用 np.lexsort ,但问题是,它是否针对只有两列(两个1D数组)的情况进行了优化,以及它是否是懒惰的?同样的问题是,lexsort的结果可能不足以有三种可能的答案 < / == / > ,也许这只足以说明 <= 此外,lexsort还需要一些非懒惰的预处理,如np.stack和颠倒行顺序。

print('a ' + ('<=' if np.lexsort(np.stack((a, b), 1)[::-1])[0] == 0 else '>') + ' b')

但是,它能在numpy中缓慢而快速地实现吗?我需要懒惰行为,因为1D数组可能相当大,但在大多数情况下,比较结果非常接近开始。

0 回复 | 直到 4 年前

Nick 4 年前

在直python中,你会迭代 zip ped列表:

def lazy_compare(a, b):
    for x, y in zip(a, b):
        if x < y:
            return 'a < b'
        if x > y:
            return 'a > b'
    return 'a == b'

例如

print(lazy_compare(['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'b', 'd', 'e']))
print(lazy_compare(['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'f']))
print(lazy_compare(['a', 'b', 'c', 'd', 'e'], ['a', 'b', 'c', 'd', 'e']))

输出:

a > b
a < b
a == b

自从 拉链 返回一个迭代器,它只在您使用值时生成值,这是懒惰的,一旦找到结果,它就会返回一个结果,因此只需要在两个列表相等的情况下遍历整个列表。

Galen 3 年前

人们可能会猜测,使用循环并对数组进行索引可能比使用循环更快 zip ,但事实并非如此。

以这些定义作为比较的基础。

def lex_leq_zip(a, b):
    for x, y in zip(a, b):
        if x > y:
            return False
    return True

def lex_leq_index(x,y):
    for i in np.arange(x.size):
        if x[i] > y[i]:
            return False
    return True

然后我们扫描不同大小的数组以收集变化数据:

for L in range(1,100000, 1000):
    for rep in range(10):
        x = np.random.random(size=L)
        y = np.random.random(size=L)
        z = timeit('lex_leq_zip(x,y)',
              globals={'lex_leq_zip':lex_leq_zip,
                       'x':x,
                       'y':y},
              number=1)
        i = timeit('lex_leq_index(x,y)',
              globals={'lex_leq_index':lex_leq_index,
                       'x':x,
                       'y':y},
              number=1)
        plt.scatter([L], [z], color='k')
        plt.scatter([L], [i], color='b')
plt.show()

放大结果图,我得到了以下结果:

从上面的代码中可以回想起,纵轴是以秒为单位的时间,横轴是数组的长度,蓝色因子是基于索引的实现,黑色因子是 拉链 -基于实施。虽然我们考虑的是非常小的几分之一秒(在某些情况下可能很宝贵),但很明显 拉链 -基于的方法更快。

脚注:我也试着用Numba的 @jit(nopython=True) 基于索引的实现上的装饰器,但它显示了类似的模式。

脚注:我也试过NumPy的 np.vectorize 在这两种实现中,但实际上都会导致与尝试索引数字有关的错误。