FYI, often I will first convert a graph to a list of bitsets
representing the neighbors, then I use Cython to access the bitsets for
really fast access.
Wayyy later : you may like patch #14589 !
Nathann
--
You received this message because you are subscribed to the Google
Hellooo !!!
You are totally right about the performance issue, but do you know the
memory size of a Sage graph compared to dict of dict ? I have no idea -- I
have just been *VERY* scared by the size of a dict of dict compared to a C
array in the past.
Nathann
--
You received this
Le 02/01/2013 09:22, Nathann Cohen a écrit :
Hellooo !!!
You are totally right about the performance issue, but do you know the
memory size of a Sage graph compared to dict of dict ? I have no idea --
I have just been *VERY* scared by the size of a dict of dict compared to
a C array in
Heey!
Do we actually need to have a dict of a dict? Aren't sets implemented with
some other data structure? I suppose if networkX uses this approach then it
is doable!
Best,
Jernej
On Wednesday, 2 January 2013 09:22:08 UTC+1, Nathann Cohen wrote:
Hellooo !!!
You are totally right
Helloo !!!
Do we actually need to have a dict of a dict? Aren't sets implemented with
some other data structure? I suppose if networkX uses this approach then
it
is doable!
Oh. You wanted a dictionary of sets ?
Well, the main reason I have not rewritten this backend 10 times
On 2013-01-02, Nathann Cohen nathann.co...@gmail.com wrote:
--20cf3003bcb0a9ec4404d24bbbff
Content-Type: text/plain; charset=ISO-8859-1
Helloo !!!
Do we actually need to have a dict of a dict? Aren't sets implemented with
some other data structure? I suppose if networkX uses
I suppose that for many graph algorithms the graph can well stay
immutable, and this does not really need a dictionary (perhaps at a
slight cost of efficiency of determining whether two vertices are
adjacent).
And many algorithms actually do not need the latter, as they parse the
Le 02/01/2013 13:54, Nathann Cohen a écrit :
I suppose that for many graph algorithms the graph can well stay
immutable, and this does not really need a dictionary (perhaps at a
slight cost of efficiency of determining whether two vertices are
adjacent).
And many algorithms actually do not need
On 1/2/13 6:29 AM, Thierry Dumont wrote:
The problem is that Python dictionaries are *very* slow. Do you know how
they are implemented?
a hash table:
http://hg.python.org/cpython/file/tip/Objects/dictobject.c
http://hg.python.org/cpython/file/tip/Include/dictobject.h
http://stackoverflow.com/questions/327311/how-are-pythons-built-in-dictionaries-implemented
has many good answers, it seems.
Wow. And they flagged it as non constructive. These guys are great.
Thank you very much Jason !!! O_O
Nathann
--
You received this message because you are subscribed
see inline.
On Wed, Jan 2, 2013 at 12:31 PM, Nathann Cohen nathann.co...@gmail.com wrote:
http://stackoverflow.com/questions/327311/how-are-pythons-built-in-dictionaries-implemented
has many good answers, it seems.
Wow. And they flagged it as non constructive. These guys are great.
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
On 1/2/13 5:54 AM, Nathann Cohen wrote:
I also prefer to write a good graph structure for my algorithms than
to use Sage's when it is worth spending the extra time :-)
FYI, often I will first convert a graph to a list of bitsets
representing the neighbors, then I use Cython to access the
On 1/2/13 10:22 AM, Nils Bruin wrote:
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)?
IIRC, our discussion is that the dict approach *is* the
On 1/2/13 11:56 AM, Jason Grout wrote:
To repeat the benchmark on my computer:
sage: G = graphs.RandomBarabasiAlbert(100,2)
sage: type(G.vertices()[0])
int
here is Sage's implementation:
sage: %timeit E = [(u,v) for u in G for v in G.neighbor_iterator(u)]
1000 loops, best of 3: 1.14 ms per
Helloo
A few more data points to narrow in on just the neighbors functionality:
We are definitely way behind when it comes to the enumeration of neighbors.
At the time we moved from default networkx backends to Sage's own
implementation, the point was more to improve the runtime of
Le 02/01/2013 18:22, Nils Bruin a écrit :
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
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;
Yeah. But we have labels to
I decided to do some profiling. And there is something that worries my
slightly more then the factor +/-10 difference in iteration speed that
caused the start of this topici. Namely conversion from a sparse sage graph
to a networkx graph seems to have quadratic runtime complexity instead of
On 1/1/13 2:45 PM, Jernej Azarija wrote:
This can of course be improved by storing a hash map for each vertex and
updating its neighbouring vertices on each addition/deletion of an edge
and deletion of a vertex.
IIRC, this is exactly how networkx works, as a dict of vertices/neighbors.
As mentioned on the ticket it might be good to still post your broken
patch. Not every patch needs to be perfect the first time. By posting your
code it is easier for people to see exactly what is broken by your faster
code (probably it is because there are some functions that directly modify
21 matches
Mail list logo
