Velocity Reviews > inner sublist positions ?

# inner sublist positions ?

Bernard A.
Guest
Posts: n/a

 04-20-2005
hello,

while trying to play with generator, i was looking for an idea to get
the position of a inner list inside another one, here is my first idea
:
- first find position of first inner element,
- and then see if the slice starting from here is equal to the inner
->

>>> def subPositions(alist, innerlist):

if innerlist == []:
return
first, start = innerlist[0], 0
while 1:
try:
p = alist[start:].index(first)
except ValueError:
break # or should i better use return ?
start = start + p
if alist[start: start + len(innerlist)] == innerlist:
yield start, start + len(innerlist)
start += 1

>>> list(subPositions(range(5) + range(5), [2,3]))

[(2, 4), (7, 9)]

maybe have you some better / faster ideas / implementations ? or even
a more pythonic to help me learning that

game2 => how can i imagine a way to have the inclusion test rather
be a test upon a regular expression ? i mean instead of checking for
an inner list, rather checking for an "inner regular expression"
matching upon consecutives items of a list ? (btw it isn't still not
really clear in my own mind, but it looks like ideas from here are
always clever one, it may help

best,

Steven Bethard
Guest
Posts: n/a

 04-20-2005
Bernard A. wrote:
> hello,
>
> while trying to play with generator, i was looking for an idea to get
> the position of a inner list inside another one, here is my first idea
> :
> - first find position of first inner element,
> - and then see if the slice starting from here is equal to the inner
> ->
>
>>>>def subPositions(alist, innerlist):

>
> if innerlist == []:
> return
> first, start = innerlist[0], 0
> while 1:
> try:
> p = alist[start:].index(first)
> except ValueError:
> break # or should i better use return ?
> start = start + p
> if alist[start: start + len(innerlist)] == innerlist:
> yield start, start + len(innerlist)
> start += 1
>
>
>
>>>>list(subPositions(range(5) + range(5), [2,3]))

>
> [(2, 4), (7, 9)]
>
> maybe have you some better / faster ideas / implementations ? or even
> a more pythonic to help me learning that

I don't know if this is any faster, but you could try:

py> def indexes(lst, sublist):
.... sublen = len(sublist)
.... for i in range(len(lst)):
.... if lst[i:i+sublen] == sublist:
.... yield i, i+sublen
....
py> list(indexes(range(5) + range(5), [2, 3]))
[(2, 4), (7, 9)]

Use the timeit module to see if it's any faster. Also, in your version
you should probably use
p = alist.index(first, start)
p = alist[start:].index(first)
so you don't make so many new lists.

STeVe

tiissa
Guest
Posts: n/a

 04-21-2005
Bernard A. wrote:
> maybe have you some better / faster ideas / implementations ? or even
> a more pythonic to help me learning that

You may want to look at string matches algorithm (a good review: [1]).
In particular there are classics like Boyer-Moore and some involving
minimal automatons similar to your regular expression ideas.

[1] http://www-igm.univ-mlv.fr/~lecroq/string/index.html