我可以在python中对包含重复条目的列表执行减号或联接操作吗

Question

我有两个或两个以上的大列表（每个列表包含20到25gb的数据）操作。用于示例我想找出列表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

在python中，multiset是以counter的形式提供的，因为您有同一个hashable对象的多个实例，因此您应该考虑使用它。你知道吗

这里是减号和联接列表

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)

两者都返回对结果的迭代器，在python2中使用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中使用defaultdict(int)，在python3中使用Counter

Answer 2

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

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

我建议使用^{}列表，因为很容易将原始列表中的值分组，但也可以使用标准字典。你知道吗

从列表中减去。原始列表中的每一项都是此词典中的一个键，相应的值是一个包含相同键的列表，原始列表中的每一项都有一个条目。你知道吗

然后遍历第二个列表，从字典的值中删除条目（如果存在）。这个位应该比直接在列表上操作快，因为字典上的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]

替代品

使用int的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)

使用^{}：

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)

执行次数

使用^{}模块：

# 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)

请注意，每个函数都返回一个生成器，该生成器使预先完成的工作量最小化，并允许调用代码对值进行迭代或根据需要转换为列表。如果愿意，每个函数都可以返回一个完全实现的列表。下面的测试一次性消耗了生成器中的所有项目。你知道吗

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

结果

如果您使用的是python2，请使用int的defaultdict。对于python3，使用Counter。你知道吗

根据实际使用的数据，您的里程数会有所不同。这个测试数据比20GB小得多，小对象的长列表的行为可能不同于大对象的短列表。你知道吗

这个测试还忽略了每个方法在内存使用上的差异，因为我不知道一个简单的方法来测量它，而且我的测试数据可能不具有代表性。不过，列表的defaultdict可能会消耗更多。你知道吗

Answer 3

下面是一些有趣的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]