Find the lowest value in an array

I have an array that holds 4 values ( they contain random numbers). I would
like to find the lowest value (if there is a tie i would like to find one of
the tie.) then remove that value. I am new to Programming and C#.

Hello,
>
I have an array that holds 4 values ( they contain random numbers). I would
like to find the lowest value (if there is a tie i would like to find one of
the tie.) then remove that value. I am new to Programming and C#.
Thanks for any help you can provide
>
Thomas

When you say "...then remove that value.", do you mean that after the
process, you should have a low value, and an array with only three
elements?
Lilith and Arne answered the sorting issue.

ModelBuilder wrote:>
Yeah, but sorting is destructive and a very inefficient way to find the
lowest of four numbers. Since the 'remove' requirement was well specified,
I'm going to ignore it here. To find the lowest value, I definitely
wouldn't use a Sort or Math.Min or Max.

Hilton <nospam@nospam.comwrote:>
Why wouldn't you use Math.Min but keep the same overall structure? I
can't see how your code is more readable, and I highly doubt that this
is a likely bottleneck.
>
>
Alternatively, I'd possibly just write a separate method:
>
int FindMin(params int[] values)
{
int min = int.MaxValue;
foreach (int value in values)
{
if (value < min)
{
min = value;
}
}
return min;
}
>
That individual method is pretty readable, and the calling code is
going to be very easy to understand.
>
Fortunately with .NET 3.5 it's all built in:
>
int min = values.Min();
>
(And that works with any IEnumerable<int>.)
>
--
Jon Skeet - <skeet@pobox.com>
http://www.pobox.com/~skeet Blog: http://www.msmvps.com/jon.skeet
If replying to the group, please do not mail me too

Hello,
>
I have an array that holds 4 values ( they contain random numbers). I would
like to find the lowest value (if there is a tie i would like to find one of
the tie.) then remove that value. I am new to Programming and C#.
Thanks for any help you can provide
>
Thomas

Why wouldn't you use Math.Min but keep the same overall structure? I
can't see how your code is more readable, and I highly doubt that this
is a likely bottleneck.

Jon,
>>
I never claimed it was more readable, I claimed "to maximize efficiency".
Your method and my method are the same, except mine has been (kinda) "loop
unrolled" again "to maximize efficiency". I certainly wouldn't use my
method for larger arrays.
>
FWIW: Unrolling the loop as I did was 20% faster. As Jon pointed out, I
would only use my method if the method was in a CPU bottleneck piece of
code.
>
Hilton
>
>
>

ThomasT22 wrote:>
Loop through the values to find the smallest:
>
int low = int.MaxValue;
int index = -1;
for (int i = 0; i < items.Length; i++) {
if (items[i] < low) {
low = items[i];
index = i;
}
}
>
Now you have the lowest value in "low" and the index of the item
containing the value in "index".
>
You can't remove an item from an array, so you have to create a new array:
>
int[] n = new int[items.Length - 1];
int pos = 0;
for (int i = 0; i < items.Length; i++) {
if (i != index) {
n[pos] = items[i];
pos++;
}
}
>
Now you have a new array "n" with one less value than "items". You can
throw away the old array and use the new one instead:
>
items = n;
>
--
Göran Andersson
_____
http://www.guffa.com
>

>
I never claimed it was more readable, I claimed "to maximize efficiency".

Hilton <nospam@nospam.comwrote:>
But that was never requested.
>
You said:
>
<quote>
To find the lowest value, I definitely wouldn't use a Sort or Math.Min
or Max.
</quote>
>
If Sort/Min/Max are more readable and performance isn't an issue (which
for most code it isn't), why use a less readable form?
>
--
Jon Skeet - <skeet@pobox.com>
http://www.pobox.com/~skeet Blog: http://www.msmvps.com/jon.skeet
If replying to the group, please do not mail me too

I'm not going to get into a p-match here, but I clearly stated the solution
I was giving was for maximum efficiency, and secondly, I still wouldn't use
Sort or Math.Min - neither did you.

If I *did* write a version which just compared a few versions, I
*would* use Math.Min because it's more readable than your alternative.

So I did some testing:
Hilton's 'unreadable' version took: 23 seconds
Jon's looping "if" version took: 30 seconds
The Math.Min version took: 37 seconds

