optimizing code to print sorted items in nested dictionary

Question

I am new to python so I wanted to know if the code I wrote for printing items inside a nested dictionary in a sorted alphabetical order is optimal especially for checking if key exists. Let me know if there is a better optimal solution

# Code
import operator
locations = {'North America': {'USA': ['Mountain View']}}
locations['Asia'] = {'India':['Bangalore']}
locations['North America']['USA'].append('Atlanta')
locations['Africa'] = {'Egypt':['Cairo']}
locations['Asia']['China'] = ['Shanghai']

# TODO: Print a list of all cities in the USA in alphabetic order.
if 'North America' in locations:
    for key,value in locations['North America'].items():
        if 'USA' in key:
            for item in sorted(value):
                print(f"{item}")


# TODO: Print all cities in Asia, in alphabetic order, next to the name of the country
if 'Asia' in locations:
    for key,value in sorted(locations['Asia'].items(),key=operator.itemgetter(1)):
        print(f"{value[0]} {key}")

score 1 · Accepted Answer · answered Jun 04 '19 at 02:44

1

Make these two lines your code:

print('\n'.join(sorted([x for i in locations.get('North America', {}).values() for x in i])))
print('\n'.join(sorted([x + ' ' + k for k,v in locations.get('Asia', {}).items() for x in v])))

Which outputs:

Atlanta
Mountain View
Bangalore India
Shanghai China

answered Jun 04 '19 at 02:44

U13-Forward

69,221
14
89
114

What happens if you have Canada? – Kenny Ostrom Jun 04 '19 at 03:40
@KennyOstrom Then add a new category, or do the same for two i.e `print('\n'.join(sorted([x for i in list(locations.get('North America', {}).values()) + list(locations.get('Canada', {}).values()) for x in i])))` – U13-Forward Jun 04 '19 at 09:53
Canada is a country in North America. I was trying to be subtle, hinting that you have a bug printing the cities in 'USA'. It gets the whole continent, and it's not taking advantage of O(1) lookup – Kenny Ostrom Jun 04 '19 at 13:07

score 0 · Answer 2 · answered Jun 04 '19 at 02:51

Dictionaries in python are unordered. Given that, I will try to help solve for your actual problem of checking for a key in a dictionary.

locations = {'North America': {'USA': ['Mountain View']}}
locations['Asia'] = {'India':['Bangalore']}
locations['North America']['USA'].append('Atlanta')
locations['Africa'] = {'Egypt':['Cairo']}
locations['Asia']['China'] = ['Shanghai']

# First we clean up all the loops.
# You are just checking if the key is in the dictionary with all the loops
if 'North America' in locations and 'USA' in locations['North America']:
    for item in sorted(value):
            print(f"{item}")

if 'Asia' in locations:
    # Since dictionaries are unordered, we will make a list of the countries to order
    countries = []
    for k in locations['Asia'].keys():
        countries.append(k)

    # Using a similar loop to the one to print cities
    for country in sorted(countries):
        # Adding a dimension for cities.
        for city in sorted(locations['Asia'][country]):
            print(f"{country}:{city}")

The Asia dictionary should loop through each country and in alphabetical order print each country and city.

How how how is this better? – U13-Forward Jun 04 '19 at 02:54 — U13-Forward, Jun 04 '19 at 02:54

Kenny Ostrom · Answer 3 · 2019-06-04T03:43:36.030

dictionaries are used because they give direct lookup of any specific key. For testing existence, you don't need to search. The downside is they are not sorted.

You iterate through all countries in north america when you already know you want usa, so ... don't do that.

print(sorted(locations['North America']['USA']))

This is better because it is O(1) lookup on the second layer when you do O(n) where n is the number of nations in that particular continent. Which admittedly isn't much so that's why they say don't optimize if you don't need to. But maybe you have a lot more data and the geography sample data was just filler.

To test for existence of a key, use "in" or write a try-except for KeyError. Python is one of the few languages where it's often better to just handle the exception.

To print all the cities in Asia, you will have to combine all the lists in asia and sort that: Combining two sorted lists in Python

You can do better by maintaining the city lists in sorted order all the time, using the bisect module. Inserting or removing in a sorted list is less work than sorting it each time, assuming you look at the list more often than you add and remove cities.

If you maintain sorted lists, you can efficiently get the sorted merge with https://docs.python.org/3.0/library/heapq.html#heapq.merge Although sadly you don't have the nation name doing that.

optimizing code to print sorted items in nested dictionary

3 Answers3