Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Python > python bisect questions

Reply
Thread Tools

python bisect questions

 
 
ankitks.mital@gmail.com
Guest
Posts: n/a
 
      04-03-2008
I am week on functional programming, and having hard time
understanding this:

class myPriorityQueue:
def __init__(self, f=lamda 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

isn't it is returning truple of (self.f(item), item)).
why it is not
biset.insort(self.A, item)
A.sort(f)

thanks for your comments
 
Reply With Quote
 
 
 
 
Terry Reedy
Guest
Posts: n/a
 
      04-03-2008

<(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...
|I am week on functional programming, and having hard time
| understanding this:
|
| class myPriorityQueue:
| def __init__(self, f=lamda 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

The snippet is missing 'import bisect'. The module is documented in the
Lib Ref. Or, in the interpreter, help(bisect.insort) redirects you to
help(bisect.insort_right), which will answer your question.

| isn't it is returning truple of (self.f(item), item)).

no, see doc

| why it is not
| biset.insort(self.A, item)
| A.sort(f)

Efficiency, given that self.A is already sorted.

tjr



 
Reply With Quote
 
 
 
 
ankitks.mital@gmail.com
Guest
Posts: n/a
 
      04-03-2008
On Apr 3, 4:24*pm, "Terry Reedy" <(E-Mail Removed)> wrote:
> <(E-Mail Removed)> wrote in message
>
> news:(E-Mail Removed)...
> |I am week on functional programming, and having hard time
> | understanding this:
> |
> | class myPriorityQueue:
> | * * *def __init__(self, f=lamda 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


here is doc
insort_right(a, x[, lo[, hi]])

Insert item x in list a, and keep it sorted assuming a is sorted.

If x is already in a, insert it to the right of the rightmost x.

Optional args lo (default 0) and hi (default len(a)) bound the
slice of a to be searched.

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).
Also I am new to Python
Please help?


>
> The snippet is missing 'import bisect'. *The module is documented in the
> Lib Ref. *Or, in the interpreter, help(bisect.insort) redirects you to
> help(bisect.insort_right), which will answer your question.
>
> | isn't it is returning truple of (self.f(item), item)).
>
> no, see doc
>
> | why it is not
> | biset.insort(self.A, item)
> | A.sort(f)
>
> Efficiency, given that self.A is already sorted.
>
> tjr


 
Reply With Quote
 
John Machin
Guest
Posts: n/a
 
      04-03-2008
On Apr 4, 9:21 am, (E-Mail Removed) wrote:
> On Apr 3, 4:24 pm, "Terry Reedy" <(E-Mail Removed)> wrote:
>
>
>
>
>
>
>
> > <(E-Mail Removed)> wrote in message

>
> >news:(E-Mail Removed)...
> > |I am week on functional programming, and having hard time
> > | understanding this:
> > |
> > | class myPriorityQueue:
> > | def __init__(self, f=lamda 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

>
> here is doc
> insort_right(a, x[, lo[, hi]])
>
> Insert item x in list a, and keep it sorted assuming a is sorted.
>
> If x is already in a, insert it to the right of the rightmost x.
>
> Optional args lo (default 0) and hi (default len(a)) bound the
> slice of a to be searched.
>
> 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).


That's correct. You are passing a tuple of (sort_key, actual_data).

Example use case: caseless sortorder but you want to retrieve the
original data. f is lambda x: x.upper() or similar. Your data is
'foo', 'Bar', 'zOt'. Calls to your_queue.append will result in the
following 2nd args for bisect.insort:
('FOO', 'foo')
('BAR', 'Bar')
('ZOT', 'zOt')

Consider executing the code with a couple of print statements in it so
that you can see what is happening.
 
Reply With Quote
 
ankitks.mital@gmail.com
Guest
Posts: n/a
 
      04-03-2008
On Apr 3, 5:43*pm, John Machin <(E-Mail Removed)> wrote:
> On Apr 4, 9:21 am, (E-Mail Removed) wrote:
>
>
>
>
>
> > On Apr 3, 4:24 pm, "Terry Reedy" <(E-Mail Removed)> wrote:

>
> > > <(E-Mail Removed)> wrote in message

>
> > >news:(E-Mail Removed)....
> > > |I am week on functional programming, and having hard time
> > > | understanding this:
> > > |
> > > | class myPriorityQueue:
> > > | * * *def __init__(self, f=lamda 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

>
> > here is doc
> > insort_right(a, x[, lo[, hi]])

>
> > * * Insert item x in list a, and keep it sorted assuming a is sorted..

>
> > * * If x is already in a, insert it to the right of the rightmost x.

>
> > * * Optional args lo (default 0) and hi (default len(a)) bound the
> > * * slice of a to be searched.

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

>
> That's correct. You are passing a tuple of (sort_key, actual_data).
>
> Example use case: caseless sortorder but you want to retrieve the
> original data. f is lambda x: x.upper() or similar. Your data is
> 'foo', 'Bar', 'zOt'. Calls to your_queue.append will result in the
> following 2nd args for bisect.insort:
> ('FOO', 'foo')
> ('BAR', 'Bar')
> ('ZOT', 'zOt')


Thanks John and Terry,
Wow! great way to keep original values with transformation.
Thanks for explaining.

>
> Consider executing the code with a couple of print statements in it so
> that you can see what is happening.- Hide quoted text -
>
> - Show quoted text -


 
Reply With Quote
 
Gabriel Genellina
Guest
Posts: n/a
 
      04-03-2008
En Thu, 03 Apr 2008 19:21:19 -0300, <(E-Mail Removed)> escribió:

> On Apr 3, 4:24*pm, "Terry Reedy" <(E-Mail Removed)> wrote:
>> <(E-Mail Removed)> wrote in message
>>
>> news:(E-Mail Removed)...
>> |I am week on functional programming, and having hard time
>> | understanding this:
>> |
>> | class myPriorityQueue:
>> | * * *def __init__(self, f=lamda 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

 
Reply With Quote
 
ankitks.mital@gmail.com
Guest
Posts: n/a
 
      04-04-2008
Thanks Gabriel

 
Reply With Quote
 
ankitks.mital@gmail.com
Guest
Posts: n/a
 
      04-04-2008

>
> 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>


I liked decorate-sort-undecorate pattern idea.
But is there anyway I can provide information for tie breaking.
so for case, where keyfunc(x) returns same values,
I need to provide additional tie-breaking rules, is that possible to
do?
 
Reply With Quote
 
Gabriel Genellina
Guest
Posts: n/a
 
      04-04-2008
En Fri, 04 Apr 2008 18:08:57 -0300, <(E-Mail Removed)> escribió:

>> 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.
>>

> I liked decorate-sort-undecorate pattern idea.
> But is there anyway I can provide information for tie breaking.
> so for case, where keyfunc(x) returns same values,
> I need to provide additional tie-breaking rules, is that possible to
> do?


Use as much elements in the tuple as you need. By example, you could have
(year, month, amount, invoice_object) - you would get invocies sorted by
year, then by month, then by amount.

--
Gabriel Genellina

 
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
why not bisect options? Robert Bossy Python 7 03-04-2008 05:36 PM
bisect on a list of lists Paulo da Silva Python 9 03-10-2007 04:49 AM
bisect and Queue modules in Python 2.4 SA Trygubenko Python 2 03-16-2006 03:33 PM
plebe comment re [Python-Dev] SF patch 864863: Bisect Cimplementation cognizor@cognizor.com Python 0 01-16-2004 07:41 PM
bisect uses __cmp__()? Gary Robinson Python 0 07-29-2003 08:05 PM



Advertisments