操作設置

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