Неспособность понять некоторый основной синтаксис сита

Может ли кто-нибудь провести меня построчно через это главное сито? Я пытаюсь разработать свое собственное сито, но большинство более быстрых содержат синтаксис, который я не понимаю (например, строки, которые я комментировал). Извините, если это своего рода вопрос новичка - также, если у вас есть какие-либо ссылки, которые могут помочь мне с написанием сит, они будут очень благодарны.

def rwh_primes1(n):
    """ Returns  a list of primes < n """
    sieve = [True] * (n/2) # What does the '[True]' mean?
    for i in xrange(3,int(n**0.5)+1,2):
        if sieve[i/2]: # The same complaint as in line 3, I don't understand the variable 'sieve'
            sieve[i*i/2::i] = [False] * ((n-i*i-1)/(2*i)+1) # how is sieve used here - it seems to be as a list but i'm unsure
    return [2] + [2*i+1 for i in xrange(1,n/2) if sieve[i]] # 'sieve' is confusing me here yet again.
Источник

2 ответа

Решение

Я выделю значение каждой строки кода курсивом и добавлю свои комментарии обычным шрифтом.

sieve = [True] * (n/2)

Объявите новую локальную переменную sieve и инициализировать его в значение [True] * (n/2) , Что означает это выражение? [True] это одноэлементный список, содержащий только логическое значение True, Умножение списка на число повторяет список, поэтому sieve сейчас n/2 -элементный список всех True ценности.

for i in xrange(3, int(n**0.5)+1, 2):

Начните считать с шагом 2, начиная с 3 и заканчивая sqrt(n). Этот конкретный выбор диапазона является оптимизацией алгоритма Sieve: мы могли бы считать от 1 до n с шагом 1, но это было бы менее эффективно.

if sieve[i/2]:

Посмотрите на i/2 й элемент sieve список. Если это True затем продолжайте if ветка. Автор использует i/2 чтобы компенсировать тот факт, что код считается с шагом 2. Таким образом, вы можете работать с более коротким списком и использовать меньше памяти.

sieve[i*i/2::i] = [False] * ((n-i*i-1)/(2*i)+1)

Обновить каждый i-й элемент sieve в False начиная с i*i/2. sieve[i*i/2::i] называется обозначением слайса - поскольку он появляется в левой части назначения, этот код обновит этот фрагмент sieve, Правая часть является повторением трюка со списком-числом-числом. Он вычисляет все False список правильной длины.

return [2] + [2*i+1 for i in xrange(1,n/2) if sieve[i]]

Этот код просто превращает True / False значения в sieve в список простых чисел. Расчет компенсирует тот факт, что sieve не содержит четных чисел, умножая каждый True значение индекса на 2.

Источник

Предположим, что n=7:

    sieve = [True] * (n/2) # What does the '[True]' mean?

Составьте список логических значений True длины половины n. Например, sieve = [True,True,True] (так как 3.5 - это дробная длина, она будет округлена в python2)

Так xrange(3,int(n**0.5)+1,2) будет генератор, который дает нам эту последовательность: []

    for i in 
        if sieve[i/2]: # The same complaint as in line 3, I don't understand the variable 'sieve'
            sieve[i*i/2::i] = [False] * ((n-i*i-1)/(2*i)+1) # how is sieve used here - it seems to be as a list but i'm unsure
    return [2] + [2*i+1 for i in xrange(1,n/2) if sieve[i]] # 'sieve' is confusing me here yet again.

Когда мы видим [i::2] или что-то такое, что просто означает, мы срезаем список с повторяющимися интервалами. Так что, если mylist содержит (0..19):

>>> mylist = range(20)
>>> mylist[0::1]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
>>> mylist[0::2]
[0, 2, 4, 6, 8, 10, 12, 14, 16, 18]
>>> mylist[0::3]
[0, 3, 6, 9, 12, 15, 18]

Попробуйте поиграть с этим сами, чтобы вы с ним познакомились. Так что в этом случае sieve[i*i/2::i] = [False] * ((n-i*i-1)/(2*i)+1) будет устанавливать для каждого i-го значения в списке значение False.

Источник
Другие вопросы по тегам