Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #112266 > unrolled thread

Algorithm/code to compare values in an array

Back to article view | Back to comp.lang.c

Contents

  Algorithm/code to compare values in an array DFS <nospam@dfs.com> - 2017-06-15 11:16 -0400
    Re: Algorithm/code to compare values in an array Richard Heathfield <rjh@cpax.org.uk> - 2017-06-15 16:41 +0100
      Re: Algorithm/code to compare values in an array DFS <nospam@dfs.com> - 2017-06-15 13:48 -0400
        Re: Algorithm/code to compare values in an array Richard Heathfield <rjh@cpax.org.uk> - 2017-06-15 19:47 +0100
          Re: Algorithm/code to compare values in an array Gareth Owen <gwowen@gmail.com> - 2017-06-15 20:17 +0100
            Re: Algorithm/code to compare values in an array Richard Heathfield <rjh@cpax.org.uk> - 2017-06-15 20:51 +0100
    Re: Algorithm/code to compare values in an array Barry Schwarz <schwarzb@dqel.com> - 2017-06-15 11:43 -0700
      Re: Algorithm/code to compare values in an array DFS <nospam@dfs.com> - 2017-06-15 19:21 -0400
        Re: Algorithm/code to compare values in an array Barry Schwarz <schwarzb@dqel.com> - 2017-06-15 18:49 -0700
    Re: Algorithm/code to compare values in an array Real Troll <Real.Troll@Trolls.com> - 2017-06-15 16:35 -0400
      Re: Algorithm/code to compare values in an array Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-06-15 21:34 +0100
        Re: Algorithm/code to compare values in an array Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-06-15 23:23 +0100
          Re: Algorithm/code to compare values in an array Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-06-16 00:35 +0100
            Re: Algorithm/code to compare values in an array Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-06-16 01:04 +0100
            Re: Algorithm/code to compare values in an array Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-06-16 01:10 +0100
          Re: Algorithm/code to compare values in an array DFS <nospam@dfs.com> - 2017-06-15 20:45 -0400
      Re: Algorithm/code to compare values in an array DFS <nospam@dfs.com> - 2017-06-15 20:00 -0400

#112266 — Algorithm/code to compare values in an array

Given two int arrays:

q = {100,200};
s = {50,125,150,175,190,210};

I want to find:

1. the min s > the min q
2. the max s < the max q

Those would be 125 and 190

This code works fine, but maybe there's a better or shorter approach 
than 2 loops (one forward and one backward)?

------------------------------------------------
int main(int argc, char *argv[])
{
	int q[] = {100,200};
	int s[] = {50,125,150,175,190,210};

	int qmin = q[0];
	int qmax = q[1];

	int min_s = qmin;
	int max_s = qmax;

	for(int i = 0; i < 5; i++)
	{
	   if (s[i] > qmin) {min_s = s[i]; break;}
	}

	for(int i = 4; i >= 0; i--)
	{
	   if (s[i] < qmax) {max_s = s[i]; break;}
	}
	
	printf("min %d, max %d\n", min_s, max_s);	
	return 0;
}
------------------------------------------------

[toc] | [next] | [standalone]

#112268

On 15/06/17 16:16, DFS wrote:
> Given two int arrays:
>
> q = {100,200};
> s = {50,125,150,175,190,210};
>
> I want to find:
>
> 1. the min s > the min q
> 2. the max s < the max q
>
> Those would be 125 and 190
>
> This code works fine, but maybe there's a better or shorter approach
> than 2 loops (one forward and one backward)?

There may be a shorter approach, but whether it's "better" depends on 
what you mean by the word. At the moment, the intent of the code is 
clear, or at least reasonably clear. If you try to conflate the two 
objectives into a single loop, the clarity of the code is almost bound 
to suffer.

While s is small, what you have is probably ideal: quick, clear, simple. 
Cramming the two loops into one is a pointless exercise in code golf.

On the other hand, your linear approach doesn't scale well. There comes 
a point where it makes sense to write a binary search routine that will 
return the index of the smallest s > qmin, and another that returns the 
index of the greatest s < qmax.

-- 
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within

[toc] | [prev] | [next] | [standalone]

#112278

