Эффективный способ сделать две пары в Python

Question

Я хотел бы сделать две пары из пар. Пара состоит из двух элементов, а пара состоит из двух пар. Вот список ограничений:

1. В паре важен порядок элементов: (element1, element2)! = (Element2, element1)
2. В двух парах порядок пар не важен: (pair1, pair2) == (pair2, pair1)

Я написал псевдокод, который удовлетворяет вышеуказанным ограничениям, следующим образом:

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

Возможно, вам лучше придерживаться стандартных структур данных 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,без комбинаторного взрыва или накладных расходов на тестирование каждый раз перед добавлением новой пары в набор результатов.

Answer 2

Есть ли причина, по которой вам нужно писать свои собственные классы?Я не вижу в вашей спецификации ничего, что не могло бы быть удовлетворено использованием кортежей в качестве пар и наборов в качестве двух пар.

Но если вы настроены оптимизировать свой собственный код, всегда начинайте с профилирования.Введите в Google "профиль Python" и прочитайте первые пять ссылок или около того, если вы не знаете, как.