Hilton <nospam@nospam.comwrote:>
Just did some myself for the sake of interest. I tested four different
sets of values, and here were the results for a US billion (1 thousand
million) iterations:
>
{1, 2, 3, 4}:
Hilton: 9s
Jon: 12s
Math.Min: 13s
>
{4, 3, 2, 1}:
Hilton: 10s
Jon: 12s
Math.Min: 12s
>
{4, 1, 3, 2}:
Hilton: 10s
Jon: 12s
Math.Min: 11s
>
Much closer than your measurements give... I wonder if this is a .NET
framework version problem? My results are from .NET 2.0.
>
>
The important thing is just how fast this is for *any* algorithm. It
takes about 10 nanoseconds to do this computation, even on my laptop
which is a couple of years old. You'd have to be doing a *hell* of a
lot of these for it to be the performance bottleneck.
>
>
My code is below, if anyone else wants to try it...
>
using System;
using System.Diagnostics;
>
public class Test
{
const int Iterations = 1000000000;
static void Main()
{
int[] vals = new int[] {1, 2, 3, 4};
>
Stopwatch watch = Stopwatch.StartNew();
for (int i=0; i < Iterations; i++)
{
FindMinHilton(vals);
}
Console.WriteLine (watch.ElapsedMilliseconds);
>
watch = Stopwatch.StartNew();
for (int i=0; i < Iterations; i++)
{
FindMinJon(vals);
}
Console.WriteLine (watch.ElapsedMilliseconds);
>
watch = Stopwatch.StartNew();
for (int i=0; i < Iterations; i++)
{
FindMinMathMin(vals);
}
Console.WriteLine (watch.ElapsedMilliseconds);
}
>
static int FindMinHilton(int[] x)
{
int a = x[0];
int b = x[1];
int c = x[2];
int d = x[3];
>
// Effectively "a = Math.Min (a, b)"
if (b < a)
{
a = b;
}
>
// Effectively "a = Math.Min (c, d)"
if (d < c)
{
c = d;
}
>
// Effectively "Math.Min (a,bmc)" which in summary
// is really "Math.Min (a,b, c, d)"
return (a < c) ? a : c;
}
>
static int FindMinJon(params int[] values)
{
int min = int.MaxValue;
foreach (int value in values)
{
if (value < min)
{
min = value;
}
}
return min;
}
>
static int FindMinMathMin(int[] a)
{
return Math.Min(Math.Min(a[0], a[1]), Math.Min(a[2], a[3]));
}
}
>
--
Jon Skeet - <skeet@pobox.com>
http://www.pobox.com/~skeet Blog: http://www.msmvps.com/jon.skeet
If replying to the group, please do not mail me too

It would be interesting seeing your numbers using 2.5 billion - that would
give times close to mine, For example, in your first test, the 12s and 13s
might really be closer to 11.5s and 13.49s (assuming it does rounding)

and there's roughly the 20% (i.e. rounding grossly affecting the outcome). BTW:
I'm running 'release', CF 2.0. My array was {1, 3, 2, 4}.
>
Now you've got me wondering how these run times would vary if run on the CF,
especially the Math.Min one.

Hilton <nospam@nospam.comwrote:>
I was doing the rounding myself - I remember that your version was
actually about 8900ms, but I can't remember the other ones.
>
Here are the results for 2 billion, in ms - 2.5 billion takes us over
int.MaxValue, and changing the loop variables to be longs changes the
results significantly.
>
Hilton: 18675
Jon: 25219
Math.Min: 26844
>
A larger proportional difference than before, but still less than your
results.
>>
Yes, that would be interesting. I'm still surprised that Math.Min
doesn't end up being the same speed as your code though - I'd expect
inlining to take care of it all.
>

>
Currently on v2, defining this:
return Math.Min( Math.Min(a[0], a[1]), Math.Min(a[2], a[3]));
in general stops the JIT from optimizing the arguments, make it look like:
int x = Math.Min(a[0], a[1]);
int y = Math.Min(a[2], a[3]);
return Math.Min(x, y);

>
and watch the results.
Also, note that running these tests in sequence produce different results
from running them separately (one per process).
>
Willy.
>
>

>
(scratches head remembering hearing claims that the .NET JIT was as good
as the C++ optimizing compiler)
>

>
For what it's worth, I never made such claim, did I?

As you know, the JIT is time constrained while the C++ back-end optimizer
is not (or say less). The result is that in some cases the result is less
optimal. Maybe one day when MS stops adding features and starts to
prioritize on JIT quality we may see better code generated for these
corner cases as well.
>
Willy.
>

>
Several C# MVPs were doing so but I don't think you were among them.

