大型Python集的操作

Question

更新1

两个集合都包含最大长度为20的字符串,只能从'abcdefghijklmnopqrstuvwxyz'获取值

更新2

我通过使用名为ujson的库(类似于simplejson)从磁盘读取2个文件然后将返回的列表转换为集合来构建集合.

---

我试图区分2组,每组包含1亿个元素.

此代码在2分钟内执行:

temp = set()                              #O(1)
for i in first_100_million_set:           #O(N)
    temp.add(i)                           #O(1)

此代码在6小时内执行:

temp = set()                              #O(1)
for i in first_100_million_set:           #O(N)
    if i in second_100_million_set:       #O(1)
        temp.add(i)                       #O(1)

我所做的就是添加会员资格检查,如果我没有弄错,可以在O(1)中完成吗？这种大规模减少来自哪里？

我知道set(a) - set(b),它实际上正在完成我的第二个代码块正在做的事情,也需要6个小时来完成,我只是想编写整个过程来证明我的困惑点.

您是否认为我正在努力做出更好的解决方案？

Answer 1

在谈论1亿个元素集时,我担心数据会从RAM中逐出(转到swap/pagefile).setPython 3.5上的一个100M元素是为64位处理器构建的(你正在使用它,因为你甚至无法set在32位构建的Python中创建这样的内容)使用4 GB内存仅用于set开销(忽略使用的内存)由它包含的对象).

您的代码创建一个set没有成员资格的新代码,然后set按顺序访问此内存,因此操作系统可以预测访问模式,并且可能会在您需要之前将数据拉入缓存,即使大部分内容已set被分页.唯一的随机访问发生在第二个的构建中set(但很方便,插入的对象已经在缓存中,因为你从原始中提取它们set).因此,您可以从无随机访问增长到可能随机访问的4 GB(加上包含对象的大小)内存,并且不得在不导致性能问题的情况下进行分页.

在第二种情况下,set在每次测试中随机访问正在测试的成员资格,并且它必须使用匹配的哈希加载桶冲突链中的每个对象(诚然,具有良好的哈希生成,这些匹配不应该太多) ).但这意味着随机访问内存的大小从0增长到4 GB,从4增长到8 GB(取决于sets 之间存在多少重叠;再次忽略对存储对象本身的访问) .如果这会让你从主要执行RAM访问到发生需要从页面文件读取的页面错误(这比RAM访问慢几个数量级),我不会感到惊讶.并非巧合的是,该代码的执行时间要长几个数量级.

对于记录,set开销可能只是存储对象成本的一小部分.Python中最小的有用对象是floats(Python 3.5 x64上的24个字节),但set由于完全相等测试的问题,它们对s的选择很差.int需要小于30位的s是可以想象的有用的,每块吃28个字节(为存储该值所需的每个完整的30位增加4个字节).因此,100M元素集可能"仅"使用4 GB用于数据结构本身,但这些值最少为2.6 GB左右; 如果它们不是Python内置类型,那么用户定义的对象,即使使用,在它们甚至为其属性支付RAM之前__slots__,至少会将其加倍(如果不使用则为五倍__slots__).我的机器上有12 GB的RAM,而你的第二个用例会导致大量的页面抖动,而你的第一个案例会因为set初始化而运行得很好range(100000000)(尽管这会导致大多数其他进程被分页; Python与两个sets加上int他们共享的s使用~11 GB).

更新:您的数据(1-20个ASCII字符的字符串)将在Python 3.5 x64上使用50-69个字节(可能多一点包括分配器开销),或每个4.65-6.43 GB set(假设没有共享的字符串,那是原始数据为9-13 GB).添加所set涉及的三个,并且您正在查看最多25 GB的RAM(您不会再为第三个成员付费,set因为它们与第一个共享set).我不会尝试在任何RAM少于32 GB的计算机上运行代码.

至于"有更好的解决方案吗？" 这取决于你需要什么.如果你实际上并不需要原始的sets,只有产生的差异,流式传输你的数据会有所帮助.例如:

with open(file1) as f:
    # Assume one string per line with newlines separating
    myset = set(map(str.rstrip, f))

with open(file2) as f:
    myset.difference_update(map(str.rstrip, f))

这将在大约10-11 GB的内存中达到峰值,然后随着第二个输入中的元素被删除而下降,只留下差异set而没有别的.其他选项包括使用排序list的数据,这会将开销从每个4 GB减少到每个set850 MB list,然后并行迭代它们(但不是同时; zip这里不好),以找到第一个list但存在的元素不是第二个,也删除了一些随机访问费用.