переполнение, встречающееся в длинных скейлерах при стресс-тестировании для максимального попарного продукта

Question

Я пытаюсь провести стресс-тестирование по алгоритму максимального парного произведения, где ограничения: 2 <= n <= 2.10^5; 0 <= a1,...,an <= 2.10^5, где n - длина массива, а a1,a2,...,an - элемент списка. Когда я запускаю код, показанный ниже, он выдает ошибку «1004 *». Этого можно избежать в 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

Ошибка, которую вы получаете, связана с вашим типом данных, как обсуждается в этого похожего вопроса . Я думаю, что решение состоит в том, чтобы указать тип данных как 64-битный тип данных. Вы можете сделать это при создании вектора:

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

"np.float64" заставляет код работать на меня. Это все еще делает то, что вы собираетесь делать? В противном случае вы также можете посмотреть другие 64-битные типы данных , такие как "int64" и "uint64".