我可以在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

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

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

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

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

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