Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Python > inner sublist positions ?

Reply
Thread Tools

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,
 
Reply With Quote
 
 
 
 
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)
instead of
p = alist[start:].index(first)
so you don't make so many new lists.

STeVe
 
Reply With Quote
 
 
 
 
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

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
find sublist inside list Matthias Gallé Python 13 05-05-2009 10:26 AM
append to a sublist - please help Helmut Jarausch Python 2 04-06-2008 05:36 PM
fixed positions of images versus relative positions Knut Krueger HTML 2 05-21-2007 10:18 AM
finding sublist giampiero mu Python 5 08-03-2005 04:52 PM
sublist copies result in behavioural anomoly Paul Whipp Python 1 11-07-2003 08:51 AM



Advertisments