我可以对 python 中的列表执行减法或加入操作，包括重复条目

Question

我有两个或更多大列表（每个列表包含 20 到 25 GB 数据）。我想执行减号并加入 operations.For 示例我想找出列表 1 中存在但列表 2 中不存在的项目以下列表。

    list1=[1,2,1,3,4,4,5,6,2,8]
    list2=[3,5,3,8,1,9,9]

结果应该是：

    result_list1minuslist2 =[1,2,2,4,4,6]
    result_list2minuslist1 =[3,9,9]

加入操作：

    result_list1joinlist2 =[1,1,3,5,8]
    result_list2joinlist1 =[3,5,3,8,1]

Answer 1

对于列表减法，您可以尝试使用包含列表的字典对源列表中的值进行分组，并提供快速查找操作。假设列表中的项目是可哈希的，因此可以用作字典键。

这可能是合理的内存效率，因为对象引用应该在数据结构中使用，所以原始列表中的数据重复应该最小化。但是，如果原始列表包含许多小对象，那么在构建数据结构的开销中仍然会消耗大量内存。取决于你的数据。

我建议使用 defaultdict 列表，因为很容易将原始列表中的值分组，但您也可以使用标准字典。

因此，将要减去的列表转换为 defaultdict 个列表。原始列表中的每一项都是此字典中的一个键，对应的值是包含相同键的列表，原始列表中每个条目一个条目。

然后遍历第二个列表，从字典的值中删除条目（如果存在）。这个位应该比直接在列表上操作更快，因为在字典上的 in 操作平均是 O(1)，而在列表上的 in 操作是 O(N)。

from collections import defaultdict

def list_sub(list1, list2):
    '''Subtract list2 from list1'''    
    dd = defaultdict(list)
    for i in list1:
        dd[i].append(i)

    # now remove items in list2 from the defaultdict
    for i in list2:
        if dd[i]:
            dd[i].pop()

    return (x for v in dd.itervalues() for x in v)


list1=[1,2,1,3,4,4,5,6,2,8]
list2=[3,5,3,8,1,9,9]

>>> list_sub(list1, list2)
[1, 2, 2, 4, 4, 6]
>>> list_sub(list2, list1)
[3, 9, 9]

备选方案

使用一个 defaultdict 的整数作为计数器：

from collections import defaultdict

def list_sub_ddi(list1, list2):
    dd = defaultdict(int)
    for i in list1:
        dd[i] += 1

    for i in list2:
        dd[i] -= 1

    return (x for l in ([k]*n for k,n in dd.iteritems() if n>0) for x in l)

使用 collections.Counter:

from collections import Counter

def list_sub_counter(list1, list2):
    c = Counter(list1) - Counter(list2)
    return (x for l in ([k]*n for k,n in c.iteritems() if n>0) for x in l)

执行次数

使用timeit模块：

# test.py
from random import randint
from collections import defaultdict
from collections import Counter

list1 = [randint(1, 10000) for i in range(1000000)]
list2 = [randint(1, 5000) for i in range(10000)]

def list_sub_ddl(list1, list2):
    dd = defaultdict(list)
    for i in list1:
        dd[i].append(i)

    for i in list2:
        if dd[i]:
            dd[i].pop()

    return (x for v in dd.itervalues() for x in v)

def list_sub_ddi(list1, list2):
    dd = defaultdict(int)
    for i in list1:
        dd[i] += 1

    for i in list2:
        dd[i] -= 1

    return (x for l in ([k]*n for k,n in dd.iteritems() if n>0) for x in l)

def list_sub_counter(list1, list2):
    c = Counter(list1) - Counter(list2)
    return (x for l in ([k]*n for k,n in c.iteritems() if n>0) for x in l)

请注意，每个函数 return 都是一个生成器，它最大限度地减少了预先完成的工作量，并允许调用代码迭代值或根据需要转换为列表。如果愿意，每个函数都可以 return 一个完全实现的列表。下面的测试一次性消耗了生成器中的所有项目。

Python 2

$ python -m timeit -s 'import test' 'list(test.list_sub_ddl(test.list1, test.list2))'
10 loops, best of 3: 362 msec per loop

$ python -m timeit -s 'import test' 'list(test.list_sub_ddi(test.list1, test.list2))'
10 loops, best of 3: 223 msec per loop

