Home > Software engineering >  Customized scan of lists for consecutive values
Customized scan of lists for consecutive values

Time:12-22

I have a list as follows:

A = [3 1 2 3 0 4 3 1 2 3 1 0 0 0 1]

Given an initial index (e.g., id = 5), I would like to find the index of the last item (ld) in the list such that all values between id and ld are greater than zero (inclusive). Consider this example:

If id = 5 (A[5] = 4), ld = 10 (ld = 1).

A = [3 1 2 3 0 4 3 1 2 3 1 0 0 0 1]

What would be the most efficient way for doing so?

CodePudding user response:

You can have a companion list that contains True iff the condition (element > 0) is met, and add a sentinel (False) at the end. Then you can just use list.index(value, start) to find the next False from a given position. At least, if you are going to do several such "queries" on your given list, you'll have looped only once explicitly (each .index() also does an iteration, internally, but faster).

Putting it all together:

p = [x > 0 for x in A]   [False]

# then
id_ = 5  # don't shadow id
p.index(False, id_) - 1
# gives 10

CodePudding user response:

Here is a solution that avoids using explicit indexes on the list, only scans the relevant elements and does it once only

import itertools as it
from typing import Iterable


def f(iterable: Iterable, start: int) -> int:
    try:
        pos, _ = next(
            it.dropwhile(
                lambda el: el[1]>0,
                enumerate(
                    it.islice(iterable, start, None),
                    start=start
                )
            )
        )
    except StopIteration:
        pos = len(iterable)
    return pos - 1


a = [3, 1, 2, 3, 0, 4, 3, 1, 2, 3, 1, 0, 0, 0, 1]
print(f(a, 5))

b = [3, 1, 2, 3, 0, 4, 3, 1, 2, 3, 1, 3, 3, 3, 1]
print(f(b, 5))

which produces

10
14
  • Related