Python数组交集高效实现

Question

我不知道如何让这两个数组相交：

a = [[125, 1], [193, 1], [288, 23]]
b = [[108, 1], [288, 1], [193, 11]]

result = [[288,24], [193, 12]]

那么交集是由数组的第一个元素确定的，第二个元素被求和，有什么高效的方法吗？

好的，我犯了一个错误，没有解释我所说的“高效”，对不起。考虑以下朴素实现：

a = [[125, 1], [193, 1], [288, 23]]
b = [[108, 1], [288, 1], [193, 11]]
result = {}
for i, j in a:
    for k, l in b:
        if i == k:
            result[i] = j + l
print result

我试图寻找一种更加高效的解决方案来解决我的问题，并以更Pythonic的方式来实现。这就是为什么我需要你的帮助。

请尝试以下测试用例（我的代码也在其中）：

测试用例

运行时间：28.6980509758

- badc0re

---

如果a中有两个匹配元素，行为应该是什么？它们也应该被相加吗？例如，a = [[100, 1], [100, 2]]，b = [[50, 1]]。 - Brionius

我不确定是否应该将这些数据保存为列表的列表。也许使用字典或更好的计数器会更合适。 - cmd

如果你认真使用词语“高效”，你尝试了哪些替代方案？为什么它们的性能不足？另外，非常重要的是，数据集的大小是多少？ - Mario Rossi

@badc0re，我们似乎在使用表达性（易于编写、测试和理解）语言特性与效率（也非常重要）之间存在争议。为什么不在这个特定的案例中帮助我们解决这个问题？您能够运行和计时不同答案的测试并发布结果吗？ - Mario Rossi

@badc0re 你的期望是什么？为什么29秒不好？这非常重要。大多数有经验的开发人员会逐步提高性能（并减少可读性）直到性能可以接受，但不再提高一点点。他们重视自己的时间和可能遇到他们代码的其他开发人员的时间。 - Mario Rossi

Answer 1

这些数据似乎更适合以字典形式存储。

da = dict(a)
db = dict(b)

一旦你完成了这样的设置，你只需要：

result = [[k, da[k] + db[k]] for k in set(da.keys()).intersection(db.keys())]

在Python 2.7中，您还可以直接使用viewkeys而不是集合。

result = [[k, da[k] + db[k]] for k in da.viewkeys() & db]

- cmd

---

我没有给你的解决方案点踩，它目前的性能最佳，计算时间为0.0124080181122。 - badc0re

不错！具有 Python 风格和高效性。 - FUD

Answer 2

result = []
ms, mb = (dict(a),dict(b)) if len(a)<len(b) else (dict(b),dict(a))
for k in ms:
  if k in mb:
    result.append([k,ms[k]+mb[k]])

- FUD

---

抱歉，我意识到在最后一个语句中漏掉了方括号。 - FUD

还添加了一些不错的优化，以防您有一个数组非常小的数据，仅供参考。 - FUD

在我的笔记本上，0.0067秒的速度相当快，而且结果经过验证与原始数据匹配。我认为它也很易读。干得好！ - Kirk Strauser

Answer 3

使用计数器：

c_sum = Counter()
c_len = Counter()
for elt in a:
    c_sum[elt[0]] += elt[1]
    c_len[elt[0]] += 1

for elt in b:
    c_sum[elt[0]] += elt[1]
    c_len[elt[0]] += 1

print [[k, c_sum[k]] for k, v in c_len.iteritems() if v > 1]

- guyrt

Answer 4

这是你需要的内容

a = [[125, 1], [193, 1], [288, 23]]
b = [[108, 1], [288, 1], [193, 11]]
for e in a:
    for e2 in b:
        if e[0] == e2[0]:
            inter.append([e[0], e[1]+e2[1]])
print inter

输出

[[193, 12], [288, 24]]

- mavili

---

也许你在问题中漏掉了“高效”的词？我认为O(n^2)的算法不符合要求。 - Mark Ransom

我认为楼主只是出于习惯或者无知而使用了“高效”的词汇。如果他真的有这个意思，他应该指定列表的大小、一般时间限制、尝试过的其他解决方案及其计时信息，甚至是为什么要使用Python而不是其他语言。 - Mario Rossi

很可能OP并不太关心解决方案的时间复杂度。因为他们没有展示任何改进基本解决方案的尝试，而只是针对问题提出了一个一般性的问题。 - mavili

Answer 5

如果您还想计算列表中的重复项，则此解决方案可行。

from collections import defaultdict

a = [[125, 1], [193, 1], [288, 23]]
b = [[108, 1], [288, 1], [193, 11]]

