dictionary search & insert optimization

Question

I'm experiencing serious slow downs when working with dictionaries as the dictionary grows to a few thousands keys.

I'm processing a file with ~1,000,000 lines of data, I'm constructing a graph like data structure using dictionaries

here's my bottle neck function

def create_edge(node_a, node_b, graph):
    if node_a not in graph.keys():
        graph[node_a] = {node_b: 1}
    elif node_b in graph[node_a].keys():
        graph[node_a][node_b] += 1
    else:
        graph[node_a][node_b] = 1

create_edge will create and edge from node_a to node_b, or add 1 to the weight of an already existing edge between them.

Since my nodes are identified by a string unique id, I'm using dictionaries for storage, assuming that search if a key exist, and insert would take O(1) on average.

If I comment out create_edge I can process around 20,000 records per seconds, with create_edge as a part of my pipeline it's about 20 records per sec.

The first 100 records takes about 500ms to process. When the dictionary size grows to around 10,000 - Processing 100 records take about 15,000ms, every record process invokes create_edge about 4 times on average - So 400 calls for create_edge takes 15 seconds when the dictionary size is 10,000.

First, do these runtimes make sense? Seems way to much to me, correct me if I'm wrong.

Second, suggestions of optimizing the dictionary usage for better run time would be greatly appreciated.

I'm expecting the dictionary size to be at least 100,000 to complete processing for the entire 1,000,000 records.

---

Edit: Conclusions

You were right on the money, did two noob mistakes here.. :)

The keys() calls increase complexity dramaticly, taking it from constant time to poly time (squared) per edge insertion, replacing if node in graph.keys() with if node in graph produces a constant process time of 100 records in ~300ms.

Second mistake was virtualenv config which led me to believe im using python3 while I was actualy using python2.

python3 do optimizes the keys() code into a constant time search, which is good for run time but less for proper code style.

Thanks a lot for your assistance.

---

I performed a run time comparison after removing the keys() calls.

# graph = {}
python version: 3.6.3
start time 11:44:56
Number of records: 1029493
graph created, 1231630 nodes
end time 11:50:35
total ~05:39

# graph = defaultdict(lambda : defaultdict(int))
python version: 3.6.3
start time 11:54:52
Number of records: 1029493
graph created, 1231630 nodes
end time  12:00:34
total ~05:42

# graph = {}
python version: 2.7.10
start time 12:03:25
Number of records: 1029493
graph created, 1231630 nodes
end time 12:09:40
total ~06:15

Answer 1

Can't u just use a defaultdict with defaultdict(int) as seen here: Python: defaultdict of defaultdict?

from collections import defaultdict

graph = defaultdict(lambda : defaultdict(int))

graph['a']['b'] += 1
graph['a']['b'] += 1
graph['a']['c'] += 1

graph

Returns:

defaultdict(<function __main__.<lambda>>,
            {'a': defaultdict(int, {'b': 2, 'c': 1})})
# equal to: {'a': {'b': 2, 'c': 1}}

Answer 2

When testing for the existence of a key in a dict, just use key in d, rather than key in d.keys(). Extracting the keys to test for membership negates the benefit of using a dict in the first place.

Try the following:

def create_edge(node_a, node_b, graph):
    if node_a not in graph:
        graph[node_a] = {node_b: 1}
    elif node_b in graph[node_a]:
        graph[node_a][node_b] += 1
    else:
        graph[node_a][node_b] = 1

Notice that keys() isn't called at all. This should be a lot faster than what you're doing now.

Note that in Python 2 the keys() check will be much slower than in Python 3, since in Python 2 keys() creates a list of the entire set of keys. It works differently in Python 3, but even in Python 3 checking for membership directly, without using keys(), will be faster.

Answer 3

I tried several methods and this is one that seems to work. This method use a counter to count all occurances first and then build the dictionary. Thanks @Stefan Pochmann to provide benchmark scripts. One I used is from ideone.com/ckF0X5

I am using Python 3.6 and the result is tested on my computer.

from timeit import timeit
from collections import defaultdict, Counter
from random import shuffle
from itertools import product

def f():   # OP's method modified with Tom Karzes' answer above.
    d = {}
    for i, j in edges:
        if i not in d:
            d[i] = {j: 1}
        elif j in d[i]:
            d[i][j] += 1
        else:
            d[i][j] = 1

def count_first(): 
    d = dict()
    for (v, w), c in Counter(edges).items():
        if v not in d:
            d[v] = {w: c}
        else:
            d[v][w] = c
    # Alternatively, (Thanks to Jean-François Fabre to point it out.)
    # d = defaultdict(lambda : defaultdict(int)) 
    # for (v, w), c in Counter(edges).items(): 
    #     d[v][w] = c

edges = list(product(range(300), repeat=2)) * 10
shuffle(edges)

# %timeit f()
270 ms ± 23.6 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
# %timeit count_first()
180 ms ± 15.2 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

Declaimer: The results of count_first() that I get from the ideone.com is, however, slower than the OP's answer, f() here.

Stefan Pochmann did a benchmark experiment to compare different approaches in both Python 2 and 3. His result in Python 2 can be found here. For Python 3, check this. Credits to him and thanks his code review.