I think that this kind of question is more dedicated to sage-support
because it does not deal about combinatorics
(http://groups.google.com/group/sage-support)
2010/7/28 Christian Stump <christian.st...@gmail.com>:
> Salut cython specialists,
>
> I would like to implement a routine adding dictionaries with possibly
> different keys pointwise and delete all zero entries in the end:
>
> sage: def dict_sum( list_of_dics, remove_zeros=True ):
> ... return_dict = {}
> ... for D in list_of_dics:
> ... for key in D:
> ... if key in return_dict:
> ... return_dict[ key ] += D[ key ]
> ... else:
> ... return_dict[ key ] = D[ key ]
> ...
> ... if remove_zeros:
> ... return_dict = dict( [ (key,value) for key,value in
> d.iteritems() if value != 0 ] )
> ... return return_dict
>
> sage: d = dict(zip(range(100000),range(0,100000,2)))
> sage: timeit("p = dict_sum([d]*10, True)")
> sage: timeit("p = dict_sum([d]*10, False)")
> 5 loops, best of 3: 216 ms per loop
> 5 loops, best of 3: 138 ms per loop
>
> Improving it a little and putting it into cython gives
>
> sage: %cython
> sage: def dict_sum_cython( list_of_dicts, remove_zeros=True ):
> ... return_dict = list_of_dicts[0].copy()
> ... for D in list_of_dicts[1:]:
> ... for key in D:
> ... if key in return_dict:
> ... return_dict[key] += D[key]
> ... else:
> ... return_dict[key] = D[key]
> ...
> ... if remove_zeros:
> ... for_removal = [key for (key,value) in
> return_dict.iteritems() if not value]
> ... for key in for_removal:
> ... del return_dict[key]
> ... return return_dict
>
> sage: timeit("p = dict_sum_cython([d]*10, True)")
> sage: timeit("p = dict_sum_cython([d]*10, False)")
> 5 loops, best of 3: 56 ms per loop
> 5 loops, best of 3: 57.8 ms per loop
>
> This is already much faster! Any ideas how to improve the speed now?
> All I know about the variables is that all dict values live in a
> common ring ( mostly QQ ), can I use this somehow?
>
> Thanks for your help, Christian
One remark: for a list l it is much more faster to use l.append(0)
than l += [0]. Moreover, dictionnaries have a special method for
iteration through key and values which is a little bit faster
{{{
sage: d=dict((i,i) for i in xrange(10000))
sage: timeit('for i in d: d[i]')
625 loops, best of 3: 1.1 ms per loop
sage: timeit('for i,j in d.iteritems(): pass')
625 loops, best of 3: 839 µs per loop
}}}
I would have written for the main loop
{{{
for D in list_of_dicts[1:]:
for key,value in D.iteritems():
if key in return_dict:
return_dict[key].append(value)
else:
return_dict[key] = [value]
}}}
Cheers,
Vincent
--
To post to this group, send email to sage-support@googlegroups.com
To unsubscribe from this group, send email to
sage-support+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/sage-support
URL: http://www.sagemath.org
