inner sublist positions ?

Discussion in 'Python' started by Bernard A., Apr 20, 2005.

  1. Bernard A.

    Bernard A. Guest

    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,
    Bernard A., Apr 20, 2005
    #1
    1. Advertising

  2. 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
    Steven Bethard, Apr 21, 2005
    #2
    1. Advertising

  3. Bernard A.

    tiissa Guest

    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
    tiissa, Apr 21, 2005
    #3
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Paul Whipp
    Replies:
    1
    Views:
    365
    Alex Martelli
    Nov 7, 2003
  2. giampiero mu

    finding sublist

    giampiero mu, Aug 2, 2005, in forum: Python
    Replies:
    5
    Views:
    379
    Johan Lindberg
    Aug 3, 2005
  3. Knut Krueger
    Replies:
    2
    Views:
    434
    Knut Krueger
    May 21, 2007
  4. Helmut Jarausch

    append to a sublist - please help

    Helmut Jarausch, Apr 6, 2008, in forum: Python
    Replies:
    2
    Views:
    347
  5. Matthias Gallé

    find sublist inside list

    Matthias Gallé, May 4, 2009, in forum: Python
    Replies:
    13
    Views:
    1,196
    mzdude
    May 5, 2009
Loading...

Share This Page