bisect on a list of lists

[Paulo da Silva]

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.

 

[Gabriel Genellina]

En Fri, 09 Mar 2007 17:15:44 -0300, 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?

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

 

[bearophileHUGS]

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

 

[Peter Otten]

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]].... def __init__(self, value, index):
.... self.value = value
.... self.index = index
.... def __cmp__(self, other):
.... return cmp(self.value, other[self.index])
....3

Peter

 

[Paulo da Silva]

Gabriel Genellina escreveu:

En Fri, 09 Mar 2007 17:15:44 -0300, Paulo da Silva
<[email protected]> 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

 

[Gabriel Genellina]

En Fri, 09 Mar 2007 21:25:24 -0300, Paulo da Silva

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

 

[Steven D'Aprano]

En Fri, 09 Mar 2007 17:15:44 -0300, Paulo da Silva


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

Not quite. Classes and types are *almost* the same, but not exactly.
.... pass
....<type 'classobj'>

Usually the difference doesn't make a difference, but sometimes it does.
Traceback (most recent call last):
File "<stdin>", line 1, in ?
TypeError: can't set attributes of built-in/extension type 'list'

 

[Gabriel Genellina]

En Fri, 09 Mar 2007 23:45:50 -0300, Steven D'Aprano

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

... pass
...
<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()

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

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.

 

[Paulo da Silva]

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.

 

[Gabriel Genellina]

En Sat, 10 Mar 2007 01:23:11 -0300, Paulo da Silva

Gabriel Genellina escreveu:



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.