$ python -m timeit -s 'import test' 'list(test.list_sub_counter(test.list1, test.list2))'
10 loops, best of 3: 476 msec per loop

Python 3

代码与Python2相同，但itervalues()和iteritems()改为values()和items()。

$ python3 -m timeit -s 'import test' 'list(test.list_sub_ddl(test.list1, test.list2))'
10 loops, best of 3: 386 msec per loop

$ python3 -m timeit -s 'import test' 'list(test.list_sub_ddi(test.list1, test.list2))'
10 loops, best of 3: 267 msec per loop

$ python3 -m timeit -s 'import test' 'list(test.list_sub_counter(test.list1, test.list2))'
10 loops, best of 3: 214 msec per loop

结果

如果您使用 Python 2，请使用 defaultdict 整数。对于 Python 3 使用 Counter.

您的里程会有所不同，具体取决于使用的实际数据。此测试数据远小于 20GB，包含小对象的长列表可能与包含较大对象的较短列表的行为不同。

此测试还忽略了每种方法在内存使用方面的差异，因为我不知道有什么简单的方法可以测量它，而且我的测试数据可能不具有代表性。不过，列表的 defaultdict 可能会消耗更多。

Answer 2

这里有一些有趣的 pythonic 版本，用于减号：

from heapq import heapify, heappop

def sort_gen(l, StopException=StopIteration):
    heapify(l)
    for i in xrange(len(l)):
        yield heappop(l)
    raise StopException

class YStopIteration(StopIteration):
    pass

def diff_gen(l1, l2):
    xgen = sort_gen(l1)
    ygen = sort_gen(l2, YStopIteration)

    try:
        x = next(xgen)
        y = next(ygen)
        while True:
            if x < y:
                yield x
                x = next(xgen)
            elif x == y:
                x = next(xgen)
                y = next(ygen)
            else:
                y = next(ygen)
    except YStopIteration:
        # 2nd generator exhausted: yield all the rest
        yield x
        for x in xgen:
            yield x


list1=[1,2,1,3,4,4,5,6,2,8]
list2=[3,5,3,8,1,9,9] 

dg = diff_gen(list1, list2)

d = list(dg)  # [1, 2, 2, 4, 4, 6]

Answer 3

在 python 中，多重集以 counter 的形式提供，因为您有多个相同的可哈希且因此不可变对象的实例，您应该考虑使用它。

这里是减号和加入列表

def list_sub(list1, list2):
    result = Counter(list1)
    result.subtract(list2)
    return result.elements()

def list_join(list1,list2):
    test = set(list2)
    return filter(lambda x: x in test,list1)  
    #return (x for x in list1 if x in test)

两者都是 return 结果的迭代器，在 python 中具有相同的效果 2 使用 itertools.ifilter 或生成器表达式

>>> list(list_sub(list1,list2))
[1, 2, 2, 4, 4, 6]
>>> list(list_sub(list2,list1))
[3, 9, 9]
>>> list(list_join(list1,list2))
[1, 1, 3, 5, 8]
>>> list(list_join(list2,list1))
[3, 5, 3, 8, 1]
>>>

现在将此版本与@mhawke 版本进行比较（使用与 mhawke 相同的脚本）

在python3

>python3 -m timeit -s 'import test' 'list(test.list_sub_counter(test.list1, test.list2))'
10 loops, best of 3: 274 msec per loop

>python3 -m timeit -s 'import test' 'list(test.list_sub(test.list1, test.list2))'
10 loops, best of 3: 199 msec per loop

在python2

>python2 -m timeit -s 'import test' 'list(test.list_sub_counter(test.list1, test.list2))'
10 loops, best of 3: 627 msec per loop

>python2 -m timeit -s 'import test' 'list(test.list_sub(test.list1, test.list2))'
10 loops, best of 3: 558 msec per loop

在这两种情况下，这个版本都更好，除了我在 defaultdict 和 Counter 中得到相同的结果，所以使用 [= python2 中的 14=] 或 python3

中的 Counter

我可以对 python 中的列表执行减法或加入操作，包括重复条目

Can I perform minus or join operations on lists in python including duplicate entries

python

join

list

set

left-join

备选方案

执行次数

结果