Complexity, Algorithms and Graphs...

[Nathann Cohen]

Hello everybody !!!!

During the review of http://trac.sagemath.org/sage_trac/ticket/7364,
Florent Hivert mentionned it could be a great idea to add a
"complexity" note in all of our algorithms, and some informations
about optimality if known ( or even approximations if available, etc
... ). What do you think of it, and what would you think of such
information as "required" before giving a positive review to patches ?

Nathann

[William Stein]

I'm strongly against requiring this, but certainly for encouraging it
and establishing a good format.

William

> Nathann
>
> --
> To post to this group, send an email to sage-...@googlegroups.com
> To unsubscribe from this group, send an email to sage-devel-...@googlegroups.com
> For more options, visit this group at http://groups.google.com/group/sage-devel
> URL: http://www.sagemath.org



--
William Stein
Associate Professor of Mathematics
University of Washington
http://wstein.org

[Florent Hivert]

Hi There,

> > During the review of http://trac.sagemath.org/sage_trac/ticket/7364,
> > Florent Hivert mentionned it could be a great idea to add a
> > "complexity" note in all of our algorithms, and some informations
> > about optimality if known ( or even approximations if available, etc
> > ... ). What do you think of it, and what would you think of such
> > information as "required" before giving a positive review to patches ?
>
> I'm strongly against requiring this, but certainly for encouraging it
> and establishing a good format.

+1

As indicated in my review, it was not at all my idea to *require* it. But It
is undoubtedly a valuable information... I'm trying to hire a student to do
this job for all the basic method throughout combinat. We started to do this
more or less systematically in MuPAD before the switch to sage. See for
examples:

http://mupad-combinat.sourceforge.net/doc/en/combinat/permutations.html

My (obvious) suggestion is to add at the end of a function doc (close to
reference) a section e.g.:

ALGORITHM:

- modified merge sort algorithm. The complexity ``O(n * ln(n))`` is
optimal however it has a bad constant time factor. We therefore use a
naive method for ``n <= 27``.


REFERENCES:

- ...

AUTHORS:

- ...

Do you think about something even more structured ?

Cheers,

Florent

[William Stein]

That's a good example. I wonder if LaTeX typesetting would be nicer,
e.g. `O(n\ln(n))` and `n\leq 27`?

William

[Florent Hivert]

> > My (obvious) suggestion is to add at the end of a function doc (close to
> > reference) a section e.g.:
> >
> > � �ALGORITHM:
> >
> > � � - modified merge sort algorithm. The complexity ``O(n * ln(n))`` is
> > � �optimal however it has a bad constant time factor. We therefore use a
> > � �naive method for ``n <= 27``.
> >
> >
> > � �REFERENCES:
> >
> > � � - ...
> >
> > � �AUTHORS:
> >
> > � �- ...
> >
> > Do you think about something even more structured ?
>
> That's a good example. I wonder if LaTeX typesetting would be nicer,
> e.g. `O(n\ln(n))` and `n\leq 27`?

Unfortunately, we currently have very few notes like this (I found only 6 of
them). So I copy pasted the example from MuPAD rather than from sage, which is
a Pity. If we agree on the "ALGORITHM:" section, I'll post a patch to
advertise this design in the developer guide, and apply this in some place in
combinat. Just to be sure: there is no special treatment by sphinx for this
kind of section ? Sphinx isn't aware at all of the meaning of REFERENCES or
AUTHORS, is it ?

Cheers,

Florent

[Nathann Cohen]

> As indicated in my review, it was not at all my idea to *require* it.

I am really sorry if my message implied the contrary :-)

Nathann

[Nicolas M. Thiery]

On Sun, Nov 22, 2009 at 08:59:17PM +0100, Florent hivert wrote:
> My (obvious) suggestion is to add at the end of a function doc (close to
> reference) a section e.g.:
>
> ALGORITHM:
>
> - modified merge sort algorithm. The complexity ``O(n * ln(n))`` is
> optimal however it has a bad constant time factor. We therefore use a
> naive method for ``n <= 27``.

+1, possibly with latex formatting as suggested by William.

An other thing I would love to see in the documentation are synthetic
benchmarks comparing several algorithms. And maybe even trying to
estimate their practical complexity? Something like:

sage: def setup(n): return Permutations(n).random()
sage: def to_cycles(p, algorithm): p.to_cycles(algorithm = algorithm)
sage: benchmark(to_cycles, setup = setup,
algorithm = ["naive", "bitmap", "set", "list"],
n = [2^i for i in range(15)]) # not tested
+----+--------+--------+------+
| n | bitmap | set | list |
+----+--------+--------+------+
| 2 | 1ms | ...
| 4 |
| ...|
| | 50s | ... | |
+----+--------+--------+------+
| |O(n^1.1)|O(n^1.0)| ... |
+----+--------+--------+------+

Of course, the timings (should they be one of the 3 best, as returned
by timeit?) are specific for each platform; hence the # not tested.

The point is that will make it trivial for anyone to rerun the
benchmark on his platform of choice, play around with how far to run
it, ... without having to redevise what's the most natural way of
benchmarking the algorithms.

If making a nice benchmark becomes easy to do, then we will do a lot
of benchmarks. And systematically check that the complexity is as
advertised (I expect some surprises :-)).

Florent: do you think we should give this as project to your student?
It's hard to tell the amount of work needed. Maybe Python already has
some libraries to do such benchmarks? Or at least for simple
complexity estimates (a non trivial thing in general!!!)?

Desirable features:

- reuse the same input for all the algorithms, for a fairer comparison
- benchmark() could return an object, whose _repr_ gives the ascii
array above. But it could also have a _latex_ method for direct
inclusion in a paper (or for the notebook)

Thoughts? I'll create a ticket as soon as I will have received some
feedback.

Cheers,
Nicolas
--
Nicolas M. Thi�ry "Isil" <nth...@users.sf.net>
http://Nicolas.Thiery.name/