d = defaultdict(int)

for value, num in a+b:
    d[value] += num
result = filter(lambda x:x[1]>1, d.items())
result = map(list, result)  # If it's important that the result be a list of lists rather than a list of tuples
print result
# [[288, 24], [193, 12]]

- Brionius

Answer 6

首先，Python没有数组。它有列表。只是名称上的区别，但可能会令人困惑。这个问题的一句话解决方法是:

[ [ae[0],ae[1]+be[1]] for be in b for ae in a if be[0] == ae[0] ]

PS：根据你所说的“交集”，我假设这些列表是集合（实际上是“袋子”），并且作为袋子，它们已经被正确地规范化了（即它们没有重复的元素/键）。

- Mario Rossi

---

一行代码被高估了，这特别低效。 - FUD

当你理解它们时，它们有重要的地位。如果你非常担心性能问题，那么为什么还要用Python进行开发呢？与其他语言相比，它的主要优势在于表达能力，而不是性能。请不要贬低语言的重要部分，阻止人们了解它。让他们自己得出结论。在这种情况下，我认为性能差异不大。你计时过吗？ - Mario Rossi

这并没有回答OP提出的问题。这不是高效的。反对语言本身并不能减轻你的解决方案是一个低效的算法的事实。 - cmd

效率是相对于问题而言的。如果你认为“表达能力强但不如其他语言高效”是反对Python的理由，那么你是正确的。对我来说，前者是Python的优点，后者只是一个事实陈述。 - Mario Rossi

我同意对于小数据集，你的解决方案很好且表达清晰。然而，OP多次提到需要一个高效的算法，这让我认为这些列表可能非常大。你的算法的时间复杂度是n*m，还有更好的方法可以保持表达清晰。此外，我不同意“只因为某人在使用Python编码，就意味着他们不关心性能”的说法。 - cmd

Answer 7

假设a和b是唯一的，以下是我处理它的方法：

k = {} # store totals
its = {} # store intersections
for i in a + b:
    if i[0] in k:
        its[i[0]] = True
        k[i[0]] += i[1]
    else:
        k[i[0]] = i[1]
# then loop through intersections for results
result = [[i, k[i]] for i in its]

- Faisal

---

还有很棒的表现（0.0174601078033），但我不理解其[i[0]] = True这部分。 - badc0re

当第二次按下键/ID时，表示它们相交了，然后我们将其存储起来，而不是再进行另一个循环来查找是否相交。 - Faisal

Answer 8

I got:

from collections import defaultdict
d = defaultdict(list)
for series in a, b:
    for key, value in series:
        d[key].append(value)
result2 = [(key, sum(values)) for key, values in d.iteritems() if len(values) > 1]

该算法的时间复杂度为O(len(a)+len(b))，在我的笔记本上大约只需要0.02秒，而在你的电脑上需要18.79秒。我还确认它返回了与你的算法中result.items()相同的结果。

- Kirk Strauser

Answer 9

这个解决方案可能不是最快的，但很可能是最简单的实现方式，所以我决定发布它，以便完整性。

aa = Counter(dict(a))
bb = Counter(dict(b))
cc = aa + bb
cc
=> Counter({288: 24, 193: 12, 108: 1, 125: 1})

list(cc.items())
=> [(288, 24), (193, 12), (108, 1), (125, 1)]

如果您只需要包含常见键：

[ (k, cc[k]) for k in set(aa).intersection(bb) ]
=> [(288, 24), (193, 12)]

- shx2

Answer 10

numpy中的serachsorted()、argsort()和intersect1d()都是可能的替代方案，并且速度相当快。这个例子也应该解决了第一个元素不唯一的问题。

>>> import numpy as np
>>> a=np.array([[125, 1], [193, 1], [288, 23]])
>>> b=np.array([[108, 1], [288, 1], [193, 11]])
>>> aT=a.T
>>> bT=b.T
>>> aS=aT[0][np.argsort(aT[0])]
>>> bS=bT[0][np.argsort(bT[0])]
>>> i=np.intersect1d(aT[0], bT[0])
>>> cT=np.hstack((aT[:,np.searchsorted(aS, i)], bT[:,np.searchsorted(bS, i)]))
>>> [[item,np.sum(cT[1,np.argwhere(cT[0]==item).flatten()])] for item in i]
[[193, 12], [288, 24]] #not quite happy about this, can someone comes up with a vectorized way of doing it?

- CT Zhu

---

性能将取决于 a 和 b 数组的维度，请参阅此帖子：https://dev59.com/lXA65IYBdhLWcg3wvxeE - CT Zhu