#18972: twographs and Seidel switching
-------------------------------------+-------------------------------------
Reporter: dimpase | Owner:
Type: enhancement | Status: needs_work
Priority: major | Milestone: sage-6.9
Component: graph theory | Resolution:
Keywords: | Merged in:
Authors: | Reviewers: Nathann Cohen
Report Upstream: N/A | Work issues:
Branch: | Commit:
u/dimpase/seidelsw | 1b7f6b99019699fdccb4bb9afa86315defc87994
Dependencies: #18960, #18948, | Stopgaps:
#18988, #18991 |
-------------------------------------+-------------------------------------
Comment (by ncohen):
> > - Stop using map and filter. You do not know what it does, i.e. Python
is not
> > lisp. You are building in memory lists that you do not need, only to
throw
> > them away later. Use list-comprehension instead (also faster).
> this is an urban myth that the latter is much faster:
I said 'faster', not 'much faster', and this is what your timing proves.
It also eats less memory. I also suspect that the resulting Cython code is
much better (and so that the timings could differ in that case).
> besides, I do find the list comprehension syntax ugly and error-prone.
It is much shorter and easier to read. Get used to it.
> > - `Graph([V, lambda i, j: frozenset((i,j)) in edges])` THINK ABOUT
WHAT IT
> > DOES. This is insulting.
>
> Indeed, I wish I could write `Graph(V,edges)` or `Graph([V,edges])` or
even `Graph(edges)` instead. Why can't I?
There is no God above forbidding this syntax. If the constructor does not
do what you want, then improve it.
In this situation, `Graph(edges)` simply works.
> Why must I instead do something like
> `blah=Graph(V); blah.add_edges(edges); return blah`? Cause the GC is
hungry and must be fed `blah` on each return?
What your code does is this:
"For every pair of points among V, build a frozen set {i,j} then test if
this set is contained in a LIST (linear time) of sets". That's ridiculous.
> I copied this one from the ` elif format == 'adjacency_matrix':` block.
Should one fix both places?
Lazy code.... Yeah yeah, please `-_-`
> > - Use `g.copy()` (which should be called by `copy(g)`), not deepcopy.
>
> the docs to `g.copy()` say something like "use only if you change the
backend..."
> {{{
> Warning: Please use this method only if you need to copy but
> change the underlying implementation or weightedness. Otherwise
> simply do "copy(g)" instead of "g.copy()".
> }}}
> Should I ignore this? Should the docs be improved?
All that it says is that "g.copy()" is equivalent to "copy(g)", and that
the latter should be preferred. The advantage of `g.copy()` is that you
can give it additional arguments, e.g. change the backend.
I'd say that we can do without this warning, though.. To me it enforces a
personal taste, not something we should ask users (or even developers) to
follow. Makes no difference in what gets run.
> > - Really, STOP using lambda functions. You don't know what it does, so
stop
> > that.
>
> This is a myth that they are slow, see above.
I am not saying that it is slow to use lambda function, I say that you
have no idea of what you are doing.
> > {{{
> > + return Graph([Nv+NonNv, lambda i, j:
> > + (i in NonNv and j in NonNv and i in
self.neighbors(j)) or
> > + (i in Nv and j in Nv and i in
self.neighbors(j)) or
> > + (i in Nv and j in NonNv and not i in
self.neighbors(j)) or
> > + (j in Nv and i in NonNv and not i in
self.neighbors(j))])
> > }}}
> > Build this graph by adding edges to it. It will be incomparably
> > faster. Writing code like this should not be allowed.
>
> in my book using temporary variables is slow; perhaps Python
implementations will get fuller use of this fact as its devs and users get
wiser...
This code call `.neighbors()` for around `Theta(n^2)` times. Each time it
builds a list in memory, and does a linear search in a list of things
which may not even be integers. That's madness. THIS IS NOT SYMBOLICS.
THIS IS ACTUAL CODE. For every pair of i,j this function is run, and every
time all these lists are creates for nothing.
> > - `is_even`.
>
> I like it better than `%`, more readable: one does not need to swap out
some other language in the head to recall the meaning. But if you
insist...
Are you telling me that you are having a hard time remembering the meaning
of `%` ? Is that a joke?
Besides, how many CPU instructions do you think it takes to compute a `%2`
on a C int variable? Now, what happens when you load a function, turn the
int into a Python object, compute '%2', then return the result?
Nathann
--
Ticket URL: <http://trac.sagemath.org/ticket/18972#comment:54>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
