Efficient Dictionary Searching?

Question

I had a quick question about efficiency of searching through large dictionaries in Python. I am reading a large comma-separated file and getting a key and value from each line. If my key is already in the dictionary, I'm adding the value to the value listed in the dictionary, if the key doesn't exist in the dictionary, I simply add the value. Previously I was using this:

if key in data_dict.keys():     add values else:     data_dict[key] = value 

This starts pretty fast, but as the dictionary grows it becomes slower and slower, to the point where I can't use it at all. I changed the way I search for the key in the dictionary to this:

try:     # This will fail if key not present     data_dict[keyStr] = input_data[keyStr] + load_val except:     data_dict[keyStr] = load_val 

This is infinitely faster, and can read / write over 350,000 lines of code in 3 seconds.

My question was why does the if key in data_dict.keys(): command take sooo much longer than the call to try: data_dict[keyStr]? And why wouldn't Python utilize the try statement when searching for a key in a dictionary?

Answer 1

The problem is that for every test you're generating a new list of keys with .keys(). As the list of keys gets longer, the time required goes up. Also as noted by dckrooney, the search for the key becomes linear instead of taking advantage of the hash-table structure of the dictionary.

Replace with:

if key in data_dict: 

Answer 2

data_dict.keys() returns an unsorted list of keys in the dictionary. Thus each time you check to see if a given key is in the dictionary, you're doing a linear search across the list of keys (an O(n) operation). The longer your list, the longer it takes to search for a given key.

Contrast this to data_dict[keyStr]. This performs a hash lookup, which is an O(1) operation. It doesn't (directly) depend on the number of keys in the dictionary; even as you add more keys, the time to check if a given key is in the dictionary stays constant.