找到所有常見的N大小的元組的元組

的名單我要創建一個，做如下操作的應用（我有一次解析數據，並將它們存儲在數據庫中）：找到所有常見的N大小的元組的元組

我給ķ元組（具有K超過1000000）和每個元組是在

(UUID, (tuple of N integers))

形式，例如，假設N等於20，用於每k元組，並且每20大小的元組被排序。我在以下兩種形式（2個不同的表）救了我的所有數據在數據庫中，這樣我可以更容易地處理它們：

_id，UUID，tuple.as_a_string（）
_id， UUID，1st_elem，2nd_elem，3rd_3lem，... 20th_elem

的目標是從元組的列表，如那些元組的每一個到一個以上的20大小的存在找到所有10級的元組元組**。**

例如，如果我們給出兩個關注荷蘭國際集團20大小的元組：

(1, (1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,161,17,18,19,20)) 
(2, (1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,33,35,37,39))

共用元組是：（1,3,5,7,9,11,13,15,17,19）

這是一個10大小的元組，所以結果是類似以下內容：

(1, 2, (1,3,5,7,9,11,13,15,17,19))

爲了做到這一點，有什麼我目前做的是（在Python 3）：

創建一組與20的元素-si數據庫中第一行的元組。
使用數據庫中其餘行的20個元組的元素爲每一行創建一個集合。
對於第二組列表中的每個集合，我都與第一組相交。
然後，我創建了交叉點與10個元素（在Python中是itertools.combinations（new_set，10））的組合，它給了我想要的結果。

但是這個程序是很慢。即使使用多處理技術來充分利用我的8個CPU內核，每個計算都需要一個不同的編號，但這需要花費很長時間。我現在有2天的計劃，只有20％。

您對如何優化流程有任何建議嗎？ NumPy陣列可以幫助執行速度嗎？ SQL中有什麼方法可以計算每行所需的內容，即使是每行一行？

在此先感謝。

來源

2016-10-01 TIMace

爲什麼這個標記的SQL？你的數據表示是什麼？ –

對不起。我的意思是隻用SQLite標記。我錯過點擊。我的數據是大小爲20的整數的元組，每個元組都有唯一的ID分配給元組。 – TIMace

如果它是sqlite的，你不應該寫SQL來做到這一點，而不是python？ – deltaskelta

似乎沒有成爲這麼多的希望：忘記combinations()一部分，你需要檢查每對K元組的交集。有choose(K, 2) = K*(K-1)/2對，所以有一百萬個元組有近5000億對。

你可以玩的一個低級別技巧是將一個元組表示爲一個整數而不是一個整數，其中位2**i設置爲整數，當且僅當i位於元組中時。既然你在評論中說，一個元組包含沒有重複，每個元組元素是range(1, 100)，100位的整數是足夠了（它可能被削減到99位，但不值得理會）。

點是一個整數的不同位「&」雲快了很多比交集。在我的盒子上，快了大約7倍。下面是一些代碼來說明這個概念，有些馬虎的時序結果（一臺機器同時做很多其他的東西上運行）：

def build(K, values, N): 
    from random import sample 
    sets = [] 
    ints = [] 
    for i in range(K): 
     t = sample(values, N) 
     sets.append(set(t)) 
     ints.append(sum(1 << i for i in t)) 
    return sets, ints 

def run(K, values, N): 
    from time import time 
    as_sets, as_ints = build(K, values, N) 
    for meth, collection in [("sets", as_sets), 
          ("ints", as_ints)]: 
     s = time() 
     for i in range(K-1): 
      base = collection[i] 
      for j in range(i+1, K): 
       x = base & collection[j] 
     t = time() 
     print("K", K, meth, t-s) 

for K in 5000, 10000, 20000: 
    run(K, range(1, 100), 20)

輸出：

K 5000 sets 7.322501182556152 
K 5000 ints 1.0357279777526855 
K 10000 sets 30.60071086883545 
K 10000 ints 4.150524377822876 
K 20000 sets 128.24610686302185 
K 20000 ints 15.933331727981567

需要注意的是，符合市場預期，運行時間因爲任何一種方法在K中都是二次的（所以K的加倍大約需要4倍;而使K大10倍會使運行時間增加大約10 ** 2 = 100）。

雖然交點的整數更快，但確定結果的基數較慢。有很多方法可以做到這一點，但「最好的」取決於期望的分佈和對編碼疼痛的容忍度;-)下面是major methods的概述。

