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データフレームの1つの列に由来し、各タプルの2番目の要素は同じデータフレームの別の列に由来します。実際の問題で

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ループベースのソリューションを除いて、データフレームまたは何百万ものタプルで動作するアプローチはすべて問題ありません。私がこれまで試してみました何

： を私は凍結されたセットを使用して独自のタプルのリストを取得することができました：

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})} 

私は、このソリューションで進歩して非のためのループ方法を取得、またはループを避け、他のアプローチを使用するように見えることはできません。

私は現在Python 3.5を使用していますが、Python 2.7ソリューションも使用していません。

ご入力いただきありがとうございます。

Answer 1

プレーンなPythonでこれを行うのに合理的に効率的な方法です。タプルにすでに受け入れられたタプルに含まれている要素が含まれているかどうかをテストするには、関数not_seenを使用します。それは見ての要素をキャッシュするデフォルトの可変引数seenを使用し、そのセットをクリアすることができないので、あなたが実行する必要がある場合：

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

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) 

出力はnot_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を使用して受け入れられるペアを示すナンシーブール値配列を作成し、そのブール値配列を使用して目的のペアを選択します。

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実装よりも高速である必要があります。ループ処理自体は速くなければなりません。ボトルネックはまだ平凡なPython関数であるnot_seenと呼んでいるということです。また、boolean配列を構築する必要があるため、RAMを多く使用します。

---

更新

それnot_seen機能外部からseenセットをクリアする実際に可能です。関数のデフォルト引数には、.__default__属性（または古いバージョンのPython 2では.func_defaults; .__default__はPython 2.6で動作しますが、2.5では動作しません）を介してアクセスできます。

例えば、

not_seen.__defaults__[0].clear() 

Answer 2

for-loopsやlist comprehensionsを避けることはできません。お互いに何らかの形でそれらの上にループする必要がある要素を比較しています。メモリ使用のためにfor-loopsやlist comprehensionsを避けたいのであれば、irangeやxrangeのようなイテレータやジェネレータに興味があるかもしれません。

（（この問題のより理論的な説明：。。それは、時間と空間の複雑さについてですが、この問題は時間複雑O（N）か悪いしかし、スペースのため（=メモリを持っている可能性があります）複雑あなたがOを避ける（N）とOのようなもの（1）またはO（Nを記録）。））

ドゥn個を持っている良い変化があなたの話のパンダのことを知っている。私はそのパッケージで十分な経験がありません。

Answer 3

あなたが同じ時間に、あなたの例のソリューションでそれらを使用している間、ループのないようにしたい理由を私は知らないが、（私は思う）簡単な関数を生成するために、あなたの出力は次のようになります。

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にはない。