比较两个数组的相同元素并将其从两个数组中删除

Question

假设我有两个NumPy数组，它们的元素如下所示：

arr1 = [[1, 2], [3, 5], [3, 4]]
arr2 = [[2, 3], [3, 4], [6, 6]]

我希望得到的数组将arr2附加或水平堆叠到arr1中，其中包含两个数组中都不存在的元素：

arr3 = [[1, 2], [3, 5], [2, 3], [6, 6]]

正如您所看到的，期望的结果数组中并没有[3, 4]。对于这个问题，最佳的numpy和python实现是什么？

- hulkinBrain

Answer 1

我有点晚了，但这里有一种方法可以在中等算法成本的情况下利用numpy的速度：O(n log n)。事实证明，对于许多输入数组的大小，运行时间由类型转换的成本主导。请参见以下基准测试：

from timeit import timeit
import numpy as np

def make_inputs(N, ncol):
    global arr1, arr2, list1, list2, lot1, lot2
    # create making sure there are no duplicates *within* arr1 or arr2
    all_ = np.array(list(set(map(tuple, np.random.randint(0, 2 * N, (N + N//2, ncol))))))
    # create input of various data types
    arr1 = all_[np.random.choice(len(all_), N, False)]
    arr2 = all_[np.random.choice(len(all_), N, False)]
    list1 = arr1.tolist()
    list2 = arr2.tolist()
    lot1 = list(map(tuple, list1))
    lot2 = list(map(tuple, list2))

def np_unique_preserve_order(a, b):
    c = np.r_[a, b]
    cr = c.view(np.dtype("|S" + str(c.shape[-1] * c.dtype.itemsize)))
    uniq, inv, count = np.unique(cr.ravel(), return_inverse=True,
                                 return_counts=True)
    return c[(count==1)[inv], :]

def np_unique(a, b):
    c = np.r_[a, b]
    cr = c.view(np.dtype("|S" + str(c.shape[-1] * c.dtype.itemsize)))
    uniq, count = np.unique(cr.ravel(), return_counts=True)
    return uniq[count==1, None].view(c.dtype)

def np_sort(a, b):
    c = np.r_[a, b]
    cr = np.sort(c.view(np.dtype("|S" + str(c.shape[-1] * c.dtype.itemsize))).ravel())
    m = np.empty(cr.shape, bool)
    m[0] = True
    m[1:] = cr[:-1] != cr[1:]
    m[:-1] &= m[1:]
    return cr[m, None].view(c.dtype)

# check
make_inputs(1000, 2)
assert set(map(tuple, lot1)).symmetric_difference(set(map(tuple, lot2))) == set(map(tuple, np_sort(arr1, arr2)))
assert set(map(tuple, lot1)).symmetric_difference(set(map(tuple, lot2))) == set(map(tuple, np_unique(arr1, arr2)))
assert set(map(tuple, lot1)).symmetric_difference(set(map(tuple, lot2))) == set(map(tuple, np_unique_preserve_order(arr1, arr2)))


for N, ncol in ((10, 2), (10000, 2), (100000, 20)):
    make_inputs(N, ncol)
    results = []
    for inputs in 'lot', 'list', 'arr':
        res = []
        if inputs == 'lot':
            res.append('{:11.5f} ms'.format(timeit(f'list(set({inputs}1).symmetric_difference(set({inputs}2)))',
                 f'from __main__ import {inputs}1, {inputs}2', number=10) * 100))
        else:
            res.append('{:11.5f} ms'.format(timeit(f'list(set(map(tuple, {inputs}1)).symmetric_difference(set(map(tuple, {inputs}2))))',
                 f'from __main__ import {inputs}1, {inputs}2', number=10) * 100))

        res.append('{:11.5f} ms'.format(timeit(f'np_sort({inputs}1, {inputs}2)', f'from __main__ import {inputs}1, {inputs}2, np_sort',
                 number=10) * 100))
        res.append('{:11.5f} ms'.format(timeit(f'np_unique({inputs}1, {inputs}2)', f'from __main__ import {inputs}1, {inputs}2, np_unique',
                 number=10) * 100))
        res.append('{:11.5f} ms'.format(timeit(f'np_unique_preserve_order({inputs}1, {inputs}2)', f'from __main__ import {inputs}1, {inputs}2, np_unique_preserve_order',
                 number=10) * 100))
        results.append(res)
    results = zip(*results)
    appmin = lambda l: l + (min(l),)
    print(f'\nno rows {N}, no colums {ncol}')
    print('input type                           lot           list          array           best')
    print(f'symm_diff                ', *appmin(next(results)))
    print(f'np_sort                  ', *appmin(next(results)))
    print(f'np_unique                ', *appmin(next(results)))
    print(f'np_unique_preserve_order ', *appmin(next(results)))

输出：

no rows 10, no colums 2
input type                           lot           list          array           best
symm_diff                     0.00232 ms     0.00453 ms     0.02034 ms     0.00232 ms
np_sort                       0.03890 ms     0.03269 ms     0.03060 ms     0.03060 ms
np_unique                     0.04209 ms     0.04118 ms     0.04136 ms     0.04118 ms
np_unique_preserve_order      0.05289 ms     0.05253 ms     0.05253 ms     0.05253 ms

no rows 10000, no colums 2
input type                           lot           list          array           best
symm_diff                     3.71800 ms     8.30081 ms    21.92841 ms     3.71800 ms
np_sort                       7.98128 ms     8.09973 ms     2.80091 ms     2.80091 ms
np_unique                     8.49229 ms     8.25701 ms     3.00654 ms     3.00654 ms
np_unique_preserve_order     10.12377 ms     8.67133 ms     3.36172 ms     3.36172 ms

no rows 100000, no colums 20
input type                           lot           list          array           best
symm_diff                    97.83141 ms   211.20736 ms   590.15145 ms    97.83141 ms
np_sort                     317.73268 ms   316.50081 ms    89.97820 ms    89.97820 ms
np_unique                   324.68922 ms   326.89891 ms    98.06377 ms    98.06377 ms
np_unique_preserve_order    339.18597 ms   339.00286 ms   120.94041 ms   120.94041 ms

对于非常小的数组，使用symm_diff 是最快的，但对于较大的数组，当所有方法都可以使用它们最擅长的数据类型时，np_sort 稍微占优。

- Paul Panzer

---

这是一个非常全面的解决方案！感谢您！您有我的支持。 - hulkinBrain

Answer 2

arr_3 = list(set(arr_1).symmetric_difference(set(arr_2)))

或者：

arr_3 = list(set(map(tuple, arr_1))
    .symmetric_difference(set(map(tuple, arr_2))))

一些研究:

from random import randint
from timeit import timeit

import itertools

arr1 = [[randint(0, 5), randint(0, 5)] for _ in range(1000)]
arr2 = [[randint(0, 5), randint(0, 5)] for _ in range(1000)]


def symmetric_difference(a, b):
    now_exists = set()
    results = []
    for e in itertools.chain(a, b):
        rerp_of_e = repr(e)
        if rerp_of_e not in now_exists:
            now_exists.add(rerp_of_e)
            results.append(e)

    return results


def method2(a, b):
    c = a + b
    return [l for l in c if c.count(l) == 1]


print(timeit('[l for l in arr1 + arr2 if (arr1 + arr2).count(l) == 1]', 'from __main__ import arr1, arr2',
             number=10) / 10)

print(timeit('method2(arr1, arr2)', 'from __main__ import arr1, arr2, method2',
             number=10) / 10)

print(timeit('list(set(map(tuple, arr1)).symmetric_difference(set(map(tuple, arr2))))',
             'from __main__ import arr1, arr2', number=10) / 10)

print(timeit('symmetric_difference(arr1, arr2)', 'from __main__ import arr1, arr2, symmetric_difference',
             number=10) / 10)

输出：

0.16653713929933542
0.14676828165012284
0.00030277483018301685
0.0008909022958581315

- ADR

---

它可以转换为“元组”。但是，是的，应该有更好的方法来做这件事。 - ADR

哇！这是最快的方法！我尝试了大型二维数组。对于具有大尺寸的数组，对称方法确实非常好。你提出的第二种方法执行时间最短！当数组大小为10000时，执行时间分别为2.14437940844、0.0020706277306、0.0064447811589。第一种方法和第二种方法之间存在巨大差异。请问你能否解释一下它在做什么？ - hulkinBrain

第三个打印语句中使用的方法具有最短的执行时间，我想要解释一下那个方法。就是使用 map 的那个方法。 - hulkinBrain

非常抱歉这么久才完成翻译，需要一些时间。 - ADR

@hulkinBrain - 如果您不考虑代码的可读性和/或优雅度，那么这种方法可能会更好。但是，如果有人需要与此代码一起工作，或者如果您将来要回到它并尝试理解自己所做的事情，我强烈建议您采用我的解决方案（如果您不想接受也可以...）。 - Binyamin Even

Answer 3

如何呢：

[l for l in arr1+arr2 if (arr1+arr2).count(l)==1]

输出：

[[1, 2], [3, 5], [2, 3], [6, 6]]

或者，如果您希望更加高效：

c=arr1+arr2
[l for l in c if c.count(l)==1]

- Binyamin Even

---

@ADR 根据您的评论，我建议使用更高效的代码 :) - Binyamin Even

是的，当然没问题！我也点赞了 :D 我正在检查执行所需的时间。它很快！平均所需时间为 0.0009s。 - hulkinBrain

事实上，这个解决方案在大型列表上速度较慢。但是它很好和干净。如果您有一个短列表，一切都没问题。 - ADR

是的，这是一个适用于小型列表的好的、干净的“易于阅读”的方法。@ADR，你建议的方法具有最少的执行时间！这很尴尬，我感到很尴尬！但我确实要求最佳的numpythonic方法，所以我必须相应地接受答案。 - hulkinBrain

一个主要的优点是你的代码非常优雅。但对于大数组，ADR的方法执行时间较短。我希望我能接受你们两个的答案！但由于你的易读性更好，我会接受你的。 - hulkinBrain

Answer 4

如果只有相同索引的项目可以相似，您可以使用以下简单的NumPy方法：

In [10]: mask = ~(arr1 == arr2).all(1)

In [11]: np.vstack((arr1[mask], arr2[mask]))
Out[11]: 
array([[1, 2],
       [3, 5],
       [2, 3],
       [6, 6]])

否则，您可以基于Jaime的答案找到相交点，然后将它们从组合数组中排除。

或者使用以下方法：

In [17]: arr1_view = arr1.view([('', arr1.dtype)] * arr1.shape[1])

In [18]: arr2_view = arr2.view([('', arr2.dtype)] * arr2.shape[1])

In [19]: diff_arr1 = np.setdiff1d(arr1_view, arr2_view).view(arr1.dtype).reshape(-1, arr1.shape[1])

In [20]: diff_arr2 = np.setdiff1d(arr2_view, arr1_view).view(arr2.dtype).reshape(-1, arr2.shape[1])

In [21]: np.vstack((diff_arr1, diff_arr2))
Out[21]: 
array([[1, 2],
       [3, 5],
       [2, 3],
       [6, 6]])

如果你正在处理 python 数组，特别是短数组的话，可以使用列表推导式，像下面这样：

In [204]: [i for i in arr1 + arr2 if not (i in arr1 and i in arr2)]
Out[204]: [[1, 2], [3, 5], [2, 3], [6, 6]]

请注意，对于短数组而言，它比将列表转换为元组并使用集合更快；但对于较大的数组，基于集合的方法更胜一筹，在这种情况下最好使用Numpy：

In [209]: %timeit set(map(tuple, arr1)).symmetric_difference(map(tuple, arr2))
100000 loops, best of 3: 1.51 µs per loop

In [210]: %timeit [i for i in arr1 + arr2 if not (i in arr1 and i in arr2)]
1000000 loops, best of 3: 1.28 µs per loop

- Mazdak

---

不，它们可以出现在任何位置。感谢您指出问题中的歧义！我现在会进行编辑。 - hulkinBrain

是的，Jaime的答案采用了我自己尝试使用numpy.intersect1d实现的类似方法。没想到还有一个类似的问题存在！谢谢。 - hulkinBrain

你的方法相对于ADR的方法需要花费更多时间。很高兴知道有不止一种方法可以解决我的问题！谢谢 :D - hulkinBrain

@hulkinBrain 这是因为你的数组太小了。尝试使用大数组进行基准测试，看看Numpy有多快。在这种情况下根本无法比较。但如果你处理的是像这样的短数组，最好只用Python。 - Mazdak

@hulkinBrain 终究，检查一下Pythonic方法的更新。 - Mazdak