Binary search tree

Discussion in 'Python' started by maxim.novak@gmail.com, Nov 9, 2007.

  1. Guest

    Hi,

    I have to get list of URLs one by one and to find the URLs that I have
    more than one time(can't be more than twice).

    I thought to put them into binary search tree, this way they'll be
    sorted and I'll be able to check if the URL already exist.

    Couldn't find any python library that implements trees.
    Is there some library of this kind in python? Or can I find it
    somewhere else?
     
    , Nov 9, 2007
    #1
    1. Advertising

  2. Larry Bates Guest

    wrote:
    > Hi,
    >
    > I have to get list of URLs one by one and to find the URLs that I have
    > more than one time(can't be more than twice).
    >
    > I thought to put them into binary search tree, this way they'll be
    > sorted and I'll be able to check if the URL already exist.
    >
    > Couldn't find any python library that implements trees.
    > Is there some library of this kind in python? Or can I find it
    > somewhere else?
    >

    Put them into a set. You can check for existence (very fast) and at the end it
    is easy to sort.

    -Larry
     
    Larry Bates, Nov 9, 2007
    #2
    1. Advertising

  3. Neil Cerutti Guest

    On 2007-11-09, Larry Bates <> wrote:
    > wrote:
    >> I have to get list of URLs one by one and to find the URLs
    >> that I have more than one time(can't be more than twice).
    >>
    >> I thought to put them into binary search tree, this way
    >> they'll be sorted and I'll be able to check if the URL already
    >> exist.
    >>
    >> Couldn't find any python library that implements trees. Is
    >> there some library of this kind in python? Or can I find it
    >> somewhere else?

    >
    > Put them into a set. You can check for existence (very fast)
    > and at the end it is easy to sort.


    The set is likely the way to go.

    Python's library support for binary search trees consists of the
    bisect module.

    --
    Neil Cerutti
    Ask about our plans for owning your home --sign at mortgage company
     
    Neil Cerutti, Nov 9, 2007
    #3
  4. D.Hering Guest

    On Nov 9, 4:06 pm, wrote:
    > Hi,
    >
    > I have to get list of URLs one by one and to find the URLs that I have
    > more than one time(can't be more than twice).
    >
    > I thought to put them into binary search tree, this way they'll be
    > sorted and I'll be able to check if the URL already exist.
    >
    > Couldn't find any python library that implements trees.
    > Is there some library of this kind in python? Or can I find it
    > somewhere else?


    Can you use set() or set.difference()?
     
    D.Hering, Nov 9, 2007
    #4
  5. a écrit :
    > Hi,
    >
    > I have to get list of URLs one by one and to find the URLs that I have
    > more than one time(can't be more than twice).
    >
    > I thought to put them into binary search tree, this way they'll be
    > sorted and I'll be able to check if the URL already exist.


    What about a set ?

    s = set()
    for url in urls:
    if url in s:
    print "already have ", url
    else:
    set.add(url)
     
    Bruno Desthuilliers, Nov 9, 2007
    #5
  6. On Nov 9, 11:45 pm, Bruno Desthuilliers
    <> wrote:
    > a écrit :
    >
    > > Hi,

    >
    > > I have to get list of URLs one by one and to find the URLs that I have
    > > more than one time(can't be more than twice).

    >
    > > I thought to put them into binary search tree, this way they'll be
    > > sorted and I'll be able to check if the URL already exist.

    >
    > What about a set ?
    >
    > s = set()
    > for url in urls:
    > if url in s:
    > print "already have ", url
    > else:
    > set.add(url)


    Interesting. For this case I usually used dicts. As in:

    d = {}
    for url in urls:
    if url in d:
    print "already have ", url
    else:
    d = 1 Now, I can see that this meth...ess the data. Just asking out of curiosity ;)
     
    Michel Albert, Nov 12, 2007
    #6
  7. > Now, I can see that this method has some superfluous data (the `1`
    > that is assigned to the dict). So I suppose this is less memory
    > efficient. But is this slower then? As both implementations use hashes
    > of the URL to access the data. Just asking out of curiosity ;)


    Performance-wise, there is no difference in the implementations.
    What matters when comparing programs one-by-one is how many method
    calls you need. In this example, the dictionary is slightly faster
    in my measurements, since for the set, you need to perform a lookup
    of .add, whereas the access to __setitem__ for the dict need no
    additional dictionary lookup.

    Regards,
    Martin
     
    =?ISO-8859-1?Q?=22Martin_v=2E_L=F6wis=22?=, Nov 12, 2007
    #7
    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. Stub

    B tree, B+ tree and B* tree

    Stub, Nov 12, 2003, in forum: C Programming
    Replies:
    3
    Views:
    10,128
  2. sharan
    Replies:
    4
    Views:
    691
    CBFalconer
    Oct 30, 2007
  3. sharan
    Replies:
    2
    Views:
    834
    SM Ryan
    Oct 31, 2007
  4. sharan
    Replies:
    1
    Views:
    692
    CBFalconer
    Oct 30, 2007
  5. Bogdan

    Binary tree search vs Binary search

    Bogdan, Oct 18, 2010, in forum: C Programming
    Replies:
    22
    Views:
    3,081
    Michael Angelo Ravera
    Oct 21, 2010
Loading...

Share This Page