Inserting while itterating

[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.

thomas

[Francis Avila]

Re: Inserting while itterating


Thomas Guettler wrote in message ...[color=blue]
>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
>[/color]
This a homework problem?
[color=blue][color=green][color=darkred]
>>> 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[/color][/color][/color]
True

--
Francis Avila

[Samuel Walters]

Re: Inserting while itterating

| Thomas Guettler said |
[color=blue]
> 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[/color]

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?"""

[Mike C. Fletcher]

Re: Inserting while itterating

Thomas Guettler wrote:
[color=blue]
>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]
>
>[/color]
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/

[anton muhin]

Re: Inserting while itterating

Thomas Guettler wrote:
[color=blue]
> 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
>[/color]

1:

previous = l[0]
current = 1

while current < len(l):
for e in range(previous + 1, l[current]):
l.insert(curren t, 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.

[Thomas Guettler]

Re: Inserting while itterating

Am Wed, 14 Jan 2004 09:43:01 +0100 schrieb Thomas Guettler:
[color=blue]
> 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.[/color]

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<nex t)
for add in range(this+1, next):
i+=1
l.insert(i, add)
print l

[Mark McEahern]

Re: Inserting while itterating

On Wed, 2004-01-14 at 02:43, Thomas Guettler wrote:[color=blue]
> 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.[/color]

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.T estCase):

def test(self):
l = [1, 2, 4, 7, 8, 12]
fillGaps(l)
self.assertEqua ls(l, range(1, 13))

unittest.main()

[Skip Montanaro]

Re: Inserting while itterating

>>>>> "Mark" == Mark McEahern <mark@mceahern. com> writes:

Mark> On Wed, 2004-01-14 at 02:43, Thomas Guettler wrote:[color=blue][color=green]
>> Hi,
>>
>> Simple excerise:
>>
>> You have a sorted list of integers:[/color][/color]
...[color=blue][color=green]
>> and you should fill all gaps:[/color][/color]
...[color=blue][color=green]
>> How would you code this?
>>
>> Constrain: The original list should be changed, don't create a copy.[/color][/color]

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(se tup='from fillgaps import fillGaps1 as fillGaps',
stmt='fillGaps([1, 5000])')
print "old fillgaps:", t.timeit(number =100)
t = timeit.Timer(se tup='from fillgaps import fillGaps',
stmt='fillGaps([1, 5000])')
print "new fillgaps:", t.timeit(number =100)

print "timing with many small gaps:"
t = timeit.Timer(se tup='from fillgaps import fillGaps1 as fillGaps;l=rang e(1,5001,2)',
stmt='fillGaps( l)')
print "old fillgaps:", t.timeit(number =100)
t = timeit.Timer(se tup='from fillgaps import fillGaps;l=rang e(1,5001,2)',
stmt='fillGaps( l)')
print "new fillgaps:", t.timeit(number =100)

import unittest
class test(unittest.T estCase):
def test(self):
for fg in (fillGaps1, fillGaps):
l = [1, 2, 4, 7, 8, 12]
fg(l)
self.assertEqua ls(l, range(1, 13))

l = [1, 5000]
fg(l)
self.assertEqua ls(l, range(1, 5001))

unittest.main()

[Peter Otten]

Re: Inserting while itterating

Skip Montanaro wrote:
[color=blue][color=green][color=darkred]
>>>>>> "Mark" == Mark McEahern <mark@mceahern. com> writes:[/color][/color]
>
> Mark> On Wed, 2004-01-14 at 02:43, Thomas Guettler wrote:[color=green][color=darkred]
> >> Hi,
> >>
> >> Simple excerise:
> >>
> >> You have a sorted list of integers:[/color][/color]
> ...[color=green][color=darkred]
> >> and you should fill all gaps:[/color][/color]
> ...[color=green][color=darkred]
> >> How would you code this?
> >>
> >> Constrain: The original list should be changed, don't create a
> >> copy.[/color][/color]
>
> 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):[/color]
if len(seq) == seq[-1]:
raise Exception("noth ing to do")[color=blue]
> 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(se tup='from fillgaps import fillGaps1 as fillGaps',
> stmt='fillGaps([1, 5000])')
> print "old fillgaps:", t.timeit(number =100)
> t = timeit.Timer(se tup='from fillgaps import fillGaps',
> stmt='fillGaps([1, 5000])')
> print "new fillgaps:", t.timeit(number =100)
>
> print "timing with many small gaps:"
> t = timeit.Timer(se tup='from fillgaps import fillGaps1 as
> fillGaps;l=rang e(1,5001,2)',
> stmt='fillGaps( l)')[/color]

I think the list should be initialized in the statement instead of the
setup. Otherwise subsequent passes will measure for range(1, 5000).
[color=blue]
> print "old fillgaps:", t.timeit(number =100)
> t = timeit.Timer(se tup='from fillgaps import
> fillGaps;l=rang e(1,5001,2)',
> stmt='fillGaps( l)')
> print "new fillgaps:", t.timeit(number =100)
>
> import unittest
> class test(unittest.T estCase):
> def test(self):
> for fg in (fillGaps1, fillGaps):
> l = [1, 2, 4, 7, 8, 12]
> fg(l)
> self.assertEqua ls(l, range(1, 13))
>
> l = [1, 5000]
> fg(l)
> self.assertEqua ls(l, range(1, 5001))
>
> unittest.main()[/color]

Here's another fillgap version:

def fillGapsPeter(s eq):
# 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(se q):
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(se q):
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(getatt r(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(se tup='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.T estCase):
def test_all(self):
for fg in [getattr(fillgap s, fn) for fn in fnames]:
l = [1, 2, 4, 7, 8, 12]
fg(l)
self.assertEqua ls(l, range(1, 13))

l = [1, 5000]
fg(l)
self.assertEqua ls(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__(se lf)

original = map(myint, [1, 2, 4, 7, 8, 12])
l = list(original)
fillGapsPeter(l )
self.assertEqua ls(l, range(1, 13))
for i in original:
self.assert_(i is l[i-1])
self.assert_(re pr(i).startswit h("my"))
unittest.main()

My findings:

original test case
fillGapsMark: 0.0015141963958 7
fillGapsPeter: 0.0012738704681 4
fillGapsSkip: 0.0016269683837 9

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

[Peter Abel]

Re: Inserting while itterating

"Thomas Guettler" <guettli@thom as-guettler.de> wrote in message news:<pan.2004. 01.14.08.43.00. 894047@thomas-guettler.de>...[color=blue]
> 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[/color]

[color=blue][color=green][color=darkred]
>>> l = [1, 2, 4, 7, 8, 12]
>>> id(l)[/color][/color][/color]
27295112[color=blue][color=green][color=darkred]
>>> for i in range(len(l)-1,0,-1):[/color][/color][/color]
.... for j in range(l[i]-l[i-1]-1):
.... l.insert(i,l[i]-1)
....[color=blue][color=green][color=darkred]
>>> id(l)[/color][/color][/color]
27295112[color=blue][color=green][color=darkred]
>>> l[/color][/color][/color]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12][color=blue][color=green][color=darkred]
>>>[/color][/color][/color]

Tested, but no idea about timing.

Regards
Peter

[Jeremy Bowers]

Re: Inserting while itterating

On Wed, 14 Jan 2004 09:43:01 +0100, Thomas Guettler wrote:
[color=blue]
> 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[/color]

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.

[Paul Rubin]

Re: Inserting while itterating

Jeremy Bowers <jerf@jerf.or g> writes:[color=blue]
> 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.[/color]

Um, why the list comprehension? Something wrong with

l[:] = range(min(l), max(l) + 1)

?