473,240 Members | 1,673 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,240 software developers and data experts.

A dumb question about a class

I'm still trying to understand classes. I've made some progress, I
think, but I don't understand how to use this one. How do I call it,
or any of its functions? It's from the Cookbook, at
<http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/523048>.

Thanks,

Dick Moores

================================================== ===
class PrimeList:
def __init__(self, initial=0):
self.primelist = [2,3]
self.primelookup = [0,0,1,1]
self.max_prime = 3
self.grow_primelist(initial)

def grow_primelist(self,number):
newprimes = []
while self.max_prime <= number:
next = self.nextprime()
newprimes.append(next)
self.max_prime = next
size_difference = self.max_prime - len(self.primelookup) + 1
self.primelookup.extend([0] * size_difference)
for i in newprimes:
self.primelookup[i]=1

def contains(self,number):
if number < 2:
return 0
if number len(self.primelookup) - 1:
self.grow_primelist(number)
return self.primelookup[number]
return self.primelookup[number]

def nextprime(self):
i = self.max_prime + 2
while 1:
isprime = True
for prime in self.primelist:
if i % prime == 0:
isprime = False
i += 2
break
if isprime:
self.primelist.append(i)
return(i)
================================================== ====

Aug 12 '07 #1
10 1322
Dick Moores wrote:
I'm still trying to understand classes. I've made some progress, I
think, but I don't understand how to use this one. How do I call it, or
any of its functions? It's from the Cookbook, at
<http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/523048>.
The short answer is that use should look something like::
>>plist = PrimeList()
plist.contains(32)
False
>>plist.contains(23)
True

But this doesn't seem like a particularly good recipe. Seems like you
would really rather be writing code like::
>>plist = PrimeList()
1 in plist
False
>>2 in plist
True
>>22 in plist
False
>>23 in plist
True
>>782 in plist
False
>>787 in plist
True

Here's how I'd write the recipe::

import itertools

def iter_primes():
# an iterator of all numbers between 2 and +infinity
numbers = itertools.count(2)

# generate primes forever
while True:

# get the first number from the iterator (always a prime)
prime = numbers.next()
yield prime

# remove all numbers from the (infinite) iterator that are
# divisible by the prime we just generated
numbers = itertools.ifilter(prime.__rmod__, numbers)
class PrimeList(object):
def __init__(self):
# infinite iterator of primes
self._prime_iter = iter_primes()

# the last prime we've seen
self._last_prime = None

# all primes seen so far
self._prime_set = set()

# add the first prime (so that _last_prime is set)
self._add_prime()

def __contains__(self, n):
# add primes to the list until we exceed n
while n self._last_prime:
self._add_prime()

# return True if n is one of our primes
return n in self._prime_set

def _add_prime(self):
# take a prime off the iterator and update the prime set
self._last_prime = self._prime_iter.next()
self._prime_set.add(self._last_prime)
STeVe
Aug 12 '07 #2
At 03:09 PM 8/12/2007, Steven Bethard wrote:
>Here's how I'd write the recipe::

import itertools

def iter_primes():
# an iterator of all numbers between 2 and +infinity
numbers = itertools.count(2)

# generate primes forever
while True:

# get the first number from the iterator (always a prime)
prime = numbers.next()
yield prime

# remove all numbers from the (infinite) iterator that are
# divisible by the prime we just generated
numbers = itertools.ifilter(prime.__rmod__, numbers)
class PrimeList(object):
def __init__(self):
# infinite iterator of primes
self._prime_iter = iter_primes()

# the last prime we've seen
self._last_prime = None

# all primes seen so far
self._prime_set = set()

# add the first prime (so that _last_prime is set)
self._add_prime()

def __contains__(self, n):
# add primes to the list until we exceed n
while n self._last_prime:
self._add_prime()

# return True if n is one of our primes
return n in self._prime_set

def _add_prime(self):
# take a prime off the iterator and update the prime set
self._last_prime = self._prime_iter.next()
self._prime_set.add(self._last_prime)
I'm afraid my next question is "How do I run this"?

Dick
Aug 12 '07 #3
Dick Moores wrote:
At 03:09 PM 8/12/2007, Steven Bethard wrote:
>Here's how I'd write the recipe::

