Hi All
I came across a Perl implementation of Infinite Lists the other day, and was wondering about implementing it in python.
The specific example was to generate the first 3000 Hamming numbers, that is numbers of the form 2**i*3**j*5**k for i,j,k>=0.
I implemented something similar to their approach as follows: - from time import time
-
startTime=time()
-
-
def getHeads(Hamming,prods,inds):
-
"Returns heads of three streams"
-
heads=[]
-
for p,i in zip(prods,inds):
-
heads.append(p*Hamming[i])
-
return heads
-
-
def merge(heads,inds):
-
"returns value to be added to hamming, and next set of inds"
-
val=min(heads)
-
for i in range(len(heads)):
-
if heads[i]==val:
-
inds[i]+=1
-
return val,inds
-
-
Hamming=[1]
-
-
prods=[2,3,5]
-
inds=[0,0,0]
-
for k in range(1,3000):
-
heads=getHeads(Hamming,prods,inds)
-
val,inds=merge(heads,inds)
-
Hamming.append(val)
-
-
print 3000,Hamming[3000-1]
-
print "time: ",time()-startTime
This works rather well, generating the 3000 hamming numbers in about 14ms. But I was wondering about a more general setup to solve this problem generally. Like a class structure for these streams.
I started with this: - class Stream(object):
-
"""Stream objects have a head (which is the front element), a
-
tail (which can be another stream, or a function(n,head)"""
-
def __init__(self,head,tail,n=0,tailIsStream=False):
-
self.n=0
-
self.tailStream=tailIsStream
-
self.head=head
-
self.tail=tail
-
self.values=[head]
-
-
def call(self):
-
ans=self.head
-
self.n+=1
-
if self.tailStream:
-
self.head=self.tail.call()
-
else:
-
self.head=self.tail(self.n,self.head)
-
self.values.append(self.head)
-
return ans
-
-
def __mul__(self,other):
-
return Stream(self.head*other,lambda n,head: head*other)
-
-
-
-
s=Stream(1,lambda n,head:n**2)
-
for i in range(10):
-
print i, s.call()
which sort of works, but it's not obvious (at least to me) how to approach the coding of the hamming problem in this framework. And I wondered if there was a neater way anyway.
Thoughts?
0 1082 Sign in to post your reply or Sign up for a free account.
Similar topics
by: Ville Vainio |
last post by:
Pythonic Nirvana - towards a true Object Oriented Environment
=============================================================
IPython (by Francois Pinard) recently (next release - changes are...
|
by: Bulba! |
last post by:
Hello everyone,
I'm reading the rows from a CSV file. csv.DictReader puts
those rows into dictionaries.
The actual files contain old and new translations of software
strings. The dictionary...
|
by: jelle |
last post by:
I now some hostility to functional programming is flaming up now and
then; still could someone suggest me a pythonic equivalent for
Mathematica's FixedPoint function? For those not familiar with...
|
by: Gremlin |
last post by:
If you are not familiar with the halting problem, I will not go into
it in detail but it states that it is impossible to write a program
that can tell if a loop is infinite or not. This is a...
|
by: Gregory Petrosyan |
last post by:
Buenos dias, amigos!
I have to write _simple_ gui library, for embedding into game. My
first attempt was to use XML: isn't it cute to describe ui in such a
way:
<window>
<title>Hello...
|
by: SMB |
last post by:
I have two lists of data like the following:
LIST1
, ]
LIST2
, 'label': 'First Name',
'width': 0L, 'separator': ',', 'height': 0L, 'type': 2L, 'order': 1L},
{'code': 14L, 'name': 'Last...
|
by: akameswaran |
last post by:
Disclaimer - I recognize this is not a practical exercise. There are
many implementations around that would do the job better, more
efficiently (Meaning in C) or whatever.
I caught some thread...
|
by: Simon Forman |
last post by:
I've got a function that I'd like to improve.
It takes a list of lists and a "target" element, and it returns the set
of the items in the lists that appear either before or after the target...
|
by: Frank Samuelson |
last post by:
I love Python, and it is one of my 2 favorite
languages. I would suggest that Python steal some
aspects of the S language.
-------------------------------------------------------
1. Currently...
|
by: breal |
last post by:
I have three lists... for instance
a = ;
b = ;
c = ;
I want to take those and end up with all of the combinations they
create like the following lists
|
by: Charles Arthur |
last post by:
How do i turn on java script on a villaon, callus and itel keypad mobile phone
|
by: emmanuelkatto |
last post by:
Hi All, I am Emmanuel katto from Uganda. I want to ask what challenges you've faced while migrating a website to cloud.
Please let me know.
Thanks!
Emmanuel
|
by: Sonnysonu |
last post by:
This is the data of csv file
1 2 3
1 2 3
1 2 3
1 2 3
2 3
2 3
3
the lengths should be different i have to store the data by column-wise with in the specific length.
suppose the i have to...
|
by: Hystou |
last post by:
There are some requirements for setting up RAID:
1. The motherboard and BIOS support RAID configuration.
2. The motherboard has 2 or more available SATA protocol SSD/HDD slots (including MSATA, M.2...
|
by: Hystou |
last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can...
|
by: Oralloy |
last post by:
Hello folks,
I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>".
The problem is that using the GNU compilers,...
|
by: Hystou |
last post by:
Overview:
Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows...
|
by: tracyyun |
last post by:
Dear forum friends,
With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each...
|
by: agi2029 |
last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing,...
| |