Hi all,
Given several objects with the same key, max() returns the first one:
>>> key = lambda x: 0 >>> max(1, 2, key=key) 1
This means it is not stable, at least according to the definition in "Elements of Programming" by Alexander Stepanov and Paul McJones (pg. 52):
"Informally, an algorithm is stable if it respects the original order of equivalent objects. So if we think of minimum and maximum as selecting, respectively, the smallest and the second smallest from a list of two arguments, stability requires that when called with equivalent elements, minimum should return the first and maximum should return the second."
A page later, In a side note, the authors mention that "STL incorrectly requires that `max(a, b)` return `a` when `a` and `b` are equivalent." (As a reminder, Stepanov is the chief designer of the STL).
So, I know this is not a big issue, to say the least, but is there any reason *not* to return the last argument? Are we trying to be compatible with STL somehow?
I admit I don't know of any real use case where this really matters, but I can point out that
ab = (1, 2) (min(ab, key=key), max(ab, key=key))
(1, 1)
is visibly less sensible than (1, 2).
Hope I'm not being a crank here...
Elazar
On Fri, Jan 17, 2014 at 03:45:14PM +0200, אלעזר wrote:
Hi all,
Given several objects with the same key, max() returns the first one:
>>> key = lambda x: 0 >>> max(1, 2, key=key) 1
A more natural example showing that both min and max return the *first* of equal elements is:
py> values = (1, 2, 1.0, 2.0) py> min(values) 1 py> max(values) 2
This means it is not stable, at least according to the definition in "Elements of Programming" by Alexander Stepanov and Paul McJones (pg. 52):
"Informally, an algorithm is stable if it respects the original order of equivalent objects.
Stability is normally only of concern with sorting algorithms. I'm not sure whether Stepanov and McJones' definition is widely accepted, or important. There are clear reasons for desiring sorting to be stable. Are there any clear reasons to desire max to be stable in this sense?
(There is another, unrelated, meaning of stability with regard to numeric algorithms, but it has nothing to do with the order of objects.)
Note that stability in this sense only is meaningful when your values are objects that you care about their identity as well as value.
So if we think of minimum and maximum as selecting, respectively, the smallest and the second smallest from a list of two arguments, stability requires that when called with equivalent elements, minimum should return the first and maximum should return the second."
A page later, In a side note, the authors mention that "STL incorrectly requires that `max(a, b)` return `a` when `a` and `b` are equivalent." (As a reminder, Stepanov is the chief designer of the STL).
So, I know this is not a big issue, to say the least, but is there any reason *not* to return the last argument? Are we trying to be compatible with STL somehow?
No, I expect that the result is an accident of implementation. Specifically, the min and max algorithms probably look something like this:
min = first item for each item: if item < min: min = item
max = first item for each item: if item > max: max = item
I admit I don't know of any real use case where this really matters, but I can point out that
ab = (1, 2) (min(ab, key=key), max(ab, key=key))
(1, 1)
is visibly less sensible than (1, 2).
Using your weird key function here is going to give bizarre results. Consider:
ab = (2, 1) min(ab, key=key), max(ab, key=key)
Current behaviour is to return (2, 2). I don't think that returning 2 for the minimum and 1 for the maximum is more sensible, but that's because the key function is not sensible, not because of any objection to making max stable in this sense.
On Sat, Jan 18, 2014 at 3:06 AM, Steven D'Aprano steve@pearwood.info wrote:
Using your weird key function here is going to give bizarre results. Consider:
ab = (2, 1) min(ab, key=key), max(ab, key=key)
Current behaviour is to return (2, 2). I don't think that returning 2 for the minimum and 1 for the maximum is more sensible, but that's because the key function is not sensible, not because of any objection to making max stable in this sense.
Imagine implementing min and max this way (ignoring key= and the possibility of a single iterable arg):
def min(*args): return sorted(args)[0]
def max(*args): return sorted(args)[-1]
By that definition, a stable sort means that:
lst = sorted((x,y)) assert lst == [min(lst), max(lst)]
will pass for any x and y.
That said, I don't see any particular use cases for this identity. Maybe the OP can enlighten?
ChrisA
On Wed, Jan 22, 2014 at 7:17 AM, random832@fastmail.us wrote:
On Fri, Jan 17, 2014, at 11:15, Chris Angelico wrote:
By that definition, a stable sort means that:
lst = sorted((x,y)) assert lst == [min(lst), max(lst)]
will pass for any x and y.
What definition of stable is this? Why not assert lst == [min(lst), max(lst[::-1])]?
The OP's definition.
ChrisA
Imagine implementing min and max this way (ignoring key= and the possibility of a single iterable arg):
lst = sorted((x,y)) assert lst == [min(lst), max(lst)]
will pass for any x and y.
Well, that's not possible, of course, if one is willing to be slightly perverse:
@total_ordering
... class SomewhatOrdered(object): ... def __init__(self, val): ... self.val = val ... def __eq__(self, other): ... return self.val == other.val ... def __lt__(self, other): ... return (self.val, random()) < (other.val, random()) ... def __repr__(self): ... return repr(self.val) ...
x, y, z = map(SomewhatOrdered, (1, 1.0, 2))
But even if you were slightly less perverse than this, *sets* (and set-like collections) return elements in indeterminate order which the language does not guarantee. In particular, I do not think we are promised this holds:
assert tuple(a)==tuple(b) if a==b else False
I can certainly construct a class where that won't hold (i.e. a set-like class that iterates in a non-deterministic order; this need not even be perverse, e.g. if it is 'AsyncResultsSet' that gets its data from I/O source or parallel computations).
I have a feeling I could find plain old Python sets that would fail that, but I'm not sure about it.
Slightly related, here's an invariant that I've wished would hold for a decade, but isn't likely to, even in Python 4:
assert all(not x<y for x,y in zip(a,b)) if a==b else False
But this is just a question of inequality versus identity and that sets and dictionaries are, IMO, too sloppy about that. That is, they behave exactly as documented and as the BDFL has decreed, but I still feel uneasy about:
a = {1, 1+0j, 2} b = {1+0j, 1, 2} a
{(1+0j), 2}
b
{1, 2}
a == b
True
On Tue, Jan 21, 2014 at 1:02 PM, David Mertz mertz@gnosis.cx wrote:
Imagine implementing min and max this way (ignoring key= and the
possibility of a single iterable arg):
lst = sorted((x,y)) assert lst == [min(lst), max(lst)]
will pass for any x and y.
Well, that's not possible, of course, if one is willing to be slightly perverse:
@total_ordering
... class SomewhatOrdered(object): ... def __init__(self, val): ... self.val = val ... def __eq__(self, other): ... return self.val == other.val ... def __lt__(self, other): ... return (self.val, random()) < (other.val, random()) ... def __repr__(self): ... return repr(self.val) ...
x, y, z = map(SomewhatOrdered, (1, 1.0, 2))
But even if you were slightly less perverse than this, *sets* (and set-like collections) return elements in indeterminate order which the language does not guarantee. In particular, I do not think we are promised this holds:
assert tuple(a)==tuple(b) if a==b else False
I can certainly construct a class where that won't hold (i.e. a set-like class that iterates in a non-deterministic order; this need not even be perverse, e.g. if it is 'AsyncResultsSet' that gets its data from I/O source or parallel computations).
I have a feeling I could find plain old Python sets that would fail that, but I'm not sure about it.
-- Keeping medicines from the bloodstreams of the sick; food from the bellies of the hungry; books from the hands of the uneducated; technology from the underdeveloped; and putting advocates of freedom in prisons. Intellectual property is to the 21st century what the slave trade was to the 16th.
On Tue, Jan 21, 2014 at 1:11 PM, David Mertz mertz@gnosis.cx wrote:
Slightly related, here's an invariant that I've wished would hold for a decade, but isn't likely to, even in Python 4:
assert all(not x<y for x,y in zip(a,b)) if a==b else False
Ooops, I meant:
assert all(not x<y for x,y in zip(a,b)) if a==b else True
But the point is that it fails where a==b because equal elements may not be "not unequal."
But this is just a question of inequality versus identity and that sets and
dictionaries are, IMO, too sloppy about that. That is, they behave exactly as documented and as the BDFL has decreed, but I still feel uneasy about:
a = {1, 1+0j, 2} b = {1+0j, 1, 2} a
{(1+0j), 2}
b
{1, 2}
a == b
True
On Tue, Jan 21, 2014 at 1:02 PM, David Mertz mertz@gnosis.cx wrote:
Imagine implementing min and max this way (ignoring key= and the
possibility of a single iterable arg):
lst = sorted((x,y)) assert lst == [min(lst), max(lst)]
will pass for any x and y.
Well, that's not possible, of course, if one is willing to be slightly perverse:
@total_ordering
... class SomewhatOrdered(object): ... def __init__(self, val): ... self.val = val ... def __eq__(self, other): ... return self.val == other.val ... def __lt__(self, other): ... return (self.val, random()) < (other.val, random()) ... def __repr__(self): ... return repr(self.val) ...
x, y, z = map(SomewhatOrdered, (1, 1.0, 2))
But even if you were slightly less perverse than this, *sets* (and set-like collections) return elements in indeterminate order which the language does not guarantee. In particular, I do not think we are promised this holds:
assert tuple(a)==tuple(b) if a==b else False
I can certainly construct a class where that won't hold (i.e. a set-like class that iterates in a non-deterministic order; this need not even be perverse, e.g. if it is 'AsyncResultsSet' that gets its data from I/O source or parallel computations).
I have a feeling I could find plain old Python sets that would fail that, but I'm not sure about it.
-- Keeping medicines from the bloodstreams of the sick; food from the bellies of the hungry; books from the hands of the uneducated; technology from the underdeveloped; and putting advocates of freedom in prisons. Intellectual property is to the 21st century what the slave trade was to the 16th.
-- Keeping medicines from the bloodstreams of the sick; food from the bellies of the hungry; books from the hands of the uneducated; technology from the underdeveloped; and putting advocates of freedom in prisons. Intellectual property is to the 21st century what the slave trade was to the 16th.
On Wed, Jan 22, 2014 at 8:11 AM, David Mertz mertz@gnosis.cx wrote:
But this is just a question of inequality versus identity and that sets and dictionaries are, IMO, too sloppy about that. That is, they behave exactly as documented and as the BDFL has decreed, but I still feel uneasy about:
a = {1, 1+0j, 2} b = {1+0j, 1, 2} a
{(1+0j), 2}
b
{1, 2}
a == b
True
This is because Python's made the decision that an int, a float, and a complex, representing the same number, should compare equal. I personally think they shouldn't (partly because it implies that they're all in some sort of tower, where the higher types can represent the lower types perfectly, and can perfectly represent that there's no further information - true of (float, complex) but not of (int, float), and it leads to problems with large integers), but it's a decision that's been made, and sets/dicts have to follow that. With small numbers, it just means that there's an identity-vs-value distinction (1 == 1.0 == 1+0j, but they're not is-identical), and sets have always had and will always have that issue.
ChrisA
Oh yeah, this has been my bête noire for a long time. I think I first mentioned this in 2003 at:
https://mail.python.org/pipermail/python-list/2003-March/205446.html
Then later in an IBM developerWorks article in 2005:
http://gnosis.cx/publish/programming/charming_python_b25.html
(the URL for the IBM version seems to have gone 404).
I do know why things are as they are and how to work with them... but hey, at least it let me coin the phrase "Incomparable abominations" which I am still rather proud of.
On Tue, Jan 21, 2014 at 1:21 PM, Chris Angelico rosuav@gmail.com wrote:
On Wed, Jan 22, 2014 at 8:11 AM, David Mertz mertz@gnosis.cx wrote:
But this is just a question of inequality versus identity and that sets
and
dictionaries are, IMO, too sloppy about that. That is, they behave
exactly
as documented and as the BDFL has decreed, but I still feel uneasy about:
a = {1, 1+0j, 2} b = {1+0j, 1, 2} a
{(1+0j), 2}
b
{1, 2}
a == b
True
This is because Python's made the decision that an int, a float, and a complex, representing the same number, should compare equal. I personally think they shouldn't (partly because it implies that they're all in some sort of tower, where the higher types can represent the lower types perfectly, and can perfectly represent that there's no further information - true of (float, complex) but not of (int, float), and it leads to problems with large integers), but it's a decision that's been made, and sets/dicts have to follow that. With small numbers, it just means that there's an identity-vs-value distinction (1 == 1.0 == 1+0j, but they're not is-identical), and sets have always had and will always have that issue.
ChrisA _______________________________________________ Python-ideas mailing list Python-ideas@python.org https://mail.python.org/mailman/listinfo/python-ideas Code of Conduct: http://python.org/psf/codeofconduct/
On 1/17/2014 8:45 AM, אלעזר wrote:
Hi all,
Given several objects with the same key, max() returns the first one:
>>> key = lambda x: 0 >>> max(1, 2, key=key) 1
As documented: "If multiple items are maximal, the function returns the first one encountered."
This means it is not stable, at least according to the definition in "Elements of Programming" by Alexander Stepanov and Paul McJones (pg. 52):
"Informally, an algorithm is stable if it respects the original order of equivalent objects.
Min and max are inherently functions of multisets, with order irrelevant but duplicate values allowed. So I do not think 'stability' applies, even if a multiset is presented in some arbitrary order.
So if we think of minimum and maximum as selecting, respectively, the smallest and the second smallest from a list of two arguments,
Why not say largest and second largest, but why either rather than just smallest and largest?
stability requires that when called with equivalent elements, minimum should return the first and maximum should return the second."
The Python dev who wrote the doc disagrees: "This is consistent with other sort-stability preserving tools such as sorted(iterable, key=keyfunc, reverse=True)[0] and heapq.nlargest(1, iterable, key=keyfunc)."
A simpler reason for the current behavior is that it is more efficient to not rebind the internal variable when an equal object is encountered.
In any case, changing the definition and implementation of max will break any code that depends on returning first versus last. We have to have a good reason to do so. If there is no such code (other than the test code that checks the 'first encountered' behavior), then there is no need to change.
On Jan 17, 2014, at 15:34, Terry Reedy tjreedy@udel.edu wrote:
On 1/17/2014 8:45 AM, אלעזר wrote:
Hi all,
Given several objects with the same key, max() returns the first one:
>>> key = lambda x: 0 >>> max(1, 2, key=key) 1
As documented: "If multiple items are maximal, the function returns the first one encountered."
This means it is not stable, at least according to the definition in "Elements of Programming" by Alexander Stepanov and Paul McJones (pg. 52):
"Informally, an algorithm is stable if it respects the original order of equivalent objects.
Min and max are inherently functions of multisets, with order irrelevant but duplicate values allowed.
I'm not sure that's necessarily true. The maximal value of a sequence makes every bit as much sense as the maximal value of a set or multiset, and I think it comes up quite often. For example, if I have a series of experiments at different times, the (time, value) pairs have an obvious meaningful order, and asking for max(experiments, key=itemgetter(1)) is a meaningful thing to do.
But often, even for a sequence, you don't care which max you get.
And often, when you do care, you explicitly want the first. The high score on a video game belongs to the first person who reached that score, not to someone who later tied him.
Sure, _sometimes_ you want the last rather than the first. I've actually written variants of max, nlargest, groupby, etc. that track the last value instead of the first (e.g., to make groupby treat adjacent runs as a group) multiple times. But I wouldn't expect that to be the default behavior of any of those functions.
So, I think the existing design of all these functions is less surprising than the alternative, and adequately documented, and it's easy enough to write the alternative when you need it.
In any case, changing the definition and implementation of max will break any code that depends on returning first versus last.
This is about as perfect a reason as possible. If it ever matters, we can't change it; if it never matters, we have no reason to change it...
On 1/17/2014 7:09 PM, Andrew Barnert wrote:
On Jan 17, 2014, at 15:34, Terry Reedy tjreedy@udel.edu wrote:
Min and max are inherently functions of multisets, with order irrelevant but duplicate values allowed.
I should have said a multiset of comparable objects.
I'm not sure that's necessarily true. The maximal value of a sequence makes every bit as much sense as the maximal value of a set or multiset
A list of comparable objects *is* a multiset of comparable objects. So is any iterable of comparable objects. Which is why 'iterable of comparable objects' is the proper domain for max. Similar comments apply to any commutative associative operator.
For example, if I have a series of experiments at different times, the (time, value) pairs have an obvious meaningful order, and asking for max(experiments, key=itemgetter(1)) is a meaningful thing to do.
max((value,time) for time,value in experiments)
gives the lastest high value. In general
max((val,i) for i,val in enumerate(iterable))
does the same.
If max gave the last maximum, it would be trickier to get the first maximum, just as it is now to get the last minimum.
From: Terry Reedy tjreedy@udel.edu
Sent: Friday, January 17, 2014 4:48 PM
On 1/17/2014 7:09 PM, Andrew Barnert wrote:
On Jan 17, 2014, at 15:34, Terry Reedy tjreedy@udel.edu wrote:
Min and max are inherently functions of multisets, with order irrelevant but duplicate values allowed.
I should have said a multiset of comparable objects.
I'm not sure that's necessarily true. The maximal value of a
sequence
makes every bit as much sense as the maximal value of a set or multiset
A list of comparable objects *is* a multiset of comparable objects.
No, a list is a multiset _with order_. Which is the whole point. You claimed that because it's a multiset, the order doesn't matter. But because the domain of max is a sequence (or, better, as you correctly point out, an iterable), not a multiset, the order does matter. Otherwise this entire question wouldn't arise in the first place.
… asking for max(experiments, key=itemgetter(1)) is a meaningful thing to do.
max((value,time) for time,value in experiments)
gives the lastest high value. In general
max((val,i) for i,val in enumerate(iterable))
does the same.
Sure, given my list of experiments in time order, these give the same result as my expression (except with the members of the tuple reversed, which we can ignore). And?
No matter how you write this, you're not just picking the highest value, you're picking the highest value _with the earliest time_. Which is a meaningful thing to do.
If max gave the last maximum, it would be trickier to get the first maximum, just as it is now to get the last minimum.
Of course. If you read my whole message, that was exactly my point: both are useful. Well, that, and the fact that the current behavior is (a) useful more often than the opposite, and (b): compatible with reams of existing code. And therefore, it would be a bad idea to gratuitously change max to return the last instead of the first. Which I think you agree with completely, so I'm not sure why you're trying to disprove it.
Andrew Barnert writes:
No, a list is a multiset _with order_. Which is the whole point. You claimed that because it's a multiset, the order doesn't matter. But because the domain of max is a sequence (or, better, as you correctly point out, an iterable), not a multiset, the order does matter. Otherwise this entire question wouldn't arise in the first place.
Iterables need not have order in a sense that allows definition of "stability". That's why things like OrderedDict are necessary.
On 1/17/14 8:45 AM, אלעזר wrote:
Hi all,
Given several objects with the same key, max() returns the first one:
key = lambda x: 0 max(1, 2, key=key)
1
This means it is not stable, at least according to the definition in "Elements of Programming" by Alexander Stepanov and Paul McJones (pg. 52):
"Informally, an algorithm is stable if it respects the original order of equivalent objects. So if we think of minimum and maximum as selecting, respectively, the smallest and the second smallest from a list of two arguments, stability requires that when called with equivalent elements, minimum should return the first and maximum should return the second."
I don't understand this logic at all. Stability matters in sorting because sort() takes a sequence and returns a sequence, and for various reasons you might need to sort a list twice, with different criteria. Stability guarantees that the second sort won't discard the work of the first sort.
Is there an example of an actual problem that stability of min and max would make easier to solve?
--Ned.
Ned Batchelder writes:
On 1/17/14 8:45 AM, אלעזר wrote:
"Informally, an algorithm is stable if it respects the original order of equivalent objects. So if we think of minimum and maximum as selecting, respectively, the smallest and the second smallest from a list of two arguments, stability requires that when called with equivalent elements, minimum should return the first and maximum should return the second."
I don't understand this logic at all. Stability matters in sorting because sort() takes a sequence and returns a sequence, and for various reasons you might need to sort a list twice, with different criteria. Stability guarantees that the second sort won't discard the work of the first sort.
Two comments. First, I don't understand at all why earlier members of a sequence may be presumed to be smaller. It could easily go the other way around.
Second, since these operations are *selections* from a collection (which might impose order or not, which might impose uniqueness or not), it's the same problem that Steven d'Aprano faced in defining mode for the statistics PEP: Do you admit failure (here, noncomparability of some of the maximal items), so that a value that is none of the items must be returned? In the case of multiple equivalent values, do you return a representative or the collection?
On Fri, Jan 17, 2014 at 5:35 PM, Ned Batchelder ned@nedbatchelder.com wrote:
Is there an example of an actual problem that stability of min and max would make easier to solve?
In a language like C++, you if min and max had the property specified by the OP, you might do:
x = min(a, b); y = max(a, b);
And then x is the smallest, and y is the other one, and it's simple and easy and less code than an if statement. I suspect this is where the desire comes from.
In Python, of course, you do x, y = sorted([a, b])
-- Devin
On Fri, Jan 17, 2014 at 11:40:49PM -0800, Devin Jeanpierre wrote:
On Fri, Jan 17, 2014 at 5:35 PM, Ned Batchelder ned@nedbatchelder.com wrote:
Is there an example of an actual problem that stability of min and max would make easier to solve?
In a language like C++, you if min and max had the property specified by the OP, you might do:
x = min(a, b); y = max(a, b);
And then x is the smallest, and y is the other one, and it's simple and easy and less code than an if statement.
But that's how max and min work right now, modulo that object identity is not important. If you care about object identity, you're probably doing something underhanded *wink*
Given the case that a and b are *equal* (as measured by the key function, if given) then it shouldn't matter whether you get
smallest = a biggest = b
or
smallest = b biggest = a
or
smallest = biggest = a
or
smallest = biggest = b
These variations only are meaningful if a and b are different types with the same value, or the same type but different identities. Even if these variations are important, I don't think there is any inherent benefit to one over the other.
Personally, I'd either keep the current behaviour, or purely for the symmetry, pick the so-called "stable" behaviour. But I don't see any rational reason for preferring one over the other. Now that Python 3 documents the specific behaviour, it's not worth changing.
I suspect this is where the desire comes from.
In Python, of course, you do x, y = sorted([a, b])
Now the interesting thing here is that sorted *is* stable, so if a and b are equal, sorted([a, b]) is guaranteed to return [a, b]. Which gives the behaviour requested.
On Sat, Jan 18, 2014 at 12:12 AM, Steven D'Aprano steve@pearwood.info wrote:
These variations only are meaningful if a and b are different types with the same value, or the same type but different identities. Even if these variations are important, I don't think there is any inherent benefit to one over the other.
These variations are also important if a and b are just plain different values, same type or no. This can happen if max/min are passed a key function -- equality of a sort key doesn't mean the values are interchangeable for all purposes
if x and y are strings with the same length, min(x, y, key=len) + max(x, y, key=len) is something different in each of those helpfully enumerated cases, and that's with a well behaved type and a superficially OK looking expression.
That said, considering (as Greg points out) that all four variations can be transformed into one another by rearranging the arguments to min and max, I think it's pretty clear that there's nothing strongly favoring any one of them, so on that (and the rest) I agree.
-- Devin
On Sat, Jan 18, 2014, at 5:40, Devin Jeanpierre wrote:
On Sat, Jan 18, 2014 at 12:12 AM, Steven D'Aprano steve@pearwood.info wrote:
These variations only are meaningful if a and b are different types with the same value, or the same type but different identities. Even if these variations are important, I don't think there is any inherent benefit to one over the other.
These variations are also important if a and b are just plain different values, same type or no. This can happen if max/min are passed a key function -- equality of a sort key doesn't mean the values are interchangeable for all purposes
I suspect you're getting hung up on two definitions of "value" - or maybe two definitions of "identity".
Apropos of nothing, both functions will return NaN if it is the first element of the list, but not if it is in any other position. Of course, the behavior of sorting is also unreliable when faced with lists containing NaN.
Devin Jeanpierre wrote:
In a language like C++, you if min and max had the property specified by the OP, you might do:
x = min(a, b); y = max(a, b);
And then x is the smallest, and y is the other one
With Python's current definition of max(), you can get that effect using
x, y = min(a, b), max(b, a)
So max() *does* respect the order of its operands; it's just that the order it respects may not be obvious unless you're Dutch.
From: Devin Jeanpierre jeanpierreda@gmail.com
Sent: Friday, January 17, 2014 11:40 PM
In a language like C++, you if min and max had the property specified by the OP, you might do:
x = min(a, b); y = max(a, b);
And then x is the smallest, and y is the other one, and it's simple and easy and less code than an if statement. I suspect this is where the desire comes from.
In Python, of course, you do x, y = sorted([a, b])
You can write the exact same thing in C++:
template <typename T> whatever(T a, T b) { T x, y; tie(x, y) = tuplize(sorted(make_vector(a, b)));
And then x is the smallest, and y is the other one. Plus, all that static type safety makes it even better than the Python version, right? And extending all those helpers to take a variable number of arguments is a simple matter of template metaprogramming (either with a bit of preprocessor help via boost, or with template parameter packs).
Of course you need to write those three helper function templates. Making them work for two parameters is trivial; making them work for an arbitrary number of parameters is a simple matter of template metaprogramming, which any sixth-year C++ student can write in a matter of weeks; it's just partially specializing on parameter packs, which can be done with simple compile-time recursion.
And the advantage is that all that static typing makes sure that you get errors at compile time instead of run time if you make any mistakes—or often even if you don't.
Andrew Barnert wrote:
And the advantage is that all that static typing makes sure that you get
verrors at compile time instead of run time if you make any mistakes—or often
even if you don't.
Also, if you do it right, the whole computation is performed at compile time, so you don't even have to run the program. This makes it very easy to deploy in a cross-platform manner on minimally-specced hardware.
[אלעזר elazarg@gmail.com]
Given several objects with the same key, max() returns the first one:
>>> key = lambda x: 0 >>> max(1, 2, key=key) 1
This means it is not stable, at least according to the definition in "Elements of Programming" by Alexander Stepanov and Paul McJones (pg. 52):
"Informally, an algorithm is stable if it respects the original order of equivalent objects. So if we think of minimum and maximum as selecting, respectively, the smallest and the second smallest from a list of two arguments, stability requires that when called with equivalent elements, minimum should return the first and maximum should return the second."
A sound argument, provided one accepts the "if". But nobody in the known history of the world *does* think of min and max that way outside this silly quote ;-)
A page later, In a side note, the authors mention that "STL incorrectly requires that `max(a, b)` return `a` when `a` and `b` are equivalent." (As a reminder, Stepanov is the chief designer of the STL).
So, I know this is not a big issue, to say the least, but is there any reason *not* to return the last argument? Are we trying to be compatible with STL somehow?
No. We're just doing what everyone *really* expects min and max to do - including whoever implemented the STL's max().
... Hope I'm not being a crank here...
One removed from being a crank is not itself being a crank :-)