Прости числа с генератор
# Primes - Initial version
def primes():
number = 2
while True:
if all([number % divisor for divisor in range(2, (number//2) + 1)]):
yield number
number += 1
Това е кода в слайдовете. Но той въобще не е оптимален! (Не, че е писан, за да бъде оптимален...)
С малко математика може значително да се подобри: най-малкото просто число е 2, така че най-голямото число, което има значение е number/2 (всъщност "//", тъй като иначе се получава float на половината числа => error).
# Primes - First version
def primes():
number = 2
while True:
if all([number % divisor for divisor in range(2, number//2)]):
yield number
number += 1
Всичко е добре, появяват се всички прости числа, но има едно НО - числото 4 също се оказва измежду простите! И защо се получава така? Много просто 4//2 = 2, а range функцията прави списък на всички числа до последното число-1. Следователно в списъка ще има само [] (нищо! Nil! Празен, препразен списък!) И в такъв случай се йелдва (принтва) числото. (Между другото, същото нещо става и при 2, 3 и 5 - празен списък.) При числото 6 имаме 2 във списъка (но не и 3?), но 6 се дели на 2 => пропускаме го. Но защо 3 не ни трябва - много просто: 2 * 3 дава 6. 2 вече е просто число, така че няма смисъл да проверяваме с 3. Така че в действителност ние търсим всички числа, които са <= number//2 (точно, което ни дава range). И ако не беше проблема с 4, всичко щеше да е наред.
Но тъй като имаме проблем с 4, се налага да хитруваме:
# Primes - Second version
def primes():
number = 2
while True:
if all([number % divisor for divisor in range(2, (number//2) + 1)]):
yield number
number += 1
Като добавим 1 към number//2 ще получим още едно число (в общия случай ненужно) число, което всеки път трябва да итерираме, но все ще го преглътнем. Така при 4//2 получаваме 2 и като добавим 1 получаваме 3. range(2, 3) дава [2] => 4 няма да се принтва. Което е готино. Но има още по-добър метод!
Засега съкратихме числата за итериране наполовина (почти)! Но ако искаме да проверим дали числото 211 е просто (просто е, вярвайте ми!), има да итерираме през над 100(!) числа* (чети забележката най-долу). Което не е готино. Ама никак!
Защо просто да не итерираме само през простите числа. И това е добра идея! Ето как ще стане:
# Primes - Third version
def primes():
number = 2
prime = []
while True:
if all([number % divisor for divisor in prime]):
prime.append(number)
yield number
number += 1
Така за 211 проверяваме всички прости числа до него (46 на брой). Което е под 25% (а не 50%, както беше досега) от всичките числа до 211. Дори е почти 20%! При 503 (също просто) дори пада под 20%. И продължава да пада! При 1009 (първото просто число над 1000) процента е малко под 17. Доста добре, а?
Но разбира се, може да се оптимизира още! Как? Това ще оставя на вас да си помислите! Ще ви дам само малък hint: за числото 211 се проверяват 12 елемента (преди това малко по-малко от 50), за 503 - 20 (предишни 96), а за 1009 - само 29! А сега мислете хора! Тая вечер ще я публикувам, ако никой не се сети.
===================
Забележка:
* Нека забравим, че all спира веднага след първия False и връща... False. Вярно е, че половината числа се делят на 2, а повечето други се делят на поне някое от другите числа до 10, но може да ви се случи случай, в която да не използвате all и да ви се наложи всеки път да итерирате до края. Което е гадно. Надявам се, че това може да ви научи да хитрувате и не винаги да търсите най-очевидния път, за да си оптимизирате кода.
Но дори с all, положението пак може да не е розово. Напрмиер, ако търсите всички прости числа от 2 до 1,000,000 или дори 1,000,000,000 на компютъра ще му отнеме адски много време докато итерира изцяло при всички прости числа. При 1,000,000,000 ще трябва да итерира през почти 500,000,000 елемента от списъка при последното просто число (и то с моята първа успешна оптимизация. Ако е без нея - итериране през всичките 1,000,000,000 елемента! - двойно повече време. Дори при втората оптимизация вероятно би трябвало да се итерират над 100,000,000 елемента (10% от 1,000,000,000). Въпреки че може и да греша и да е по-малко (но не с много!)). А това хич няма да е бързо! Ама хич!
И напомням - това е само за едно единствено просто число! За предишното просто, разликата няма да е кой знае колко голяма, тъй като надали седи много далеч.
От друга страна, ако се сетите за последната оптимизация, елементите, през които ще трябва да минете при 1,000,000,000 са само 31,621, което в сравнение със 100-тината милиона е нищо.
Така че оптимизацията е хубаво нещо, дори когато го има all (или any).