import itertools

def iter_primes():
# an iterator of all numbers between 2 and +infinity
numbers = itertools.count(2)

# generate primes forever
while True:

# get the first number from the iterator (always a prime)
prime = numbers.next()
yield prime

# remove all numbers from the (infinite) iterator that are
# divisible by the prime we just generated
numbers = itertools.ifilter(prime.__rmod__, numbers)
class PrimeList(object):
def __init__(self):
# infinite iterator of primes
self._prime_iter = iter_primes()

# the last prime we've seen
self._last_prime = None

# all primes seen so far
self._prime_set = set()

# add the first prime (so that _last_prime is set)
self._add_prime()

def __contains__(self, n):
# add primes to the list until we exceed n
while n self._last_prime:
self._add_prime()

# return True if n is one of our primes
return n in self._prime_set

def _add_prime(self):
# take a prime off the iterator and update the prime set
self._last_prime = self._prime_iter.next()
self._prime_set.add(self._last_prime)

I'm afraid my next question is "How do I run this"?

The same way I showed at the top (which you snipped in your reply)::
>>plist = PrimeList()
1 in plist
False
>>2 in plist
True
>>22 in plist
False
>>23 in plist
True
>>782 in plist
False
>>787 in plist
True

The first line, ``plist = PrimeList()`` creates a PrimeList object and
names it ``plist``. You can then check whether a prime is in that
PrimeList object much like you might check a normal ``list`` or ``set``
object -- using the ``in`` operator as above.

Note that if you just want to iterate over all the primes, there's no
need for the class at all. Simply write::

for prime in iter_primes():
...

HTH,

STeVe
Aug 12 '07 #4
At 03:35 PM 8/12/2007, Steven Bethard wrote:
>Note that if you just want to iterate over all the primes, there's no
need for the class at all. Simply write::

for prime in iter_primes():
Even if I want to test only 1 integer, or want the list of primes in
a certain interval, I don't need the class at all:

====================================
import itertools

def iter_primes():
# an iterator of all numbers between 2 and +infinity
numbers = itertools.count(2)
# generate primes forever
while True:
# get the first number from the iterator (always a prime)
prime = numbers.next()
yield prime
# remove all numbers from the (infinite) iterator that are
# divisible by the prime we just generated
numbers = itertools.ifilter(prime.__rmod__, numbers)

def listPrimes(n,m):
"""
Returns the list of primes in closed interval [n,m]
"""
primes = []
for prime in iter_primes():
if prime m:
return primes
if n <= prime <= m:
primes.append(prime)
============================================

Thanks for your help. I didn't learn much about classes, but
appreciated your iter_primes() a lot!

Dick Moores

Aug 13 '07 #5
On Aug 12, 5:09 pm, Steven Bethard <steven.beth...@gmail.comwrote:
def iter_primes():
# an iterator of all numbers between 2 and +infinity
numbers = itertools.count(2)

# generate primes forever
while True:

# get the first number from the iterator (always a prime)
prime = numbers.next()
yield prime

# remove all numbers from the (infinite) iterator that are
# divisible by the prime we just generated
numbers = itertools.ifilter(prime.__rmod__, numbers)
This is kind of OT (from the thread), but in this iter_primes
function, numbers is becoming an ifilter of an ifilter of an ifilter
of an ifilter of an ifilter of an ifilter of... Is that really at all
efficient for larger numbers (millions or billions, or even bigger)?

Aug 13 '07 #6
On Aug 12, 7:35 pm, Dustan <DustanGro...@gmail.comwrote:
On Aug 12, 5:09 pm, Steven Bethard <steven.beth...@gmail.comwrote:
def iter_primes():
# an iterator of all numbers between 2 and +infinity
numbers = itertools.count(2)
# generate primes forever
while True:
# get the first number from the iterator (always a prime)
prime = numbers.next()
yield prime
# remove all numbers from the (infinite) iterator that are
# divisible by the prime we just generated
numbers = itertools.ifilter(prime.__rmod__, numbers)

