的Python：獲取獨特的元組，使得所有元組元素是不相交的

Question

有元組的列表：

all_tups = [(1, 2), (2, 1), (3, 4), (3, 5), (4, 3), (6, 8), (6, 7), (7, 9)] 

我想要做的事情： 獲取的元組，例如，如果在任何元組，一個元素出現，那麼帶有這個元素的任何其他元組都應該被丟棄（不管元素在任何元組中的位置）。

所以，有幾種所需的輸出可能：

[(1,2) (3,4) (6,8) (7,9)] OR 
[(2,1) (4,3) (6,8) (7,9)] 

等。

最初，每個元組的第一個元素來自Pandas數據框的一列，每個元組的第二個元素來自同一個數據幀的另一列。

C1 C2 0 1 2 1 2 1 2 3 4 3 3 5 4 4 3 5 6 8 6 6 7 7 7 9

在實際的問題，還有數以百萬計的數據幀的行。因此，我不在尋找一個基於for-loop的解決方案。除了基於for-loop的解決方案之外，任何適用於數據框或數百萬個元組的方法都很好。

我迄今爲止嘗試： 我已經能夠獲得使用冷凍套獨特的元組的列表：

uniq_tups = {frozenset(k) for k in all_tups} 

（誠然，使用列表理解我在理想情況下還要避免）。這給了我：

{frozenset({1, 2}), 
frozenset({6, 7}), 
frozenset({3, 5}), 
frozenset({3, 4}), 
frozenset({6, 8}), 
frozenset({7, 9})} 

我似乎無法得到使這種解決方案取得進展的非for循環的方式，或使用避免循環任何其他的辦法。

我目前使用Python 3.5，但使用Python 2.7解決方案也沒有問題。

在此先感謝您的意見。

Answer 1

下面是在普通Python中這樣做的合理有效方法。我們使用函數not_seen來測試元組是否包含已經在接受的元組中看到的元素。

all_tups = [(1, 2), (2, 1), (3, 4), (3, 5), (4, 3), (6, 8), (6, 7), (7, 9)] 

def not_seen(t, seen=set()): 
    if t[0] in seen or t[1] in seen: 
     return False 
    seen.update(t) 
    return True 

unique = list(filter(not_seen, all_tups)) 
print(unique) 

輸出

[(1, 2), (3, 4), (6, 8), (7, 9)] 

有與not_seen一個小問題：它採用的是默認的可變參數seen緩存看到的元素，並集不能被清除，因此，如果您需要執行這個操作再次seen仍然會保留舊的元素。我們可能使得seen是一個全球性的，但那會運行得更慢。另一種選擇是每次我們需要一個工廠函數來生成一個乾淨版本的seen。例如：

def make_checker(): 
    def not_seen(t, seen=set()): 
     if t[0] in seen or t[1] in seen: 
      return False 
     seen.update(t) 
     return True 
    return not_seen 

not_seen = make_checker() 

FWIW，這裏有not_seen壓縮版本;它應該是差不多與原始效率一樣高，如果它實際上更快，我會感到驚訝。 :)

def not_seen(t, seen=set()): 
    return False if t[0] in seen or t[1] in seen else seen.update(t) or True 

我們可以在緊湊型轉換成拉姆達，然後我們就不必擔心清除seen集的問題。

all_tups = [(1, 2), (2, 1), (3, 4), (3, 5), (4, 3), (6, 8), (6, 7), (7, 9)] 

unique = list(filter(lambda t, seen=set(): 
    False if t[0] in seen or t[1] in seen else seen.update(t) or True, all_tups)) 
print(unique) 

---

這裏是一個NumPy的實現。首先我們將數據轉換爲2D Numpy數組。然後，我們使用not_seen和numpy.apply_along_axis創建一個Numpy布爾數組，表示應接受的對，然後使用該布爾數組來選擇所需的對。

import numpy as np 

def not_seen(t, seen=set()): 
    if t[0] in seen or t[1] in seen: 
     return False 
    seen.update(t) 
    return True 

all_tups = [(1, 2), (2, 1), (3, 4), (3, 5), (4, 3), (6, 8), (6, 7), (7, 9)] 

all_tups = np.array(all_tups) 
print(all_tups, all_tups.dtype) 
print('- ' * 20) 

filtered = all_tups[np.apply_along_axis(not_seen, 1, all_tups)] 
print(filtered) 

輸出

[[1 2] 
[2 1] 
[3 4] 
[3 5] 
[4 3] 
[6 8] 
[6 7] 
[7 9]] int32 
- - - - - - - - - - - - - - - - - - - - 
[[1 2] 
[3 4] 
[6 8] 
[7 9]] 

這應該比上述普通Python實現更快。循環過程本身應該更快，瓶頸是我們仍然調用not_seen這是一個普通的Python函數。此外，它使用更多的RAM，因爲它必須構造布爾數組。

---

更新

這是實際上可以從not_seen功能外清除seen集。我們可以通過訪問其.__default__屬性函數的默認參數（或舊版本的Python 2 .func_defaults; .__default__作品在Python 2.6，而不是2.5）。

例如，

not_seen.__defaults__[0].clear() 

Answer 2

我不認爲有可能避免for循環或列表解析。你正在比較彼此的元素，所以你必須循環它們。如果你想避免由於內存使用而導致的for-loops或列表解析，那麼你可能會對迭代器或生成器感興趣，像irange或xrange可以節省你（大量的）內存。

（（這個問題的更多的理論解釋：它是關於時間和空間的複雜性，這個問題可能有時間複雜度Ø（ñ），或者更糟，但空間（=內存）。複雜你有一個很好的改變，以避免Ø（ñ），並有類似Ø（1）或Ø（日誌ñ）））

待辦事項ñ不瞭解你的故事的熊貓一面。我對這個軟件包沒有足夠的經驗。

Answer 3

我不知道爲什麼你要避免for循環，而在同一時間，你在你的榜樣解決方案使用它們，但一個簡單的（我認爲）功能，以您製作輸出爲：

all_tups = [(1, 2), (2, 1), (3, 4), (3, 5), (4, 3), (6, 8), (6, 7), (7, 9)] 
def tup_gen(tuple_list): 
    s = set() 
    for element in tuple_list: 
     if s.intersection(element): 
      continue 
     yield element 
     s.update(element) 

這將是懶惰的，在同一時間產生一個元組（這將讓你在一個大的數據集工作），輸出將是：

result = list(tup_gen(all_tups)) 
print(result) 
[(1, 2), (3, 4), (6, 8), (7, 9)] 

當然，這是做的方式它沒有使用任何特定的庫。我很確定一定會有更快的速度（甚至直接在PF中），但我還沒有投入到PF中去，所以還沒有給你答案。