6
\$\begingroup\$

I'm working on a Talent Buddy challenge . In this challenge you have to design the autocomplete functionality of Twitter. You are given a list of queries and possible usernames. You have to return the most suited username based on the query. This whole functionality should run under 2 seconds for arrays which do not exceed 100.000 entries. Below you can find my attempt. On my computer it runs the biggest list in 0.517 seconds. But apperently it is not under 2 sec on their system. In the code bellow I did not add the big list, because it will be too much text for a question. Therefore I included the example lists.

My strategy is to divide the usernames into 26 lists (1 list for every letter in the alphabet). So this means that for each query, I do not have to go over all the user names, but only those starting with the same letter. For the rest I optimized my code with best practice rules.

Does anyone know how to make this faster?

usernames= ["james", "jBlank"]
queries= ["j", "jm", "jbl", "JB"]

import cProfile

def do_cprofile(func):
    def profiled_func(*args, **kwargs):
        profile = cProfile.Profile()
        try:
            profile.enable()
            result = func(*args, **kwargs)
            profile.disable()
            return result
        finally:
            profile.print_stats()
    return profiled_func



@do_cprofile
def typeahead(usernames, queries):

    amount_of_queries = len(queries)
    queries_lower = [query.lower() for query in queries]
    username_lower = [item.lower() for item in usernames]
    username_lower = sorted(username_lower)
    querylen = [len(query) for query in queries]

    results = [-1]*amount_of_queries
    alphabet = [[] for x in xrange(26)]
    myDict = {'a':0,'b':1,'c':2,'d':3,'e':4,'f':5,'g':6,'h':7,'i':8,'j':9,'k':10,'l':11,'m':12,'n':13,'o':14,'p':15,'q':16,'r':17,'s':18,'t':19,'u':20,'v':21,'w':22,'x':23,'y':24,'z':25}

    [alphabet[myDict[username[0]]].append(username) for username in username_lower]

    matches=[]
    for q in xrange(amount_of_queries):
        matches[:] = []
        quer = queries_lower[q]

        if querylen[q]==1:
            results[q] = alphabet[myDict[quer[0]]][0]
        else:                            
            matches = [item  for item in alphabet[myDict[quer[0]]] if quer==item[:querylen[q]]]
            if len(matches)>=1:
                results[q]= matches[0]


    print '\n'.join(map(str, results))

if __name__=="__main__":
    typeahead(usernames, queries);
\$\endgroup\$
4
\$\begingroup\$

Organisation of the function

You are doing many things in the same function which make the whole thing a bit confusing. First thing to do is to split the two main parts of the functions : one does preprocessing on usernames, one handles queries. One this is done, your code looks like :

def typeahead(usernames, queries):
    # Pre-processing on usernames
    username_lower = [item.lower() for item in usernames]
    username_lower = sorted(username_lower)

    alphabet = [[] for x in xrange(26)]
    myDict = {'a':0,'b':1,'c':2,'d':3,'e':4,'f':5,'g':6,'h':7,'i':8,'j':9,'k':10,'l':11,'m':12,'n':13,'o':14,'p':15,'q':16,'r':17,'s':18,'t':19,'u':20,'v':21,'w':22,'x':23,'y':24,'z':25}

    [alphabet[myDict[username[0]]].append(username) for username in username_lower]

    # Handling the queries
    matches=[]
    amount_of_queries = len(queries)
    results = [-1]*amount_of_queries
    queries_lower = [query.lower() for query in queries]
    querylen = [len(query) for query in queries]
    for q in xrange(amount_of_queries):
        matches[:] = []
        quer = queries_lower[q]

        if querylen[q]==1:
            results[q] = alphabet[myDict[quer[0]]][0]
        else:
            matches = [item  for item in alphabet[myDict[quer[0]]] if quer==item[:querylen[q]]]
            if len(matches)>=1:
                results[q]= matches[0]

    print '\n'.join(map(str, results))

Before we go any further, something to keep in mind

I am not quite sure that this is an issue but in your example, your print lower-case usernames even though usernames with their original case is printed on this original problem.

Making your map from letters to username a bit cleaner

