我不知道如何使这两个数组相交:
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
所以我试图找到一种更有效的方法来解决我的问题,在某种程度上更像蟒蛇。所以这就是为什么我需要你的帮助。
试试这个测试用例(我的代码也在上面):
测试用例
运行时间:28.6980509758
这些数据似乎最好作为字典存储
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]
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]])
使用计数器:
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]
开始
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]]
如果您还希望对列表中的重复项进行计数,则此解决方案有效。
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]]
首先,Python并没有数组。它有列表。只是名字的问题,但可能会让人困惑。其中一条是:
[ [ae[0],ae[1]+be[1]] for be in b for ae in a if be[0] == ae[0] ]
PS:正如你所说的"交集",我假设列表设置为(实际上是"袋子"),并且作为袋子,它们被适当地规范化了(即它们没有重复的元素/键)。
以下是我如何处理它,假设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]
我得到了:
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()
相同的结果。
这个解决方案可能不是最快的,但它可能是最简单的实现,所以为了完整性,我决定发布它。
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)]
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?