On Thu, May 21, 2015 at 5:35 PM, Steven D'Aprano
<steve+comp.lang.pyt...@pearwood.info> wrote:
>> You don't need huge. On any algorithm where slices are being used you
>> will have to account for the linear complexity. You seem to be
>> dismissive of this fact, but it can have tremendous performance
>> implications, since it can turn a linear algorithm into a quadratic
>> one just like that.
>
> Sure. And for small enough N, everything is fast.
>
> There's a sorting algorithm, usually called "Bozo sort", which shuffles the
> list, then checks whether it is sorted. If not, it shuffles it again, until
> it is sorted. Bozo sort is a *terrible* algorithm, with no upper limit to
> the worst case, and O(N!) for the average case. And yet, with small lists
> (say, five items) the performance is acceptable if your requirements are
> low.
A less ridiculous, but equally valid, comparison is with
multiplication algorithms. A while ago someone asked about what Python
uses, and on learning that CPython uses Karatsuba [1], suggested that
some other algorithm (I don't remember which) had better asymptotic
complexity. Downside: It'd be slower for smaller numbers, and the
complexity cost of an additional cutoff ("use grade-school up to X,
then Karatsuba up to Y, then Fuerer's") would also negatively impact
performance overall. Grade-school arithmetic is O(N*N) which looks
terrible... but for smallish numbers, its performance is quite
adequate.
ChrisA
[1] https://en.wikipedia.org/wiki/Karatsuba_algorithm
--
https://mail.python.org/mailman/listinfo/python-list
