Find the lowest value in an array

[Guest]

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

 

[Lilith]

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

Easiest way for me is sort the array and choose the first element.

int [] myList = {12, 42, 50, 2, 67, 100, 9, 1};

Array.Sort (mylist);

should sort the list into ascending order with the number '1' in the
first position.

 

[Guest]

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#.

If it is always 4 elements then maybe:

minval = Math.Min(Math.Min(a[0], a[1]), Math.Min(a[2], a[3]));

Arne

 

[Guest]

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.

 

[Hilton]

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.

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. To maximize efficiency, something
along the lines of:

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, c)" which in summary is really "Math.Min (a,
b, c, d)"
return (a < c) ? a : c;

Hilton

 

[Jon Skeet [C# MVP]]

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.

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>.)

 

[Wole Ogunremi]

That's a fantastic new method! Thanks for sharing that Jon... I really need
to dig into .NET 3.5 and learn the new tricks!



Wole

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.

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>.)

 

[Guest]

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

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 < low) {
low = items;
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;
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;

 

[Hilton]

Jon,

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.

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

 

[Guest]

I refered to Arne's post, which in my view is pretty much the same as you are
suggesting. My question to the OP was with regards to whether they wanted a
function to return a new array with only 3 items (destructive), or just
"blank" the item entry (non-destructive).

 

[Guest]

Thank you all for your help. The array.sort was the trick I needed.

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

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 < low) {
low = items;
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;
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;

 

[Jon Skeet [C# MVP]]

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

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?

 

[Hilton]

Jon,

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.

Hilton

 

[Jon Skeet [C# MVP]]

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.

No, I didn't use Math.Min - but not due to efficiency, but due to
finding a better overall solution.

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.

 

[Jon Skeet [C# MVP]]

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.

Sorry, that should have been "compared a few values".

I'd also run benchmarks if I really needed ultimate efficiency (which
is unlikely). I wouldn't be surprised if the call to Math.Min got
inlined into the same code anyway.

Basically, I'm concerned about people getting the impression that it's
worth writing long and less readable code for the sake of efficiency
when:

a) there's no indication that this is a bottleneck
b) there's no evidence that the longer version is more efficient

 

[Hilton]

I'd also run benchmarks if I really needed ultimate efficiency (which
is unlikely). I wouldn't be surprised if the call to Math.Min got
inlined into the same code anyway.

Basically, I'm concerned about people getting the impression that it's
worth writing long and less readable code for the sake of efficiency
when:

a) there's no indication that this is a bottleneck
b) there's no evidence that the longer version is more efficient

I agree 100%.

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
The Sort version seemed so horrendously inefficient, I didn't have the
stomach or 'boredom level' to test it.

If I had to use this code, I would use my original version and document the
method as:
/// Returns the minimum value in an int array with 4 ints

That's really obvious to the reader and if they want to dig around, it's
very simple code. Having said all that, we both agree not to over
complicate code, and to keep it simple and readable.

Hilton

 

[Jon Skeet [C# MVP]]

I agree 100%.

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

Gosh - I'm surprised that the Math.Min version was that slow, even
slower than my "if" form.

Was this running outside a debugger, using a release version etc?

The Sort version seemed so horrendously inefficient, I didn't have the
stomach or 'boredom level' to test it.

Yeah, that's fair enough. Using a destructive *and* inefficient version
seems silly to me.

If I had to use this code, I would use my original version and document the
method as:
/// Returns the minimum value in an int array with 4 ints

That's really obvious to the reader and if they want to dig around, it's
very simple code.

Out of interest, why would you not use the more general form? It's
clearly more useful (by being more general) and it's (IMO) the simplest
version to read (barring .NET 3.5 of course). Of course, in a situation
where we'd determined performance to be crucial, it might be worth
doing something like this, but not before that point.

Having said all that, we both agree not to over complicate code, and to keep
it simple and readable.

Cool. I guess we just disagree over what's overcomplicating it

 

[Jon Skeet [C# MVP]]

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

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]));
}
}

 

[Hilton]

Jon,

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

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

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 [C# MVP]]

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)

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.

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.

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.