在 Numpy 中获得向量集并集的有效方法

Question

我正在尝试实现特定的二分搜索算法。“结果”一开始应该是一个空集，在搜索过程中，结果变量将与我们得到的新结果成为并集。

基本上：

results = set()
for result in search():
  results = results.union(result)

但这样的代码实际上不能与 Numpy 数组一起使用，因此我们np.union1d为此目的使用：

results = np.array([])
for result in search():
    result = np.union1d(results, result)

上面的代码也不起作用，因为如果我们有两个向量a = [1,2,3]和b=[3,4,5]，np.union1d(a, b)将返回：

[1, 2, 3, 4, 5]

但我希望它返回：

[[1, 2, 3], [3,4,5]]

由于没有重复的向量，如果我们有例如union([[1, 2, 3], [3,4,5]], [1,2,3])，返回值应保持不变：

[[1, 2, 3], [3,4,5]]

---

所以我想说我需要一个基于 numpy 数组的 union。

我还考虑过使用np.append(a, b)and then np.unique(x)，但这两个函数都将低维数组投影到高维数组。np.append还有axis=0属性，它保留插入的所有数组的维度，但我无法在没有维度错误的情况下有效地实现它。

问题：

如何有效地实现基于向量的集合？因此并集中的点将被视为向量而不是标量，并将保留其向量形式和维度。

Answer 1

这是一些基本的集合操作。

\n\n

定义一对列表（它们可以是np.array([1,2,3])，但这不是您所显示的。

\n\n

In [261]: a = [1,2,3]; b=[3,4,5]\n

\n\n

其中几个的列表：

\n\n

In [263]: alist = [a, b, a]\nIn [264]: alist\nOut[264]: [[1, 2, 3], [3, 4, 5], [1, 2, 3]]\n

\n\n

我可以通过转换为元组并将它们放入set.

\n\n

In [265]: set([tuple(i) for i in alist])\nOut[265]: {(1, 2, 3), (3, 4, 5)}\n

\n\n

我还可以将该列表转换为二维数组：

\n\n

In [266]: arr = np.array(alist)\nIn [267]: arr\nOut[267]: \narray([[1, 2, 3],\n       [3, 4, 5],\n       [1, 2, 3]])\n

\n\n

unique并使用轴参数获取唯一行：

\n\n

In [269]: np.unique(arr, axis=0)\nOut[269]: \narray([[1, 2, 3],\n       [3, 4, 5]])\n

\n\n

比较一下时间

\n\n

In [270]: timeit np.unique(arr, axis=0)\n46.5 \xc2\xb5s \xc2\xb1 142 ns per loop (mean \xc2\xb1 std. dev. of 7 runs, 10000 loops each)\nIn [271]: timeit set([tuple(i) for i in alist])\n1.01 \xc2\xb5s \xc2\xb1 1.7 ns per loop (mean \xc2\xb1 std. dev. of 7 runs, 1000000 loops each)\n

\n\n

将数组转换为列表或列表转换为数组会增加一些时间，但基本模式仍然存在。

\n\n

In [272]: timeit set([tuple(i) for i in arr.tolist()])\n1.53 \xc2\xb5s \xc2\xb1 13.2 ns per loop (mean \xc2\xb1 std. dev. of 7 runs, 1000000 loops each)\nIn [273]: timeit np.unique(alist, axis=0)\n53.3 \xc2\xb5s \xc2\xb1 90.3 ns per loop (mean \xc2\xb1 std. dev. of 7 runs, 10000 loops each)\n

\n\n

对于更大的、现实的源，相对时间可能会稍微改变，但我预计元组集仍然是最好的。集合运算不是numpy强项。 unique进行排序，然后消除重复项。 set使用哈希方法，类似于 Python 用于字典的方法。

\n\n

如果您必须从 a 迭代收集值source，我建议您构建一个列表，然后执行set/unique一次。

\n\n

alist = []\nfor x in source():\n    alist.append(x)\n

\n\n

或以下之一：

\n\n

alist = [x for x in source()]\nalist = list(source())\nalist = [tuple(x) for x in source()]\nalist = [tuple(x.tolist()) for x in source()]\n

\n