# Inserting while itterating

Skip Montanaro skip at pobox.com
Thu Jan 15 21:51:35 CET 2004

```>>>>> "Mark" == Mark McEahern <mark at 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()

```