На практическом упражнении по простым числам я обнаружил, что filter
сам по себе не возвращает список, и мне нужно сделать:
list(filter())
чтобы получить этот список.
Я делаю это упражнение дважды, один раз с циклом for:
def is_prime_for(n:init):
if n <=3:
return True
else:
m=list(range(2,n//2+1)) #+1 on the range for evade a bad result if 'n==4'
for i in m:
if n % i == 0:
return False
else:
return True
value = 864203
print(is_prime_for(value))
в другой раз с filter
и lambda
:
def is_divisible(num1:float,num2:float):
if num1 % num2 == 0:
return True
else:
return False
def is_prime(num:int):
if list(filter(lambda x: is_divisible(num,x), list(range(2,num//2+1)))) != []:
return False
else:
return True
value = 864203 #Same prime number that i found on google
print(is_prime(value))
Позже я повторно использую код для функций более высокого порядка и обнаруживаю, что выполнение моей «компактной» функции filter
и lambda
занимает вдвое больше времени, чем выполнение функции, и многое другое с «ложным» числом (например, числом, которое можно разделить на 2). ).
Я могу понять двойное время, потому что оно проходит по списку дважды, а не один раз, но в случае с «ложным» номером я думал, что filter() выдаст мне пустой список до тех пор, пока не появится первое число, но это не так. , список «пустой» до завершения фильтрации.
Кто-нибудь знает способ «обновить» список отфильтрованных элементов один раз, а не в конце фильтрации?
Теперь это мой код с функцией более высокого порядка, показывающей время выполнения:
import time
def timeis(func): #Decorator that reports the execution time.
def wrap(*args, **kwargs):
start = time.time()
result = func(*args, **kwargs)
end = time.time()
print(func.__name__, end-start)
return result
return wrap
def is_divisible(num1:float,num2:float):
if num1%num2 == 0:
return True
else:
return False
@timeis
def is_prime(num:int):
if list(filter(lambda x: is_divisible(num,x),list(range(2,num//2+1)))) != []: #+1 on the range for evade a bad result if 'n==4'
return False
else:
return True
@timeis
def is_prime_for(n : int = 2):
if n <= 3:
return True
else:
m = list(range(2,n//2+1))
for i in m:
if n%i == 0:
return False
else:
return True
value = 864203 #A prime number that i found on google
#print(is_prime(value)) #That is used for prove the value find on google for no "false" positives
is_prime(value)
is_prime_for(value)
и это вывод:
is_prime 0.06304740905761719
is_prime_for 0.02378678321838379
**
**
После тестирования с кодом из ответа и комментариями конец кода выглядит следующим образом:
import time
def timeis(func): #Decorator that reports the execution time.
def wrap(*args, **kwargs):
start = time.time()
result = func(*args, **kwargs)
end = time.time()
print(func.__name__, end-start)
return result
return wrap
def is_divisible(num1:float,num2:float):
if num1%num2 == 0:
return True
else:
return False
@timeis
def is_prime(num:int):
if any(is_divisible(num,x) for x in range(2,int(num**0.5+1.01))): #Improved math with @Trincot answer and the help of @OneCricketeer on comments section
return False
else:
return True
@timeis
def is_prime_all(num: int): #@Trincot answer
return all(num%x for x in range(2, int(num**0.5+1.01)))
@timeis
def is_prime_all_mod(num: int): #@Trincot answer 'moded', it's faster on "False" numbers
return all(num%x for x in range(2, num//2+1))
@timeis
def is_prime_for(n : int = 2): #Improved math with @Trincot answer
if n <= 3:
return True
else:
m = range(2,int(n**0.5+1.01))
for i in m:
if n%i == 0:
return False
else:
return True
@timeis
def is_prime_while(n : int = 2): #Improved math with @Trincot answer
if n <= 3:
return True
else:
x = int(n**0.5+1.01)
i = 2
while i < x:
if n % i == 0:
return False
i+=1
else:
return True
#value = 28122221 #A prime number that i found on google
value = 28122222 #A "false" prime number for tests
#print(is_prime(value))
is_prime(value)
is_prime_all(value)
is_prime_all_mod(value)
is_prime_for(value)
is_prime_while(value)
С выходом с «реальным» простым числом:
is_prime 0.00029087066650390625
is_prime_all 0.0001399517059326172
is_prime_all_mod 0.607919454574585
is_prime_for 0.0001266002655029297
is_prime_while 0.00017380714416503906
И вывод, если число не является простым, например:
is_prime 1.0013580322265625e-05
is_prime_all 7.152557373046875e-06
is_prime_all_mod 1.6689300537109375e-06
is_prime_for 1.1920928955078125e-06
is_prime_while 4.76837158203125e-07
Вам также нужно выполнять итерацию только до квадратного корня из num (а не до половины + 1) и только с шагом в два. (Или, что еще лучше, используйте кэширование, чтобы перебирать простые числа только до квадратного корня из num.)
@OneCricketeer Действительно ли any
замкнет его? Насколько я понимаю, полный список все еще рассчитывается до применения any
.
@MichaelCao Согласно кодовому блоку в документации, он возвращает первое истинное значение docs.python.org/3/library/functions.html#any ; если передается выражение генератора, то весь список не будет повторяться
@OneCricketeer да, большое спасибо, any()
сделайте его намного чище, чем фильтр, но он все равно принимает полный список, потому что он создается перед передачей any()
any()
принимает итерацию. Это означает, что он может работать на генераторе и материализовать следующее значение только тогда, когда это необходимо (лень). Это означает, что он не генерирует все значения сначала. Он также останавливается на первом истинном значении, что означает, что ему не нужно генерировать/оценивать все элементы, если таковые имеются.
Откуда такая одержимость списками? Также list(range(...))
. Просто переберите диапазон.
@nocomment, это не одержимость, я изучаю Python (с 30-дневным репозиторием, ссылкой, другими веб-сайтами с «упражнениями» и некоторыми «изменениями», которые я пробую сам, чтобы посмотреть, сработает ли это) и без опыта , я стараюсь сделать как можно более чисто, и (в моем коде), если вы попытаетесь отфильтровать диапазон, каждый раз if
возвращайте True
, потому что фильтр возвращает что-то вроде <filter object at 0x7f8dcc30fc40>
и python
принимает это выражение действительным для if
. С any()
всё работает корректно any(is_divisible(num,x) for x in range(2,num//2+1))
Здесь есть несколько вещей, которые можно улучшить:
Нет необходимости применять list
к диапазону второго аргумента filter
. фильтр просто нуждается в итерации в качестве второго аргумента, поэтому диапазон подойдет.
Нет необходимости применять list
к результату filter
, если цель состоит в том, чтобы убедиться, что filter
не дает результатов. В этом случае вы можете использовать any
вместо filter
. Если вы используете противоположное условие для фильтрации, вы можете использовать all
.
От следующего шаблона стоит избавиться:
if <boolean-expression>:
return True
else:
return False
Вместо этого просто верните значение логического выражения.
Вы дали is_prime_for
небольшое преимущество, заставив его выполнять операцию по модулю в строке, в то время как is_prime
для этого необходимо вызвать функцию. Чтобы иметь равные условия игры, is_prime
также следует выполнить эту операцию по очереди.
Обе реализации могут добиться большего успеха, ограничив поиск делителей квадратным корнем из n
. Любой больший делитель будет иметь меньшую противоположную часть. Например, если n
имеет n//2
в качестве делителя, то он также имеет 2 в качестве делителя, поэтому нет необходимости проверять оба.
Это подводит нас к следующей версии кода:
@timeis
def is_prime(num: int):
return all(num%x for x in range(2, int(num**0.5+1.01)))
Возможны дальнейшие улучшения .
Большое спасибо за вашу помощь, я слишком многому научился благодаря этому. Я улучшил свой код благодаря вашему ответу, ответам в разделе комментариев и доказательству с циклом while
. Ваш самый быстрый на реальном простом числе, за которым следует цикл while
(но с вашим математическим выражением), но я попробовал несколько случаев для лучшего понимания функций и с «ложным» простым числом (делящимся на 2) int()
замедлился (минимум всего 10^-5 из 10^-6 секунд для вашего и 10^-6 из 10^-7 для while
) код и выражение (2//2+1) были быстрее, потому что они возвращали int напрямую без конвертации.
Да, если вы запустите код с четным числом n, возведение в степень замедлит его. Но есть много оптимизаций, которые вы можете реализовать, например, изолировать проверку четности, чтобы вы могли переходить на 2 в диапазоне (начиная с 3 вместо 2), и это можно дополнительно улучшить, внедрив колесо и т. д. и т. д. Это действительно огромная тема, которая обсуждалась в других вопросах и ответах. Я просто сосредоточился на вашем вопросе.
Похоже, вам нужна функция
any()
, а неfilter()
, если вы ожидаете короткого замыкания во время итерации, например.if not any(is_divisible(num, x) for x in range(2,num//2+1))