python bisect questions

Discussion in 'Python' started by ankitks.mital@gmail.com, Apr 3, 2008.

  1. Guest

    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
    , Apr 3, 2008
    #1
    1. Advertising

  2. Terry Reedy Guest

    <> wrote in message
    news:...
    |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
    Terry Reedy, Apr 3, 2008
    #2
    1. Advertising

  3. Guest

    On Apr 3, 4:24 pm, "Terry Reedy" <> wrote:
    > <> wrote in message
    >
    > news:...
    > |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?


    >
    > 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
    , Apr 3, 2008
    #3
  4. John Machin Guest

    On Apr 4, 9:21 am, wrote:
    > On Apr 3, 4:24 pm, "Terry Reedy" <> wrote:
    >
    >
    >
    >
    >
    >
    >
    > > <> wrote in message

    >
    > >news:...
    > > |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.
    John Machin, Apr 3, 2008
    #4
  5. Guest

    On Apr 3, 5:43 pm, John Machin <> wrote:
    > On Apr 4, 9:21 am, wrote:
    >
    >
    >
    >
    >
    > > On Apr 3, 4:24 pm, "Terry Reedy" <> wrote:

    >
    > > > <> wrote in message

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

    >
    > 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 -
    , Apr 4, 2008
    #5
  6. En Thu, 03 Apr 2008 19:21:19 -0300, <> escribió:

    > On Apr 3, 4:24 pm, "Terry Reedy" <> wrote:
    >> <> wrote in message
    >>
    >> news:...
    >> |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
    Gabriel Genellina, Apr 4, 2008
    #6
  7. Guest

    Thanks Gabriel
    , Apr 4, 2008
    #7
  8. Guest


    >
    > 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?
    , Apr 4, 2008
    #8
  9. En Fri, 04 Apr 2008 18:08:57 -0300, <> 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
    Gabriel Genellina, Apr 4, 2008
    #9
    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:
    324
    Gary Robinson
    Jul 29, 2003
  2. Replies:
    0
    Views:
    322
  3. SA Trygubenko

    bisect and Queue modules in Python 2.4

    SA Trygubenko, Mar 16, 2006, in forum: Python
    Replies:
    2
    Views:
    728
    Alex Martelli
    Mar 16, 2006
  4. Paulo da Silva

    bisect on a list of lists

    Paulo da Silva, Mar 9, 2007, in forum: Python
    Replies:
    9
    Views:
    369
    Gabriel Genellina
    Mar 10, 2007
  5. Robert Bossy

    why not bisect options?

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

Share This Page