On 30/05/15 19:14, Mirage Web Studio wrote:
and have at first devised a solution using class-object, thinking it
easier, but it proved to be slower than my basic algorithm which i
submitted earlier,
I'm not surprised. You seem to have a talent for finding complex
solutions to fairly simple problems :-)
in about 230 sec. After putting some thought i used dict for a change
with the sieve method and am able to produce primes for 1 million nos in
about 10 sec, which is better than both earlier algorithms.
Yes, using built in data structures (implemented in highly
optimised C) will nearly always be faster than building
your own in interpreted Python.
My query is does using classes slowed it or the python hardcoded
algorithm for dicts was better?
See above.
classes are great for modelling concepts that are not available
in the language. But both numbers and collections are well
provided for in Python.
if you had to implement the sieve algorithm how would u have done it.
Similarly to your dict approach but probably using lists.
After all lists are naturally indexed by numbers so using
a dict keyed by numbers doesn't add much value.
There are also a few tweaks you can do to improve efficiency
but you are pretty much there.
---------------------
class based algorithm
---------------------
import time
starttime=time.time()
class Number:
def __init__(self,number,p=None,n=None):
self.no=number
self.marked=None
self.p=p
self.n=n
A class with no methods other than init() is usually a bad sign.
You should always think very carefully whether another data
structure might not be more suitable. The whole point of
objects is that you do things to them. That means you need
methods to make them useful.
node=Number(2,None,None)
Note the extra work you make Python do to initialise a number
each time compared to just assigning a built-in integer object.
start=node
counter=1
for i in range(3,110000):
counter+=1
newnode=Number(i,node)
node.n=newnode
node=newnode
node=start
while start != None:
if start.marked==True:
start=start.n
continue
else:
newprime = start.no
print ("\nNewPrime",newprime,"\nMarking no:")
tmpnode=start
while tmpnode !=None:
Notice you now have a loop within a loop. If you are
looking for speed that's another bad sign. Compare with
your dict version there are two loops but they are not
nested, they run one after the other (and the first one
could be avoided using a list)
for i in range (newprime):
And now you have a third nested loop. Oh dear!
tmpnode=tmpnode.n
if tmpnode==None:
break
if tmpnode==None:
break
#print ( tmpnode.no, end=" ")
tmpnode.marked=True
start=start.n
print ("primes")
counter=0
while node!=None:
if not node.marked:
counter+=1
print(node.no)
node=node.n
print("--- %s seconds ---" % (time.time() - starttime), counter)
--
Alan G
Author of the Learn to Program web site
http://www.alan-g.me.uk/
http://www.amazon.com/author/alan_gauld
Follow my photo-blog on Flickr at:
http://www.flickr.com/photos/alangauldphotos
_______________________________________________
Tutor maillist - Tutor@python.org
To unsubscribe or change subscription options:
https://mail.python.org/mailman/listinfo/tutor
