python bisect questions

[ankitks.mital]

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

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

 

[Terry Reedy]

|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

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

 

[ankitks.mital]

|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

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?

 

[John Machin]

<[email protected]> wrote in message

|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

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.

 

[ankitks.mital]

|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

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.

 

[Gabriel Genellina]

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

 

[ankitks.mital]

Thanks Gabriel

 

[ankitks.mital]

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?

 

[Gabriel Genellina]

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.