[sage-devel] Re: Graph neighbours - room for huge performance boost
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 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.
Re: [sage-devel] Re: Graph neighbours - room for huge performance boost
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 the past. Nathann -- A similar problem exists withn sparse matrices used by scipy:; scipy builds a dict of (i,j) for all the non zero coefficients of the matrix; this is so slow that it cannot be used in any real application ! t.d. -- 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
Re: [sage-devel] upgrade from 5.4.1 by installing package sage-5.5 failed
On 2013-01-01 14:05, -sam- wrote: machine: AMD Athlon 64 X2 Dual Core Processor 5000+ operating system: Mandriva linux 2010.2 (32 bit) This is a bug (or missing feature if you want) in Mandriva's version of bash. The only workaround that I know is to install vanilla upstream bash. -- 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.
Re: [sage-devel] Re: tests fail for sage-5.5
On 2013-01-01 19:13, Rajeev Singh wrote: I ran the tests again and this time only one test failed - sage -t --long -force_lib devel/sage/sage/modular/modform/find_generators.py There was a segmentation fault for this test. Sorry for the noise about other tests earlier. Could you apply the patch from #13870 and see whether that solves the problem? -- 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.
Re: [sage-devel] Re: sage 5.6.beta1 build error (mercurial-2.2.2.p0) on OS X 10.8.2
On 2013-01-01 20:01, Volker Braun wrote: The following ticket says that this was fixed in XCode 4.5. Are you sure you don't have an old version floating around? http://trac.sagemath.org/sage_trac/ticket/13309 It's also strange that nobody else reported this problem. -- 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.
Re: [sage-devel] Re: sage 5.6.beta1 build error (mercurial-2.2.2.p0) on OS X 10.8.2
On 2013-01-01 21:31, Robert Zeier wrote: I do not see how this would be possible as I did upgrade Xcode to the latest version some time ago and I have never installed a second version of Xcode: Perhaps you still have some remnants of some old XCode on your system which cause this problem. But then you might run into more errors apart from this Mercurial one. -- 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.
[sage-devel] Re: Graph neighbours - room for huge performance boost
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 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 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.
Re: [sage-devel] Re: Graph neighbours - room for huge performance boost
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 since I started working on Sage is that in order to replace it you need to deal with a wealth of unpleasant things : loops, multiple edges and labels. These things are a nightmare. This being said, I think that the memory cost of dict or dict and sets are comparable... Whatever it is :-) Nathann -- 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.
Re: [sage-devel] Re: sage 5.6.beta1 build error (mercurial-2.2.2.p0) on OS X 10.8.2
I ended up patching also python and R in the same way as mercurial. @Volker: Thanks for showing me how to do this. Everything did build with the patches for mercurial, python, and R! Am Mittwoch, 2. Januar 2013 10:08:11 UTC+1 schrieb Jeroen Demeyer: On 2013-01-01 21:31, Robert Zeier wrote: I do not see how this would be possible as I did upgrade Xcode to the latest version some time ago and I have never installed a second version of Xcode: Perhaps you still have some remnants of some old XCode on your system which cause this problem. But then you might run into more errors apart from this Mercurial one. Hopefully, somebody else can independently verify that the problem exist. Please let me know if there is something else I can try or test! * some details follow below: * Without the patches python did build, but some modules did not: Python build finished, but the necessary bits to build these modules were not found: bsddb185 dl gdbm imageoplinuxaudiodev ossaudiodev spwd sunaudiodev To find the necessary bits, look in setup.py in detect_modules() for the module's name. Failed to build these modules: _scproxy This resulted in cython not building: from Cython.Tempita import sub File /opt/sage/sage-5.6.beta1/spkg/build/cython-0.17.2/src/Cython/Tempita/__init__.py, line 34, in module import cgi File /opt/sage/sage-5.6.beta1/local/lib/python/cgi.py, line 40, in module import urllib File /opt/sage/sage-5.6.beta1/local/lib/python/urllib.py, line 1379, in module from _scproxy import _get_proxy_settings, _get_proxies ImportError: No module named _scproxy Error installing Cython real 0m0.339s user 0m0.294s sys 0m0.041s Error installing package cython-0.17.2 Please email sage-devel (http://groups.google.com/group/sage-devel) explaining the problem and including the relevant part of the log file /opt/sage/sage-5.6.beta1/spkg/logs/cython-0.17.2.log Describe your computer, operating system, etc. If you want to try to fix the problem yourself, *don't* just cd to /opt/sage/sage-5.6.beta1/spkg/build/cython-0.17.2 and type 'make' or whatever is appropriate. Instead, the following commands setup all environment variables correctly and load a subshell for you to debug the error: (cd '/opt/sage/sage-5.6.beta1/spkg/build/cython-0.17.2' '/opt/sage/sage-5.6.beta1/sage' -sh) When you are done debugging, you can type exit to leave the subshell. make[2]: *** [installed/cython-0.17.2] Error 1 make[1]: *** [all] Error 2 * * P.S. There was one spurious testing error with eclib-20120830. But this did go away after I reran it. make[4]: *** [check_g0n] Error 127 make[4]: *** Waiting for unfinished jobs ... make[3]: *** [check-recursive] Error 1 Error: eclib's test suite failed to pass. -- 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.
[sage-devel] Re: Graph neighbours - room for huge performance boost
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 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 since I started working on Sage is that in order to replace it you need to deal with a wealth of unpleasant things : loops, multiple edges and labels. These things are a nightmare. This being said, I think that the memory cost of dict or dict and sets are comparable... Whatever it is :-) 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 neighbourhouds of vertices and the vertices themselves sequentially. In these cases representing graphs as lists of edges is very bad, one would be much better off using a tuple of sets (or even the list of lists) to represent the graph. I don't know whether there are backhands available to deal with this. Dima Nathann -- 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.
Re: [sage-devel] Re: Graph neighbours - room for huge performance boost
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 neighbourhouds of vertices and the vertices themselves sequentially. In these cases representing graphs as lists of edges is very bad, one would be much better off using a tuple of sets (or even the list of lists) to represent the graph. I don't know whether there are backhands available to deal with this. Not a backend, but still... :-P http://www.sagemath.org/doc/reference/sage/graphs/base/static_sparse_graph.html 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 :-) Nathann -- 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.
Re: [sage-devel] Re: Graph neighbours - room for huge performance boost
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 the latter, as they parse the neighbourhouds of vertices and the vertices themselves sequentially. In these cases representing graphs as lists of edges is very bad, one would be much better off using a tuple of sets (or even the list of lists) to represent the graph. I don't know whether there are backhands available to deal with this. Not a backend, but still... :-P http://www.sagemath.org/doc/reference/sage/graphs/base/static_sparse_graph.html This structure is used for the sparse matrices which appear in the solution of discretized PDE (known as csl or csr structures, have a look at scipy): everybody uses this, and, at the time I write thousands of codes are running this. OK, BUT: how do you build this structure ? In my applications (PDEs), the pairs of coefficients (i,j) appear in *any* order. Do you know an efficient algorithm to build the structure ? This is here that the dictionary appears: you first put your coefficients in the dictionary in the order they appear; when your graph has been fully constructed, you transform it into this static graph structure. The problem is that Python dictionaries are *very* slow. Do you know how they are implemented? Personally (but not is Sage), I use a C++ stl::map: mapint,int. Actually, C++ maps are represented by B-Trees. They are reasonably fast and the transformation into the static graph structure is very easy: you just use a mapint,int::iterator to get the coefficients in the order they will appear in the final structure. If you want do do this in parallel (current problems can have 10^10 edges), it's a bit more tricky, but feasible, and it is not the concern, here. t.d. 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 :-) Nathann -- 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
[sage-devel] Re: Sage 5.5 on ARM
On 31 dic 2012, 14:37, Julien Puydt julien.pu...@laposte.net wrote: Hi, it compiles well, except for conversion.c in libm4rie, which does compile, but needs too much ram. It passes all but three doctests (the gamma-related ones...). I made a bdist available in the bdist/ directory of my home directory on sage.math.washington.edu. It's a little early but still: happy new year! Snark on #sagemath Is it available for download? -- 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.
[sage-devel] Re: Sage 5.5 on ARM
On Wednesday, January 2, 2013 2:41:14 PM UTC+1, mmarco wrote: Is it available for download? I don't know, if someone tells me where it is, I'll update the mirror with the new version. H -- 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.
Re: [sage-devel] Re: Sage 5.5 on ARM
Le 02/01/2013 14:41, mmarco a écrit : On 31 dic 2012, 14:37, Julien Puydt julien.pu...@laposte.net wrote: I made a bdist available in the bdist/ directory of my home directory on sage.math.washington.edu. Is it available for download? Well, as I said it's available on sage.math.washington.edu ; the full path is: /home/jpuydt/bdist/sage-5.5-armv7l-Linux.tar.gz Snark on #sagemath -- 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.
[sage-devel] Re: Graph neighbours - room for huge performance boost
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/cpython/file/tip/Objects/dictnotes.txt http://stackoverflow.com/questions/327311/how-are-pythons-built-in-dictionaries-implemented has many good answers, it seems. Thanks, Jason -- 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.
Re: [sage-devel] Re: Graph neighbours - room for huge performance boost
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 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.
Re: [sage-devel] Re: Sage 5.5 on ARM
On Wed, Jan 2, 2013 at 4:24 PM, Julien Puydt julien.pu...@laposte.net wrote: /home/jpuydt/bdist/sage-5.5-armv7l-Linux.tar.gz ah, bdist :-) thanks! file is being mirrored! h -- 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.
Re: [sage-devel] Re: Graph neighbours - room for huge performance boost
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. Stackoverflow is totally botched! I decided never more to try to use that place. Kjetil Thank you very much Jason !!! O_O Nathann -- 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. -- If you want a picture of the future - imagine a boot stamping on the human face - forever. George Orwell (1984) -- 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.
[sage-devel] Re: Strange performance (bug?) computing a specific determinant
Hello! Has anyone already looked into this thing? The bug appears to slow down all matrix computations related to pariGP. For example it gets stuck computing the eigenvalues of a matrix as well. It's quite annoying. The pariGP guys confirmed it's a bug in pari so we should update the pari package that sage ships! Best, Jernej On Thursday, 6 September 2012 14:12:07 UTC+2, Jernej Azarija wrote: Consider the following program sage: G = graphs.OddGraph(4) sage: G.spanning_trees_count() 336140 It takes approximately 8 minutes to compute the number of spanning trees using this method. However, the number of spanning trees can be computed directly from the charpoly of the respective Kirchhoff matrix sage: (G.kirchhoff_matrix()).charpoly().coeffs()[1]/35 336140 which takes an instant (less than a second) to compute. Looking at the way spanning_trees_count is implemented within generic_graph.py, one can see: M=self.kirchhoff_matrix() M.subdivide(1,1) M2 = M.subdivision(1,1) return abs(M2.determinant()) # -The abs() here is redundant someone should remove it To speed the computation one can pass the parameter algorithm='padic' to the determinant() method and get the result of spanning_trees_count() instantly. That said, I am wondering if this is perhaps a bug in the default implementation of determinant()? It seems strange to me that it takes 8 minutes to compute a determinant of a 34x34 matrix while other algorithms do it within a second. -- 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.
[sage-devel] Re: Graph neighbours - room for huge performance boost
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)? 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.
[sage-devel] Re: Possible bug in polynomial .reduce()
Thanks. Should I open a trac ticket for this then? -- 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.
[sage-devel] Re: Graph neighbours - room for huge performance boost
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 bitsets for really fast access. Thanks, Jason -- 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.
[sage-devel] Re: Graph neighbours - room for huge performance boost
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 faster one (faster than Sage's data structure), about a tenth the time in one concrete benchmark. In this benchmark, the vertices are just plain integers. Sage does not use plain dicts to store the neighborhood lists, if I recall correctly, and it doesn't do nearly as well as networkx, which does use dicts to store neighborhoods. 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 loop and here is a neighborhood dict approach: sage: ggnx = G.networkx_graph() sage: %timeit EE = [(u,v) for u in ggnx for v in ggnx.neighbors_iter(u)] 1 loops, best of 3: 111 us per loop Thanks, Jason -- 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.
[sage-devel] Re: Graph neighbours - room for huge performance boost
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 loop and here is a neighborhood dict approach: sage: ggnx = G.networkx_graph() sage: %timeit EE = [(u,v) for u in ggnx for v in ggnx.neighbors_iter(u)] 1 loops, best of 3: 111 us per loop A few more data points to narrow in on just the neighbors functionality: Sage: sage: %timeit G.neighbors(0) 1 loops, best of 3: 23.2 us per loop sage: %timeit G[0] 1 loops, best of 3: 24 us per loop Networkx: sage: %timeit ggnx.neighbors(0) 100 loops, best of 3: 1.21 us per loop sage: %timeit ggnx[0].keys() 100 loops, best of 3: 1.02 us per loop sage: %timeit ggnx[0] # return the neighbors dictionary 100 loops, best of 3: 590 ns per loop Thanks, Jason -- 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.
[sage-devel] Re: Possible bug in polynomial .reduce()
This was a cross post, but I didn't realize the original discuss wouldn't be included. The discussion is at https://groups.google.com/forum/?fromgroups=#!topic/sage-support/Ar7z2b5cOic and, at its simplest, is that R.y1,y2=PolynomialRing(Qp(5) ,2, order='lex') G=[y1^2 + y2^2, y1*y2 + y2^2, y2^3] (y2^3).reduce(G) returns an `int` -- 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.
Re: [sage-devel] Re: Graph neighbours - room for huge performance boost
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 more complicated algorithms (than the enumeration of neighbors), i.e. the computation of distances/shortest path and all versions that take weidhted edges into account. Having Cython graphs is a way to get more performances on such algorithms than it would be possible with just plain dictionaries otherwise, with everything written at C level. For instance the content of this file : http://www.sagenb.org/src/graphs/base/c_graph.pyx And there is yet another kind of algorithms for which the solution is different : dedicated code for which it is more interesting to make a copy of the graph in a format optimised for the algorithm itself. Many of the most time-consuming methods of Graph actually do that : - everything related to cliques is solved with Cliquer, which has its own structure - everything solved with LP solvers - everything related to the computations of distances between all pairs of vertices The problem lies in this space : the algorithms whose running time is not sufficient to deserve a copy of the graph into a better structure. And we are definitely way behind networkx for the enumeration of neighbors. I expect that we are much more compact in memory, though. I always wanted to dig inside of the graph backends but never went that far. Recently, I prefer to think of new graph structures that can be used by time-consuming algorithms, especially because it prevents me from having to deal with the labels/loops/multiple edges hell that drives me crazy at the slightest touch :-P This being said, if we ever go back to networkx-type graph structure, I would prefer to have our own implementation of it. Otherwise I will spend my time working for networkx, and I won't like that :-P Nathann -- 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.
Re: [sage-devel] Re: Graph neighbours - room for huge performance boost
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 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)? I'll try to make precise measurements and comparisons, otherwise this discussion is non sense I ll do it, when I'll have time :-( 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
Re: [sage-devel] Re: Graph neighbours - room for huge performance boost
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 deal with. Remove vertex and edge labels from Graphs and you will not recognize the running time :-P Nathann -- 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.
Re: [sage-devel] Re: Graph neighbours - room for huge performance boost
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 linear. As you can see below you see the timings of: G = graphs.RandomBarabasiAlbert(2^i,2) E = [(u,v) for u in G for v in G.neighbor_iterator(u)] #and EE = [(u,v) for u in ggnx for v in ggnx.neighbors_iter(u)] seem to double each step as one would expect with linear complexity. However the time of ggnx = G.networkx_graph() increases each step by a factor of about 4, indicating quadratic runtime complexity :S. sage: for i in range(10,21): : print i : time G = graphs.RandomBarabasiAlbert(2^i,2) : time E = [(u,v) for u in G for v in G.neighbor_iterator(u)] : time ggnx = G.networkx_graph() : time EE = [(u,v) for u in ggnx for v in ggnx.neighbors_iter(u)] : 10 Time: CPU 0.05 s, Wall: 0.05 s Time: CPU 0.02 s, Wall: 0.02 s Time: CPU 0.03 s, Wall: 0.03 s Time: CPU 0.00 s, Wall: 0.00 s 11 Time: CPU 0.09 s, Wall: 0.09 s Time: CPU 0.03 s, Wall: 0.03 s Time: CPU 0.07 s, Wall: 0.07 s Time: CPU 0.01 s, Wall: 0.01 s 12 Time: CPU 0.19 s, Wall: 0.19 s Time: CPU 0.07 s, Wall: 0.07 s Time: CPU 0.20 s, Wall: 0.20 s Time: CPU 0.01 s, Wall: 0.01 s 13 Time: CPU 0.40 s, Wall: 0.40 s Time: CPU 0.13 s, Wall: 0.13 s Time: CPU 0.66 s, Wall: 0.66 s Time: CPU 0.02 s, Wall: 0.02 s 14 Time: CPU 0.92 s, Wall: 0.92 s Time: CPU 0.27 s, Wall: 0.27 s Time: CPU 2.45 s, Wall: 2.46 s Time: CPU 0.04 s, Wall: 0.04 s 15 Time: CPU 1.86 s, Wall: 1.87 s Time: CPU 0.55 s, Wall: 0.55 s Time: CPU 8.85 s, Wall: 8.86 s Time: CPU 0.08 s, Wall: 0.08 s 16 Time: CPU 3.96 s, Wall: 3.96 s Time: CPU 1.10 s, Wall: 1.10 s Time: CPU 33.85 s, Wall: 33.85 s Time: CPU 0.16 s, Wall: 0.16 s 17 Time: CPU 8.29 s, Wall: 8.30 s Time: CPU 2.21 s, Wall: 2.22 s Time: CPU 139.72 s, Wall: 140.03 s Time: CPU 0.35 s, Wall: 0.35 s 18 Time: CPU 18.02 s, Wall: 18.08 s Time: CPU 4.46 s, Wall: 4.46 s ^C^C -- 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.
[sage-devel] Re: tests fail for sage-5.5
I solved the problem by installing atlas-3.10.0 and recompiling numpy and scipy. Now all the tests pass. Rajeev On Tue, Jan 1, 2013 at 11:43 PM, Rajeev Singh rajs2...@gmail.com wrote: I ran the tests again and this time only one test failed - sage -t --long -force_lib devel/sage/sage/modular/modform/find_generators.py There was a segmentation fault for this test. Sorry for the noise about other tests earlier. Rajeev -- 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.
