Inserting while itterating

[Skip Montanaro]

>>>>> "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()