Hi,
Simple excerise:
You have a sorted list of integers:
l=[1, 2, 4, 7, 8, 12]
and you should fill all gaps:
result == [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
How would you code this?
Constrain: The original list should be changed,
don't create a copy.
thomas 11 1353
Thomas Guettler wrote in message ... Hi,
Simple excerise:
You have a sorted list of integers: l=[1, 2, 4, 7, 8, 12]
and you should fill all gaps:
result == [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
How would you code this?
Constrain: The original list should be changed, don't create a copy.
thomas
This a homework problem? L = [1, 2, 4, 7, 8, 12] result = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12] L.extend([i for i in range(L[0], L[-1]) if i not in L]) L.sort() L == result
True
--
Francis Avila
| Thomas Guettler said | Hi,
Simple excerise:
You have a sorted list of integers: l=[1, 2, 4, 7, 8, 12]
and you should fill all gaps:
result == [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
How would you code this?
Constrain: The original list should be changed, don't create a copy.
thomas
The word "exercise" raises my suspicions that this is a homework problem.
You know you only cheat yourself when you ask others to do your homework.
#simple, but only works for ints
l = [1, 2, 4, 7, 8, 12]
l = range(l[0],l[-1]+1)
print l
#naive, but broader
#only use when sorting is cheap.
l = [1, 2, 4, 7, 8, 12]
#iterate through each possible item.
for x in range(l[0],l[-1]+1):
if x not in l:
l.append(x)
l.sort()
print l
#missing-merge: more general pattern
#useful for strange, hard to sort data:
#where sorting is expensive,
#but comparison is cheap.
l = [1, 2, 4, 7, 8, 12]
missing = []
#iterate through each possible item
for x in range(l[0], l[-1]+1):
#build a list of each missing item.
if x not in l:
missing.append(x)
#merge the two lists
for x in range(0, len(l) + len(missing) - 1):
if l[x] > missing[0]:
l = l[:x] + missing[0:1] + l[x:]
missing.pop(0)
print l
Sam Walters.
--
Never forget the halloween documents. http://www.opensource.org/halloween/
""" Where will Microsoft try to drag you today?
Do you really want to go there?"""
Thomas Guettler wrote: Hi,
Simple excerise:
You have a sorted list of integers: l=[1, 2, 4, 7, 8, 12]
and you should fill all gaps:
result == [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
Well, here's the simplest one...
if l:
l[:] = range(l[0],l[-1])
but what you're probably looking for is (untested):
for x in range( len(l)-2, -1, -1 ):
if l[x+1] != l[x]+1:
l[x+1:x+1] = range(l[x]+1,l[x+1])
Enjoy,
Mike
_______________________________________
Mike C. Fletcher
Designer, VR Plumber, Coder http://members.rogers.com/mcfletch/
Thomas Guettler wrote: Hi,
Simple excerise:
You have a sorted list of integers: l=[1, 2, 4, 7, 8, 12]
and you should fill all gaps:
result == [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
How would you code this?
Constrain: The original list should be changed, don't create a copy.
thomas
1:
previous = l[0]
current = 1
while current < len(l):
for e in range(previous + 1, l[current]):
l.insert(current, e)
current += 1
previous = l[current]
current += 1
2:
first, last = l[0], l[-1]
for _ in range(len(l)): l.pop()
l.extend(range(first, last + 1))
:)
hth,
anton.
Am Wed, 14 Jan 2004 09:43:01 +0100 schrieb Thomas Guettler: Hi,
Simple excerise:
You have a sorted list of integers: l=[1, 2, 4, 7, 8, 12]
and you should fill all gaps:
result == [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
How would you code this?
Constrain: The original list should be changed, don't create a copy.
No, this is not a homework exerice,
I was just interested if you have better solutions.
Thank you for your solutions.
Mine looks like this:
l=[1, 2, 4, 7, 8, 12]
i=-1
while 1:
i+=1
this=l[i]
if i+1==len(l):
# End of list
break
next=l[i+1]
assert(this<next)
for add in range(this+1, next):
i+=1
l.insert(i, add)
print l
On Wed, 2004-01-14 at 02:43, Thomas Guettler wrote: Hi,
Simple excerise:
You have a sorted list of integers: l=[1, 2, 4, 7, 8, 12]
and you should fill all gaps:
result == [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
How would you code this?
Constrain: The original list should be changed, don't create a copy.
In the spirt of unit testing...
#!/usr/bin/env python
import unittest
def fillGaps(seq):
expectedLength = seq[-1] - seq[0] + 1
i = 1
while i < expectedLength:
if seq[i] - seq[i-1] > 1:
seq.insert(i, seq[i-1] + 1)
i += 1
class test(unittest.TestCase):
def test(self):
l = [1, 2, 4, 7, 8, 12]
fillGaps(l)
self.assertEquals(l, range(1, 13))
unittest.main()
>>>>> "Mark" == Mark McEahern <ma**@mceahern.com> writes:
Mark> On Wed, 2004-01-14 at 02:43, Thomas Guettler wrote: Hi,
Simple excerise:
You have a sorted list of integers:
... and you should fill all gaps:
... How would you code this?
Constrain: The original list should be changed, don't create a copy.
Mark> In the spirt of unit testing...
Mark> #!/usr/bin/env python
...
Here's a version which is much faster if you have large gaps and appears to
be only marginally slower if you have small gaps.
Skip
#!/usr/bin/env python
#!/usr/bin/env python
def fillGaps1(seq):
expectedLength = seq[-1] - seq[0] + 1
i = 1
while i < expectedLength:
if seq[i] - seq[i-1] > 1:
seq.insert(i, seq[i-1] + 1)
i += 1
def fillGaps(seq):
expectedLength = seq[-1] - seq[0] + 1
i = 1
while i < expectedLength:
if seq[i] - seq[i-1] > 1:
gap = seq[i-1] - seq[i]
fill = range(seq[i-1]+1, seq[i])
seq[i:i] = fill
i += len(fill)
i += 1
if __name__ == "__main__":
import timeit
print "timing with one large gap:"
t = timeit.Timer(setup='from fillgaps import fillGaps1 as fillGaps',
stmt='fillGaps([1, 5000])')
print "old fillgaps:", t.timeit(number=100)
t = timeit.Timer(setup='from fillgaps import fillGaps',
stmt='fillGaps([1, 5000])')
print "new fillgaps:", t.timeit(number=100)
print "timing with many small gaps:"
t = timeit.Timer(setup='from fillgaps import fillGaps1 as fillGaps;l=range(1,5001,2)',
stmt='fillGaps(l)')
print "old fillgaps:", t.timeit(number=100)
t = timeit.Timer(setup='from fillgaps import fillGaps;l=range(1,5001,2)',
stmt='fillGaps(l)')
print "new fillgaps:", t.timeit(number=100)
import unittest
class test(unittest.TestCase):
def test(self):
for fg in (fillGaps1, fillGaps):
l = [1, 2, 4, 7, 8, 12]
fg(l)
self.assertEquals(l, range(1, 13))
l = [1, 5000]
fg(l)
self.assertEquals(l, range(1, 5001))
unittest.main()
Skip Montanaro wrote: >> "Mark" == Mark McEahern <ma**@mceahern.com> writes: Mark> On Wed, 2004-01-14 at 02:43, Thomas Guettler wrote: >> Hi, >> >> Simple excerise: >> >> You have a sorted list of integers: ... >> and you should fill all gaps: ... >> How would you code this? >> >> Constrain: The original list should be changed, don't create a >> copy. Mark> In the spirt of unit testing...
Mark> #!/usr/bin/env python ...
Here's a version which is much faster if you have large gaps and appears to be only marginally slower if you have small gaps.
Skip
#!/usr/bin/env python
#!/usr/bin/env python
def fillGaps1(seq):
if len(seq) == seq[-1]:
raise Exception("nothing to do") expectedLength = seq[-1] - seq[0] + 1 i = 1 while i < expectedLength: if seq[i] - seq[i-1] > 1: seq.insert(i, seq[i-1] + 1) i += 1
def fillGaps(seq): expectedLength = seq[-1] - seq[0] + 1 i = 1 while i < expectedLength: if seq[i] - seq[i-1] > 1: gap = seq[i-1] - seq[i] fill = range(seq[i-1]+1, seq[i]) seq[i:i] = fill i += len(fill) i += 1
if __name__ == "__main__": import timeit
print "timing with one large gap:" t = timeit.Timer(setup='from fillgaps import fillGaps1 as fillGaps', stmt='fillGaps([1, 5000])') print "old fillgaps:", t.timeit(number=100) t = timeit.Timer(setup='from fillgaps import fillGaps', stmt='fillGaps([1, 5000])') print "new fillgaps:", t.timeit(number=100)
print "timing with many small gaps:" t = timeit.Timer(setup='from fillgaps import fillGaps1 as fillGaps;l=range(1,5001,2)', stmt='fillGaps(l)')
I think the list should be initialized in the statement instead of the
setup. Otherwise subsequent passes will measure for range(1, 5000).
print "old fillgaps:", t.timeit(number=100) t = timeit.Timer(setup='from fillgaps import fillGaps;l=range(1,5001,2)', stmt='fillGaps(l)') print "new fillgaps:", t.timeit(number=100)
import unittest class test(unittest.TestCase): def test(self): for fg in (fillGaps1, fillGaps): l = [1, 2, 4, 7, 8, 12] fg(l) self.assertEquals(l, range(1, 13))
l = [1, 5000] fg(l) self.assertEquals(l, range(1, 5001))
unittest.main()
Here's another fillgap version:
def fillGapsPeter(seq):
# inspired by anton muhin
lo = seq[0]
hi = seq[-1]
seq[1:1] = range(lo+1, hi+1)
while len(seq) > hi:
i = seq.pop()
seq[i-lo] = i
def fillGapsMark(seq):
expectedLength = seq[-1] - seq[0] + 1
i = 1
while i < expectedLength:
if seq[i] - seq[i-1] > 1:
seq.insert(i, seq[i-1] + 1)
i += 1
def fillGapsSkip(seq):
expectedLength = seq[-1] - seq[0] + 1
i = 1
while i < expectedLength:
if seq[i] - seq[i-1] > 1:
gap = seq[i-1] - seq[i]
fill = range(seq[i-1]+1, seq[i])
seq[i:i] = fill
i += len(fill)
i += 1
if __name__ == "__main__":
import timeit, fillgaps, sys
fnames = [fname for fname in dir(fillgaps) if callable(getattr(fillgaps,
fname))]
fnames.sort()
for header, lst in [
("original test case", [1, 2, 4, 7, 8, 12]),
("timing with one large gap:", [1, 5000]),
("timing with many small gaps:", range(1, 5001, 2))]:
print header
for fn in fnames:
t = timeit.Timer(setup='from fillgaps import %s as fillGaps' %
fn,
stmt='fillGaps(%s)' % (lst,))
print "\t%s:" % fn, t.timeit(number=100)
print
import unittest
class test(unittest.TestCase):
def test_all(self):
for fg in [getattr(fillgaps, fn) for fn in fnames]:
l = [1, 2, 4, 7, 8, 12]
fg(l)
self.assertEquals(l, range(1, 13))
l = [1, 5000]
fg(l)
self.assertEquals(l, range(1, 5001))
def test_mine(self):
""" Hard to prove I'm not cheating,
hope I got it right...
"""
class myint(int):
def __repr__(self):
return "my" + int.__repr__(self)
original = map(myint, [1, 2, 4, 7, 8, 12])
l = list(original)
fillGapsPeter(l)
self.assertEquals(l, range(1, 13))
for i in original:
self.assert_(i is l[i-1])
self.assert_(repr(i).startswith("my"))
unittest.main()
My findings:
original test case
fillGapsMark: 0.00151419639587
fillGapsPeter: 0.00127387046814
fillGapsSkip: 0.00162696838379
timing with one large gap:
fillGapsMark: 0.872708797455
fillGapsPeter: 0.0312719345093
fillGapsSkip: 0.0336079597473
timing with many small gaps:
fillGapsMark: 0.973310947418
fillGapsPeter: 0.412738800049
fillGapsSkip: 1.47315406799
Peter
"Thomas Guettler" <gu*****@thomas-guettler.de> wrote in message news:<pa****************************@thomas-guettler.de>... Hi,
Simple excerise:
You have a sorted list of integers: l=[1, 2, 4, 7, 8, 12]
and you should fill all gaps:
result == [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
How would you code this?
Constrain: The original list should be changed, don't create a copy.
thomas l = [1, 2, 4, 7, 8, 12] id(l)
27295112 for i in range(len(l)-1,0,-1):
.... for j in range(l[i]-l[i-1]-1):
.... l.insert(i,l[i]-1)
.... id(l)
27295112 l
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
Tested, but no idea about timing.
Regards
Peter
On Wed, 14 Jan 2004 09:43:01 +0100, Thomas Guettler wrote: Hi,
Simple excerise:
You have a sorted list of integers: l=[1, 2, 4, 7, 8, 12]
and you should fill all gaps:
result == [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
How would you code this?
Constrain: The original list should be changed, don't create a copy.
thomas
l[:] = [x for x in range(l[0], l[-1] + 1)]
If you care about timing, you'll want to compare against Peter Abel's
solution; I would not guarantee which is faster. All I can tell you is
which makes more sense to me when I read it.
Actually, maximal readability is
l[:] = [x for x in range(min(l), max(l) + 1)]
but that will *certainly* be less efficient if you know the list is sorted
then my first post.
Jeremy Bowers <je**@jerf.org> writes: Actually, maximal readability is
l[:] = [x for x in range(min(l), max(l) + 1)]
but that will *certainly* be less efficient if you know the list is sorted then my first post.
Um, why the list comprehension? Something wrong with
l[:] = range(min(l), max(l) + 1)
? This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics
by: Mat |
last post by:
Hi,
I have a system that uploads images as BLOBs in a database. I also
have a function that I use to resize uploaded images before saving as
files. I would like to combine these two by resising...
|
by: James |
last post by:
I am in the process of running my site through WC3 validation. I
assume the validator at www.w3c.org cant accept cookies and so PHP is
attaching &PHPSESSID=lasklijasj09jsad (or similar) to my...
|
by: Miranda |
last post by:
Hi, I have a ASP/vbscript program that generates random passwords. The
problem is I need to insert those passwords into an Access database of
327 clients.
I have the random password program...
|
by: yuchang |
last post by:
Hi,
Using the FormView control is very efficient. But I want to do some
action,like showing a success message or redirect to another page, after
inserting, updating and deleting. How do I get...
|
by: Krishna |
last post by:
Hi, I have developed a for dataentry by using datagird in C# windows
application, I am using combocolumns, textbox columns for the same,
two readonly textboxcolumns for those readonly columns i...
|
by: desktop |
last post by:
Why does insert only work when specifying an iterator plus the object to
be inserted:
std::vector<intt;
std::vector<int>::iterator it;
it = t.begin();
t.insert(it,33);
If I use push_back...
|
by: gp |
last post by:
I am and have been using PDO for about a year now...and have finally
gotten around to solving the "DB NULL value" issues I ran into early
on...
I am looking for suggestions and techniques to...
|
by: Bunty |
last post by:
I want to insert values in the database.If i insert values one by one
then it works till 4 or 5 fields then after it gives error.In my
database there are more than 20 field.Pls help me.
|
by: AlexanderDeLarge |
last post by:
Hi!
I got a problem that's driving me crazy and I'm desperately in need of help.
I'll explain my scenario:
I'm doing a database driven site for a band, I got these tables for their discography...
|
by: rando1000 |
last post by:
Okay, here's my situation. I need to loop through a file, inserting records based on a number field (in order) and if the character in a certain field = "##", I need to insert a blank record.
...
|
by: Charles Arthur |
last post by:
How do i turn on java script on a villaon, callus and itel keypad mobile phone
|
by: nemocccc |
last post by:
hello, everyone, I want to develop a software for my android phone for daily needs, any suggestions?
|
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: marktang |
last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However,...
|
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: 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,...
|
by: isladogs |
last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM).
In this session, we are pleased to welcome a new...
| |