长缩放器在对最大成对产品进行压力测试时遇到溢出

Question

我正在尝试对最大成对乘积算法进行压力测试，其中约束是 2 <= n <= 2.10^5; 0 <= a1,...,an <= 2.10^5，其中 n 是数组的长度，a1,a2,...,an 是元素列表。当我运行下面显示的代码时，它给我一个错误 overflow encountered in long scalers。这可以在 c 中使用 long long 避免，但如何在 python 中避免。请帮助。

我的代码

# python3
import numpy as np

def max_pairwise_product(numbers):

    n = len(numbers)
    max_product = 0
    for first in range(n):
        for second in range(first + 1, n):
            max_product = max(max_product, (numbers[first] * numbers[second]))

    return max_product

def fast_max_pairwise_product(numbers):

    max_num = max(numbers)  
    numbers.remove(max_num)
    sec_max_num = max(numbers)
    max_product = max_num * sec_max_num

    return max_product

while(True):
    n = np.random.randint(0,1000) + 2
    print(n)
    vector = list(np.random.randint(0,1000000, n))
    print(vector)
    res1 = max_pairwise_product(vector)
    res2 = fast_max_pairwise_product(vector)
    if(res1 != res2):
        print('Wrong Answer', res1, ' ' , res2)
        break
    else:
        print()

错误

C:/Users/INTEL/Desktop/Algorithm Specialization/Algorithm toolbox/Week 1/week1_programming_challenges/2_maximum_pairwise_product/stress_test.py:11: RuntimeWarning: overflow encountered in long_scalars
  max_product = max(max_product, (numbers[first] * numbers[second]))
C:/Users/INTEL/Desktop/Algorithm Specialization/Algorithm toolbox/Week 1/week1_programming_challenges/2_maximum_pairwise_product/stress_test.py:23: RuntimeWarning: overflow encountered in long_scalars
  max_product = max_num * sec_max_num

Answer 1

您遇到的错误与您的数据类型有关，如 this similar question 中所述。我认为解决方案是将数据类型指定为 64 位数据类型。您可以在创建矢量时执行此操作：

vector = list(np.float64(np.random.randint(0,1000000, n)))

"np.float64" 让代码对我有用。它仍然做你打算做的事吗？否则你也可以看看 other 64-bit datatypes，比如 "int64" 和 "uint64".

长缩放器在对最大成对产品进行压力测试时遇到溢出

overflow encountered in long scalers while stress testing for maximum pair-wise product

python

algorithm

stress-testing