python - 如何在此循环中利用排列对称性？

我有一个具有以下置换对称性的标量函数f(a,b,c,d)f(a,b,c,d) = f(c,d,a,b) = -f(b,a,d,c) = -f(d,c,b,a)
我正在使用它完全填充4D数组。下面的代码(使用python/NumPy)可以工作:

A = np.zeros((N,N,N,N))
for a in range(N):
    for b in range(N):
        for c in range(N):
            for d in range(N):
                A[a,b,c,d] = f(a,b,c,d)

但是显然我想利用对称性来减少本节代码的执行时间。我试过了:

A = np.zeros((N,N,N,N))
ab = 0
for a in range(N):
    for b in range(N):
        ab += 1
        cd  = 0
        for c in range(N):
            for d in range(N):
                cd += 1
                if ab >= cd:
                    A[a,b,c,d] = A[c,d,a,b] = f(a,b,c,d)

这将执行时间缩短了一半。但是对于最后的对称性，我尝试了:

A = np.zeros((N,N,N,N))
ab = 0
for a in range(N):
    for b in range(N):
        ab += 1
        cd  = 0
        for c in range(N):
            for d in range(N):
                cd += 1
                if ab >= cd:
                    if ((a >= b) or (c >= d)):
                        A[a,b,c,d] = A[c,d,a,b] = f(a,b,c,d)
                        A[b,a,d,c] = A[d,c,b,a] = -A[a,b,c,d]

哪个可行，但不能给我带来两个提速的另一个因素。我认为出于正确的原因这是不对的，但看不到原因。

我如何在这里更好地利用这种特定的排列对称性？

最佳答案

有趣的问题!

对于N=3，应该有4个元素的81个组合。
使用循环，您将创建156。

看起来重复项的主要来源是or中的(a >= b) or (c >= d)，它太宽容了。不过，(a >= b) and (c >= d)太严格了。

您可以比较a + c >= b + d。要获得几毫秒(如果有的话)，可以将a + c保存为ac在第三循环内:

A = np.zeros((N,N,N,N))
ab = 0
for a in range(N):
    for b in range(N):
        ab += 1
        cd  = 0
        for c in range(N):
            ac = a + c
            for d in range(N):
                cd += 1
                if (ab >= cd and ac >= b+d):
                    A[a,b,c,d] = A[c,d,a,b] = f(a,b,c,d)
                    A[b,a,d,c] = A[d,c,b,a] = -A[a,b,c,d]

使用此代码，我们创建了112个组合，因此重复项的数量少于您的方法，但是可能还需要进行一些优化。

更新

这是我用来计算已创建组合数量的代码:

from itertools import product

N = 3
ab = 0

all_combinations = set(product(range(N), repeat=4))
zeroes = ((x, x, y, y) for x, y in product(range(N), repeat=2))
calculated = list()

for a in range(N):
    for b in range(N):
        ab += 1
        cd = 0
        for c in range(N):
            ac = a + c
            for d in range(N):
                cd += 1
                if (ab >= cd and ac >= b + d) and not (a == b and c == d):
                    calculated.append((a, b, c, d))
                    calculated.append((c, d, a, b))
                    calculated.append((b, a, d, c))
                    calculated.append((d, c, b, a))

missing = all_combinations - set(calculated) - set(zeroes)

if missing:
    print "Some sets weren't calculated :"
    for s in missing:
        print s
else:
    print "All cases were covered"
    print len(calculated)

使用and not (a==b and c==d)，该数字降至88。

关于python - 如何在此循环中利用排列对称性？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/42822401/