Le 02/01/2013 18:22, Nils Bruin a écrit :
I'll try to make precise measurements and comparisons, otherwise this discussion is non sense.... I ll do it, when I'll have time :-(On Jan 2, 5:29 am, Thierry Dumont <tdum...@math.univ-lyon1.fr> wrote:The problem is that Python dictionaries are *very* slow. Do you know how they are implemented?That's an interesting observation. I think python developers have put a lot of time into optimizing their dict structures, because they are used *everywhere* in python itself (global variables and attribute lookups are all dictionary based). The main hurdle for hash tables is the computation of the hash function. So perhaps your indices are slow to hash? Or perhaps your code is written in such a way that there's quite a bit of allocation/deallocation for lookup of a key (e.g. the construction of a tuple)?
But anyway, why a hash table? In C++, to build these graph structures we are talking about, I only use B-Tree based structures, for which we only need to have an order (actually a weak ordering), and an order on pairs of integers is something simple to compute; also B-Trees allow much more memory locality than containers based on hash tables. If dict rely on hash tables (because we do not presuppose we have an ordering?--may be this is necessary for other purpose--) this is certainly slower...
I'll look a this...
For your application it seems you know a lot about the key format beforehand, so it's possible that that allows a more efficient implementation anyway. However, if you find yourself stuck with having to use python dictionaries and you're unhappy with the speed, my guess would be: - check if you can use/design a key that's fast to hash - check if you can carry around entire keys in your code (i.e., don't pack/unpack into/from tuples all the time) As far as hash tables go, Python dicts are supposed to be one of the state-of-the-art implementations.
-- You received this message because you are subscribed to the Google Groups "sage-devel" group. To post to this group, send email to sage-devel@googlegroups.com. To unsubscribe from this group, send email to sage-devel+unsubscr...@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel?hl=en.
<<attachment: tdumont.vcf>>
