bisect on a list of lists

Discussion in 'Python' started by Paulo da Silva, Mar 9, 2007.

  1. Hi!

    What is the best way to have something like the bisect_left
    method on a list of lists being the comparision based on an
    specified arbitrary i_th element of each list element?

    Is there, for lists, something equivalent to the __cmp__ function for
    classes?

    Thanks.
     
    Paulo da Silva, Mar 9, 2007
    #1
    1. Advertising

  2. En Fri, 09 Mar 2007 17:15:44 -0300, Paulo da Silva
    <> escribió:

    > What is the best way to have something like the bisect_left
    > method on a list of lists being the comparision based on an
    > specified arbitrary i_th element of each list element?
    >
    > Is there, for lists, something equivalent to the __cmp__ function for
    > classes?


    lists *are* classes (at least since Python 2.2)
    Inherit from the builtin list, redefine __cmp__(self, other) as
    cmp(self[i_th], other[i_th])
    and then redefine all the rich comparison methods (__eq__, __lt__, etc)
    using __cmp__, e.g. __le__(self, other) as __cmp__(self, other)<=0 etc.
    See http://docs.python.org/ref/customization.html

    --
    Gabriel Genellina
     
    Gabriel Genellina, Mar 9, 2007
    #2
    1. Advertising

  3. Paulo da Silva

    Guest

    Paulo da Silva:
    > What is the best way to have something like the bisect_left
    > method on a list of lists being the comparision based on an
    > specified arbitrary i_th element of each list element?


    You may use this recipe of mine that I've just put there for you, but
    it's not fully tested yet (if you spot problems I'm willing to fix
    them):
    http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/502295

    Or you can create a little class, that wraps your list with just a
    __cmp__ method that works on the n-th element of the list. Then you
    can use heapq on many instances of that class created with a list
    comphrension.

    Probably there are other solutions too.

    Bye,
    bearophile
     
    , Mar 9, 2007
    #3
  4. Paulo da Silva

    Peter Otten Guest

    Paulo da Silva wrote:

    > What is the best way to have something like the bisect_left
    > method on a list of lists being the comparision based on an
    > specified arbitrary i_th element of each list element?


    A simple way that leaves the lists untouched:

    >>> import bisect, random
    >>> from operator import itemgetter
    >>> items = [random.sample(xrange(10), 3) for _ in range(7)]
    >>> items.sort(key=itemgetter(2))
    >>> items

    [[1, 7, 0], [9, 6, 1], [9, 8, 1], [9, 3, 2], [2, 1, 3], [9, 2, 4], [5, 2,
    7]]
    >>> class C(object):

    .... def __init__(self, value, index):
    .... self.value = value
    .... self.index = index
    .... def __cmp__(self, other):
    .... return cmp(self.value, other[self.index])
    ....
    >>> bisect.bisect_left(items, C(2, 2))

    3

    Peter
     
    Peter Otten, Mar 9, 2007
    #4
  5. Gabriel Genellina escreveu:
    > En Fri, 09 Mar 2007 17:15:44 -0300, Paulo da Silva
    > <> escribió:

    ....

    >
    > lists *are* classes (at least since Python 2.2)
    > Inherit from the builtin list, redefine __cmp__(self, other) as

    ....

    Thanks Gabriel. This sounds very nice for my purpose.
    I have some doubts however. How do I "transform" a list into
    MyList? Is this the best way?

    class MyList(list):
    def __init__(self,l=None):
    if l != None:
    self=copy(l) (or self.extend(l) - this does not need copy module)

    Then I can do something like xl=MyList([ ... ])

    I read the description of __new__ but I didn't fully understand it and
    didn't find any examples on how it is used.
    Is it usable in this context? How?

    Thanks
    Paulo
     
    Paulo da Silva, Mar 10, 2007
    #5
  6. En Fri, 09 Mar 2007 21:25:24 -0300, Paulo da Silva
    <> escribió:

    > Thanks Gabriel. This sounds very nice for my purpose.
    > I have some doubts however. How do I "transform" a list into
    > MyList? Is this the best way?
    >
    > class MyList(list):
    > def __init__(self,l=None):
    > if l != None:
    > self=copy(l) (or self.extend(l) - this does not need copy module)
    >
    > Then I can do something like xl=MyList([ ... ])


    Just omit the __init__ method, if you don't have anything additional to
    do. The inherited method will be used instead, as always:

    py> class MyList(list):
    .... def cdr(self):
    .... return self[1:]
    ....
    py> a = MyList([1,2,3])
    py> a
    [1, 2, 3]
    py> type(a)
    <class '__main__.MyList'>
    py> a.cdr()
    [2, 3]

    > I read the description of __new__ but I didn't fully understand it and
    > didn't find any examples on how it is used.
    > Is it usable in this context? How?


    Not really. Would be useful for a tuple (inmutable), because it has no
    __init__. But ask again when you really need it :)

    --
    Gabriel Genellina
     
    Gabriel Genellina, Mar 10, 2007
    #6
  7. On Fri, 09 Mar 2007 18:57:42 -0300, Gabriel Genellina wrote:

    > En Fri, 09 Mar 2007 17:15:44 -0300, Paulo da Silva
    > <> escribió:
    >
    >> What is the best way to have something like the bisect_left
    >> method on a list of lists being the comparision based on an
    >> specified arbitrary i_th element of each list element?
    >>
    >> Is there, for lists, something equivalent to the __cmp__ function for
    >> classes?

    >
    > lists *are* classes (at least since Python 2.2)


    Not quite. Classes and types are *almost* the same, but not exactly.

    >>> type(list)

    <type 'type'>
    >>> class Spam:

    .... pass
    ....
    >>> type(Spam)

    <type 'classobj'>

    Usually the difference doesn't make a difference, but sometimes it does.

    >>> Spam.x = 3
    >>> list.x = 3

    Traceback (most recent call last):
    File "<stdin>", line 1, in ?
    TypeError: can't set attributes of built-in/extension type 'list'




    --
    Steven.
     
    Steven D'Aprano, Mar 10, 2007
    #7
  8. En Fri, 09 Mar 2007 23:45:50 -0300, Steven D'Aprano
    <> escribió:

    > On Fri, 09 Mar 2007 18:57:42 -0300, Gabriel Genellina wrote:
    >
    >> En Fri, 09 Mar 2007 17:15:44 -0300, Paulo da Silva
    >> <> escribió:
    >>
    >>> What is the best way to have something like the bisect_left
    >>> method on a list of lists being the comparision based on an
    >>> specified arbitrary i_th element of each list element?
    >>>
    >>> Is there, for lists, something equivalent to the __cmp__ function for
    >>> classes?

    >>
    >> lists *are* classes (at least since Python 2.2)

    >
    > Not quite. Classes and types are *almost* the same, but not exactly.


    I were talking about new style classes, that's why I said Python 2.2

    >>>> type(list)

    > <type 'type'>
    >>>> class Spam:

    > ... pass
    > ...
    >>>> type(Spam)

    > <type 'classobj'>


    py> class New(object): pass
    ....
    py> type(New)
    <type 'type'>

    New-style clases are instances of type too (like list, tuple and other
    builtins), and subclasses of object:

    py> New.mro()
    [<class '__main__.New'>, <type 'object'>]
    py> list.mro()
    [<type 'list'>, <type 'object'>]

    > Usually the difference doesn't make a difference, but sometimes it does.
    >
    >>>> Spam.x = 3
    >>>> list.x = 3

    > Traceback (most recent call last):
    > File "<stdin>", line 1, in ?
    > TypeError: can't set attributes of built-in/extension type 'list'


    That's not because list is a builtin type, but because it lacks (by
    design) any means to store instance attributes (it has an empty
    tp_dictoffset slot, by example).
    Functions, exceptions, modules are examples of builtin types whose
    instances can handle attributes.

    --
    Gabriel Genellina
     
    Gabriel Genellina, Mar 10, 2007
    #8
  9. Gabriel Genellina escreveu:
    ....

    > Just omit the __init__ method, if you don't have anything additional to
    > do. The inherited method will be used instead, as always:



    Then, if I have something additional, I can do
    def __init__(self,l=None):
    if l!=None:
    list.__init__(self,l)
    ...

    Good! This is great!
    Thanks.
     
    Paulo da Silva, Mar 10, 2007
    #9
  10. En Sat, 10 Mar 2007 01:23:11 -0300, Paulo da Silva
    <> escribió:

    > Gabriel Genellina escreveu:
    >
    >> Just omit the __init__ method, if you don't have anything additional to
    >> do. The inherited method will be used instead, as always:

    >
    >
    > Then, if I have something additional, I can do
    > def __init__(self,l=None):
    > if l!=None:
    > list.__init__(self,l)
    > ...


    Yes, something like that.

    --
    Gabriel Genellina
     
    Gabriel Genellina, Mar 10, 2007
    #10
    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. Gary Robinson

    bisect uses __cmp__()?

    Gary Robinson, Jul 29, 2003, in forum: Python
    Replies:
    0
    Views:
    333
    Gary Robinson
    Jul 29, 2003
  2. Replies:
    0
    Views:
    332
  3. SA Trygubenko

    bisect and Queue modules in Python 2.4

    SA Trygubenko, Mar 16, 2006, in forum: Python
    Replies:
    2
    Views:
    738
    Alex Martelli
    Mar 16, 2006
  4. =?UTF-8?B?w4FuZ2VsIEd1dGnDqXJyZXogUm9kcsOtZ3Vleg==

    List of lists of lists of lists...

    =?UTF-8?B?w4FuZ2VsIEd1dGnDqXJyZXogUm9kcsOtZ3Vleg==, May 8, 2006, in forum: Python
    Replies:
    5
    Views:
    410
    =?UTF-8?B?w4FuZ2VsIEd1dGnDqXJyZXogUm9kcsOtZ3Vleg==
    May 15, 2006
  5. Robert Bossy

    why not bisect options?

    Robert Bossy, Feb 29, 2008, in forum: Python
    Replies:
    7
    Views:
    279
    Robert Bossy
    Mar 4, 2008
Loading...

Share This Page