Consider a data set whose elements can be mapped to a particular floating 
point number.  In order to determine the smallest floating point number 
computed from each element from the set, is it a good idea to initialize a 
temporary float as infinite, compare the temporary float with the value 
mapped from each data element and then update the temporary if the mapped 
value is smaller?

More importantly, is there a better way to do this?


Thanks in advance,
Rui Maciel

Rui Maciel  wrote:

> Consider a data set whose elements can be mapped to a particular floating 
> point number.  In order to determine the smallest floating point number 
> computed from each element from the set, is it a good idea to initialize a 
> temporary float as infinite, compare the temporary float with the value 
> mapped from each data element and then update the temporary if the mapped 
> value is smaller?

It's a very common way to do it.

> More importantly, is there a better way to do this?

You can use the first element of your data set to initialize the minimum
and only start the loop from the second element. In some cases that can
be inconvenient to do.

Marc <marc.glisse@gmail.com> wrote:
> Rui Maciel  wrote:

>> Consider a data set whose elements can be mapped to a particular floating 
>> point number.  In order to determine the smallest floating point number 
>> computed from each element from the set, is it a good idea to initialize a 
>> temporary float as infinite, compare the temporary float with the value 
>> mapped from each data element and then update the temporary if the mapped 
>> value is smaller?

(snip)
> You can use the first element of your data set to initialize the minimum
> and only start the loop from the second element. In some cases that can
> be inconvenient to do.

Specifically, it fails in the case that the data set length is zero.

-- glen

On Mar 23, 12:39=A0pm, glen herrmannsfeldt <g...@ugcs.caltech.edu>
wrote:
> > You can use the first element of your data set to initialize the minimu=
m
> > and only start the loop from the second element. In some cases that can
> > be inconvenient to do.
>
> Specifically, it fails in the case that the data set length is zero.

It only fails if you think you know what the right answer for the
minimum value of an empty set is.

On 3/23/2012 8:27 AM, Rui Maciel wrote:
> Consider a data set whose elements can be mapped to a particular floating
> point number.

I assume you mean "whose elements can be mapped to floating point 
numbers (each element to its own particular FP number)".

 >  In order to determine the smallest floating point number
> computed from each element from the set, is it a good idea to initialize a
> temporary float as infinite, compare the temporary float with the value
> mapped from each data element and then update the temporary if the mapped
> value is smaller?
>
> More importantly, is there a better way to do this?

The usual way to find the minimum is to initialize the value from the 
first element, and then start comparing from the second element.  An 
empty set is a special case for which the calculation of the "minimum" 
should just throw an exception.  A set of one element is also a special 
case: there is no need to compare anything.  Two elements *could* be 
made into a special case by use of std::min.

As for infinity (unrelated to searching through a set of numbers), there 
is 'std::numeric_limits<double>::infinity()', which you could call if 
'std::numeric_limits<double>::has_infinity' is 'true'.

V
-- 
I do not respond to top-posted replies, please don't ask

glen herrmannsfeldt wrote:

> Specifically, it fails in the case that the data set length is zero.

Conversely, initializing a FP value as infinity may also bring unwanted 
consequences.  After all, if the data set length is zero then the minimum 
value is set as infinity.


Rui Maciel

Victor Bazarov wrote:

> The usual way to find the minimum is to initialize the value from the
> first element, and then start comparing from the second element.  An
> empty set is a special case for which the calculation of the "minimum"
> should just throw an exception.  A set of one element is also a special
> case: there is no need to compare anything.  Two elements could be
> made into a special case by use of std::min.

I was hoping to use a single loop.  Relying on a separate initialization 
block feels a bit like a crude-ish hack.


> As for infinity (unrelated to searching through a set of numbers), there
> is 'std::numeric_limits<double>::infinity()', which you could call if
> 'std::numeric_limits<double>::has_infinity' is 'true'.

Yes, I was using that, and according to the standard 
std::numeric_limits<T>::has_infinity is true for T = float and double, so no 
test is necessary.  The only problem I have with it is that it doesn't feel 
quite right to handle infinity values like this.  At least I never saw this 
being done anywhere else.


