3
\$\begingroup\$

Problem statement:

The html pages for each year which represents the top 1000 most common Girl and Boy names in the order of their frequency are ranked and provided. And they are ranked based on the frequency of their naming. To elaborate if John is named 101 times and Johan is named 130 times they both are ranked serially as

Johan   1  
John    2

To get an idea of this you can refer to this website: https://www.ssa.gov/oact/babynames/decades/names2010s.html.

In some years, a name appears more than once in the html, but we'll just have to use one number per name. We have to make the algorithm smart about this case and choose whichever number is smaller. After retrieving the names along with their ranks we have to write that data into text file in the following format:

2006
Aaliyah 91
Aaron 57
Abagail 895
Abbey 695
Abbie 650

Implementation: I have retrieved the Girl names and Boy names along with their rankings using regular expressions. Later on I have created two dictionaries boyNames_Rank_Dict, girlNames_Rank_Dict. These dictionaries have basically names of Girls and Boys that are named in that particular year along with their ranks.

Now the challenge is to look for common girls names, boys names and their corresponding ranks. Now if there is a girl and a boy name that are same then the ranks are to be compared and the lowest rank in them has to be selected.

I have written a script for this, below is the code which is an implementation of the requirement:

from time import time
import re


def extract_names(filename):

    boyNames_rank_Dict = {}
    girlNames_rank_Dict = {}
    filestream = open(filename, "r")
    filebuffer = filestream.read()
    filematch_year = re.search(r"Popularity\s([\w.-]+)\s([\d.-]+)", filebuffer)
    year1 = filematch_year.group(2)

    filematch_rank_names = re.findall(r'td>([\d.-]+)</td><td>([\w.-]+)</td><td>([\w.-]+)', filebuffer)

    for filematch_rank_name in filematch_rank_names:
        x = int(filematch_rank_name[0])
        boyNames_rank_Dict[x] = filematch_rank_name[1]
        girlNames_rank_Dict[x] = filematch_rank_name[2]

    for boy_Rank, boy_Name in boyNames_rank_Dict.items():
        for girl_Rank, girl_Name in girlNames_rank_Dict.items():
            if boy_Name == girl_Name and boy_Rank < girl_Rank:
                 del girlNames_rank_Dict[girl_Rank]
            elif boy_Name == girl_Name and girl_Rank < boy_Rank:
                 del boyNames_rank_Dict[boy_Rank]

    names_Rank_Dict = girlNames_rank_Dict.items() + boyNames_rank_Dict.items()

    file = open("output.txt", 'w')
    file.write(year1)

    for rank, name in names_Rank_Dict:
        strx = name+' '+str(rank)
        file.write('\n')
        file.write(strx)

    file.close()

def timex():
    return round(time()*1000)

def main():
    start_time = timex()
    extract_names("/home/sreedhar/Desktop/google-python-exercises/babynames/baby1998.html")
    end_time = timex()
    print "time taken:%d seconds", (end_time-start_time)

if __name__ == "__main__":
    main()

How can I search for the rank in these Dictionaries when a matching name is found in a more efficient manner. Since when I tried to Profile the time it has taken to execute this program it took 263 milliseconds on a mere 1000 records.

1017 function calls in 0.263 seconds

When I extrapolate this function to work on a million records the time complexity seems to be out of bounds.

Could some body kindly guide towards a more efficient implementation of this. Also make note that I'm an amateur to Python.

\$\endgroup\$
3
\$\begingroup\$

There is a number of things we can do to improve the solution performance-wise, but, most importantly, you don't need two dictionaries for boy and girl names and can have a single dictionary checking for the minimum value on the fly.

What if we use a collections.defaultdict with a default int value being a big number, such as sys.maxint, then we iterate over every row with ranks, boy and girl names and leave minimum ranks only.

We can also use re.finditer() instead of re.findall() to avoid having an extra list created in memory - you may notice the difference on bigger input files:

from collections import defaultdict
from time import time
import re

import sys


def extract_names(filename):
    names = defaultdict(lambda: sys.maxint)

    with open(filename, "r") as f:
        html_data = f.read()

    filematch_year = re.search(r"Popularity\s([\w.-]+)\s([\d.-]+)", html_data)
    year = filematch_year.group(2)

    filematch_rank_names = re.finditer(r'td>([\d.-]+)</td><td>([\w.-]+)</td><td>([\w.-]+)', html_data)
    for match in filematch_rank_names:
        rank, boy_name, girl_name = match.groups()
        rank = int(rank)

        names[boy_name] = min(names[boy_name], rank)
        names[girl_name] = min(names[girl_name], rank)

    with open("output.txt", 'w') as output_file:
        output_file.write(year + "\n")

        for name, rank in sorted(names.items()):
            output_file.write("{name} {rank}\n".format(name=name, rank=rank))

Note that the results are sorted by the names as required by your Google challenge:

1998
Aaliyah 222
Aaron 37
Abbey 408
Abbie 603
Abbigail 612
Abby 194
Abdul 970
Abdullah 897
Abel 378
...

Here is the simple timeit benchmark for both yours (extract_names) and mine (extract_names_new) solutions showing a dramatic improvement on my machine:

In [1]: %timeit extract_names("baby1998.html")
10 loops, best of 3: 103 ms per loop

In [2]: %timeit extract_names_new("baby1998.html")
100 loops, best of 3: 5.66 ms per loop
\$\endgroup\$
2
\$\begingroup\$

Strategy

You aren't using the dictionaries effectively. In your code, the keys are the ranks, and the values are the names. Basically, your "dictionary" is being used like an array.

Furthermore, the task that you completed is a bit weaker than the Google Python exercise, which calls for the output to list the names in alphabetical order. Your solution lists them in an arbitrary order.

To address both the performance and the sorting issue, what you want is the inverse: the keys should be the names, and the values should be the ranks.

Implementation details

Try to adhere to the official PEP 8 naming guidelines. A variable name like boyNames_rank_Dict is an awkward mixture of capitalization and underscores.

Calls to open() should nearly always be done using a with block. The file handle will automatically be closed for you, even if an exception occurs. The code will look cleaner, too.

with open(filename) as f:
    html = f.read()
year = re.search(r"Popularity\s([\w.-]+)\s([\d.-]+)", html).group(2)

The extract_names() function does a lot of work: parsing the file, merging the ranks, and writing the output. Each of those three tasks should be extracted as a separate helper function.

\$\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.