4

我不知道如何在这两个数组之间进行相交：

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

4

10 回答 10

4

这些数据似乎最好存储为字典

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]
于 2013-08-21T16:17:56.487 回答
3 
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]])
于 2013-08-21T15:34:40.150 回答
2

假设 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]
于 2013-08-21T16:56:07.057 回答
2

如果您还希望计算列表中的重复项目，则此解决方案有效。

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]]
于 2013-08-21T15:38:48.370 回答
2

我有：

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()与您的算法相同。

于 2013-08-21T17:11:33.217 回答
2

使用计数器：

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]
于 2013-08-21T15:37:57.283 回答
2

干得好

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]]
于 2013-08-21T15:37:57.877 回答
2

首先，Python 没有数组。它有列表。只是名字的问题，但它可能会令人困惑。单线是：

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

PS：正如您所说的“交集”，我假设列表是类似集合的（实际上是“袋子”），并且作为袋子，它们被正确规范化（即它们没有重复的元素/键）。

于 2013-08-21T15:49:02.197 回答
1

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?
于 2013-08-21T17:21:37.407 回答
1

这个解决方案可能不是最快的，但它可能是最简单的实现，所以为了完整起见，我决定发布它。

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)]
于 2013-08-21T17:16:07.553 回答