Pythonで2つのペアを作る効率的な方法

Question

私はペアから2つのペアを作りたいと思います。 ペアは2つの要素で構成され、2つのペアは2つのペアで構成されます。ここで は、制約のリストです：ペアで

1. 、要素の順序は重要である：（要素1、要素2）=（要素2は、要素1）2ペアで
2. は、ペアの順序はありません！重要：（PAIR1、PAIR2）==（PAIR2、PAIR1）

Iは次のように、上記の制約を満足する擬似コードを書いた：

class Pair: 
    def __init__(self, element1, element2): 
     assert isinstance(element1, Element) 
     assert isinstance(element2, Element) 
     self.element1 = element1 
     self.element2 = element2 

    def __eq__(self, other): 
     if not isinstance(other, Pair): 
      return False 
     if self.element1 != other.element1: 
      return False 
     if self.element2 != other.element2: 
      return False 
     return True 

    def __ne__(self, other): 
     return not (self.__eq__(other)) 

    def __hash__(self): 
     return hash(self.element1)^hash(self.element2) 

    def getFirst(self): 
     return self.element1 

    def getSecond(self): 
     return self.element2

class TwoPair: 
    def __init__(self, pair1, pair2): 
     assert isinstance(pair1, Pair) 
     assert isinstance(pair2, Pair) 
     self.pair1 = pair1 
     self.pair2 = pair2 

    def __eq__(self, other): 
     if not isinstance(other, TwoPair): 
      return False 
     if self.pair1 == other.pair1 and self.pair2 == other.pair2: 
      return True 
     if self.pair1 == other.pair2 and self.pair2 == other.pair1: 
      return True 
     return False 

    def __ne__(self, other): 
     return not (self.__eq__(other)) 

    def __hash__(self): 
     return hash(self.pair1)^hash(self.pair2) 

    def getFirst(self): 
     return self.pair1 

    def getSecond(self): 
     return self.pair2

def makeTwoPairs(allPairs): 
    allTwoPairs = set([]) 
    for pair1 in allPairs: 
     for pair2 in allPairs: 
      if pair1 == pair2: 
       continue 
      twoPair = TwoPair(pair1, pair2) 
      if twoPair in allTwoPairs: 
       continue 
      else: 
       allTwoPairs.add(twoPair) 
    return allTwoPairs

機能makeTwoPairsは私のコードでは時間がかかります。 2組の他の表現はありますか？または、上記のコードを改善できますか？

Answer 1

標準のPythonデータ構造を守る方がよいでしょう。 tupleのPairとsetのTwoPair（メソッドを追加するにはsetサブクラスを記述することもできます）。例えば

：

import operator 

class TwoPairs(set): 
    def __hash__(self): 
    return reduce(operator.xor, map(hash, self)) 

あなたmakeTwoPairs機能の実行に時間がかかる、あなたはこのようにそれを書き換えることができるという事実について：

def make_two_pairs(all_pairs): 
    all_two_pairs = set() 
    # uniqify the pairs list 
    all_pairs = list(set(all_pairs)) 
    for i in range(len(all_pairs)-1): 
    for j in range(i+1, len(all_pairs)): 
     all_two_pairs.add(TwoPairs(all_pairs[i], all_pairs[j])) 

    return all_two_pairs 

それからのみユニークが生成されますTwoPairs、組み合わせの爆発、または結果セットに新しいペアを追加する前に、毎回テストのオーバーヘッドはありません。

Answer 2

独自のクラスを作成する必要がありますか？あなたの仕様では、タプルをペアとして使用することで満足できないものや、2つのペアとして設定するものはありません。

独自のコードを最適化する場合は、常にプロファイリングから始めます。 Googleの "Python profile"を読んで最初の5つのリンクを読んでみてください。