Optimisation

[Andy Armstrong]

On 3 Mar 2009, at 12:57, Paul Makepeace wrote:
>> Think mainly about algorithm choice at write time - O(NlogN) always  
>> beats
>> O(N^2).
>
> It beats it only when the constant factors cancel. Often nlogn algos
> have larger constant factors e.g. owing to simply more ops in the
> process, so only start to win on larger n. IIRC Knuth says simple
> sorts beat quicksort often up to n=1000, which in many scripting
> scenarios is fair percentage of problems. (Not that anyone doesn't use
> 'sort' in perl but rather that going to the work of getting a lower
> order algo needs justification in terms of expected large datasets,
> and, realistically perf testing.)

Yeah, excuse the sloppy generalisation :)

-- 
Andy Armstrong, Hexten