At the moment, you always use alphabet and myDict together. This is a good sign that something is wrong. (Also, if you really want to map letters to their index, you don't need dictionnary with hardcoded value, you just need arithmetic, ord/chr). If what you want is just to match letters with the list of corresponding usernames, you can use normal dictionnary and check if items are already present, normal dictionnary and fill with empty list from the very beginning or you could play it smart and use Python good stuff as defaultdict and setdefault :

from collections import defaultdict
mapping = defaultdict(list)
mapping2 = dict()
for username in usernames:
    low = username.lower()
    mapping[low[0]].append(low)
    mapping2.setdefault(low[0], []).append(low)

I'll assume we are using the defaultdict option from now.

In order to integrate this part of the solution in your code, let's remove the duplicated code from what we have in the part handling the queries :

for q in xrange(amount_of_queries):
    matches[:] = []
    quer = queries_lower[q]

    candidates = alphabet[myDict[quer[0]]] ### THIS IS WHAT IS HAVE ADDED
    if querylen[q]==1:
        results[q] = candidates[0]
    else:
        matches = [item  for item in candidates if quer==item[:querylen[q]]]
        if len(matches)>=1:
            results[q]= matches[0]

Replacing this with our defaultdict logic, we get :

def typeahead(usernames, queries):
    # Pre-processing on usernames
    mapping = defaultdict(list)
    for username in usernames:
        mapping[username.lower()[0]].append(username.lower())

    # Handling the queries
    matches=[]
    amount_of_queries = len(queries)
    results = [-1]*amount_of_queries
    queries_lower = [query.lower() for query in queries]
    querylen = [len(query) for query in queries]
    for q in xrange(amount_of_queries):
        matches[:] = []
        quer = queries_lower[q]

        candidates = mapping[quer[0]]
        if querylen[q]==1:
            results[q] = candidates[0]
        else:
            matches = [item  for item in candidates if quer==item[:querylen[q]]]
            if len(matches)>=1:
                results[q]= matches[0]

    print '\n'.join(map(str, results))

Please note that I took this chance to remove the list you were building with a useless list-comprehension.

Handling the queries

As you are about to iterate on queries anyway, there's no real need to build lists with information you will need. You can just iterate over queries and that will do the trick.

Also, you can initialise matches inside the loop and use enumerate if you really need the index. At this point, the part of the code looks like :

# Handling the queries
results = [-1]*len(queries)
for i,q in enumerate(queries):
    matches=[]
    low_quer = q.lower()
    l = len(low_quer)

    candidates = mapping[low_quer[0]]
    if l==1:
        results[i] = candidates[0]
    else:
        matches = [item  for item in candidates if low_quer==item[:l]]
        if len(matches)>=1:
            results[i]= matches[0]

Finally, we don't even need the indices as we can build results as we go. Also, we don't need matches in that part of the function. Things get even more concise :

# Handling the queries
results = []
for q in queries:
    low_quer = q.lower()
    l = len(low_quer)

    candidates = mapping[low_quer[0]]
    if l==1:
        results.append(candidates[0])
    else:
        matches = [item  for item in candidates if low_quer==item[:l]]
        if len(matches)>=1:
            results.append(matches[0])
        else:
            results.append('-1')

Another issue found

What if we look for "c" ? At the moment, we'll do results.append(candidates[0]) with an empty list of candidates : this will crash. This should be handled much the same way we do for longer strings : check if we do have a match. Also, this removes some unrequired logic :

# Handling the queries
results = []
for q in queries:
    low_quer = q.lower()
    l = len(low_quer)

    matches = [item for item in mapping[low_quer[0]] if low_quer==item[:l]]
    if len(matches)>=1:
        results.append(matches[0])
    else:
        results.append('-1')

If we want to play it cool, we can use the fact that in a boolean context, an empty list is considered False while a non-empty list is considered True. Also, we can use the ternary operator. Finally, because I am now using the string -1 and not the integer, we don't need the conversion to string at the end. We get :

# Handling the queries
results = []
for q in queries:
    low_quer = q.lower()
    l = len(low_quer)

    matches = [item for item in mapping[low_quer[0]] if low_quer==item[:l]]
    results.append(matches[0] if matches else '-1')

print '\n'.join(results)

Using the right function

Using startswith you don't need to do some tricky string handling :

# Handling the queries
results = []
for q in queries:
    q = q.lower()
    matches = [item for item in mapping[q[0]] if item.startswith(q)]
    results.append(matches[0] if matches else '-1')

Your final code becomes :

def typeahead(usernames, queries):
    # Pre-processing on usernames
    mapping = defaultdict(list)
    for username in usernames:
        low = username.lower()
        mapping[low[0]].append(low)
    print mapping

    # Handling the queries
    results = []
    for q in queries:
        q = q.lower()
        matches = [item for item in mapping[q[0]] if item.startswith(q)]
        results.append(matches[0] if matches else '-1')

    print '\n'.join(results)

A few things are not perfect yet : the fact that we get the lower-case name, the fact that we haven't sorted the values but I'll let your play with this.

And now for something different

The trick you have used to map first letter to potential candidates makes things at most 26 times faster. In real life, this performance boost will not be that huge because usernames are not uniform over the alphabet. You might want to generalise this trick over all letters of the words. Here are a few pages that you might find interesting :

\$\endgroup\$
  • \$\begingroup\$ Thank you for your answer and time. I quickly read your answer (not yet in depth) and had a quick test with your final code. Although your function is much more read-able than mine, it is 3x slower. Mine takes 0.517sec and yours 1.66sec. Yours takes 5.953.488 function calls while mine takes only 54.489 . \$\endgroup\$ – Olivier_s_j Jun 17 '14 at 10:33
  • \$\begingroup\$ +1 for Trie - @Ojtwist you should see some serious lookup improvement from that \$\endgroup\$ – jonrsharpe Jun 17 '14 at 10:41
  • \$\begingroup\$ @Ojtwist Thanks for letting me know. I'll try to have a look at this but I am not too sure I'll have time. In any case, if you understand which particular change leads to a performance impact, I am quite interested. \$\endgroup\$ – SylvainD Jun 17 '14 at 11:36
  • \$\begingroup\$ Also, please keep in mind that it might not be worth focusing on performances if correctness is known to be missing. \$\endgroup\$ – SylvainD Jun 17 '14 at 11:38
  • \$\begingroup\$ I've had a more thorough look at your answer and there are some improvements that I can use. First of all the use of defaultdic is indeed a boost in performance. Looping twice over the queries is indeed too much. The enumerator is also better. But some things are slower such as startswith and the logic to construct the results list. Using the improvements I got it down to 0.431sec. So thanks! I'll have a look at the datastructures you mentioned. And yes for the challenge the results have to be capitalized but I thought of just looking them up in the original list. \$\endgroup\$ – Olivier_s_j Jun 17 '14 at 12:01
1
\$\begingroup\$

instead of mapping

mapping = defaultdict(list)
    for username in usernames:
        mapping[username.lower()[0]].append(username.lower())

you can use

from itertools import groupby
from operator import itemgetter

mapping = {g.lower():list(values)  for g, values in groupby(sorted(usernames,key=str.lower), itemgetter(0))}
\$\endgroup\$

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.