python - 对大型 Python 集的操作

Question

更新 1

两个集合都包含最大长度为 20 的字符串，并且只能从“abcdefghijklmnopqrstuvwxyz”中获取值

更新 2

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

我试图取 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 中驱逐(进入交换/页面文件)。一个 100M 元素 set在为 64 位处理器构建的 Python 3.5 上(您正在使用，因为您甚至无法在 Python 的 32 位构建中创建这样的 set)使用 4 GB 内存仅用于 set开销(忽略它包含的对象使用的内存)。

您创建新 set 的代码没有成员(member)资格测试第二个 set顺序访问此内存，因此操作系统可以预测访问模式，并且即使大多数 set 也很可能在您需要之前将数据拉入缓存中。被调出。唯一的随机访问发生在二楼set (但方便的是，被插入的对象已经在缓存中，因为您从原始 set 中提取了它们)。因此，您从没有随机访问增长到可能是 4 GB(加上包含对象的大小)的内存，这些内存被随机访问，并且不能在没有导致性能问题的情况下被调出。

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

郑重声明，set开销可能只是存储对象成本的一小部分。 Python 中最小的有用对象是 float s(在 Python 3.5 x64 上每段 24 字节)，尽管它们对于 set 来说是糟糕的选择由于精确相等测试的问题。 int需要少于 30 位大小的 s 可以想象是有用的，并且每块会占用 28 个字节(存储值所需的每满 30 位增加 4 个字节)。因此，一个 100M 的元素集可能“仅”将 4 GB 用于数据结构本身，但该值至少需要 2.6 GB 左右；如果它们不是 Python 内置类型、用户定义的对象，即使使用 __slots__ , 至少会加倍(如果不使用 __slots__ 则加倍)，甚至在他们为自己的属性支付 RAM 费用之前。我的机器上有 12 GB 的 RAM，你的第二个用例会导致大量页面抖动，而你的第一个用例在 set 上运行得很好。初始化为 range(100000000) (虽然它会导致大多数其他进程页面出；Python 有两个 set 加上它们之间共享的 int 使用~11 GB)。

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

至于“有没有更好的解决方案？”这取决于你需要什么。如果您实际上不需要原始 set s，只是由此产生的差异，流式传输您的数据会有所帮助。例如:

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 s 的数据，这将减少每个 set 4 GB 的开销每个 list 到 ~850 MB ，然后并行迭代它们(但不是同时迭代；zip 在这里不好)找到第一个 list 中存在的元素但不是第二个，也消除了一些随机访问成本。