[Tutor] Aschenputtel problem - Shorter is not better?

[Christopher Arndt]

Terry Kemmerer schrieb:
> 
> 
> "Bearing in mind that shorter is not necessarily better..."
> 
> Wouldn't shorter, as a rule of thumb, as in less language statements, mean fewer 
> executions, and therefore faster?

Well, see for yourself...

I wrote a little benchmarking script for different solutions to my problem. It
turns out, that the original "traditional for-loop" approach is not only the
most readable but also one of the fastest.

Here are my timings (Python 2.4, Athlon64 1.8 Ghz, Ubuntu Hoary) (see the
attached script for the functions names):

List length: 100, Function calls: 3 x 1000

cinderella1: (1) 0.188769, (2) 0.189790, (3) 0.188901
cinderella2: (1) 0.263702, (2) 0.254624, (3) 0.254050
cinderella3: (1) 0.430694, (2) 0.270807, (3) 0.265921
cinderella4: (1) 0.154761, (2) 0.142940, (3) 0.139610
cinderella5: (1) 0.145273, (2) 0.139491, (3) 0.133930
cinderella6: (1) 0.144191, (2) 0.139056, (3) 0.141840
cinderella7: (1) 0.737320, (2) 0.726961, (3) 0.732526

List length: 1000, Function calls: 3 x 1000

cinderella1: (1) 1.639245, (2) 0.975745, (3) 0.971775
cinderella2: (1) 1.337324, (2) 1.330888, (3) 1.319431
cinderella3: (1) 18.772992, (2) 18.764382, (3) 18.759283
cinderella4: (1) 1.140375, (2) 1.120827, (3) 1.119281
cinderella5: (1) 1.460923, (2) 1.444996, (3) 1.444842
cinderella6: (1) 1.481483, (2) 1.469315, (3) 1.478990
cinderella7: (1) 7.211108, (2) 7.208998, (3) 7.202029

"cinderella1" ist the traditional approach, "cinderella3" builds up a list of
positives and then checks that against the original list by using the "in"
operator. This scales very badly for longer lists, as you can see in the second
timing.

"cinderella7" ist the Numeric approach proposed by Pierre Barbier de Reuille.
It doesn't compare very well, probably because it has to iterate 3 times over
the original list and once more over the list of positives.

The solution using sets ("cinderella4") seems to do very well too, but has
several limitations:

- does not preserver order of elements
- elements must be unique
- only available from Python 2.3

I leave it as an axcercise to the reader to try how the different soltutions
behave when condition(item) is more expansive (i.e takes longer).

Chris
-------------- next part --------------
A non-text attachment was scrubbed...
Name: cinderella.py
Type: text/x-python
Size: 2677 bytes
Desc: not available
Url : http://mail.python.org/pipermail/tutor/attachments/20050916/55f26118/cinderella.py