This is kind of OT (from the thread), but in this iter_primes
function, numbers is becoming an ifilter of an ifilter of an ifilter
of an ifilter of an ifilter of an ifilter of... Is that really at all
efficient for larger numbers (millions or billions, or even bigger)?
To word my question better:

How does this algorithm compare and contrast to maintaining a
dictionary or set and iterating through those structures to find out
if a number is divisible? All of those algorithms I've described are
O(n^2), if I'm not mistaken, but as far as memory-efficiency and the
likes, how do they compare/contrast?

Aug 13 '07 #7
Dustan wrote:
On Aug 12, 7:35 pm, Dustan <DustanGro...@gmail.comwrote:
>On Aug 12, 5:09 pm, Steven Bethard <steven.beth...@gmail.comwrote:
>> def iter_primes():
# an iterator of all numbers between 2 and +infinity
numbers = itertools.count(2)
# generate primes forever
while True:
# get the first number from the iterator (always a prime)
prime = numbers.next()
yield prime
# remove all numbers from the (infinite) iterator that are
# divisible by the prime we just generated
numbers = itertools.ifilter(prime.__rmod__, numbers)
This is kind of OT (from the thread), but in this iter_primes
function, numbers is becoming an ifilter of an ifilter of an ifilter
of an ifilter of an ifilter of an ifilter of... Is that really at all
efficient for larger numbers (millions or billions, or even bigger)?

To word my question better:

How does this algorithm compare and contrast to maintaining a
dictionary or set and iterating through those structures to find out
if a number is divisible? All of those algorithms I've described are
O(n^2), if I'm not mistaken, but as far as memory-efficiency and the
likes, how do they compare/contrast?
I don't have the answer off hand, but if anyone wants to report some
timeit results or memory consumption here, I'd be interested.

STeVe
Aug 13 '07 #8
Dick Moores wrote:
At 03:35 PM 8/12/2007, Steven Bethard wrote:
>Note that if you just want to iterate over all the primes, there's no
need for the class at all. Simply write::

for prime in iter_primes():

Even if I want to test only 1 integer, or want the list of primes in a
certain interval, I don't need the class at all
Yep. That was the basis of my original feeling that the recipe was
kinda overkill.
Thanks for your help. I didn't learn much about classes, but appreciated
your iter_primes() a lot!
You're welcome, though I can't actually take credit for iter_primes().
The original version is due to Tim Hochberg, in a comment on this recipe:

http://aspn.activestate.com/ASPN/Coo.../Recipe/117119

FWIW, he says that he "managed to generate all primes up to 909,691
before it bombed the Python interpreter mysteriously, but it takes a while!"

I'm not particularly married to that prime generator. For your purposes,
any generator version of iter_primes() is probably more useful than the
class you were looking at. You can see some other implementations of
prime generators on that same recipe page.

STeVe
Aug 13 '07 #9
Steven Bethard wrote:
Dustan wrote:
>On Aug 12, 7:35 pm, Dustan <DustanGro...@gmail.comwrote:
>>On Aug 12, 5:09 pm, Steven Bethard <steven.beth...@gmail.comwrote:

def iter_primes():
# an iterator of all numbers between 2 and +infinity
numbers = itertools.count(2)
# generate primes forever
while True:
# get the first number from the iterator (always a prime)
prime = numbers.next()
yield prime
# remove all numbers from the (infinite) iterator that are
# divisible by the prime we just generated
numbers = itertools.ifilter(prime.__rmod__, numbers)
This is kind of OT (from the thread), but in this iter_primes
function, numbers is becoming an ifilter of an ifilter of an ifilter
of an ifilter of an ifilter of an ifilter of... Is that really at all
efficient for larger numbers (millions or billions, or even bigger)?

To word my question better:

How does this algorithm compare and contrast to maintaining a
dictionary or set and iterating through those structures to find out
if a number is divisible? All of those algorithms I've described are
O(n^2), if I'm not mistaken, but as far as memory-efficiency and the
likes, how do they compare/contrast?

I don't have the answer off hand, but if anyone wants to report some
timeit results or memory consumption here, I'd be interested.
Ok, I played around with it myself. Here are the two implementations I
tested::

def iter_primes_recursive():
# an iterator of all numbers between 2 and +infinity
numbers = itertools.count(2)

