Python: Dict based graph VS list based graph , short comparison.

Правка en4, от felipeblassioli, 2015-10-19 00:02:10

I've written this in response to this comment when I was solving a different problem.

Summary: You got weight: - Lookup time (in graph traversals) - str to int conversion -> reading the graph - int to str conversion -> output the graph ___

Take this problem for example, it has an awfully big input and also a big output. (for big I mean ~10^5 ints)

We have more than 200000 numbers. (when N=10^5 and M=10^5)

I`ve used an EC2 small machine to do the timings and they were quite close to the timus judge's output. EC2 seems slower than timus.

Here's some timings for the input with max N and M:

Using a list for the graph (int indexed):

from sys import stdin
from itertools import izip, islice

tkns = iter(map(int, stdin.read().split()))
n,m = int(tkns.next()), int(tkns.next())
graph = [[] for i in xrange(n+1)]
for u,v in islice(izip(tkns,tkns),m):
        graph[u].append(v)
        graph[v].append(u)

In 10 runs the min,max time where: 0.726s and 0m0.814s

Using a dict for the graph (str indexed):

from sys import stdin
from itertools import izip, islice

tkns = iter(stdin.read().split())
n,m = int(tkns.next()), int(tkns.next())
graph = {str(i): [] for i in xrange(1,n+1)}
for u,v in islice(izip(tkns,tkns),m):
        graph[u].append(v)
        graph[v].append(u)

In 10 runs the min,max time where: 0.582s and 0m0.652s

The time limit for this problem was 1s, my solution took 0.717 and is currently the only python solution. The "same" solution in C took 0.072s.

Should we ALWAYS use dict based graphs?

NO, even though the access time for list is faster, if you traverse the graph a lot and you have many edges or vertices you probably should pay the price of 0.1-0.2s (which is not cheap). Here's a problem (timus1389-roadworks) which I couldn`t use a dict based graph to AC it. The solution is in the post: Maximal Matching in a Tree.

Keep in mind that if you have to cast int to str for output (in this problem you had to output lots of stuff) you have to pay this price too. (and it is not cheap)

Observations: - Casting str to int is not cheap - str to int and int to str DO NOT cost the same.

Related SO: http://stackoverflow.com/questions/11687183/more-efficient-to-convert-string-to-int-or-inverse

Теги python, python in competitions, graph, optimization, performance

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en6 Английский felipeblassioli 2015-10-19 00:03:05 8
en5 Английский felipeblassioli 2015-10-19 00:02:38 10
en4 Английский felipeblassioli 2015-10-19 00:02:10 259
en3 Английский felipeblassioli 2015-10-18 23:54:08 16
en2 Английский felipeblassioli 2015-10-18 23:53:40 2 Tiny change: 'ndexed):\n~~~~~\nf' -> 'ndexed):\n\n~~~~~\nf'
en1 Английский felipeblassioli 2015-10-18 23:53:15 2659 Initial revision (published)