Min and Max

[Rici Lake-2]

On 18-Aug-05, at 4:06 AM, Philippe Lhoste wrote:

Rici Lake wrote:

For what it's worth, I still think min and max should be primitives rather than part of the math package. They are perfectly well defined for anything for which < or <= is a total-ordering, or something close to a total ordering. [2]

I don't disagree with you, but what are the use-cases? I mean, are they that much used that they need a special treatment over other math/string functions?

I don't use min and max much in my programs, that's why I ask. Of course, I don't much pow/^ either... But perhaps I am either missing opportunities, or I am just not in the "right" programming domain.

I'm not making a serious pitch for min and max operators here; just trying to illustrate a use case.

The recent "Lua uses" posting about DogLua lead me back to Øyvind Kolås' interesting Lua-based Gimp plug-in, gluas <http://pippin.gimp.org/image_processing/index.html>.

gluas allows you to write Gimp image filters in Lua; a number of examples can be found in the text. Many of them are crying out for min and max operators; here is just one example (taken from Chapter 7, <http://pippin.gimp.org/image_processing/chapter- automaticadjustments.html>). This function returns the minimum and maximum grayscale value in an image (but you'll find many more instances of this idiom in the examples):

function get_min_max()
    min, max = 1000, -1000
    for y=0, height-1 do
      for x=0, width-1 do
        value = get_value(x,y)
        if value<min then
          min = value
        end
        if value>max then
          max = value
        end
      end
    end
    return min,max
end

The author uses an if statement to do the min/max; the style is consistent in all of his scripts, presumably because:

  min, max = math.min(min, value), math.max(max, value)

would be even slower.

I personally find the following more attractive:

function get_min_max()
  local rmin, rmax = 1000, -1000
  for y = 0, height - 1 do
    for x = 0, width - 1 do
      local value = get_value(x, y)
      rmin = rmin min value
      rmax = rmax max value
    end
  end
  return rmin, rmax
end

It's not going to be lot faster to execute (well, it will but only because I made `value' a

local) but it seems clearer to me. Maybe that's just me.

However, this doesn't capture another very common idiom: if we actually wanted to know which <x,y> co-ordinates were associated with the min and the max, we'd still need the `if' statement. Probably more than half of Dr. Kolås's examples are of this form, rather than simple min and max computations.

By the way, the starting values 1000, -1000 are fine in this example because get_value returns a number between 0.0 and 1.0. But I would actually opt for a definition of `min' and `max' where:

   nil min x ==> x
   nil max x ==> x

for any x. This makes reductions a little easier to write, and could easily be achieved in the 5.1 framework, I think, by providing __min and __max metamethods for `nil'.

[Roberto Ierusalimschy]

>      rmin = rmin min value
>      rmax = rmax max value

If a<=b returned a instead of true, we could write "a<=b or b" for min
and "a>=b or b" for max :)


> This makes reductions a little easier to write,

Lua 5.1 offers the value math.huge, which you can use as the neutral
element for min.

-- Roberto

[Rici Lake-2]

On 25-Aug-05, at 11:39 AM, Roberto Ierusalimschy wrote:

     rmin = rmin min value
     rmax = rmax max value

If a<=b returned a instead of true, we could write "a<=b or b" for min
and "a>=b or b" for max :)

True enough. As long as no-one thought of defining __lt for booleans such that false < true :)

This makes reductions a little easier to write,

Lua 5.1 offers the value math.huge, which you can use as the neutral
element for min.

Yes, but that only works for numbers, not (for example) for strings.

[Adrian Sietsma]

Roberto Ierusalimschy wrote:

If a<=b returned a instead of true, we could write "a<=b or b" for min
and "a>=b or b" for max :)

what about
a = (a<=b and a) or b

Adrian

[Rici Lake-2]

On 27-Aug-05, at 10:05 AM, Adrian Sietsma wrote:

what about
a = (a<=b and a) or b

The goal of having a `min' operator would be to make the program *more* readable :)

[Adrian Sietsma]

Rici Lake wrote:

On 27-Aug-05, at 10:05 AM, Adrian Sietsma wrote:

what about
a = (a<=b and a) or b

The goal of having a `min' operator would be to make the program *more* readable :)

i agree, but i still like Roberto's option of comparison operators returning the mathing object, instead of "true" - that matches and/or behaviour.

min = a<=b or b
min = b<a or a  -- also min
max = a > b or b

min3 = (a < b and a < c) or b < c or c
max3 = (a > b and a > c) or b > c or c

you can also tune the comparison for equality ordering.

some timing, for fun

> mymin=function(a,b) return ((a <= b) and a) or b end

> t0 = function(n) local t = os.timems() for i =1,2*n do local a = ((i<=n) and i) or n end return( os.timems() - t) end > t1 = function() local t = os.timems() for i =1,1e7 do mymin(i,5e6) end return( os.timems() - t) end > t2 = function(n) local t = os.timems() local min=mymin for i =1,n*2 do min(i,n) end return( os.timems() - t) end > t1 = function(n) local t = os.timems() for i =1,n*2 do mymin(i,n) end return( os.timems() - t) end > t3 = function(n) local t = os.timems() for i =1,2*n do local a = math.min(i,n) end return( os.timems() - t) end > t4 = function(n) local t = os.timems() local min=math.min for i =1,n*2 do min(i,n) end return( os.timems() - t) end

> print(t0(1e6),t1(1e6),t2(1e6),t3(1e6),t4(1e6))
150.21606445313 440.63403320313 420.60498046875 550.7919921875  410.59008789063
>

so - inline logic is fastest (of course); local copy of math.min next, then local min func, then math.min.

Adrian

[Rici Lake-2]

On 27-Aug-05, at 11:15 AM, Adrian Sietsma wrote:

i agree, but i still like Roberto's option of comparison operators returning the mathing object, instead of "true" - that matches and/or behaviour.

I think it has its charm; I was playing with that a while ago when I was first thinking about max and min operators.

The fact that you can't define __lt on booleans is a minor flaw, but it leads to the issue that you cannot define == to work the same way. That is, a == b cannot return a if the objects are equal, because that would then mean that

  nil == nil

and

  false == false

were nil and false, respectively.

So == cannot be consistent with < and <=, which is a slightly more serious blemish.

The most serious issue, which also plagues C programs and is the reason that gcc chose to implement min and max operators (<? and >? if I recall correctly) is that you cannot open code min and max without evaluating the arguments twice. So there is nothing wrong with

  a < b and a or b

But something desperately wrong with

  f(a) < f(b) and f(a) or f(b)

This would not be a problem with

  f(a) min f(b)

and is probably the single best argument for having the operators.

Finally, I prefer min and max because there are types where min and max cannot be defined in terms of < or <=. In those cases, I would prefer to have an operator backed by a metamethod; failing that, I'm happy to use a function backed by a metamethod, which is what I actually do in practice, regardless of speed issues, because I like the self-documentation.

[Note]

Depending on what you think numeric min and max should return if one of the arguments is a NaN, numeric min and max can also be difficult to properly implement in terms of <. However, I was thinking more of partial order relationships like subset. My preference is that min of two sets is their intersection and max is their union; that cannot be defined in terms of a subset predicate. If you prefer the definition that min/max of two sets returns nil if the sets are not comparable then you can, but it looks different and arguably suffers from an efficiency problem:

  a <= b and a or b <= a and b

I'm going to shut up about this issue now. :)