python bisect questions
Gabriel Genellina
gagsl-py2 at yahoo.com.ar
Thu Apr 3 19:34:15 EDT 2008
En Thu, 03 Apr 2008 19:21:19 -0300, <ankitks.mital at gmail.com> escribió:
> On Apr 3, 4:24 pm, "Terry Reedy" <tjre... at udel.edu> wrote:
>> <ankitks.mi... at gmail.com> wrote in message
>>
>> news:6bb6927b-f553-40db-a142-2ce86b9e819f at q27g2000prf.googlegroups.com...
>> |I am week on functional programming, and having hard time
>> | understanding this:
>> |
>> | class myPriorityQueue:
>> | def __init__(self, f=lamda x:x):
>> | self.A = []
>> | self.f = f
>> |
>> | def append(self, item)
>> | bisect.insort(self.A, (self.f(item), item))
>> | ............
>> |
>> | now I know we are inserting items(user defined type objects) in list A
>> | base on sorting order provided by function A.
>> | but what I don't understand is bisect command
>> | what does bisect.insort(self.A, (self.f(item), item)) doing
>
> but I am still confuse. self.A is my list a. and item is x that
> I am trying to insert.
> So it needs to be of type item not (self.f(item), item)
> It doesn't say anything pass sorting function self.f(item).
bisect doesn't handle a custom defined sort function. So you have two
choices:
a) Define a comparison method for your items (__cmp__ is the simplest way)
so when Python evaluates x<y it actually calls your custom defined method.
This applies when items have an intrinsic ordering and you want to use
that ordering.
For example, define a __cmp__ method to compare text case-insensitively.
<code>
from bisect import insort
class CustomClass(object):
"""Holds some text."""
def __init__(self, text):
self.text = text
def __repr__(self):
return repr(self.text)
def __cmp__(self, other):
"""Case insensitive comparison.
>>> assert CustomClass("Z") > CustomClass("abc")
>>> assert CustomClass("AbC") == CustomClass("aBc")
>>> assert CustomClass("abc") < CustomClass("bcd")
"""
return cmp(self.text.upper(), other.text.upper())
x1 = CustomClass("bcd")
x2 = CustomClass("abC")
x3 = CustomClass("Z")
x4 = CustomClass("AbC")
queue = []
insort(queue, x1)
print queue
insort(queue, x2)
print queue
insort(queue, x3)
print queue
insort(queue, x4)
print queue
</code>
b) Define a function to extract a "key" from your items such that items
compare the same as their keys. For example, key(x) -> x.lower() may be
used to compare text case-insensitively.
Then, use a tuple (key, value) instead of the bare value. When extracting
items from the queue, remember to unpack both parts. This is known as the
decorate-sort-undecorate pattern; google for it.
This is the approach used on your code snippet.
<code>
def keyfunc(x):
return x.lower()
x1 = "bcd"
x2 = "abC"
x3 = "Z"
x4 = "AbC"
queue = []
insort(queue, (keyfunc(x1),x1))
print queue
insort(queue, (keyfunc(x2),x2))
print queue
insort(queue, (keyfunc(x3),x3))
print queue
insort(queue, (keyfunc(x4),x4))
print queue
print [value for (key,value) in queue]
</code>
--
Gabriel Genellina
More information about the Python-list
mailing list