Rui Maciel

On 3/23/2012 11:03 AM, Rui Maciel wrote:
> Victor Bazarov wrote:
>
>> The usual way to find the minimum is to initialize the value from the
>> first element, and then start comparing from the second element.  An
>> empty set is a special case for which the calculation of the "minimum"
>> should just throw an exception.  A set of one element is also a special
>> case: there is no need to compare anything.  Two elements could be
>> made into a special case by use of std::min.
>
> I was hoping to use a single loop.

Are you concerned with less typing, and not with implementing it 
correctly *logically*?  Do you consider "a single loop" better or more 
efficient in some way?

 >  Relying on a separate initialization
> block feels a bit like a crude-ish hack.

"Crude-ish"?  Really?  <shrug> Using an infinity value in that manner is 
crudish, IMNSHO.  It suggests that (a) infinity is not a valid value for 
any set element to be associated with (which might be true in your 
model, but doesn't necessarily sound right in all cases), and (b) that 
the maximum value from the elements of an empty set is infinity, which 
is a number (if you divide by it, you get 0).  I'd probably use NaN for 
that, although by definition of "seeking a maximum associated floating 
point number" should *not* be allowed for an empty set, such search 
shouldn't return a value.

>> As for infinity (unrelated to searching through a set of numbers), there
>> is 'std::numeric_limits<double>::infinity()', which you could call if
>> 'std::numeric_limits<double>::has_infinity' is 'true'.
>
> Yes, I was using that, and according to the standard
> std::numeric_limits<T>::has_infinity is true for T = float and double, so no
> test is necessary.  The only problem I have with it is that it doesn't feel
> quite right to handle infinity values like this.  At least I never saw this
> being done anywhere else.

<another shrug> I have.  But it's still not right.  You can use any 
other designated value that can never be found in your set.  And if you 
don't have any identifiable value to use, don't.  Use *logic*. 
Essentially you're trying to have a mapping of yourtype values to 
double/float values without

     std::map<double, yourtype const*> yourmap;

..  And you're trying to figure out a hack to get 
(*yourmap.rbegin()).first without checking whether the 'yourmap' is 
empty or not.  <third shrug>

V
-- 
I do not respond to top-posted replies, please don't ask

Victor Bazarov wrote:

> On 3/23/2012 11:03 AM, Rui Maciel wrote:
>> Victor Bazarov wrote:
>>
>>> The usual way to find the minimum is to initialize the value from the
>>> first element, and then start comparing from the second element.  An
>>> empty set is a special case for which the calculation of the "minimum"
>>> should just throw an exception.  A set of one element is also a special
>>> case: there is no need to compare anything.  Two elements could be
>>> made into a special case by use of std::min.
>>
>> I was hoping to use a single loop.
> 
> Are you concerned with less typing, and not with implementing it
> correctly *logically*?  Do you consider "a single loop" better or more
> efficient in some way?

You either failed to understand what I wrote or you are intentionally trying 
to misrepresenting what I said.  No one claimed that it is better to use 
code which is logically incorrect if it provides a way to save on typing.  I 
don't know where you came up with that nonsense.


>  >  Relying on a separate initialization
>> block feels a bit like a crude-ish hack.
> 
> "Crude-ish"?  Really? 

Really.


> <shrug> Using an infinity value in that manner is
> crudish, IMNSHO.  

What happened to logical correctness?  And do you also believe that, if the 
objective was to get the largest non-negative number, initializing it to 
zero or even any negative number would also be crudish?


> It suggests that (a) infinity is not a valid value for
> any set element to be associated with (which might be true in your
> model, but doesn't necessarily sound right in all cases), 

Zero is also not valid in a considerable number of cases, and yet variables 
are still set by default as zero.


> and (b) that
> the maximum value from the elements of an empty set is infinity, which
> is a number (if you divide by it, you get 0).  

As a side note, and nit-picking a bit, this isn't true.  Infinity isn't a 
number, and k/infinity is meaningless.  The k/infinity = 0 is only valid 
because it was a specific indeterminate form which is often defined as 
lim{x->infinity} k/x.  

Similarly, division by zero has also been defined as k/0 = infinity, but 
this doesn't mean it's a good idea to hold this as true.  For a start, this 
would mean that infinity*0 = k.


> I'd probably use NaN for
> that, although by definition of "seeking a maximum associated floating
> point number" should *not* be allowed for an empty set, such search
> shouldn't return a value.
> 
>>> As for infinity (unrelated to searching through a set of numbers), there
>>> is 'std::numeric_limits<double>::infinity()', which you could call if
>>> 'std::numeric_limits<double>::has_infinity' is 'true'.
>>
>> Yes, I was using that, and according to the standard
>> std::numeric_limits<T>::has_infinity is true for T = float and double, so
>> no
>> test is necessary.  The only problem I have with it is that it doesn't
>> feel
>> quite right to handle infinity values like this.  At least I never saw
>> this being done anywhere else.
> 
> <another shrug> I have.  But it's still not right.  You can use any
> other designated value that can never be found in your set.  And if you
> don't have any identifiable value to use, don't.  Use *logic*.

Why is it "not right"?  Is there actually a valid technical reason behind 
your assertion?


> Essentially you're trying to have a mapping of yourtype values to
> double/float values without
> 
>      std::map<double, yourtype const*> yourmap;
> 
> .  And you're trying to figure out a hack to get
> (*yourmap.rbegin()).first without checking whether the 'yourmap' is
> empty or not.  <third shrug>

Again, you either failed to understand what I wrote or you are intentionally 
trying to misrepresent what I said.  No one claimed that the set in question 
could be empty, and somehow you felt the need to attribute that claim, which 
you invented, to someone else.

So, to avoid any more misconceptions or any attempts to misrepresent 
anything, here is a clear description of this case.

- there is a non-empty set of data.
- there is a set of operators which map each element of that set to a 
floating point number.
- the objective is to evaluate which is the minimum value of the codomain of 
a particular operator.

I suggested the following approach:

<pseudo-ish code>

float minimum = std::numeric_limits<float>::infinity();
for(auto element: element_list)
{
    if( operator(element) < minimum)
        minimum = operator(element);
}

</pseudo-ish code>

Then, I asked if it was a good idea to do this.  In other words, if there 
was any reason that would made it a bad idea.  Until now, no reason has been 
given.

I also asked if there was a better way to get the minimum value.  

Simple as that.


Rui Maciel

Am 23.03.12 20:01, schrieb Rui Maciel:
> I suggested the following approach:
>
> <pseudo-ish code>
>
> float minimum = std::numeric_limits<float>::infinity();
> for(auto element: element_list)
> {
>      if( operator(element)<  minimum)
>          minimum = operator(element);
> }
>
> </pseudo-ish code>
>
> Then, I asked if it was a good idea to do this.  In other words, if there
> was any reason that would made it a bad idea.  Until now, no reason has been
> given.
>
> I also asked if there was a better way to get the minimum value.

I can't think of a reason why this could fail. The only concerns are 
non-finite math of this operator() or lack of compiler support. The 
first case is important if your operator() might be returning NaN. In 
that case, as NaN always compares false, your minimum would either 
ignore that NaN (in case there is at least one finite element) _or_ 
return -Inf (in case there are only NaNs), which would certainly be 
wrong. You could invert the condition to

	(! (minimum >= operator(element))
to recieve NaN in this case as the answer or add another clause to test 
for NaN.
The second case, lack of support for non-finite math, is relevant only 
if the code happens to be compiled with non-standard settings as a 
performance improvement.
BTW, you are calling operator() twice for each element. which is 
wasteful if operator() is a potentially complex operation:

float temp=operator(element)
if (temp< minimum || temp!=temp) minimum=temp;


	Christian

Rui Maciel <rui.maciel@gmail.com> wrote:

(snip, I wrote)
>> Specifically, it fails in the case that the data set length is zero.

> Conversely, initializing a FP value as infinity may also bring 
> unwanted consequences.  After all, if the data set length is 
> zero then the minimum value is set as infinity.

The Fortran MINVAL intrinsic function returns the minimum value of
the elements of an array. As Fortran (now) allows arrays dimensioned
zero, it has to allow for that case. 

For arrays with no elements, it returns the largest representable
value, which I believe even for IEEE implementations is not
the IEEE Infinity value. Most likely, the value returned by
the HUGE intrinsic function.

-- glen

On 3/23/2012 3:01 PM, Rui Maciel wrote:
> [snip irate response to something for some reason apparently taken personally]
>
> Again, you either failed to understand what I wrote or you are intentionally
> trying to misrepresent what I said [..]

Failed?  Maybe.  Intentionally?  You know what, if you're having a bad 
day, why are you trying to blame me for that?  Snap at somebody who 
actually gives a damn.

> So, to avoid any more misconceptions or any attempts to misrepresent
> anything, here is a clear description of this case.
>
> - there is a non-empty set of data.
> - there is a set of operators which map each element of that set to a
> floating point number.
> - the objective is to evaluate which is the minimum value of the codomain of
> a particular operator.
>
> I suggested the following approach:
>
> <pseudo-ish code>
>
> float minimum = std::numeric_limits<float>::infinity();
> for(auto element: element_list)
> {
>      if( operator(element)<  minimum)
>          minimum = operator(element);
> }
>
> </pseudo-ish code>
>
> Then, I asked if it was a good idea to do this.  In other words, if there
> was any reason that would made it a bad idea.  Until now, no reason has been
> given.

Why would a solution that works be a bad idea?  Since you didn't state 
the complexity of your 'operator', we could presume that it's expensive. 
  Then the only concern is efficiency.

The pseudo code has two inefficiencies.  First, it initializes 'minimum' 
to some value, and immediately overrides it with the 
'operator(element#0)'.  Second inefficiency is that it evaluates the 
'operator' for each element twice.

Simple as that.

> I also asked if there was a better way to get the minimum value.

Don't evaluate twice and initialize from the first element, and skip the 
first element while doing the loop.

> Simple as that.

If you need algorithm advice, consider asking in 'comp.programming'.

V
-- 
I do not respond to top-posted replies, please don't ask

Victor Bazarov <v.bazarov@comcast.invalid> writes:
>>  Relying on a separate initialization
>> block feels a bit like a crude-ish hack.
>
> "Crude-ish"?  Really?  <shrug> Using an infinity value in that manner
> is crudish, IMNSHO.  It suggests that (a) infinity is not a valid
> value for any set element to be associated with (which might be true
> in your model, but doesn't necessarily sound right in all cases),

Wait, what?

It still works fine if some set element has a value of infinity...
(if that's the _only_ set element, then infinity is indeed the minimum;
if there is some smaller element, then the smaller element will win)

-Miles

-- 
Brain, n. An apparatus with which we think we think.

On 3/23/2012 8:46 PM, Miles Bader wrote:
> Victor Bazarov<v.bazarov@comcast.invalid>  writes:
>>>   Relying on a separate initialization
>>> block feels a bit like a crude-ish hack.
>>
>> "Crude-ish"?  Really?<shrug>  Using an infinity value in that manner
>> is crudish, IMNSHO.  It suggests that (a) infinity is not a valid
>> value for any set element to be associated with (which might be true
>> in your model, but doesn't necessarily sound right in all cases),
>
> Wait, what?
>
> It still works fine if some set element has a value of infinity...
> (if that's the _only_ set element, then infinity is indeed the minimum;
> if there is some smaller element, then the smaller element will win)

Yes, but if infinity is allowed to be associated, and there are no 
elements in the set?

V
-- 
I do not respond to top-posted replies, please don't ask

Victor Bazarov wrote:

> Yes, but if infinity is allowed to be associated, and there are no
> elements in the set?

<pseudo-ish code>

float minimum = std::numeric_limits<float>::infinity();
for(auto element: element_list)
{
    if( operator(element) < minimum)
        minimum = operator(element);
}

if(minimum == std::numeric_limits<float>::infinity() )
{
    throw something;
}

</pseudo-ish code>


Rui Maciel

Victor Bazarov wrote:

> Failed?  Maybe.  Intentionally?  You know what, if you're having a bad
> day, why are you trying to blame me for that?  Snap at somebody who
> actually gives a damn.

If you express disdain towards others you shouldn't be surprized that people 
don't react kindly to that.


<snip/>
>> Then, I asked if it was a good idea to do this.  In other words, if there
>> was any reason that would made it a bad idea.  Until now, no reason has
>> been given.
> 
> Why would a solution that works be a bad idea?  Since you didn't state
> the complexity of your 'operator', we could presume that it's expensive.
>   Then the only concern is efficiency.

The complexity of any hypothetical operator is irrelevant to this 
discussion.  If you read the thread, or even just the subject, you will 
realize that the issue under discussion refers to the use of infinite values 
in a particular floating point operation. 


> The pseudo code has two inefficiencies.  First, it initializes 'minimum'
> to some value, and immediately overrides it with the
> 'operator(element#0)'.  

I believe we can agree that discussing the perceived efficiency of a pseudo-
code snippet is silly, particularly when the perceived inefficiency boils 
down to a single floating point assignment executed only once at the start 
of a iteration through an undetermined number of elements in a set.


> Second inefficiency is that it evaluates the
> 'operator' for each element twice.

I was aware of that when I wrote the pseudo-code, but, again, it is pseudo-
code and nothing more than that, and has nothing to do with the topic of 
this discussion, which is the reliance of infinite values in floating point 
operations.


> Simple as that.

Too bad it doesn't have anything to do with the topic being discussed.


Rui Maciel

On 03/23/12 15:32, Victor Bazarov wrote:

Leaving aside any matter about correctness, logic, and so on in case the 
set has zero elements...



> As for infinity (unrelated to searching through a set of numbers), there
> is 'std::numeric_limits<double>::infinity()', which you could call if
> 'std::numeric_limits<double>::has_infinity' is 'true'.

I usually use std::numeric_limits<double>::max() in such cases.
Anything wrong with this?
Any unobvious disadvantage or potential trouble?

  bye & Thanks
	av.

On 23/03/2012 12:27, Rui Maciel wrote:
> Consider a data set whose elements can be mapped to a particular floating
> point number.  In order to determine the smallest floating point number
> computed from each element from the set, is it a good idea to initialize a
> temporary float as infinite, compare the temporary float with the value
> mapped from each data element and then update the temporary if the mapped
> value is smaller?
>
> More importantly, is there a better way to do this?

Yes there is a better way, use: std::min_element

/Leigh

Victor Bazarov <v.bazarov@comcast.invalid> writes:
>> It still works fine if some set element has a value of infinity...
>> (if that's the _only_ set element, then infinity is indeed the minimum;
>> if there is some smaller element, then the smaller element will win)
>
> Yes, but if infinity is allowed to be associated, and there are no
> elements in the set?

With some algorithms (calling the min function), it doesn't matter,
and it's fine to just return infinity for either case.

If it's desirable to distinguish the "empty container" case, then just
test for it first -- it's usually cheap and straight-forward to test a
container for emptiness -- and handle empty containers that way.
Note you'd have to do the _same thing_ for the method you advocated.

-miles

-- 
"Yorton, Wressle, and Gospel Oak, the richness of your heritage is ended.
We shall not stop at you again; for Dr Beeching stops at nothing."

On 3/24/2012 8:05 AM, Andrea Venturoli wrote:
> On 03/23/12 15:32, Victor Bazarov wrote:
>
> Leaving aside any matter about correctness, logic, and so on in case the
> set has zero elements...
>
>
>
>> As for infinity (unrelated to searching through a set of numbers), there
>> is 'std::numeric_limits<double>::infinity()', which you could call if
>> 'std::numeric_limits<double>::has_infinity' is 'true'.
>
> I usually use std::numeric_limits<double>::max() in such cases.
> Anything wrong with this?
> Any unobvious disadvantage or potential trouble?

If you aren't going to use that value in such a way that can cause 
overflow or underflow after you've obtained it, there is no harm.  Any 
designated value, be it the infinity or the max, should be OK as long as 
you watch what you do with it afterwards, IME.

V
-- 
I do not respond to top-posted replies, please don't ask

Leigh Johnston <leigh@i42.co.uk> writes:

> Yes there is a better way, use: std::min_element

.... but don't forget to handle the empty set case.

Leigh Johnston wrote:

> Yes there is a better way, use: std::min_element

Considering that the values being compared aren't stored and, instead, are 
calculated by an operator which is called for this specific purpose, doesn't 
std::min_element require more than n calls to that operator, n being 
container::size() ?

Another inconvenience is that std::min_element only returns an iterator 
pointing to the element which relates to the smallest value.  If the 
objective is to determine that particular value then using std::min_element 
requires an extra call to that operator.

Meanwhile, the method which has been presented and relies on 
std::numeric_limits<float>::infinity() only requires n calls to the 
operator, and in the end the smallest value is already provided.


Rui Maciel

On 25/03/2012 12:38, Rui Maciel wrote:
> Leigh Johnston wrote:
>
>> Yes there is a better way, use: std::min_element
>
> Considering that the values being compared aren't stored and, instead, are
> calculated by an operator which is called for this specific purpose, doesn't
> std::min_element require more than n calls to that operator, n being
> container::size() ?

No.  Exactly n calls will be made to the operator (predicate).

>
> Another inconvenience is that std::min_element only returns an iterator
> pointing to the element which relates to the smallest value.  If the
> objective is to determine that particular value then using std::min_element
> requires an extra call to that operator.

Hardly a major inconvenience.  An added benefit is the returned iterator 
will point to end() if the container is empty: your method cannot 
distinguish between an empty container and a container that only 
contains elements that evaluate to std::numeric_limits<float>::infinity().

>
> Meanwhile, the method which has been presented and relies on
> std::numeric_limits<float>::infinity() only requires n calls to the
> operator, and in the end the smallest value is already provided.

std::min_element allows you to obtain this information without 
reinventing the wheel.  Bottom line: avoid explicit loops where 
possible; use standard algorithms where possible.

/Leigh

On 25/03/2012 13:36, Leigh Johnston wrote:
> On 25/03/2012 12:38, Rui Maciel wrote:
>> Leigh Johnston wrote:
>>
>>> Yes there is a better way, use: std::min_element
>>
>> Considering that the values being compared aren't stored and, instead,
>> are
>> calculated by an operator which is called for this specific purpose,
>> doesn't
>> std::min_element require more than n calls to that operator, n being
>> container::size() ?
>
> No. Exactly n calls will be made to the operator (predicate).

Sorry slight error there: max((last - first) - 1, 0) calls will be made 
so for a non-empty container that will be n-1 calls.

/Leigh

On 25/03/2012 14:00, Leigh Johnston wrote:
> On 25/03/2012 13:36, Leigh Johnston wrote:
>> On 25/03/2012 12:38, Rui Maciel wrote:
>>> Leigh Johnston wrote:
>>>
>>>> Yes there is a better way, use: std::min_element
>>>
>>> Considering that the values being compared aren't stored and, instead,
>>> are
>>> calculated by an operator which is called for this specific purpose,
>>> doesn't
>>> std::min_element require more than n calls to that operator, n being
>>> container::size() ?
>>
>> No. Exactly n calls will be made to the operator (predicate).
>
> Sorry slight error there: max((last - first) - 1, 0) calls will be made
> so for a non-empty container that will be n-1 calls.

Sorry you are correct; whilst there will be n-1 calls of the predicate 
that will mean more than n calls of your operator inside the predicate. 
  This is only a problem if your operator is an expensive operation; is 
your operator an expensive operation?

/Leigh

Leigh Johnston wrote:

> Sorry you are correct; whilst there will be n-1 calls of the predicate
> that will mean more than n calls of your operator inside the predicate.
> This is only a problem if your operator is an expensive operation; is
> your operator an expensive operation?

At this moment I can't say, but I suspect that it will be expensive.  The 
operator which maps each element to a float is defined through a strategy 
pattern, and currently I don't have any way to know which strategies will be 
implemented.


Rui Maciel