Re: [Python] numeri primi
Scusate se intervengo molto in ritardo, ma propongo un paio di algoritmi che, hanno tempi paragonabili a quelli migliori, ma risultano molto più semplici. Questo cerca di ottimizzare l'algoritmo: def crivello7(n): if n = 2: return [] c = list(range(3, n, 2)) top=len(c) for primo in c: if primo: base = (primo*primo - 3) // 2 if base = top: break for j in range(base, top, primo): c[j]=0 return [2] + list(filter(None, c)) Questo usa le capacità di Python: def sieveOfEratostenes2(n): if n = 2: return [] sieve = list(range(3, n, 2)) top = len(sieve) for si in sieve: if si: bottom = (si*si - 3) // 2 if bottom = top: break sieve[bottom::si] = [None] * -((bottom - top) // si) return [2] + list(filter(None, sieve)) Come il precedente ma usa numpy: def sieveOfEratostenes3(n): if n = 2: return [] sieve = numpy.arange(3, n, 2, dtype = int) top = len(sieve) for si in sieve: if si: bottom = (si*si - 3) // 2 if bottom = top: break sieve[bottom::si] = 0 return [2] + list(filter(None, sieve)) Sono algoritmi suggeriti, se non sbaglio da Bearophile Ciao -- Daniele www.fugamatematica.blogspot.com giusto! nel verso forse è perché non guardiamo le cose Quando non ci capiamo, ___ Python mailing list Python@lists.python.it http://lists.python.it/mailman/listinfo/python
Re: [Python] numeri primi
Scusate, ho sbagliato a ricostruire l'indentazione: def sieveOfEratostenes2(n): if n = 2: return [] sieve = list(range(3, n, 2)) top = len(sieve) for si in sieve: if si: bottom = (si*si - 3) // 2 if bottom = top: break sieve[bottom::si] = [None] * -((bottom - top) // si) return [2] + list(filter(None, sieve)) def sieveOfEratostenes3(n): if n = 2: return [] sieve = numpy.arange(3, n, 2, dtype = int) top = len(sieve) for si in sieve: if si: bottom = (si*si - 3) // 2 if bottom = top: break sieve[bottom::si] = 0 return [2] + list(filter(None, sieve)) Ciao -- Daniele www.fugamatematica.blogspot.com giusto! nel verso forse è perché non guardiamo le cose Quando non ci capiamo, ___ Python mailing list Python@lists.python.it http://lists.python.it/mailman/listinfo/python
Re: [Python] numeri primi
Enrico Franchi enrico.fran...@gmail.com writes:
A me piace barare:
% time python erat_matrix.py 1000
(array([ 2, 3, 5, ..., 971, 973, 991]),)
python erat_matrix.py 1000 0.61s user 0.12s system 38% cpu 1.930 total
Ho fatto anche di peggio.
Programma per trovare il maggior numero di cifre di pi, con tempo
massimo di esecuzione brevissimo e dimensione massima del file di 4kB
(mi pare fosse una sfida di SPOJ):
v=0
for c in'M31A ... Q\\]cEv:O{o]1y.(g':v=v*95+ord(c)-32
print'3.%d725253'%v
al posto dei puntini ci sono altri ~4000 caratteri della
rappresentazione in base 95 della parte decimale di pi.
7866 cifre calcolate in una frazione di secondo.
E non sono stato l'unico ad avere questa idea, c'erano altri programmi
con risultati simili (però quelli che arrivavano intorno ai 4000 erano
molti di più).
ciao,
Mauro
___
Python mailing list
Python@lists.python.it
http://lists.python.it/mailman/listinfo/python
Re: [Python] numeri primi
Fabrizio (in cc) sta per mettere tutte le sue librerie aggiornate su
Bitbucket [tra parentesi le ha (abbiamo) usate per risolvere un tot di
problemi di Project Eulero].
Qui metto solo il suo sieve.py che ritengo uno dei più veloci esistenti,
Rabin e/o Miller compresi.
Ciao.
Marco.
--
http://beri.it/ - Un blog
http://beri.it/i-miei-libri/ - Qualche libro
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
#
# LICENCE INFORMATIONS:
#
#
# THIS SOFTWARE** IS DISTRIBUTED UNDER THE MIT LICENSE:
# http://opensource.org/licenses/mit-license.php
#
# Copyright (c) 2011 Fabrizio Romano sfab...@gmail.com
#
# Permission is hereby granted, free of charge, to any person obtaining a copy
# of this software and associated documentation files (the Software), to deal
# in the Software without restriction, including without limitation the rights
# to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
# copies of the Software, and to permit persons to whom the Software is
# furnished to do so, subject to the following conditions:
#
# The above copyright notice and this permission notice shall be included in
# all copies or substantial portions of the Software.
#
# THE SOFTWARE IS PROVIDED AS IS, WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
# IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
# FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
# AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
# LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
# OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
# THE SOFTWARE.
from __future__ import division, print_function
from math import ceil, sqrt
from itertools import takewhile
The functions defined in this module assume the input they are passed is
correct. This is done because we need this library to be as fast as possible.
Checking the type of the input during one call to is_prime() wouldn't make that
big difference, but doing that on 10**7 calls would sure be significantly
slower. If you need to check the input for these functions, either do it in your
code before calling them or modify them.
# small primes array
_smallp = ( 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, 101, 103, 107, 109, 113, 127, 131, 137,
139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211,
223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283,
293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379,
383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461,
463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563,
569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643,
647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739,
743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829,
839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937,
941, 947, 953, 967, 971, 977, 983, 991, 997)
def sieve(N):
Return a list of primes = N.
Exploit wheel criterion (dim: 30) and bit masks.
sieve(min(200, _smallp[-1]))
[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, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151,
157, 163, 167, 173, 179, 181, 191, 193, 197, 199]
sieve(10**4)[:30]
[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, 101, 103, 107, 109, 113]
sieve(10**4)[-30:]
[9733, 9739, 9743, 9749, 9767, 9769, 9781, 9787, 9791, 9803, 9811, 9817,
9829, 9833, 9839, 9851, 9857, 9859, 9871, 9883, 9887, 9901, 9907, 9923,
9929, 9931, 9941, 9949, 9967, 9973]
const = 30 # wheel: 2*3*5
if N 2:
# no primes smaller than 2
return []
if N = _smallp[-1]:
# no need to calculate, we just use a part of _smallp
return list(takewhile(lambda p: p=N, _smallp))
# offsets list:
# if you write a number as 30k + c, foreach k there are only 8 numbers that
# could be primes: c = 1, 7, 11, 13, ...
offsets = (1, 7, 11, 13, 17, 19, 23, 29)
# prepare the prime list
p = [2, 3, 5]
dim = 1 + N // const # we need about 1/30 of the original dimension
# To be Parsed list
tp = [0b] * dim
m1,m7,m11,m13,m17,m19,m23,m29=1,11,12,13,14,15,16,17
tp[0] = ~m1
# help dictionary d
# d[a , b] = c == if we want to find the smallest useful multiple of
# (30*pos)+a on tpc, we need the index given by the product of
# [(30*pos)+a][(30*pos)+b] in general.
# If b a, we need [(30*pos)+a][(30*(pos+1))+b]
d = {}
Re: [Python] numeri primi
Il 03/08/2011 11:15, Filadelfo Fiamma ha scritto: come complessità computazionale credo sì... ma non vorrei dire caxxate :D Il 03 agosto 2011 11:10, Marco Marianibir...@gmail.com ha scritto: 2011/8/3 Filadelfo Fiammaphilosga...@gmail.com http://it.wikipedia.org/wiki/Crivello_di_Atkin quest'algoritmo dovrebbe essere uno tra i più rapidi, magari può tornarvi comodo :) ah, dici? http://www.enrico-franchi.org/2011/07/atkin-for-everyone-benchmark.html ___ Python mailing list Python@lists.python.it http://lists.python.it/mailman/listinfo/python ma secondo me piu che questione di computazione, qua è questione di interpretazione, mi spiego meglio, python è un linguaggio interpretato, e ha bisogno di troppi passaggi prima della compilazione... a mio parere, se si vuole fare un programma davvero veloce per trovare i numeri primi, conviene farlo direttamente in assembly ___ Python mailing list Python@lists.python.it http://lists.python.it/mailman/listinfo/python
Re: [Python] numeri primi
2011/8/3 matteo matteo.we...@gmail.com Marco, siccome sto sviluppando un codice per risolvere i sistemi lineari a qualsiasi numero di incognite, posso usare il codice di Fabrizio per semplificare i sistemi? P.S.: era per questo che stavo preparando quell'algoritmo sui primi Dovresti chiedere a lui (che ho rimesso in cc). Comunque mi ha appena segnalato di aver pubblicato la sua libreria: https://bitbucket.org/sfabriz/karma Ciao. Marco. -- http://beri.it/ - Un blog http://beri.it/i-miei-libri/ - Qualche libro ___ Python mailing list Python@lists.python.it http://lists.python.it/mailman/listinfo/python
Re: [Python] numeri primi
On Wed, 03 Aug 2011 20:07:34 +0200, Matteo Presutto matteo.we...@gmail.com wrote: carissimi pythoniani, esiste un modo per sapere in che punto della memoria si trova il valore di una variabile? per dare un idea: come in c++ per i puntatori, così posso collegare due programmi diversi per svolgere una stessa funzione ;) Se ci provi il sistema operativo ti taglia le manine :) Il puntatore in memoria di una variabile ce l'hai con la funzione id(), ma processi diversi non possono accedere alla stessa area di memoria normale. Quello che serve e' la shared memory (in python credo vi si acceda usando il modulo mmap). Questo modo di far collaborare piu' processi tra loro e' causa di morte e distruzione piu' delle guerre, delle carestie e delle religioni. Buona fortuna a coordinare i processi tra loro! -- Daniele Varrazzo - Develer S.r.l. http://www.develer.com ___ Python mailing list Python@lists.python.it http://lists.python.it/mailman/listinfo/python
Re: [Python] numeri primi
Fermi restanti i sacrosanti[0] avvertimenti di piro, 2011/8/3 Daniele Varrazzo p...@develer.com: Se ci provi il sistema operativo ti taglia le manine :) Il puntatore in memoria di una variabile ce l'hai con la funzione id(), ma processi diversi non possono accedere alla stessa area di memoria normale. Quello che serve e' la shared memory (in python credo vi si acceda usando il modulo mmap). Questo modo di far collaborare piu' processi tra loro e' causa di morte e distruzione piu' delle guerre, delle carestie e delle religioni. Buona fortuna a coordinare i processi tra loro! credo che il modo moderno e sano di fare in python quello che vuoi tu sia attraverso il package standard `multiprocessing`[1]. Ti consiglio di leggere bene tutta la documentazione del package, in particolare le note[2], e a meditare attentamente sopra la possibilta` di usare un modello di IPC basato su Queue o Pipe. O alla peggio, su Proxy. In tutti questi casi ci guadagni la possibilita` di distribuire l'elaborazione al di fuori del boundary del singolo server. [0] ramen a Sua Spaghettosita` FSM [1] http://docs.python.org/dev/library/multiprocessing#sharing-state-between-processes [2] http://docs.python.org/dev/library/multiprocessing#programming-guidelines Cheers, © -- Carlo Miron FSM Bless Ya Solution Architect™ ___ Python mailing list Python@lists.python.it http://lists.python.it/mailman/listinfo/python
Re: [Python] numeri primi
se vuoi far comunicare due processi davvero indipendenti o che devono restare tali, ti consiglio di dare una occhiata a zeromq oppure a dbus. Il giorno 03/ago/2011 22:03, Carlo Miron ca...@miron.it ha scritto: Fermi restanti i sacrosanti[0] avvertimenti di piro, 2011/8/3 Daniele Varrazzo p...@develer.com: Se ci provi il sistema operativo ti taglia le manine :) Il puntatore in memoria di una variabile ce l'hai con la funzione id(), ma processi diversi non possono accedere alla stessa area di memoria normale. Quello che serve e' la shared memory (in python credo vi si acceda usando il modulo mmap). Questo modo di far collaborare piu' processi tra loro e' causa di morte e distruzione piu' delle guerre, delle carestie e delle religioni. Buona fortuna a coordinare i processi tra loro! credo che il modo moderno e sano di fare in python quello che vuoi tu sia attraverso il package standard `multiprocessing`[1]. Ti consiglio di leggere bene tutta la documentazione del package, in particolare le note[2], e a meditare attentamente sopra la possibilta` di usare un modello di IPC basato su Queue o Pipe. O alla peggio, su Proxy. In tutti questi casi ci guadagni la possibilita` di distribuire l'elaborazione al di fuori del boundary del singolo server. [0] ramen a Sua Spaghettosita` FSM [1] http://docs.python.org/dev/library/multiprocessing#sharing-state-between-processes [2] http://docs.python.org/dev/library/multiprocessing#programming-guidelines Cheers, © -- Carlo Miron FSM Bless Ya Solution Architect™ ___ Python mailing list Python@lists.python.it http://lists.python.it/mailman/listinfo/python ___ Python mailing list Python@lists.python.it http://lists.python.it/mailman/listinfo/python
Re: [Python] numeri primi
2011/8/2 Marco Mariani bir...@gmail.com 2011/8/2 matteo matteo.we...@gmail.com non me ne intendo molto di programmazione, sono alle prime armi, ma secondo voi è buono un codice che riesce in 5 secondi a trovare tutti i numeri primi da 1 a 100? (ho un intel i3 da 3 ghz) in assoluto? dipende :-) marco@aigor:~$ time primes 1 100 /dev/null real0m0.018s user0m0.016s sys0m0.000s Usando un algoritmo scritto (in Python) da un amico: timeit.timeit(import km;km.sieve(100), number=1) 0.12970614433288574 timeit.timeit(import km;km.sieve(1000), number=1) 1.3863430023193359 timeit.timeit(import km;km.sieve(1), number=1) 14.972478151321411 Bravo il mio amico, eh? :-) Ciao. Marco. -- http://beri.it/ - Un blog http://beri.it/i-miei-libri/ - Qualche libro ___ Python mailing list Python@lists.python.it http://lists.python.it/mailman/listinfo/python
Re: [Python] numeri primi
senza entrare in merito ai tempi, perche come qualcuno ha detto dipende da quello che fai con i numeri, di solito la print su standard output impiega più tempo del trovare i numeri direi che puoi ottimizzare questa linea 2011/8/2 matteo matteo.we...@gmail.com for divi in primes[:int(math.sqrt(x))]: ad esempio per il 101 devi provare per i numeri primi fino a 10 quindi 2, 3, 5, 7 ossia i primi 4 non i primi 10 ciao S ___ Python mailing list Python@lists.python.it http://lists.python.it/mailman/listinfo/python
Re: [Python] numeri primi
Marco Beri wrote: Bravo il mio amico, eh? :-) Chi e'? Lo conosco... A me piace barare: % time python erat_matrix.py 1000 (array([ 2, 3, 5, ..., 971, 973, 991]),) python erat_matrix.py 1000 0.61s user 0.12s system 38% cpu 1.930 total -- . ..: -enrico- ___ Python mailing list Python@lists.python.it http://lists.python.it/mailman/listinfo/python
Re: [Python] numeri primi
2011/8/2 matteo matteo.we...@gmail.com:
Il 02/08/2011 21:15, Mauro Casini ha scritto:
Marco Berimarcob...@gmail.com writes:
Usando un algoritmo scritto (in Python) da un amico:
timeit.timeit(import km;km.sieve(100), number=1)
0.12970614433288574
[...]
Si può fare di meglio:
In [25]: timeit.timeit('num.primes(100)', 'import num', number=1)
Out[25]: 1.2874603271484375e-05
[...]
come hai fatto :O , io non riesco neanche a migliorare i miei 3,8 secondi
per 100 :/
Ha barato ;)
Rileggi bene il suo mail.
©
--
Carlo Miron
More Cheater Than Rik0 Solution Architect™
___
Python mailing list
Python@lists.python.it
http://lists.python.it/mailman/listinfo/python
Re: [Python] numeri primi
Carlo Miron wrote: Ha barato;) Rileggi bene il suo mail. Beh, in confronto io *non* ho barato... ;) -- . ..: -enrico- ___ Python mailing list Python@lists.python.it http://lists.python.it/mailman/listinfo/python
Re: [Python] numeri primi
2011/8/2 Mauro Casini ma...@iperbole.bologna.it
timeit.timeit(import km;km.sieve(100), number=1)
0.12970614433288574
timeit.timeit(import km;km.sieve(1000), number=1)
1.3863430023193359
timeit.timeit(import km;km.sieve(1), number=1)
14.972478151321411
In [29]: num.primes(100)
Out[29]: generator object primes at 0x4cb9dfa0
In [31]: timeit.timeit('list(num.primes(100))', 'import num', number=1)
Out[31]: 1.0322129726409912
In [32]: timeit.timeit('list(num.primes(1000))', 'import num',
number=1)
Out[32]: 4.1961090564727783
In [33]: timeit.timeit('list(num.primes(1))', 'import num',
number=1)
Out[33]: 35.926841974258423
Beh, visto che le funzioni del mio amico (si chiama Fabrizio Romano per la
cronaca) ritornano delle liste di primi, direi che ti battono 2.5 a 1
:-)
Scherzi a parte, ora gli chiedo se posso postarvi il codice della sua
funzione (è un crivello bello tosto).
Ciao.
Marco.
--
http://beri.it/ - Un blog
http://beri.it/i-miei-libri/ - Qualche libro
___
Python mailing list
Python@lists.python.it
http://lists.python.it/mailman/listinfo/python
