On Fri, Aug 01, 2014 at 02:37:43AM -0700, memilanuk wrote: > On 08/01/2014 01:33 AM, Ben Finney wrote:
> >* There is no guarantee all the items will be seen. ‘max’ could very > > well decide it's got the largest item and return it at any point. It's > > an implementation detail how it does that. > > What?!? Are you serious? Under what kind of conditions? Imagine a type of list which keeps a record of the largest value currently inside the list. Each time you append a new value, it compares it to the current "largest", and if bigger, changes the largest to the new value. (How you handle deletions is left as an exercise.) With this implementation, max(my_custom_list) is in principle a single, constant-time, lookup. I say in principle because I don't think Python provides any hooks for max() to take short cuts like this. But it could. Or perhaps the list is guaranteed to be sorted, in which case the max value is always the first; or you're scanning a tree, not a list, and you can find the maximum value much more efficiently than inspecting every element. Or you have a parallel processing computer which can compare all N elements and find the maximum in a single machine cycle. The point Ben is making is that one does not usually need to understand the implementation of the function to understand how to use it. Having said this, though, I find myself disagreeing with Ben's strict "ignore the implementation" stance. I sometimes find that I cannot really understand how to use a function until I've understood the algorithm it uses. It's not necessary to understand every last detail of it's implementation, but at least understanding the algorithm is useful. E.g. I don't understand the implementation of Python dicts, but I understand that they are a hash table with (I believe) linear probing, which makes it easy to see that dict look-ups are approximately constant time, degrading to linear time if all the keys have the same hash value. -- Steven _______________________________________________ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: https://mail.python.org/mailman/listinfo/tutor
