当涉及到一亿个元素集时,我会担心数据被逐出RAM(转到交换/页面文件)。在Python 3.5上构建的64位处理器的100M元素集(您正在使用,因为在Python的32位版本中无法创建这样的集)仅用于集开销就使用了4 GB内存(忽略其包含的对象使用的内存)。
您创建一个新集合的代码,而不需要测试第二个集合的成员身份,按顺序访问此内存,因此操作系统可以预测访问模式,并且即使大部分集合已分页,它也可能在您需要之前将数据拉入缓存中。唯一的随机访问发生在第二个集合的构建中(但方便的是,要插入的对象已经在缓存中,因为您从原始集合中获取了它们)。因此,您的随机访问内存从零增长到可能达到4 GB(加上包含对象的大小),这些内存被随机访问,
必须不被分页,否则会导致性能问题。
在您的第二种情况中,随机访问的集合在每个测试中都会被访问,并且必须加载与匹配哈希的桶碰撞链中的每个对象(尽管通过良好的哈希生成,这些匹配应该不会太多)。但是,这意味着您随机访问的内存大小从增长从0到4 GB到增长从4到多达8 GB(取决于
set
之间存在多少重叠;同样,忽略对存储对象本身的访问)。我不会感到惊讶,如果这将您从主要执行RAM访问推动到需要读取页面文件的页面故障,这比RAM访问慢几个数量级。不巧的是,那段代码执行的时间更长了几个数量级。
记录一下,集合的开销可能是存储的对象成本的一部分。在Python中最小的有用对象是
float
(在Python 3.5 x64上每个对象使用24字节),虽然由于精确相等性测试的问题,它们不适合于
set
。需要小于30位数量的
int
理论上是有用的,并且每个对象使用28字节(对于需要存储该值的完整30位,每增加30位,添加4字节)。因此,一个100M元素集可能仅使用4 GB的数据结构本身,但值本身最少是2.6 GB;如果它们不是Python内置类型,则用户定义的对象,即使使用
__slots__
,也会至少将其加倍(如果不使用
__ slots__
,则会增加五倍),而它们甚至还没有为其属性支付RAM。我有12 GB的RAM在我的机器上,您的第二种用例将在其中导致大量页面抖动,而您的第一种情况将仅适用于使用
range(100000000)
初始化的
set
(尽管它将导致大多数其他进程分页; Python与两个
set
以及它们之间共享的
int
s使用约11 GB)。
更新:您的数据(1-20个ASCII字符的字符串)将在Python 3.5 x64上每个使用50-69字节(包括分配器开销稍微多一些),或4.65-6.43 GB每个
set
(假设这
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
,这将把每个set
的开销从4 GB减少到约850 MB per list
,然后同时迭代它们(但不是同时;在这里无法使用zip
)以查找存在于第一个list
但不存在于第二个list
中的元素,这也减少了一些随机访问的成本。
O(1)
的操作仍可能需要5小时。 - Blendertemp
在那里是一个字典。 - BrenBarnO(log(N))
或更好。 - karlosssO(1)
。 - karlosss