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" <[email protected]>
http://Nicolas.Thiery.name/
--
To post to this group, send an email to [email protected]
To unsubscribe from this group, send an email to
[email protected]
For more options, visit this group at http://groups.google.com/group/sage-devel
URL: http://www.sagemath.org
