2
\$\begingroup\$

I am trying to implement the code described this post about how Reddit identifies duplicate user names (I do believe it is called binary search). Just to clarify, this is mainly for me figuring out how these things work; thanks @Graipher for pointing to bisect). The way I understand it, the steps are:

  1. You have a new user name you are comparing to an alphabetically sorted list of existing names

  2. You compare that new name to the middle item in the list.

  3. If there is no match, you check if the new name is higher or lower in the alphabet than the middle item, and focus on this side of the list, again checking the middle item.

  4. You repeat until there is a match ("User name taken") or none ("User name available").

Below is what I have. It seems to work when I test it on the names in the list and random other names. It'd cool if someone had some feedback re:

  • Will this work correctly or is there some kind of bug?

  • Is the while loop the right way to go? Are there better options? I especially don't like the separate loop for a list of length 1.

  • Performance-wise, are there any real hiccups in here?

  • Any other comments are much appreciated!

-

def checker(new_name, old_names):
    """
    The checker takes a string new_name and checks if it is contained in the list old_names.
    It prints out the results.
    """ 
    print "***\n\ninitializing the checker"
    print "searching for ", new_name
    print "old names", old_names
    old_names= sorted(old_names)
    #set the match variable to false
    namematch= False
    #iterate over list while new_name does not match
    while not namematch and len(old_names) > 1:
        middle= len(old_names)/2
        print "middle item is", old_names[middle], "middle index is", middle
        #match
        if old_names[middle] == new_name:
            namematch= True
        #no match
        else:
            if sorted(list((new_name, old_names[middle])))[0] != new_name:
                print "word is to the right"
                old_names = old_names[middle:]
            else:
                print "word is to the left"
                old_names = old_names[:middle]
    #check for list of length 1: is it new_name
    if (len(old_names)) == 1 and (old_names[0] == new_name):
        namematch = True
    if not namematch: 
        print "this name is not taken", new_name
    else:
        print "this name is taken:", new_name

Here is my test data:

-

names_list= [u'annie', u'max', u'chris', u'11alpha', u'zotti', u'zatti', u'zutti', u'?andy', u'getr\xfc', u'zilly']

checker('max', names_list)  # True
checker('fail', names_list)  # False
\$\endgroup\$
2
\$\begingroup\$

The description you are providing and your implementation do correspond to binary search indeed. As such, it would probably make sense to perform a few cosmetic changes to your function to make this cleaner and easier to (re)use:

  • call it binary_search (or something like that)
  • makes the signature (parameter names and documentation) more generic and not based on the concept of name. The parameters could be called item/element/x/needle and sorted_list/sorted_array.
  • make the return value clearer, for instance a boolean value telling whether the value was found or not (or maybe an index giving the position)
  • move all the input/output logic (except maybe for the debug statements) out of the function.

As for the performances, I am a bit concerned by the fact that you are actually performing copies by using the [:] sublist notation. Thus, each step of the algorithm, instead of operating in constant times will be bigger if the sublist you are copying gets bigger. Also, you are re-sorting the whole array everytime the function is called (and even more that this apparently). The point of using binary search is that you pay the cost of sorting (O(n*log(n))) upfront assuming you'll amortize it by performing many searches in O(log(n)) times. If you have to re-sort everytime, you might as well use a linear search iterating through the array and stopping when the element is found.

\$\endgroup\$
  • \$\begingroup\$ Thank you, I was thinking about that point as well. I guess the re-sorting issue can be resolved easily by just inputting a sorted list in the first place. Do you have any suggestions for the : issue? That's sth I struggled with, what would be the efficient approach? Thanks! \$\endgroup\$ – patrick Apr 20 '17 at 16:37
  • 1
    \$\begingroup\$ AFAIK Most implementations rely on something involving keeping track of low/high indices. \$\endgroup\$ – SylvainD Apr 20 '17 at 16:44
  • \$\begingroup\$ Ah I see, thanks for pointing it out. So that would be similar to what this guy does -- he has a start and a end variable that he updates throughout the process. I tried it but it got me in trouble with IndexErrors once I got to very short lists. But in this light, I might give that another go. \$\endgroup\$ – patrick Apr 20 '17 at 16:51
2
\$\begingroup\$

In general it does not make sense to roll your own, if there already is a built-in solution. In this case there is the bisect module, which has a method bisect.bisect_left which returns the index where you would have to insert an item to maintain the sorted order.

All you have to do is check if in that position there is already the user name you are checking:

from bisect import bisect_left

old_names = sorted(db_query(...))

def user_name_exists(new_name, old_names):
    return old_names[bisect_left(old_names, new_name)] == new_name

Note that this assumes that your names list is already sorted and that you get the list of old users via some function db_query.

Alternatively, you could use a set. x in set is \$mathcal{O}(1)\$ and uses binary search in the background to see if the hash is already in the set (thanks to @kyrill for suggesting sets in the comments):

old_names = set(db_query(...))

def user_name_exists(new_name, old_names):
    return new_name in old_names
\$\endgroup\$
  • \$\begingroup\$ Hi, thanks for your comment! I should have clarified that I did this mainly to understand the workings of it & not to really address a specific task. \$\endgroup\$ – patrick Apr 20 '17 at 16:32
  • 1
    \$\begingroup\$ @patrick Well, too late now :) For the next time, there is the reinventing-the-wheel tag if you want to emphasize that you don't care that there is already a built-in implementation for that. \$\endgroup\$ – Graipher Apr 20 '17 at 16:36
  • 1
    \$\begingroup\$ But if you really wanted to address the task, you wouldn't even use bisect but a set. Then it would be just new_name in old_names. \$\endgroup\$ – kyrill Apr 20 '17 at 21:02
  • \$\begingroup\$ @kyrill You are right, I was blinded by having to use binary search (which the hash lookup also uses, but whatever...). \$\endgroup\$ – Graipher Apr 21 '17 at 7:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.