优化 Python 代码以查找满足特定不等式的索引对

Question

我有一个Python代码可以有效地解决我的任务，但我担心它的时间复杂度。 任务是找到不等式 aᵢ ⊕ aʲ ≥ bᵢ ⊕ bʲ 成立的索引对 (i, j) 的数量，给定两个整数数组“a”和“b”，每个数组的长度为“n”。这里，⊕表示异或运算。

这是我当前的实现：

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

count = 0

for i in range(n):
    for j in range(n):
        if a[i] ^ a[j] >= b[i] ^ b[j]:
            count += 1

print(count)

虽然此代码适用于小输入，但由于其嵌套循环结构，我担心其对于较大数组的性能，导致时间复杂度为 O(n²)。我正在寻求有关如何优化此代码以提高其运行时效率的建议，特别是对于较大的输入大小。

任何可以实现更好时间复杂度的见解或替代方法将不胜感激。

Answer 1

使用 Numpy 提高了代码效率。
比较：

• a 和 b 上 10K 条目的代码，运行时间：0:00:46.925000
• 基于 NumPy 的代码，在 a 和 b 上运行 10K 条目，运行时间：0:00:00.453003，即快了近 100 倍

import datetime
import numpy as np

n = 10000
a = [1,2,3,4,5,16,17,18,19,20] * int(n/10)  # List with 10 K items created for testing
b = [10,9,8,7,6,11,12,13,14,15] * int(n/10)  # List with 10 K items created for testing

print("Len a : ", len(a))
print("Len b : ", len(b))

######### Your Code Test ######################
count = 0
print("Starting your code test")
start = datetime.datetime.now() # Start time
for i in range(n):
    for j in range(n):        
        if a[i] ^ a[j] >= b[i] ^ b[j]:
            count += 1

end = datetime.datetime.now() # end time
delta = end-start 
     
print("Your code time delta : ", delta)
print("Result : ", count)


############## New Code test #######################

count = 0
print("Starting new code test")
start = datetime.datetime.now() # Start time

a_arr = np.array(a).reshape(-1,1)
a_arr_biwise = np.bitwise_xor(a_arr, a_arr.transpose())  #bitwise XOR of array on itself

b_arr = np.array(b).reshape(-1,1)
b_arr_biwise = np.bitwise_xor(b_arr, b_arr.transpose())  #bitwise XOR of array on itself

comparison_matrix = np.greater_equal(a_arr_biwise,b_arr_biwise) # axor >= bxor comparison on each position.
count = comparison_matrix.sum() # find True count , i.e. where >= is True

end = datetime.datetime.now() # end time
delta = end-start      

print("New code time delta : ", delta)
print("Result : ", count)

输出

Len a :  10000
Len b :  10000
Starting your code test
Your code time delta :  0:00:46.925000
Result :  80000000
Starting new code test
New code time delta :  0:00:00.453003
Result :  80000000

可以看到两个代码的结果是相同的。

Answer 2

1. 由于 xor 是对称的：a[i] ^ a[j] == a[j] ^ a[i] （对于 b 也是如此），因此您可以将内部循环减少到 j>i。

2. 由于 a[i] ^ a[i] >= b[i] ^ b[i] 始终为 true，因此您也可以跳过这种情况。

这不会提高复杂度 O(n²)，但速度至少会提高一倍。

     n = int(input())
     a = list(map(int, input().split()))
     b = list(map(int, input().split()))

     count = n  // the cases i==j always fulfills the condition a[i] ^ a[j] >= b[i] ^ b[j]:

     for i in range(n):
         for j =0; j<i; j++ :
             if a[i] ^ a[j] >= b[i] ^ b[j]:
                 count += 2

     print(count)