我有一個> 10.000 int類型的項目列表。這些物品的價值可能非常高,高達10^27。現在我想創建所有項目對並計算它們的總和。然後我想用相同的總和查找不同的對。Python:大int鍵快字典
例如:
l[0] = 4
l[1] = 3
l[2] = 6
l[3] = 1
...
pairs[10] = [(0,2)] # 10 is the sum of the values of l[0] and l[2]
pairs[7] = [(0,1), (2,3)] # 7 is the sum of the values of l[0] and l[1] or l[2] and l[3]
pairs[5] = [(0,3)]
pairs[9] = [(1,2)]
...
的pairs[7]
的內容是什麼,我期待的。它給了我兩個相同的價值總和。
我已經實現它如下 - 我不知道它可以做得更快。目前,對於10.000個物品,在快速機器上需要> 6個小時。 (正如我所說,l
和值的pairs
所以鍵是整數可達10^27)
l = [4,3,6,1]
pairs = {}
for i in range(len(l ) ):
for j in range(i+1, len(l)):
s = l[i] + l[j]
if not s in pairs:
pairs[s] = []
pairs[s].append((i,j))
# pairs = {9: [(1, 2)], 10: [(0, 2)], 4: [(1, 3)], 5: [(0, 3)], 7: [(0, 1), (2, 3)]}
編輯:我想添加一些背景,要求由西蒙·Stelling 。
的目標是要找到正規的類比象
lays : laid :: says : said
單詞列表內的類似
[ lays, lay, laid, says, said, foo, bar ... ]
我已經有一個函數analogy(a,b,c,d)
給True
如果a : b :: c : d
。但是,我需要檢查從列表創建的所有可能的四元組,這將是O((n^4)/ 2)左右的複雜度。
作爲一個預過濾器,我想使用char-count屬性。它說每個char在(a,d)和(b,c)中都有相同的計數。例如,在「layssaid」我們有2級的,所以我們在「laidsays」
做這樣的想法到現在爲止是
- 的每一個字,以創建一個「字符計數矢量」和代表它作爲一個整數(列表中的項目
l
) - 在
pairs
中創建所有配對並查看是否存在「配對簇」,即對於特定的char計數向量和有多於一對。
它的工作原理,它只是緩慢。複雜度下降到O((n^2)/ 2)左右,但這仍然很多,特別是字典查找和插入操作經常完成。
的問題是不是整數的大小,這是事實,你有過這是在'o所有條目的雙重嵌套循環(N^2)' – blubb 2011-05-06 12:15:16
你真的等了6個小時,直到完成了嗎?不過我建議看看PEP8 :) – Ant 2011-05-06 12:25:43
...範圍還會返回一個完整列表,其中所有項目都展開,請使用xrange代替 – 2011-05-06 12:25:44