在Python中高效创建两个元组的方法

Question

我想从一对对中再组成两对。这里的“一对”是指由两个元素组成的，而“两对”则是由两对组成的。

以下是一些规则：

1. 在一对中，元素的顺序是重要的：比如 (元素1, 元素2) 和 (元素2, 元素1) 是不一样的。
2. 在两对中，顺序就不重要了：比如 (对1, 对2) 和 (对2, 对1) 是一样的。

我写了一些伪代码来满足这些规则，代码如下：

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 在我的代码中运行得很慢。有没有其他方法可以表示两对？或者，能不能改进一下上面的代码？

Answer 1

你为什么需要自己写类呢？我看你的需求其实用元组（tuples）来表示成对的数据，或者用集合（sets）来表示两个成对的数据就可以满足了。

不过如果你还是想要优化自己的代码，建议先进行性能分析。可以在网上搜索“Python profile”，看看前五个链接，了解一下怎么做。

Answer 2

你可能更适合使用标准的Python数据结构。可以用tuple来表示Pair，用set来表示TwoPair（不过你可能需要写一个set的子类，来添加__hash__方法）。

举个例子：

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，避免了组合爆炸和每次添加新对之前都要测试的麻烦。