"Undirected"元组比较

Question

我目前正在python中研究一个无向图，其中边缘由元组表示（A和B之间的边缘由（A，B）或（B，A）表示）。我想知道是否有元组操作可以像这样对元组进行无向比较：

exp1 = undirected_comp((A,B), (B,A))    #exp1 should evaluate to True
exp2 = undirected_comp((A,B), (A,C))    #exp2 should evaluate to False

Answer 1

不

完全是，但一般来说，你可以用

set (A,B) == set (B, A)

Answer 2

当然： undirected_comp = lambda e1,e2: e1==e2 or (e1[1],e1[0])==e2

由于边总是正好是 2 元组，因此假设 A 和 B 对象定义了相等，它应该足够健壮。

EDIT（无耻的自我推销）：您可能不希望为每个比较器创建两个set对象的开销，特别是如果这是更大算法的一部分。 集合非常适合查找，但实例化要慢得多：https://stackoverflow.com/a/7717668/837451

Answer 3

除了使用集合的解决方案之外，还可以轻松推出自己的比较函数：

In [1]: def undirected_comp(tup1, tup2):
   ...:     return tup1 == tup2 or tup1 == tup2[::-1]
In [2]: undirected_comp(('A','B'), ('B','A'))
Out[2]: True
In [3]: undirected_comp(('A','B'), ('A','C'))
Out[3]: False
In [4]: undirected_comp(('A','B'), ('A','B'))
Out[4]: True

正如 mmdanziger 所指出的，这比使用集合的解决方案更快，因为您不必支付创建集合的成本。

但是，如果您关心速度，并且花更多的时间比较各种边而不是创建它们，那么最好不要将边存储为具有任意顺序的元组，而是对它们进行预处理并以不同的格式存储它们。两个最佳选项可能是frozenset元组或排序元组（即按照惯例，您始终首先存储最小的节点）。一些快速时机：

# edge creation, this time is spent only once, so presumably we don't care:
In [1]: tup1 = (1, 2); tup2 = (2, 1)
In [2]: fs1 = frozenset(tup1); fs2 = frozenset(tup2)
In [3]: sorted_tup1 = tuple(sorted(tup1)); sorted_tup2 = tuple(sorted(tup2))
# now time the comparison operations
In [4]: timeit set(tup1) == set(tup2) # Corley's solution
1000000 loops, best of 3: 674 ns per loop
In [5]: timeit tup1 == tup2 or tup1 == tup2[::-1] # my solution above
1000000 loops, best of 3: 348 ns per loop
In [6]: timeit fs1 == fs2 # frozensets
10000000 loops, best of 3: 120 ns per loop
In [7]: timeit sorted_tup1 == sorted_tup2 # pre-sorted tuples
10000000 loops, best of 3: 83.4 ns per loop

因此，假设您不关心边的创建时间，将它们存储为排序元组是进行比较的最快方法。在这种情况下，您只需要进行简单的比较，而不必向后比较情况，因为顺序是由预排序保证的。

Answer 4

Python 元组是有序的，而 python 集合不是。您可以使用 set 在比较之前简单地将元组转换为集合。

(A,B) == (B,A))          # evaluates to false
set((A,B)) == set((B,A)) # evaluates to true
set((A,B) == set((A,C))  # evaluates to false

如果你想使用一个函数，你可以做这样的事情：

def undirected_comp(a,b):
     return (set(a) == set(b))

编辑：我正在使用cmp()进行比较，这是不正确的，因为它返回1如果真，如果为假，则返回-1，而不是布尔值。将函数更改为使用 == ，它应该返回布尔值 - 如果要1和-1，请使用 return cmp(set(a), set(b)) 。