Вопрос по math, python – Простой генератор Python в одну строку

6

Я пытаюсь создать генератор простых чисел в одной строке Python, как забавное упражнение.

Следующий код работает должным образом, но он слишком медленный:

primes = lambda q: (i for i in xrange(1,q) if i not in [j*k for j in xrange(1,i) for k in xrange(1,i)])
for i in primes(10):
   print i,

Поэтому я попытался сделать это, проверив только квадратный корень из j и k:

primes = lambda q: (i for i in xrange(1,q) if i not in [j*k for j in xrange(1,int(round(math.sqrt(i)+1))) for k in xrange(1,int(round(math.sqrt(i)+1)))])
for i in primes(10):
   print i,

Но это выводит:2 3 5 6 7 8

Так что, должно быть, что-то не так с моими индексами j и k, но я не понимаю.

Если вы можете жить с не oneliner, то есть такой вопрос: / Stackoverflow.com вопросы / 567222 / ... Andy♦
Мне удалось сделать это в две строки: Stackoverflow.com / а / 9302299/5987 Mark Ransom
Вы всегда можете воспользоваться тем, что МОЖЕТ обратиться к списку, который в данный момент создается внутри списка, используя выражениеlocals['_[1]']. APerson

Ваш Ответ

4   ответа
12

хотя выглядит так. На самом деле все намного хуже. Сито - лучший алгоритм для поиска простых чисел.

Видетьhttp: //en.wikipedia.org/wiki/Sieve_of_Eratosthene

редактироват: Я изменилhttps: //stackoverflow.com/a/9302299/71108 Быть однострочным (изначально это было не настоящее сито, но теперь это ... вероятно ...):

reduce( (lambda r,x: r-set(range(x**2,N,x)) if (x in r) else r), 
        range(2,N), set(range(2,N)))

Demo:

>>> primesUpTo(N): lambda N: reduce(...)
>>> primesUpTo(30)
{2, 3, 5, 7, 11, 13, 17, 19}

Кажется, я думаю, что, хотя это было бы эффективно в функциональном языке программирования, это может быть не так эффективно в Python из-за непостоянных (совместно используемых и неизменяемых) структур данных, и любое сито в Python должно было бы использовать мутацию для достичь сопоставимой производительности. Мы можем все еще втиснуть это в одну строчку, если бы мы отчаянно хотели. Но сначала..

Нормальное сито:

>>> N = 100
>>> table = list(range(N))
>>> for i in range(2,int(N**0.5)+1):
...     if table[i]:
...         for mult in range(i**2,N,i):
...             table[mult] = False
... 
>>> primes = [p for p in table if p][1:]
>>> primes
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

Теперь мы можем определять и вызывать анонимные функции в одной строке, а также взломать[...].__setitem__ чтобы сделать встроенную мутацию, и взломать... and foo оценить... возвращаясьfoo:

>>> primesUpTo = lambda N: (lambda table: [[table.__setitem__(mult,False) for mult in range(i**2,N,i)] for i in range(2,int(N**0.5)+1) if table[i]] and [p for p in table if p][1:])(list(range(N)))
>>> primesUpTo(30)
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

Продолжая сжиматься от ужаса, расшифровывался однострочник (странно красиво, потому что можно было почти напрямую перевести поток управления, но при этом ужасно злоупотреблять всем):

lambda N:
    (lambda table: 
        [[table.__setitem__(mult,False) for mult in range(i**2,N,i)] 
            for i in range(2,int(N**0.5)+1) if table[i]] 
        and [p for p in table if p][1:]
    )(list(range(N)))

Эта однорядная мутантная версия сдавалась около 108 на моей машине, в то время как оригинальная мутантная версия сдавалась около 109, не хватает памяти (странно).

Оригиналreduce версия сдалась в 107. Так что, возможно, это нечт неэффективно в конце концов (по крайней мере, для номеров, с которыми вы можете иметь дело на вашем компьютере).

Edit2 Кажется, вы можете использовать побочные эффекты более кратко:

reduce( (lambda r,x: (r.difference_update(range(x**2,N,x)) or r)
                     if (x in r) else r), 
        range(2,N), set(range(2,N)))

Сдается около 108, так же, как мутантная версия с одной строкой.

Edit3: Это работает в O (N) эмпирическая сложность, тогда как безdifference_update он побежал наO (n ^ 2.2) сложность.

Ограничение диапазона, который уменьшен, до sqrt верхнего предела и работает только с коэффициентами, оба приводят к дополнительным ускорениям 2x а также 1.6x соответственно):

reduce( (lambda r,x: (r.difference_update(range(x*x,N,2*x)) or r)
                     if (x in r) else r), 
        range(3, int((N+1)**0.5+1), 2),
        set([2] + range(3,N,2)))
