Путаница с набором и реализацией решета Эратосфена

Я хотел сначала предисловие, что я новичок в python и что я любезен со всеми, кто может объяснить это мне ясно и полностью.

Я смотрел на код, найденный в ссылке ниже:

http://rosettacode.org/wiki/Sieve_of_Eratosthenes#Python

Я только начал понимать итераторы, генераторы и команду yield, но я не понимаю, как работает код для реализации набора.

def eratosthenes2(n):
    multiples = set()
    for i in range(2, n+1):
        if i not in multiples:
            yield i
            multiples.update(range(i*i, n+1, i))

Мне трудно понять, что делает последняя строка в этой функции.

Кроме того, может ли кто-нибудь объяснить мне, почему эта реализация занимает время O (log (n))?


python sieve-of-eratosthenes
person Roger Josh    schedule 20.10.2015    source источник
comment
Спасибо, Грегор. Я ценю, что вы нашли время, чтобы сказать мне об этом, и я обязательно буду помнить об этом в следующий раз, когда я застряну на проблеме.   -  person Roger Josh    schedule 26.12.2015

Ответы (2)


arrow_upward
1
arrow_downward

Выражение range(i, j, k) создает список целых чисел от i до j (j не включает, поэтому включающая граница равна j-1) с интервалами k (что по умолчанию равно 1). Итак, range(2, 10, 2) создает список [2, 4, 6, 8].

Последняя строка вставляет все кратные i от i2 до n в набор multiples. Мы начинаем с i2, потому что i — простое число (поскольку оно не было найдено в решете), а следующее наименьшее кратное i, не входящее в multiples, равно i i. Доказательство: если бы ближайшее наименьшее кратное i было значением, равным c i для некоторого c, где 1 ‹ c ‹ i, то мы бы уже отфильтровали его в решете. Мы заканчиваем диапазон на n+1, потому что там заканчивается решето (1 компенсирует тот факт, что конечная граница не включает). И, конечно же, наш интервал установлен на i, чтобы получить его кратность.

Бит о O (log (n)) относится к временной сложности членства набора тестирования в реализациях общего набора, а не к полному алгоритму. Сложность всего алгоритма не может быть меньше O(n), так как внешний цикл выполняется n-1 раз (от 2 до n). На самом деле, проверка принадлежности набора занимает O(1) времени, поскольку наборы Python представляют собой хеш-таблицы. В качестве альтернативы вы можете использовать list из n bools, которые будут иметь лучшую производительность за счет места.

person mooiamaduck    schedule 20.10.2015
comment
Большое спасибо! Я ценю, что вы нашли время, чтобы помочь мне понять - person Roger Josh; 20.10.2015

arrow_upward
1
arrow_downward

Последняя строка:

multiples.update(range(i*i, n+1, i))

Добавляет все кратные i из квадрата i до n в набор multiples. Любое число, кратное меньше квадрата i, уже будет в наборе из более раннего i.

Розетта не говорит, что алгоритм - это O (log (n)), это, конечно, не так, но просто поиск множества - это O (log (n)) по сравнению со списком O (n). Причина в том, что наборы используют хеширование как средство поиска и на самом деле в среднем O (1) против O (n)

person AChampion    schedule 20.10.2015
comment
Поиск Python set — это O(1), а не O(log n); он основан на хэшировании, а не на двоичных деревьях или чем-то еще. На практике это обычно немного больше, чем одна проверка благодаря цепочке коллизий, но она не привязана к размеру set значимым образом. - person ShadowRanger; 20.10.2015
comment
Я думал, что описал это в своем последнем предложении, я что-то пропустил? - person AChampion; 20.10.2015
comment
Первое предложение в этом абзаце подразумевает, что ожидаемое время будет O(log n). Ошибка на стороне Розетты; извините за путаницу. - person ShadowRanger; 20.10.2015
comment
Согласитесь, Rosetta завышает стоимость поиска набора (в среднем), лучший источник: wiki.python. org/moin/TimeComplexity - person AChampion; 20.10.2015