# generate primes forever
while True:

# get the first number from the iterator (always a prime)
prime = numbers.next()
yield prime

# remove all numbers from the (infinite) iterator that are
# divisible by the prime we just generated
numbers = itertools.ifilter(prime.__rmod__, numbers)
def iter_primes_mapping():

# mapping from composite number to first prime that revealed
# that number as a composite
composite_to_factor_map = {}

# generate primes forever
for i in itertools.count(2):

# find a factor of the number
factor = composite_to_factor_map.pop(i, None)

# if no factor is found, the number is prime
if factor is None:
yield i
composite_to_factor_map[i * i] = i

# add the factor to the number until we find a new
# composite number
else:
composite = i + factor
while composite in composite_to_factor_map:
composite += factor
composite_to_factor_map[composite] = factor

And here are some timeit results::

$ python -m timeit -s "from script import iter_primes_recursive as
iter_primes" "for i in iter_primes():" " if i >= 100:"
" break"
10000 loops, best of 3: 102 usec per loop

$ python -m timeit -s "from script import iter_primes_mapping as
iter_primes" "for i in iter_primes():" " if i >= 100:"
" break"
10000 loops, best of 3: 75.2 usec per loop

$ python -m timeit -s "from script import iter_primes_recursive as
iter_primes" "for i in iter_primes():" " if i >= 10000:"
" break"
10 loops, best of 3: 111 msec per loop

$ python -m timeit -s "from script import iter_primes_mapping as
iter_primes" "for i in iter_primes():" " if i >= 10000:"
" break"
100 loops, best of 3: 8.4 msec per loop

So, somewhat unsurprisingly, the non-recursive version is much faster
for larger primes. (Someone should check that both my implementations
are right -- I only did a couple of spot checks on the output.)

STeVe
Aug 13 '07 #10
On Aug 13, 3:30 am, Steven Bethard <steven.beth...@gmail.comwrote:
Dick Moores wrote:
At 03:35 PM 8/12/2007, Steven Bethard wrote:
Note that if you just want to iterate over all the primes, there's no
need for the class at all. Simply write::
forprimein iter_primes():
Even if I want to test only 1 integer, or want the list of primes in a
certain interval, I don't need the class at all

Yep. That was the basis of my original feeling that the recipe was
kinda overkill.
Thanks for your help. I didn't learn much about classes, but appreciated
your iter_primes() a lot!

You're welcome, though I can't actually take credit for iter_primes().
The original version is due to Tim Hochberg, in a comment on this recipe:

http://aspn.activestate.com/ASPN/Coo.../Recipe/117119

FWIW, he says that he "managed to generate all primes up to 909,691
before it bombed the Python interpreter mysteriously, but it takes a while!"

I'm not particularly married to thatprimegenerator. For your purposes,
any generator version of iter_primes() is probably more useful than the
class you were looking at. You can see some other implementations ofprimegenerators on that same recipe page.

STeVe
I wrote that recipe, did not realise anyone was using it (I forgot to
update it with the version I now use)
I thought any prime generator is not a good idea for the following
reasons:
You end up carrying around a list of primes anyway,
It is not faster than the Sieve of Eratosthenes

Here is the latest version (following Steves lead doing __contains__ ,
thanks Steve)
(I held off doing this as I had not properly implemented _isprime , it
returned incorrect values if you asked it about very big numbers, now
it will bruteforce an answer)

It is slower than Steves unless you use Psyco, then its two times as
fast.
I was surprised as I had used generators and had slower time, but was
unfamiliar with ifilter (but will be playing with it soon) - that may
give the speedup

Also, does anyone know if there is some magic that makes
i in some_set
loads faster than
i in some_list
as if I tweek Steves to use a list instead, it slows down loads.

All the very best,
Tom