На самом деле лучшие сита существуют для поиска простых чисел. Я считаю, что нынешний чемпион - это решетка Аткинса. Но Эратосфен достаточно хорош практически для всего, что вы хотите. btilly
(если кому-то интересно, почему я продолжаю редактировать / редактировать, это потому, что очень трудно определить, имеет ли неортодоксальная реализация Sieve время выполнения En.wikipedia.org / вики / ...; все еще даже сейчас проверяя ... к сожалению, я думаю, что, хотя это было бы эффективно в функциональном языке программирования, оно неэффективно в python из-за неразделенных структур данных, и любое сито в python должно было бы использовать мутацию) ninjagecko
@ DavidRobinson: он явно явно больше беспокоился о скорости своего ответа, что напрямую связано с алгоритмом. Подобные алгоритмы начнут работать медленно, возможно, при 10000+, и потерпят неудачу при 1000000+. Во всяком случае, с тех пор я отредактировал свой ответ, чтобы дать реальную однострочность. ninjagecko
Правда, но это не устраняет ошибку в его однострочнике. David Robinson
@ MarkRansom нет, это то, что делает истинное Сито Эратосфена, это Делает удалить кратныенесколько ра - один раз для каждого из главных факторов числа. Это потому, что он не «удаляет» их при работе с массивами - этоМетк их. Удаление записи из массива нарушило бы произвольный доступ, который является ключом к эффективности сита - каждыйотмечат занимает O (1) раз. С наборами это, вероятно, O (log (size-of-set)), так что немного хуже. И улучшение вычеркиваниrange(i**2,N,2*i) действительно требует редактирования, ИМХО (особенно с наборами). :) (обратите внимание, это2*i при работе только с коэффициентами). Will Ness
3

чтобы проверить на простое число. Посмотрите на 8 - квадратный корень из 8 равен 2.8, поэтому он никогда не будет пытаться 4 * 2. (Действительно, единственные числа, которые Не будет простые числа являются квадратными числами).

ETA: вместо того, чтобы пробовать все возможные комбинации j и k, почему бы не проверить, делится ли i на каждое j (используяi % j == 0) до квадратного корня из j? Это требует меньше кода и намного эффективнее (хотя все еще не почти столь же эффективен, как сито Эратосфена).

3

Вот что ты хотел:

def primes (q) :
 # return (i for i in xrange(2,q) if i not in [j*k for j in xrange(1,i) for k in xrange(1,i)])
 # return (i for i in xrange(2,q) if i not in [j*k for j in xrange(1,i) for k in xrange(1,j+1)])
 # return (i for i in xrange(2,q) if i not in [j*k for j in xrange(1,i/2+1) for k in xrange(1,j+1)])

 return (i for i in xrange(2,q) if i not in [j*k for j in xrange(1,i/2+1) for k in xrange(1,min(j+1,i/j+1))])

В Хаскеле диапазоны включены, поэтомуprimes(542) являетс

[n | n<-[2..541], not $ elem n [j*k | j<-[1..n-1],     k<-[1..n-1]]]  --  25.66s
[n | n<-[2..541], not $ elem n [j*k | j<-[1..n-1],     k<-[1..j]]]    --  15.30s
[n | n<-[2..541], not $ elem n [j*k | j<-[1..n`div`2], k<-[1..j]]]    --   6.00s
                                                                      --   0.79s
[n | n<-[2..541], not $ elem n [j*k | j<-[1..n`div`2], k<-[1..min j (n`div`j)]]] 

И вообще-то,1*x == x так1 не нужен как множитель, поэтому он должен быть

[n | n<-[2..541], not $ elem n [j*k | j<-[2..n`div`2], k<-[2..min j (n`div`j)]]] 

который занимает всего 0,59 секунды. Или в Python,

def primes (q) :
 return (i for i in xrange(2,q) if i not in [j*k for j in xrange(2,i/2+1) for k in xrange(2,min(j+1,i/j+1))])

Обновить по какой-то причине,min j ... не имеет большого значения, по крайней мере, в Haskell. Таким образом, выражение становится просто

[n | n<-[2..541], not $ elem n [j*k | j<-[2..n`div`2], k<-[2..n`div`j]]] 
1

Как насчет

def primes(x):
  return [i for i in range(2,x) if 0 not in [i%j for j in range(2,i)]]
Вы можете переписать это немного короче: def primes (x): return [i для i в диапазоне (2, x), если все ([i% j для j в диапазоне (2, i)])] Eitan
Вы должны добавить регистр, если число больше 1, как показано ниже:[i for i in range(2,x) if ((0 not in [i%j for j in range(2,i)]) and i > 1)] Atıfcan Ergin
Зачем? это покрытоi in range(2,x) Questions

Похожие вопросы