> 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 Goog
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
l
> 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
Le 02/01/2013 18:22, Nils Bruin a écrit :
On Jan 2, 5:29 am, Thierry Dumont 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 struc
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 mor
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 lo
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 faste
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 bits
On Jan 2, 5:29 am, Thierry Dumont 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*
see inline.
On Wed, Jan 2, 2013 at 12:31 PM, Nathann Cohen 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.
Stackoverflow is totally
> 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 subscribe
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://hg.python.org/cpyth
On 1/1/13 5:56 PM, Jason Grout wrote:
IIRC, this is exactly how networkx works, as a dict of vertices/neighbors.
Just for referencem, here it is in the networkx docs:
http://networkx.lanl.gov/reference/introduction.html#data-structure
Thanks,
Jason
--
You received this message because you
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 t
> 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
> neighb
On 2013-01-02, Nathann Cohen 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 this approach then
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 si
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 ri
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 t
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 mes
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
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.
Thanks,
22 matches
Mail list logo