PS: I am about to go to bed, but will post the tests I used etc to my
blog tomorrow.
"""

class PrimeList:
def __init__(self, initial=0):
self.primelist = [2]
self.primelookup = [0,0,1,1]
self.max_prime = 2
self.initialise_list(initial)

def initialise_list(self,upto):
"Good old Sieve of Eratosthenes"
if upto <= 3:
pass
self.primelookup.extend([0,1] * ((upto-3)//2))
if upto % 2 == 0:
self.primelookup.extend([0])
for i in range(3, upto + 1 , 2):
if self.primelookup[i]:
self.primelist.append(i)
self.max_prime = i
j = i + i
while j <= upto:
self.primelookup[j] = 0
j += i

def __contains__(self,number):
if number < 2:
return False
if number self.max_prime - 1:
#print "Asking for what I dont have!"
return self._isprime(number)
return self.primelookup[number]

def _isprime(self, number):
for prime in self.primelist:
if prime number ** .5:
break
if number % prime == 0:
return False
if number < self.max_prime ** 2:
return True
else:
#Brute forcing
for i in range(self.max_prime,number ** .5 + 1, 2):
if number % i == 0:
return False
return True
"""
Aug 14 '07 #11

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

4
by: Piedro | last post by:
Hi group, as I was browsing the web and checking out w3schools.com I read that the font tag was deprecated and that I should use css styles for formatting like for example <p class="p1"> Text...
2
by: TGF | last post by:
How do you copy a String type into a native char buffer? Dumb question, but not sure how to do it :( TGF
6
by: wASP | last post by:
Hello everyone, I'm new to C# and ASP.NET, so pardon my stupidity on this one. I'm having a problem with referencing methods/functions external to a class member function. My code is as...
11
by: dhnriverside | last post by:
Hi peeps Ok, so I thought I'd have a go at making a console app in VS2k5... I haven't written any windows apps for years, let alone dos apps (been web programming) and I've hit a dumb error... ...
2
by: Derek Martin | last post by:
Not like I haven't asked dumb ones before, but I want to take my API that I designed and create a DLL out of it, instead of it sitting inside my main form. In VS2K3, how do I go about doing...
16
by: CMM | last post by:
Is it me or has anyone noticed that F1 is really dumb in VS2005. Since VB3 I have been able to click F1 on an ambiguous method in code and the IDE automatically determines the type based on the...
10
by: sp | last post by:
I create an xml file in a text editor: <?xml version="1.0" encoding="utf-8"?> <elts> <elt id="1" class="c1">content1</elt> <elt id="2" class="c1">content2</elt> </elts> Then I load the file...
7
by: Joel Hedlund | last post by:
Hi! There's one thing about dictionaries and __hash__() methods that puzzle me. I have a class with several data members, one of which is 'name' (a str). I would like to store several of these...
3
by: rdufour | last post by:
Downloaded a sample that is supposed to show how to localize a web site and started playing with the code, its in Vs2003, so I figure I would take code and put it in Vs 2005 and doing so use it a...
3
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 3 Jan 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). For other local times, please check World Time Buddy In...
0
by: jianzs | last post by:
Introduction Cloud-native applications are conventionally identified as those designed and nurtured on cloud infrastructure. Such applications, rooted in cloud technologies, skillfully benefit from...
0
by: abbasky | last post by:
### Vandf component communication method one: data sharing ​ Vandf components can achieve data exchange through data sharing, state sharing, events, and other methods. Vandf's data exchange method...
0
by: fareedcanada | last post by:
Hello I am trying to split number on their count. suppose i have 121314151617 (12cnt) then number should be split like 12,13,14,15,16,17 and if 11314151617 (11cnt) then should be split like...
0
Git
by: egorbl4 | last post by:
Скачал я git, хотел начать настройку, а там вылезло вот это Что это? Что мне с этим делать? ...
0
by: MeoLessi9 | last post by:
I have VirtualBox installed on Windows 11 and now I would like to install Kali on a virtual machine. However, on the official website, I see two options: "Installer images" and "Virtual machines"....
0
by: DolphinDB | last post by:
The formulas of 101 quantitative trading alphas used by WorldQuant were presented in the paper 101 Formulaic Alphas. However, some formulas are complex, leading to challenges in calculation. Take...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: Aftab Ahmad | last post by:
Hello Experts! I have written a code in MS Access for a cmd called "WhatsApp Message" to open WhatsApp using that very code but the problem is that it gives a popup message everytime I clicked on...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.