On 6/15/2017 11:41 AM, Richard Heathfield wrote:
> On 15/06/17 16:16, DFS wrote:
>> Given two int arrays:
>>
>> q = {100,200};
>> s = {50,125,150,175,190,210};
>>
>> I want to find:
>>
>> 1. the min s > the min q
>> 2. the max s < the max q
>>
>> Those would be 125 and 190
>>
>> This code works fine, but maybe there's a better or shorter approach
>> than 2 loops (one forward and one backward)?
> 
> There may be a shorter approach, but whether it's "better" depends on 
> what you mean by the word. At the moment, the intent of the code is 
> clear, or at least reasonably clear. If you try to conflate the two 
> objectives into a single loop, the clarity of the code is almost bound 
> to suffer.
> 
> While s is small, what you have is probably ideal: quick, clear, simple. 
> Cramming the two loops into one is a pointless exercise in code golf.

Before I posted I did a single pass forward, but it just seemed clunky.

for(int i = 0; i < 6; i++)
     {
        if (s[i] > qmin)
	{
		min_s = s[i];
		for(int j = i + 1 ; j < 6; j++)
		{
		  if (s[j] > qmax) {max_s = s[j-1]; break;}
		}
	break;
    }	
}


(my OP had the array size wrong - should've been 6)



> On the other hand, your linear approach doesn't scale well. There comes 
> a point where it makes sense to write a binary search routine that will 
> return the index of the smallest s > qmin, and another that returns the 
> index of the greatest s < qmax.

'scale' meaning when it seems slow?

[toc] | [prev] | [next] | [standalone]

#112281

On 15/06/17 18:48, DFS wrote:
> On 6/15/2017 11:41 AM, Richard Heathfield wrote:

<snip>

>> On the other hand, your linear approach doesn't scale well. There
>> comes a point where it makes sense to write a binary search routine
>> that will return the index of the smallest s > qmin, and another that
>> returns the index of the greatest s < qmax.
>
> 'scale' meaning when it seems slow?

Yes.

That's unlikely to happen (especially on modern machines) until the 
array gets pretty vast, or until you perform the operation 
extraordinarily often.

If either of those is likely, switching from an O(n) to an O(log n) 
approach is something you might want to consider.

-- 
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within

[toc] | [prev] | [next] | [standalone]

#112284

Richard Heathfield <rjh@cpax.org.uk> writes:

> If either of those is likely, switching from an O(n) to an O(log n)
> approach is something you might want to consider.

Assuming the arrays are guaranteed to be sorted, yes? (Or am I being obtuse)

[toc] | [prev] | [next] | [standalone]

#112290

On 15/06/17 20:17, Gareth Owen wrote:
> Richard Heathfield <rjh@cpax.org.uk> writes:
>
>> If either of those is likely, switching from an O(n) to an O(log n)
>> approach is something you might want to consider.
>
> Assuming the arrays are guaranteed to be sorted, yes? (Or am I being obtuse)

Yes and no, in that order.

-- 
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within

[toc] | [prev] | [next] | [standalone]

#112280

On Thu, 15 Jun 2017 11:16:31 -0400, DFS <nospam@dfs.com> wrote:

>Given two int arrays:
>
>q = {100,200};
>s = {50,125,150,175,190,210};
>
>I want to find:
>
>1. the min s > the min q
>2. the max s < the max q
>
>Those would be 125 and 190

Using qmin when no s[i] satisfies the condition is misleading.  It
forces the user to check the "returned" value against qmin to identify
the "no match" condition.

Are the arrays guaranteed to be sorted?

>This code works fine, but maybe there's a better or shorter approach 
>than 2 loops (one forward and one backward)?

Returning the wrong answer is a strange definition of "works fine".

>------------------------------------------------
>int main(int argc, char *argv[])
>{
>	int q[] = {100,200};
>	int s[] = {50,125,150,175,190,210};
>
>	int qmin = q[0];
>	int qmax = q[1];

Is q always an array of 2?

>	int min_s = qmin;
>	int max_s = qmax;
>
>	for(int i = 0; i < 5; i++)

How do you know the size of s?

>	{
>	   if (s[i] > qmin) {min_s = s[i]; break;}
>	}

The code produces the wrong answer if s contains 
{50, 51, 52, 57, 59, 210}.

>	for(int i = 4; i >= 0; i--)
>	{
>	   if (s[i] < qmax) {max_s = s[i]; break;}
>	}

Same issue when q contains {100, 400}.	

>	printf("min %d, max %d\n", min_s, max_s);	
>	return 0;
>}

-- 
Remove del for email

[toc] | [prev] | [next] | [standalone]

#112304

On 6/15/2017 2:43 PM, Barry Schwarz wrote:
> On Thu, 15 Jun 2017 11:16:31 -0400, DFS <nospam@dfs.com> wrote:
> 
>> Given two int arrays:
>>
>> q = {100,200};
>> s = {50,125,150,175,190,210};
>>
>> I want to find:
>>
>> 1. the min s > the min q
>> 2. the max s < the max q
>>
>> Those would be 125 and 190
> 
> Using qmin when no s[i] satisfies the condition is misleading.  
> It forces the user to check the "returned" value against qmin to identify
> the "no match" condition.

Since a range of s values may or may not be contained within q, that's 
the only way it could work.  As far as I can tell.



> Are the arrays guaranteed to be sorted?

Yes.

>> This code works fine, but maybe there's a better or shorter approach
>> than 2 loops (one forward and one backward)?
> 
> Returning the wrong answer is a strange definition of "works fine".

125 and 190 is the right answer for that set of values.


>> ------------------------------------------------
>> int main(int argc, char *argv[])
>> {
>> 	int q[] = {100,200};
>> 	int s[] = {50,125,150,175,190,210};
>>
>> 	int qmin = q[0];
>> 	int qmax = q[1];
> 
> Is q always an array of 2?

No.  But it's always evenly divisible by 2, and 2 values always form the 
upper and lower boundaries.

FYI:

I'm counting the number of words enclosed in single-quotes, enclosed in 
dbl-quotes.

q = position of dbl-quotes in the input
s = position of sgl-quotes in the input




>> 	int min_s = qmin;
>> 	int max_s = qmax;
>>
>> 	for(int i = 0; i < 5; i++)
> 
> How do you know the size of s?

The size of s is set at compile time to a relatively large value that I 
know won't be exceeded.

As s is populated I keep track of the nbr of entries, which is /not/ 
always evenly divisible by 2.




>> 	{
>> 	   if (s[i] > qmin) {min_s = s[i]; break;}
>> 	}
> 
> The code produces the wrong answer if s contains
> {50, 51, 52, 57, 59, 210}.

>> 	for(int i = 4; i >= 0; i--)
>> 	{
>> 	   if (s[i] < qmax) {max_s = s[i]; break;}
>> 	}
> 
> Same issue when q contains {100, 400}.	
> 
>> 	printf("min %d, max %d\n", min_s, max_s);	
>> 	return 0;
>> }



The code always checks the return values:

if (q[i] < min_s < max_s < q[i+1])

before moving on.

I guess I could do that check in the function and return a success or 
fail flag.  Either way.

[toc] | [prev] | [next] | [standalone]

#112317

On Thu, 15 Jun 2017 19:21:43 -0400, DFS <nospam@dfs.com> wrote:

>On 6/15/2017 2:43 PM, Barry Schwarz wrote:
>> On Thu, 15 Jun 2017 11:16:31 -0400, DFS <nospam@dfs.com> wrote:

<snip>

>
>>> This code works fine, but maybe there's a better or shorter approach
>>> than 2 loops (one forward and one backward)?
>> 
>> Returning the wrong answer is a strange definition of "works fine".
>
>125 and 190 is the right answer for that set of values.

If you already know the answer, you don't need the code.  I thought
you wanted code that would work for any set of values that meet your
conditions.  Yours doesn't as documented below.

>>> ------------------------------------------------
>>> int main(int argc, char *argv[])
>>> {
>>> 	int q[] = {100,200};
>>> 	int s[] = {50,125,150,175,190,210};
>>>
>>> 	int qmin = q[0];
>>> 	int qmax = q[1];

<snip>

>>> 	int min_s = qmin;
>>> 	int max_s = qmax;
>>>
>>> 	for(int i = 0; i < 5; i++)

<snip>

>>> 	{
>>> 	   if (s[i] > qmin) {min_s = s[i]; break;}
>>> 	}
>> 
>> The code produces the wrong answer if s contains
>> {50, 51, 52, 57, 59, 210}.

*******************************************************
*  Code that fails when different but valid values are tested does not
* qualify as working fine!
*******************************************************

>>> 	for(int i = 4; i >= 0; i--)
>>> 	{
>>> 	   if (s[i] < qmax) {max_s = s[i]; break;}
>>> 	}
>> 
>> Same issue when q contains {100, 400}.	

*******************************************************
*  Code that fails when different but valid values are tested does not
* qualify as working fine!
*******************************************************

>> 
>>> 	printf("min %d, max %d\n", min_s, max_s);	
>>> 	return 0;
>>> }

-- 
Remove del for email

[toc] | [prev] | [next] | [standalone]

#112295

On 15/06/2017 16:16, DFS wrote:
>
>
> This code works fine, but maybe there's a better or shorter approach 
> than 2 loops (one forward and one backward)?
>
>

Of course there is a better way that works all the time irrespective 
whether the array is sorted or not.  Use this code:


#include <stdio.h>

int minimum (int values [], int numberOfElements);
int maximum (int values[], int numberOfElements);

int main ()
{
     int array1 [] = {100,200};
     int array2 [] = {50,125,150,175,190,210};

     printf ("Array1 minimum is: %i\n", minimum (array1, 2) );
     printf ("Array1 maximum is: %i\n", maximum (array1, 2) );

     printf ("Array2 minimum is: %i\n", minimum (array2, 6) );
     printf ("Array2 maximum is: %i\n", maximum (array2, 6) );

     return 0;
}
int minimum (int values[], int numberOfElements)
{
     int minValue, i;
     minValue = values[0];

     for ( i = 1; i < numberOfElements; ++i )
         if ( values[i] < minValue )
             minValue = values[i];
     return minValue;
}

int maximum (int values[], int numberOfElements)
{
     int maxValue, i;
     maxValue = values[0];

     for ( i = 1; i < numberOfElements; ++i )
         if ( values[i] > maxValue )
             maxValue = values[i];
     return maxValue;
}

You could combine both Min and Max in one function but you may not use 
both in the same prog so the best thing is to keep separate.

Me thinks so anyway but like everything, somebody here will find holes 
in the code.

Also, the size of the array is hard coded as dynamic arrays is not 
supported in C like it is in C++.



>
>

[toc] | [prev] | [next] | [standalone]

#112296

Real Troll <Real.Troll@Trolls.com> writes:

> On 15/06/2017 16:16, DFS wrote:
>>
>> This code works fine, but maybe there's a better or shorter approach
>> than 2 loops (one forward and one backward)?
>
> Of course there is a better way that works all the time irrespective
> whether the array is sorted or not.  Use this code:

The code you posted does not solve the problem which was:

| Given two int arrays:
|  
| q = {100,200};
| s = {50,125,150,175,190,210};
|  
| I want to find:
|  
| 1. the min s > the min q
| 2. the max s < the max q
|  
| Those would be 125 and 190

Your code just finds min and max of q and s.

<snip>
-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#112300

ram@zedat.fu-berlin.de (Stefan Ram) writes:

> Ben Bacarisse <ben.usenet@bsb.me.uk> quoted:
>>|the min s > the min q
>
>   The quoted text and is somewhat vague and possibly ungrammatical.

It seemed clear to me.  I took it that the OP wants

  min { x in s | x > min q }

and

  max { x in s | x < max q }

What are the other interpretations?  (Obviously there are unspecified
cases but that's not quite the same thing.)

<snip>
-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#112306

ram@zedat.fu-berlin.de (Stefan Ram) writes:

> Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
>>ram@zedat.fu-berlin.de (Stefan Ram) writes:
>>> Ben Bacarisse <ben.usenet@bsb.me.uk> quoted:
>>>>|the min s > the min q
>>>The quoted text and is somewhat vague and possibly ungrammatical.
>>What are the other interpretations?
>
>   Two (hopefully) grammatical interpretations are:
>
>       - the minimum value from the set of those values which
>         are in s and are larger than the minimum value from
>         the set q.¹

Isn't that what I said?  In Haskell minimum [ x | x <- s, x > minimum q ]

>       - the truth value of the assertion "the minimum value
>         from the set s is larger than the minimum value of
>         the set q".

I don't think that's a possible meaning unless you are assuming it's
badly worded.

<snip>
-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#112310

ram@zedat.fu-berlin.de (Stefan Ram) writes:

> Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
>>Isn't that what I said?  In Haskell minimum [ x | x <- s, x > minimum q ]
>
>   Yes, but it is only one possible interpretation.
>
>>I don't think that's a possible meaning unless you are assuming it's
>>badly worded.
>
>   Using what little I learned from Haskell by your expression
>   from above, this interpretation in Haskell would read:
>
> minimum s > minimum q
>
>   which looks quite similar to
>
>>>>>>|the min s > the min q
>
>   , so it might not be that far-fetched.

Sorry, but I think it is far fetched.  The OP used English and a little
maths and I can't see how the English words used can mean what you
suppose.  The word "the" followed the word "find" and that's crucial:

| I want to find:
|  
| 1. the min s > the min q
| 2. the max s < the max q

Your "other" meaning would be "I want to find out if the min s > the min
q" and with this phrasing the two words "the" are not really needed
anymore, though not actually wrong.

(Please stop cutting the only text that matters -- what the OP wrote.)

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#112311

ram@zedat.fu-berlin.de (Stefan Ram) writes:

> ram@zedat.fu-berlin.de (Stefan Ram) writes:
>>Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
>>>Isn't that what I said?  In Haskell minimum [ x | x <- s, x > minimum q ]
>>Yes, but it is only one possible interpretation.
>>>I don't think that's a possible meaning unless you are assuming it's
>>>badly worded.
>>Using what little I learned from Haskell by your expression
>>from above, this interpretation in Haskell would read:
>>minimum s > minimum q
>>which looks quite similar to
>>>>>>>|the min s > the min q
>>, so it might not be that far-fetched.
>
>   Also, 
>
> 2>3
>
>   means »2 is larger than 3«. So, »>« is converted into
>   English words as »is larger than«. Putting that into
>   »the min s > the min q«, we get
>
> »the min s is larger than the min q«.

That's not how language or mathematics work.  The words used matter.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#112312

On 6/15/2017 7:21 PM, Stefan Ram wrote:
> ram@zedat.fu-berlin.de (Stefan Ram) writes:
>> »We have finite non-empty sets of integers, so we know that
>> they all have a maximum and minimum.
> 
>    And this too can, step by step, beautifully be formulated in SQL:
> 
> CREATE TABLE Q( Q INTEGER );
> INSERT INTO Q VALUES( 100 ),( 200 );
> 
> CREATE TABLE S( S INTEGER );
> INSERT INTO S VALUES( 50 ),( 125 ),( 150 ),( 175 ),( 190 ),( 210 );

A PK on cols Q and S would be appropriate, even though the values will 
always be unique.


>> Let m be the minimum of q.
> 
> CREATE VIEW M AS
> SELECT MIN( Q )AS M FROM Q;
> 
>> Let s+ be the set of all values from s that are larger than m.
> 
> CREATE VIEW SPLUS AS
> SELECT S AS SPLUS FROM S, M WHERE S > M;
> 
>> Now, print the minimum of s+ as a decimal numeral.«
> 
> SELECT MIN( SPLUS )AS RESULT FROM SPLUS;


No need for a VIEW:

SELECT MIN(S) FROM S WHERE S > (SELECT MIN(Q) FROM Q);



> +--------+
> | RESULT |
> +--------+
> |    125 |
> +--------+
> 
>    SQL is not as beautiful as it could theoretically be.
>    But it is close to natural English pseudocode here.
>    No algorithm, just a description.

[toc] | [prev] | [next] | [standalone]

#112309

On 6/15/2017 4:35 PM, Real Troll wrote:
> On 15/06/2017 16:16, DFS wrote:
>>
>>
>> This code works fine, but maybe there's a better or shorter approach 
>> than 2 loops (one forward and one backward)?
>>
>>
> 
> Of course there is a better way that works all the time irrespective 
> whether the array is sorted or not.  Use this code:

<snip>


> You could combine both Min and Max in one function but you may not use 
> both in the same prog so the best thing is to keep separate.
> 
> Me thinks so anyway but like everything, somebody here will find holes 
> in the code.


Yes they will.  And that's a good thing, even if it hurts your ego.

Thanks for working on it, but you didn't actually accomplish what I was 
looking for.  I don't want the min or max of each array (for q it's 
already there by default) - I want the min and max values in s that lie 
within the values in q.



> Also, the size of the array is hard coded as dynamic arrays is not 
> supported in C like it is in C++.

Apparently you can accomplish it with realloc().

http://en.cppreference.com/w/c/memory/realloc

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.c

csiph-web