#9910: Longest path
----------------------------------------------+-----------------------------
Reporter: ncohen | Owner: jason, ncohen, rlm
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-4.6.1
Component: graph theory | Keywords:
Author: Nathann Cohen | Upstream: N/A
Reviewer: Robert Miller, Minh Van Nguyen | Merged:
Work_issues: |
----------------------------------------------+-----------------------------
Comment(by mvngu):
Replying to [comment:8 ncohen]:
> Here is a patch to import on top of your, to fix the documentation.
These options are just a way for the user to compute the "longest path
leaving from s", or the "longest path ending in t", or the "longest
s-t-path"
Your improved documentation is certainly very clear to me. But note a typo
in the following:
{{{
4384 returns the longest path starting at ``s``). Thie
argument is Set to
}}}
I think you mean "The" instead of "Thie". And two more in these lines:
{{{
4388 - ``s`` (vertex) -- forces the destination of the path
(the method then
4389 returns the longest path ending at ``s``). Thie argument
is Set to
}}}
I think you mean the above to be about the argument "t", as opposed to
repeating the documentation for the argument "s". If you fix these, then
the ticket is good to go.
[[BR]][[BR]]
> About the if/else, I knew it was not useful but I let it stay anyway
thinking it would be easier to understand the code. When I look at it from
afar, I like to see a If/Else with return lines at the end of both, which
ensures the method ends because of this part of the code (and I like to
preserve symmetry when there is no reason not to `^^;`). That's just me,
if you think it's better without the "else", then let it be.
In many cases, removing the redundant "else" can result in faster code
than if you leave in the "else". Here's a sample profiling session:
{{{
#!python
sage: # define functions whose runtime are to be compared
sage: def con_else(n):
....: if n & 1:
....: 2 * n
....: return
....: else:
....: n + 1
....: return
....:
sage: def con_no_else(n):
....: if n & 1:
....: 2 * n
....: return
....: n + 1
....: return
....:
sage:
sage: # get runtime samples for the above functions
sage: %timeit con_else(100)
625 loops, best of 3: 781 ns per loop
sage: %timeit con_else(100)
625 loops, best of 3: 787 ns per loop
sage: %timeit con_else(100)
625 loops, best of 3: 795 ns per loop
sage: %timeit con_else(100)
625 loops, best of 3: 785 ns per loop
sage: %timeit con_else(100)
625 loops, best of 3: 781 ns per loop
sage: %timeit con_else(100)
625 loops, best of 3: 792 ns per loop
sage: %timeit con_else(100)
625 loops, best of 3: 784 ns per loop
sage: %timeit con_else(100)
625 loops, best of 3: 798 ns per loop
sage: %timeit con_else(100)
625 loops, best of 3: 784 ns per loop
sage: %timeit con_else(100)
625 loops, best of 3: 766 ns per loop
sage: T1even = [781, 787, 795, 785, 781, 792, 784, 798, 784, 766]
sage:
sage: %timeit con_else(101)
625 loops, best of 3: 771 ns per loop
sage: %timeit con_else(101)
625 loops, best of 3: 769 ns per loop
sage: %timeit con_else(101)
625 loops, best of 3: 771 ns per loop
sage: %timeit con_else(101)
625 loops, best of 3: 768 ns per loop
sage: %timeit con_else(101)
625 loops, best of 3: 772 ns per loop
sage: %timeit con_else(101)
625 loops, best of 3: 766 ns per loop
sage: %timeit con_else(101)
625 loops, best of 3: 772 ns per loop
sage: %timeit con_else(101)
625 loops, best of 3: 768 ns per loop
sage: %timeit con_else(101)
625 loops, best of 3: 769 ns per loop
sage: %timeit con_else(101)
625 loops, best of 3: 774 ns per loop
sage: T1odd = [771, 769, 771, 768, 772, 766, 772, 768, 769, 774]
sage:
sage: %timeit con_no_else(100)
625 loops, best of 3: 661 ns per loop
sage: %timeit con_no_else(100)
625 loops, best of 3: 667 ns per loop
sage: %timeit con_no_else(100)
625 loops, best of 3: 669 ns per loop
sage: %timeit con_no_else(100)
625 loops, best of 3: 667 ns per loop
sage: %timeit con_no_else(100)
625 loops, best of 3: 669 ns per loop
sage: %timeit con_no_else(100)
625 loops, best of 3: 661 ns per loop
sage: %timeit con_no_else(100)
625 loops, best of 3: 666 ns per loop
sage: %timeit con_no_else(100)
625 loops, best of 3: 674 ns per loop
sage: %timeit con_no_else(100)
625 loops, best of 3: 667 ns per loop
sage: %timeit con_no_else(100)
625 loops, best of 3: 664 ns per loop
sage: T2even = [661, 667, 669, 667, 669, 661, 666, 674, 667]
sage:
sage: %timeit con_no_else(101)
625 loops, best of 3: 680 ns per loop
sage: %timeit con_no_else(101)
625 loops, best of 3: 677 ns per loop
sage: %timeit con_no_else(101)
625 loops, best of 3: 680 ns per loop
sage: %timeit con_no_else(101)
625 loops, best of 3: 685 ns per loop
sage: %timeit con_no_else(101)
625 loops, best of 3: 679 ns per loop
sage: %timeit con_no_else(101)
625 loops, best of 3: 677 ns per loop
sage: %timeit con_no_else(101)
625 loops, best of 3: 678 ns per loop
sage: %timeit con_no_else(101)
625 loops, best of 3: 679 ns per loop
sage: %timeit con_no_else(101)
625 loops, best of 3: 685 ns per loop
sage: %timeit con_no_else(101)
625 loops, best of 3: 675 ns per loop
sage: T2odd = [680, 677, 680, 685, 679, 677, 678, 679, 685, 675]
sage:
sage: # And now a comparison of the average runtime
sage: RR(sum(T1even) / len(T1even))
785.300000000000
sage: RR(sum(T2even) / len(T2even))
666.777777777778
sage: RR(sum(T1odd) / len(T1odd))
770.000000000000
sage: RR(sum(T2odd) / len(T2odd))
679.500000000000
}}}
[[BR]]
> I am really sorry you had to waste time fixing my spaces and long lines.
I know I never paid attention to spaces, but I will from now on, and I
thought I was wary enough of long lines, which is clearly untrue. I also
thought I had learned not to write ``x == None`` too... `:-/`
I care about your code and how fast it runs. That's why I suggested that
you use "is not" or "is" when you do a comparison with "None", because in
that case the comparison is faster than if you used "!=" or "=".
[[BR]][[BR]]
> Here is the slight fix in the documentation you asked. If it suits you,
the ticket is good to go.
>
> Thank you for your precious help, once again !
Don't take my comments above the wrong way. Had I not cared about your
code and how fast you can make it run, I wouldn't bother reading your
patches and suggest where you can improve the runtime of your code. There
are many tricks in Python programming that can result in fast code without
having to use Cython. I just want to share with you any tricks I know. As
regards coding conventions, many programming languages have them and
people who program in such a language would more or less adhere to the
corresponding coding conventions. Remember that conventions are guidelines
that many if not most experienced programmers find to result in readable,
maintainable, and elegant looking code. This means that in some cases, it
makes sense to break a convention. In case you are uncertain about whether
to follow a convention or not, you need to use your judgement.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/9910#comment:9>
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 post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