Ben Voigt [C++ MVP] <rbv@nospam.nospamwrote:>
I can't remember any such claims. There have been *other* claims, such
as the JIT being "good enough" in most cases, and supporting the notion
that improving the optimisation in the JIT is more important than
improving it in the C# compiler (which I'd agree with for most
situations but not all).
>
Certainly if I ever made such a statement I retract it wholeheartedly -
as Willy said, the JIT just doesn't have enough time to perform as many
optimisations. (That's where Sun's Hotspot technology wins out - it can
be really agressive in a few places. It comes with its own downsides,
of course.)
>
--
Jon Skeet - <skeet@pobox.com>
http://www.pobox.com/~skeet Blog: http://www.msmvps.com/jon.skeet
If replying to the group, please do not mail me too

Ben Voigt [C++ MVP] <rbv@nospam.nospamwrote:>
I can't remember any such claims. There have been *other* claims, such
as the JIT being "good enough" in most cases, and supporting the notion
that improving the optimisation in the JIT is more important than
improving it in the C# compiler (which I'd agree with for most
situations but not all).
>
Certainly if I ever made such a statement I retract it wholeheartedly -
as Willy said, the JIT just doesn't have enough time to perform as many
optimisations. (That's where Sun's Hotspot technology wins out - it can
be really agressive in a few places. It comes with its own downsides,
of course.)

>
Hotspot does speculative optimization, doesn't it? Where the first time a
virtual call is compiled, the target is inlined, and only if another runtime
type is seen is it recompiled to use the v-table?

I think .NET could benefit from a healthy dose of this sort of thing. Also
there are an awful lot of cases where generics should be reinstantiated
for different reference types to enable inlining.

Ben Voigt [C++ MVP] <rbv@nospam.nospamwrote:>
Yup.
>>
I think the inlining is slightly less important in .NET than in Java,
where everything is virtual by default. In theory that shouldn't matter
- developers should decide whether or not something should be virtual,
and apply the right modifier or not regardless of the defaults. In
practice though, inlining would be *incredibly* rare in Java without
HotSpot :)
>
To be honest, anything I could write about how advantageous a HotSpot-
like runtime for .NET might be would only pure speculation. It's hard
to second-guess this kind of thing.
>
When it comes to generics, I see your point - I don't know how it would
be best to proceed with it, however. I suspect that giving the
developer some manual control would be the right way to go, probably
with attributes... but should those attributes be applied to the type
used as the type argument, or to the generic class itself? In other
words, do you think the developer ought to be able to write:
>
[AlwaysGenerateConcreteType]
public class Foo<T>
>
or
>
[AlwaysGenerateConcreteTypeWhenUsedInGenerics]
public class Bar
>
(with better names, of course :)

>
--
Jon Skeet - <skeet@pobox.com>
http://www.pobox.com/~skeet Blog: http://www.msmvps.com/jon.skeet
If replying to the group, please do not mail me too

Do you happen to know if the JIT can inline "through" a generic collection?
For example, List<T>.Contains is simple enough that it should be inlined,
but does the specific T.Equals(T other) method get inlined as well because
it's exactly known at the call site?

>
"Jon Skeet [C# MVP]" <skeet@pobox.comwrote in message
news:MPG.214fb6e71fa46ba477@msnews.microsoft.com.. .>
Do you happen to know if the JIT can inline "through" a generic
collection? For example, List<T>.Contains is simple enough that it should
be inlined, but does the specific T.Equals(T other) method get inlined as
well because it's exactly known at the call site?
>>
>

...
int a;
int b;
...
if(a.Equals(b))
b = ...;
is inlined and possibly optimized away.

However, List<T>.Contains is NOT inlined. This method is not as simple as
you may think, it's size is 96 bytes in IL, and methods larger than 32 are
not inlined by the JITters. Note that this class is part of the PRE_JIT'd
library mscorlib_ni, so the JIT doesn't have to JIT compile the method at
the first call, after checking the size (and quite some other stuff) he
can directly call the pre-jitted code from mscorlib_ni.

>
Willy.
>
>
>

>
Only because int is a value type. It can't be optimized away if T is a
generic type argument where the static type (compile-time actual argument)
is a reference type.
>

>
:(
>
Even TrueForAll and ForEach, which are very short, aren't that short.
>

I think 32 instructions would probably be more reasonable...
>

"Ben Voigt [C++ MVP]" <rbv@nospam.nospamwrote in message
news:uHyI9yN9HHA.4880@TK2MSFTNGP03.phx.gbl...>
True I should have said:
"T.Equals like in?",
T.Equals(T other) ends as a virtual call (callvirt in IL) and these
aren't inlined by the JIT.
>>
They aren't that short, and they contain loops, so they aren't inlined.
>That would mean that the JIT should count the instructions while
compiling, hmmm....

>
Willy.
>