在大型Python集合上的操作

Question

更新 1

两个集合中的字符串长度最长为20，且只能取值于“abcdefghijklmnopqrstuvwxyz”。

更新 2

我使用称为ujson（类似于simplejson）的库从磁盘读取了2个文件，并将返回的列表转换为集合来构造这些集合。

---

我试图计算包含每个100百万元素的2个集合之间的差异。

此代码执行时间为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 小时才能完成，我只是想写出整个过程以证明我的困惑点。

你认为有更好的解决方案来完成我所尝试的工作吗？

- RetroCode

---

一个O(1)的操作仍可能需要5小时。 - Blender

你展示的代码是无效的，因为temp在那里是一个字典。 - BrenBarn

@vyscond 不是的。集合的时间复杂度总是 O(log(N)) 或更好。 - karlosss

集合中的对象是什么？ - BrenBarn

@ayhan 这意味着Python集合只能包含可哈希元素，这是与C++的区别。因此，时间复杂度为 O(1)。 - karlosss

Answer 1

当涉及到一亿个元素集时，我会担心数据被逐出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以及它们之间共享的ints使用约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中的元素，这也减少了一些随机访问的成本。

- ShadowRanger

Answer 2

检查元素是否在集合中似乎是O(1)，请参见下面的代码。 集合必须使用哈希函数进行内部制作。 哈希表的成功率取决于您使用的键以及Python猜测您的方式。 对于集合，使用range(n)类似于理想情况。

import time
def foo(n):
  myset = set(range(n))
  to = time.time()
    for e in myset:     #O(n)
      if e in myset:    #O(n) or O(1)?
        pass
      else:
        raise "Error!"
  print time.time() - to
  return

>>> foo(10**6)
0.0479998588562
>>> foo(10**7)
0.476000070572

因此，函数foo在O(n)中执行，并且检查元素是否在集合中仅使用了O(1)。

- Bastiaan