Standard Forth versus Python: a case study

Fredrik Lundh fredrik at pythonware.com
Thu Oct 12 08:23:50 CEST 2006


Paul Rubin wrote:

>> Ok, I'll bite.  How do you compute the median of a list using just a single 
>> temp var?
> 
> Well there's an obvious quadratic-time method...

that does it without modifying the list?

if you can modify the list, there are plenty of algorithms that does it 
in expected O(n) or better, but I cannot think of a one that doesn't use 
at least a few variables (e.g. two list indexes and a pivot).

but I haven't had enough coffee yet, so I'm probably missing something 
simple here.

</F>




More information about the Python-list mailing list