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函数在我的代码中运行时间很长。是否有其他方式来表示两个对子？或者，上述代码能否改进？

- Sangmin

---

这段代码对我来说毫无意义。你试图解决的实际用例是什么？通常从'tuple'派生可能是一个更好的方法，而不是在这里重新发明轮子。这段代码看起来像是没有真正了解问题就编写的。 - user2665694

Answer 1

你最好使用标准的Python数据结构。对于Pair，使用tuple，对于TwoPair，使用set（尽管你可能需要编写一个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，无需组合爆炸或在向结果集添加新对之前每次进行测试的开销。

- Clément

---

或者对于TwoPair，可以使用frozenset，它已经是可哈希的。这取决于element1和element2是否应该是Pair的可变属性（如果不是，那么pair1和pair2是否是TwoPair的可变属性）- 我认为不是，因此你提议使用tuple是正确的。 - Steve Jessop

Answer 2

你是否有必要编写自己的类？我在你的规格说明中看不出任何不能使用元组作为对和集合作为双对的内容。

但是，如果你决定优化自己的代码，请始终从分析开始。如果你不确定如何操作，可以搜索“Python profile”并阅读前五个链接左右。

- Wang