Как я могу минимизировать код, чтобы он был более эффективным в Python3? - PullRequest
0 голосов
/ 17 сентября 2018

У меня были проблемы на сайте www.spoj.com, и проблема с основным генератором привлекла мое внимание как хорошая проблема прогрева для начала.Проблема проста и легко кодируется.Но каждый раз, когда я отправляю свой код, я получаю ошибку во время выполнения.Я предполагаю, что это проблема эффективности кода, и я хотел бы расширить свои знания о том, что эффективно с памятью, а что нет.
https://www.spoj.com/problems/PRIME1/

import numpy as np
run_times = int(input())
for i in range(run_times):
    search_range = list(map(int, input().split()))
    for j in range(search_range[0], search_range[1]):
        a = j%np.arange(2, j)
        if 0 in a:
            pass
        elif 0 not in a and j>0 :
            print(j)

1 Ответ

0 голосов
/ 18 сентября 2018

Это далеко не оптимально, но это простая переделка, которая должна значительно улучшить скорость вашего кода и исправить пару ошибок:

import numpy as np

run_times = int(input())

for _ in range(run_times):
    start, stop = map(int, input().split())

    for number in range(max(start, 2), stop + 1):

        array = number % np.arange(2, int(number ** 0.5) + 1)

        if 0 not in array:
            print(number)

В отношении ошибок, ваш код выводит 1 как простое число, но это не должно. Кроме того, учитывая диапазон «3 5», ваш код выводит «3», но в примере показано «3 5», поэтому у вас неправильно установлена ​​конечная точка. Наконец, ваш j > 0 запаздывает в вашем коде (после того, как вы закончите работу, вы в конечном итоге выбросите его), и в этом нет необходимости, поскольку проблема указывает на минимум 1 в качестве ввода.

По скорости рассмотрим наихудший случай на основе описания проблемы:

1
999900000 1000000000

Мой исправленный код должен решить эту проблему всего за минуту. Я не верю, что ваш найдет его первым за это время. Если это не достаточно быстро, это еще не все. (Например, g рассматривают 2 как особый случай и вычисляют только с нечетными числами; повторно используйте вычисления вместо их бросания и т. Д.)

Все это не касается эффективности памяти - все дело в использовании правильного алгоритма.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...