操作设置

Question

UPDATE 1

两组含有最大长度20的字符串和只能2

我通过构造的集取的值从 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'

UPDATE使用名为ujson的库（类似于simplejson）从磁盘读取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）。在Python 3.5上构建的一个100M元素set为64位处理器（您正在使用，因为甚至无法在Python的32位版本中创建set）针对set开销使用4 GB内存（忽略它包含的对象使用的内存）。

你的代码，创建一个新的set没有会员测试第二set访问该存储顺序，所以OS可以预测的存取模式，并很可能将数据提取到缓存中，你需要它之​​前，即使大部分set的是分页出。唯一的随机访问发生在第二个set的建筑物中（但方便起见，因为您将它们从原始set中拉出，所以被插入的对象已经在缓存中）。所以你从没有随机访问到可能随机访问的4 GB（加上包含对象的大小）内存的增长，并且必须不会被导出而不会导致性能问题。

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

为了记录，set开销可能是存储对象成本的一小部分。 Python中最小的有用对象是float s（Python 3.5 x64上的一个片断是24字节），尽管由于严格相等性测试的问题，它们对于set s是不好的选择。需要少于30位数量级的数据可能是有用的，并且每个数据块需要消耗28个字节（为存储该值所需的每30位全部增加4个字节）。因此，一个100M的元素集可能“仅”使用4 GB的数据结构本身，但其值至少为2.6 GB左右;如果它们不是Python内置类型，那么甚至在使用__slots__时，用户定义的对象至少会将其加倍（如果不使用__slots__，则会加倍），然后它们甚至会为内存支付其属性。我的机器上有12 GB的内存，而你的第二个用例会导致大量的页面抖动，而你的第一种情况对于用range(100000000)初始化的set运行得很好（尽管它会导致大部分其他进程页面出来; Python与两个set s加上int它们之间共享使用〜11 GB）。

更新：您的数据（1-20个ASCII字符的字符串）将在Python 3.5 x64（可能多一点包括分配器开销）上使用50-69个字节，或者每个set使用4.65-6.43 GB（假设没有字符串共享，原始数据为9-13 GB）。添加三个set s，并且您正在查看高达25 GB的RAM（您不需要再为第三个set的成员付钱，因为它们与第一个set共享）。我不会尝试在任何RAM少于32 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 s数据，这会将开销从每GB set增加4 GB减少到每个list〜850 MB，然后将它们并行重复（但不是同时; zip在这里不好），以找到存在的元素在第一个list但不是第二个，也删除了一些随机访问成本。

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）只。