pairs from a list

[Steven D'Aprano]

On Wed, 23 Jan 2008 11:57:05 -0500, Alan G Isaac wrote:

> Steven D'Aprano wrote:
>> In fact, "fastest" isn't even a meaningful attribute. Does it mean:
>> 
>> * the worst-case is fastest
>> * the best-case is fastest
>> * the average-case is fastest
>> * fastest on typical data
>> * all of the above
> 
> 
> I confess that it did not occur to me that there might be an interesting
> distinction among these cases for the question of how to get sequential
> pairs from a list.  How would one draw these distinctions in this case?

Well, in this *specific* case I don't think they're terribly interesting 
because your problem is so simple. Best-case will, presumably, occur when 
the list is empty. Worst-case will occur if somebody passes a non-
terminating iterator to your code (although that depends on the nature of 
your solution and how you are using it).

But in the broader context of optimizing, these distinctions are very 
important. For example, Quicksort is very fast on randomly ordered data, 
but terribly slow on data which is already sorted: about as slow as 
Bubblesort. Mergesort's best-case isn't as fast as Quicksort's best-case, 
but it's worst-case behaviour is much, much better. And both Quicksort 
and Mergesort are complex enough that a simpler, slower algorithm like 
Shell Sort will be significantly faster for small data sets.

But I'm sure you already know all this, I'm just mentioning it for the 
benefit of anybody else reading who still thinks that a generic "what's 
the fastest way" type question is meaningful.


-- 
Steven