Почему запуск фрагмента из массива занимает дополнительное время? - PullRequest
Новая
       5

Почему запуск фрагмента из массива занимает дополнительное время?

0 голосов
/ 13 апреля 2020 
def is_prime(n, req):
    for i in req[1:]:
        if i*i>n:
            break
        if n%i==0:
            return False
    return True

def find_primes(n):
    if n<3:
        return 0
    req = [2]
    for x in range(3,n,2):
        if is_prime(x, req):
            req.append(x)
            print(req)
    return req
  # Fill this in.

print(find_primes(499979))

Этот код занимает намного больше времени, чем 

def is_prime(n, req):
    for i in req:
        if i*i>n:
            break
        if n%i==0:
            return False
    return True

def find_primes(n):
    if n<3:
        return 0
    req = [2]
    for x in range(3,n,2):
        if is_prime(x, req):
            req.append(x)
            print(req)
    return req
  # Fill this in.

print(find_primes(499979))

Возьмите лут в функции "is-prime", внутри которой массив "req" для l oop в обоих кодах , Этот код для поиска простых чисел. Но почему 2-й выполняется в сроки, а первый - нет? Первый должен работать немного быстрее, поскольку мы пропускаем первый элемент, но почему это не так? First Code execution

2nd code execution

1 Ответ

2 голосов
/ 13 апреля 2020

Пропуск стоимости одного элемента не экономит время, если это означает выполнение копирования для других элементов n - 1. req[1:] делает совершенно новый list, в котором пропущен первый элемент, а для достаточно большого req стоимость значительно перевесит фиксированную стоимость тестирования одного дополнительного значения.

Вероятно, не стоит пропускать этот элемент, но если вы хотите сделать это без накладных расходов на элемент, вы можете сделать: 

def is_prime(n, req):
    req = iter(req)  # Convert to iterator
    next(req, None)  # Skip first element, if any
    for i in req:    # Iterate remainder with no additional overhead
    # Remainder of function unmodified

Вы можете использовать itertools.islice для достижения аналогичного эффекта с фиксированными накладными расходами памяти: 

def is_prime(n, req):
    for i in itertools.islice(req, 1, None):    # Iterate all but first element
    # Remainder of function unmodified

но этот будет иметь небольшое количество накладных расходов на элемент, поскольку итерация всегда будет проходить через объект islice для получения каждого базового элемента.

...