gpt4 book ai didi

python - 查找按原点分隔的 2 个集合的对称差异

转载 作者:行者123 更新时间:2023-12-01 04:57:04 24 4
gpt4 key购买 nike

我有两套:

>>> a = {1,2,3}
>>> b = {2,3,4,5,6}

我想获得两个包含公共(public)元素的新集合,第一个集合包含来自a的元素,第二个集合包含来自的元素b,如 ({1}, {4,5,6}),或类似:

>>> c = a&b # Common elements
>>> d = a^b # Symmetric difference
>>> (a-b, b-a)
({1}, {4, 5, 6})
>>> (a-c, b-c)
({1}, {4, 5, 6})
>>> (a&d, b&d)
({1}, {4, 5, 6})

我的问题是,我将在大量 sha1 哈希上使用它,并且我担心性能。 有效地做到这一点的正确方法是什么

注意:ab 大约有 95% 的元素是相同的,1% 位于 a 中,4% 位于b.

最佳答案

我在问题中提到的方法具有以下性能:

>>> timeit.timeit('a-b; b-a', 'a=set(range(0,1500000)); b=set(range(1000000, 2000000))', number=1000)
135.45828826893307
>>> timeit.timeit('c=a&b; a-c; b-c', 'a=set(range(0,1500000)); b=set(range(1000000, 2000000))', number=1000)
189.98522938665735
>>> timeit.timeit('d=a^b; a&d; b&d', 'a=set(range(0,1500000)); b=set(range(1000000, 2000000))', number=1000)
238.35084129583106

所以最有效的方法似乎是使用 (a-b, b-a) 方法。

我将其发布作为引用,以便其他答案可以添加新方法,而不是比较我找到的方法。

<小时/>

Python实现的函数

出于好奇,我尝试实现自己的 python 函数来执行此操作(适用于预排序的迭代器):

def symmetric_diff(l1,l2):
# l1 and l2 has to be sorted and contain comparable elements
r1 = []
r2 = []
i1 = iter(l1)
i2 = iter(l2)

try:
e1 = next(i1)
except StopIteration: return ([], list(i2))
try:
e2 = next(i2)
except StopIteration: return ([e1] + list(i1), [])

try:
while True:
if e1 == e2:
e1 = next(i1)
e2 = next(i2)
elif e1 > e2:
r2.append(e2)
e2 = next(i2)
else:
r1.append(e1)
e1 = next(i1)

except StopIteration:
if e1==e2:
return (r1+list(i1), r2+list(i2))
elif e1 > e2:
return (r1+[e1]+list(i1), r2+list(i2))
else:
return (r1+list(i1), r2+[e2]+list(i2))

与其他方法相比,该方法的性能相当低:

t = timeit.Timer(lambda: symmetric_diff(a,b))
>>> t.timeit(1000)
542.3225249653769

因此,除非在某处实现了其他方法(某些用于处理集合的库),否则我认为使用两个集合差异执行此操作的最有效方法。

关于python - 查找按原点分隔的 2 个集合的对称差异,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/27154836/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com