我有一個很大的元組列表，例如[ (1,2), (1,3), (1,4), (2,1), (2,3) ]等我想將其轉換爲[ (1, [1,2,3,4]), (2, [1,3]) ]有效。我按每個元組的第一個元素對元組進行分組，即(1,2), (1,3), (1,4)變成(1, [2,3,4])（同時參見下面的Haskell版本）。我懷疑這可以通過一次完成？ 輸入列表總是有序的。有效的元組列表

在python在嘗試使用defaultdict我認爲是沒有重新發明車輪的自然解決方案。它運作良好，但它不保留鍵的順序。一種解決方案是使用有序的defaultdict作爲explained here。

無論如何，我想知道這個問題的語言獨立和有效的解決方案。我目前的解決方案需要兩個通行證和一個呼叫到set()列表上。

更新

我想實現以下哈斯克爾版本：

a = [ (1,2), (1,3), (1,4), (2,1), (2,3) ] 
b = groupBy (\ x y -> fst x == fst y) 
b 
[[(1,2),(1,3),(1,4)],[(2,1),(2,3)]] 
map (\x -> (fst .head $ x, map snd x)) b 
[(1,[2,3,4]),(2,[1,3])]

答案

的性能我實現了兩個答案（coldspeed和pm2ring）。在中等大小的清單（高達10^4個元素）中，PM2環解決方案更快;在10^5的大小，都需要相同的時間，在更大的名單COLDSPEED開始贏。下面是數字（用python3）。

第一列是列表中的條目數，第二列是coldspeed所花的時間，第三列列出的時間爲pm2 ring解決方案。所有時間都在第二。

10 0.0001 0.0000 
100 0.0001 0.0000 
1000 0.0005 0.0001 
10000 0.0044 0.0014 
100000 0.0517 0.0452 
1000000 0.5579 1.5249

腳本是在這裏http://github.com/dilawar/playground/raw/master/Python/so_group_tuple.py

隨着阿什維尼優化

PM 2Ring解決方案甚至更快（約3倍 - 5倍）與阿什維尼的建議。

10 4.887580871582031e-05 1.2636184692382812e-05 
100 0.00010132789611816406 2.0742416381835938e-05 
1000 0.0005109310150146484 0.000110626220703125 
10000 0.004467487335205078 0.0009067058563232422 
100000 0.05056118965148926 0.017516136169433594 
1000000 0.6100358963012695 0.26450490951538086 
10000000 6.092756509780884 2.8253660202026367

隨着PYPY

有點混合的結果。最後一列是3

pypy so_group_tuple.py 
(10, [1.6927719116210938e-05, 3.409385681152344e-05], 0.4965034965034965) 
(100, [4.601478576660156e-05, 8.296966552734375e-05], 0.5545977011494253) 
(1000, [0.010258913040161133, 0.0019040107727050781], 5.388054094665665) 
(10000, [0.0002448558807373047, 0.00021600723266601562], 1.1335540838852096) 
(100000, [0.002658843994140625, 0.0018231868743896484], 1.45834967961292) 
(1000000, [0.0833890438079834, 0.02979302406311035], 2.7989452709245284) 
(10000000, [1.0556740760803223, 0.6789278984069824], 1.5549133841124023)

我與PM 2Ring解去，因爲它的速度要快得多，直到列表大小10^5列2的比例和列。

來源

2017-08-03 Dilawar

請附上您目前的解決方案，並澄清的問題是什麼 - 這是不清楚你從第一個列表到第二個列表。 – perigon

[OrderedDict]（https://docs.python.org/2/library/collections.html#ordereddict-objects）？ – 101

輸入列表是否總是這樣排序？順便說一句，你在這個列表中有一個錯字。 –

你可以用itertools.groupby做到這一點，並使用zip重新排列數據來自收集組：

from itertools import groupby 
from operator import itemgetter 

a = [(1, 2), (1, 3), (1, 4), (2, 1), (2, 3)] 
b = [(k, list(list(zip(*g))[1])) for k, g in groupby(a, itemgetter(0))] 
print(b)

輸出

[(1, [2, 3, 4]), (2, [1, 3])]

該列表比較是有點密集。這是一個使用傳統的for循環的變體，它打印出一箇中間結果，使它更容易看到發生了什麼。

b = [] 
for k, g in groupby(a, itemgetter(0)): 
    t = list(zip(*g)) 
    print(t) 
    b.append(list(t[1])) 

print('Output', b)

輸出

[(1, 1, 1), (2, 3, 4)] 
[(2, 2), (1, 3)] 
Output [[2, 3, 4], [1, 3]]

由於阿什維尼·喬杜裏提到的意見，嵌套另一個列表比較在那裏使代碼多更具可讀性，它可能也更有效率，因爲它避免了幾個電話。

b = [(k, [x for _, x in g]) for k, g in groupby(a, itemgetter(0))]

來源

2017-08-03 06:42:49

好'ol LC更容易閱讀：'[x for _，x in g]'。 –

@AshwiniChaudhary事實確實如此！感謝那。 –

@AshwiniChaudhary你的建議讓這個實現更快。我添加了一些基準。 – Dilawar

您可以使用collections.OrderedDict（import collections在前）：

In [983]: o = collections.OrderedDict() 

In [984]: for x in t: 
    ...:  o.setdefault(x[0], []).append(x[1]) 
    ...:

現在，轉換o.items()到一個列表：

In [985]: list(o.items()) 
Out[985]: [(1, [2, 3, 4]), (2, [1, 3])]

來源

2017-08-03 06:40:11

雖然這很容易閱讀，但它比「PM 2Ring」解決方案在尺寸高達10^5 - 10^6的列表中稍慢。我在問題主體中添加了一些基準。 – Dilawar

@Dilawar表現並不是唯一的考慮因素。如果你想速度使用C;）你應該使用最簡單，最清晰，最容易閱讀和理解的內容。可以理解的PM2Ring的解決方案的工作原理，很高興看到，但我希望_actually_知道我的代碼在做什麼。最終取決於你。乾杯。 –

可能是如果輸入列表已經下令，它不需要使用任何其他訂購功能或特徵再次重新排序列表。下面的代碼會自動給出你輸出的結果。

mylistarr = ((1, 2), (1, 3), (1, 4), (2, 1), (2, 3)) 
output = dict() 
for tuple in mylistarr: 
    if tuple[0] not in anotherlist: 
     output[tuple[0]] = list() 
     output[tuple[0]].append(tuple[0]) 
    output[tuple[0]].append(tuple[1]) 
print output

輸出： {1：1，2，3，4]，2：2，1，3]}

來源

2017-08-03 06:46:56

'anotherlist = dict（）'是錯誤的命名。 –

有效的元組列表

答案

隨着阿什維尼優化

隨着PYPY

回答

相關問題