排序numpy数组的交集

Question

我有一个排序的numpy数组列表。计算这些数组的排序交集的最有效方法是什么？

在我的应用程序中，我期望数组的数量小于10^4，期望单个数组的长度小于10^7，并且期望交集的长度接近p*N，其中N是最大数组的长度，其中0.99

一种快速而肮脏的方法是反复调用numpy.intersect1d()。但是，这似乎效率低下，因为intersect1d()没有利用数组排序这一事实。

Answer 1

几个月前，我为此编写了一个基于C++的python扩展。套餐称为sortednp，可通过pip获得。多个排序的numpy数组的交集，例如a、b和c，可以用

import sortednp as snp
i = snp.kway_intersect(a, b, c)

默认情况下，这将使用指数搜索在内部提前数组索引，在交集较小的情况下，这种速度相当快。在您的示例中，如果将algorithm=snp.SIMPLE_SEARCH添加到方法调用中，可能会更快。