Python, converting a list of indices to slices

Question

So I have a list of indices,

[0, 1, 2, 3, 5, 7, 8, 10]

and want to convert it to this,

[[0, 3], [5], [7, 8], [10]]

this will run on a large number of indices.

Also, this technically isn't for slices in python, the tool I am working with is faster when given a range compared to when given the individual ids.

The pattern is based on being in a range, like slices work in python. So in the example, the 1 and 2 are dropped because they are already included in the range of 0 to 3. The 5 would need accessed individually since it is not in a range, etc. This is more helpful when a large number of ids get included in a range such as [0, 5000].

Answer 1

Since you want the code to be fast, I wouldn't try to be too fancy. A straight-forward approach should perform quite well:

a = [0, 1, 2, 3, 5, 7, 8, 10]
it = iter(a)
start = next(it)
slices = []
for i, x in enumerate(it):
    if x - a[i] != 1:
        end = a[i]
        if start == end:
            slices.append([start])
        else:
            slices.append([start, end])
        start = x
if a[-1] == start:
    slices.append([start])
else:
    slices.append([start, a[-1]])

Admittedly, that's doesn't look too nice, but I expect the nicer solutions I can think of to perform worse. (I did not do a benchmark.)

Here is s slightly nicer, but slower solution:

from itertools import groupby
a = [0, 1, 2, 3, 5, 7, 8, 10]
slices = []
for key, it in groupby(enumerate(a), lambda x: x[1] - x[0]):
    indices = [y for x, y in it]
    if len(indices) == 1:
        slices.append([indices[0]])
    else:
        slices.append([indices[0], indices[-1]])

Answer 2

def runs(seq):
    previous = None
    start = None
    for value in itertools.chain(seq, [None]):
        if start is None:
            start = value
        if previous is not None and value != previous + 1:
            if start == previous:
                yield [previous]
            else:
                yield [start, previous]
            start = value
        previous = value