來源

2016-10-02 03:54:16

我選擇使用bitsets，結合您推薦的和我已經完成的工作，我看到了50倍的性能提升。我用bitsets來表示我的集合，並使用AND運算符。 0代表不存在的號碼，而1代表現有的號碼。簡單而高效。 – TIMace

看來您可以將元組放入矩陣的行中，並從行號到UUID進行映射。然後將所有的元組存儲在一個numpy數組中是可行的，因爲元組的元素很小。 numpy具有能夠計算這種數組的行之間的交集的代碼。這段代碼生成組合以首先處理元組，然後進行比較。

from itertools import combinations 
import numpy as np 
from time import time 

minInt=1 
maxInt=100 
tupleSize=20 
intersectionSize=10 

K=100 
rows=np.zeros((K,tupleSize),dtype=np.int8) 
print ('rows uses', rows.nbytes, 'bytes') 

for i,c in enumerate(combinations(range(minInt,maxInt),tupleSize)): 
    if i>=K: 
     break 
    for j,_ in enumerate(c): 
     rows[i,j]=_ 

t_begin=time() 
for i in range(K-1): 
    for j in range(i+1,K): 
     intrsect=np.intersect1d(rows[i],rows[j],True) 
     if intrsect.shape[0]==intersectionSize: 
      print (i,j,intrsect) 
t_finish=time() 

print ('K=', K, t_finish-t_begin, 'seconds')

這裏是在家裏我的老雙核心P4難有起色做了一些樣品測量。

行使用200個字節 K = 100.0009770393371582031秒

行使用1000個字節 K = 500.0410161018371582秒

行使用2000個字節 K = 1000.15625秒

行使用10000個字節 K = 500 3.610351085662842秒

行使用20000字節 K = 100014.931640863418579秒

行使用100000個字節 K = 5000379.5498049259186秒

如果你運行你的機器上的代碼，你可以推斷。我不知道這是否會讓你的計算變得可行。

也許我就把一堆反對票！

來源

2016-10-01 21:45:08

這個解決方案並不是我想要實現的改進，因爲數據集非常龐大，這讓我的生活變得艱難。然而，numpy數組中的組織實際上給了我一些性能改進，因爲訪問時間，雖然不是很大的提升。謝謝您的輸入！ – TIMace

非常歡迎。我認爲，至少它可以回答一兩個問題，並提示其他人發表評論。 –

比爾，我想這將創建一個更隨意的搭配。您的組合版本系統地通過選擇步驟。小K的交點大小接近tupleSize。

choices = np.arange(minInt, maxInt) 
for i in range(K): 
    rows[i,:] = np.random.choice(choices, tupleSize, replace=False)

使用sets約4倍比np.intersect1d更快。

sets = [set(row) for row in rows] 
dd = collections.defaultdict(int) 
for i in range(K-1): 
    for j in range(i+1,K): 
     intrsect=sets[i].intersection(sets[j]) 
     dd[len(intrsect)] += 1

我切換到收集交集大小，因爲它對迭代策略更有趣且不太敏感。

隨着K = 5000：

K= 5000 221.06068444252014 seconds 
{0: 77209, 1: 514568, 2: 1524564, 3: 2653485, 4: 3044429, 5: 2436717, 6: 1408293, 7: 596370, 8: 188707, 9: 44262, 10: 7783, 11: 1012, 12: 93, 13: 8}

越小時間是隻是爲sets創建步驟;這非常快。

K= 5000 0.058181047439575195 46.79403018951416 seconds 
{0: 77209, 1: 514568, 2: 1524564, 3: 2653485, 4: 3044429, 5: 2436717, 6: 1408293, 7: 596370, 8: 188707, 9: 44262, 10: 7783, 11: 1012, 12: 93, 13: 8}

當k比較大

K= 10000 818.3419544696808 seconds 
{0: 309241, 1: 2058883, 2: 6096016, 3: 10625523, 4: 12184030, 5: 9749827, 6: 5620209, 7: 2386389, 8: 752233, 9: 176918, 10: 31168, 11: 4136, 12: 407, 13: 18, 14: 2} 
K= 10000 0.09764814376831055 151.11484718322754 seconds

來源

2016-10-02 02:02:59 hpaulj

Paul，感謝您的回覆。對我們中的許多人來說，像這樣突出顯示的比較將是有益的。但是哪裏？ –

找到所有常見的N大小的元組的元組

回答

相關問題