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

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

Copy array with small changes

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

Contents

  Copy array with small changes Noob <root@127.0.0.1> - 2018-03-11 22:51 +0100
    Re: Copy array with small changes supercat@casperkitty.com - 2018-03-11 15:11 -0700
    Re: Copy array with small changes Richard Damon <Richard@Damon-Family.org> - 2018-03-11 18:12 -0400
      Re: Copy array with small changes Spiros Bousbouras <spibou@gmail.com> - 2018-03-11 22:35 +0000
        Re: Copy array with small changes Richard Damon <Richard@Damon-Family.org> - 2018-03-13 13:10 -0400
    Re: Copy array with small changes Spiros Bousbouras <spibou@gmail.com> - 2018-03-11 22:13 +0000
      Re: Copy array with small changes Spiros Bousbouras <spibou@gmail.com> - 2018-03-12 00:04 +0000
      Re: Copy array with small changes bartc <bc@freeuk.com> - 2018-03-12 10:35 +0000
        Re: Copy array with small changes Spiros Bousbouras <spibou@gmail.com> - 2018-03-12 12:37 +0000
          Re: Copy array with small changes bartc <bc@freeuk.com> - 2018-03-12 13:10 +0000
          Re: Copy array with small changes Jorgen Grahn <grahn+nntp@snipabacken.se> - 2018-03-12 13:34 +0000
            Re: Copy array with small changes Tim Rentsch <txr@alumni.caltech.edu> - 2018-03-17 09:22 -0700
          Re: Copy array with small changes mark.bluemel@gmail.com - 2018-03-12 07:47 -0700
            Re: Copy array with small changes bartc <bc@freeuk.com> - 2018-03-12 14:56 +0000
              Re: Copy array with small changes Spiros Bousbouras <spibou@gmail.com> - 2018-03-12 15:14 +0000
              Re: Copy array with small changes mark.bluemel@gmail.com - 2018-03-12 08:53 -0700
          Re: Copy array with small changes Keith Thompson <kst-u@mib.org> - 2018-03-12 09:08 -0700
            Re: Copy array with small changes supercat@casperkitty.com - 2018-03-12 09:57 -0700
              Re: Copy array with small changes Richard Damon <Richard@Damon-Family.org> - 2018-03-13 13:21 -0400
      Re: Copy array with small changes Noob <root@127.0.0.1> - 2018-03-12 15:25 +0100
        Re: Copy array with small changes Spiros Bousbouras <spibou@gmail.com> - 2018-03-12 15:09 +0000
    Re: Copy array with small changes Jorgen Grahn <grahn+nntp@snipabacken.se> - 2018-03-12 06:59 +0000
      Re: Copy array with small changes Noob <root@127.0.0.1> - 2018-03-12 15:55 +0100
        Re: Copy array with small changes bartc <bc@freeuk.com> - 2018-03-12 15:07 +0000
        Re: Copy array with small changes mark.bluemel@gmail.com - 2018-03-12 09:03 -0700
        Re: Copy array with small changes Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-03-12 17:42 +0000
          Re: Copy array with small changes Noob <root@127.0.0.1> - 2018-03-12 23:33 +0100
            Re: Copy array with small changes Wouter Verhelst <w@uter.be> - 2018-03-12 23:44 +0100
            Re: Copy array with small changes Tim Rentsch <txr@alumni.caltech.edu> - 2018-03-17 09:48 -0700
              Re: Copy array with small changes Steven Petruzzellis <frelwizzen@gmail.com> - 2018-03-18 03:31 -0700
              Re: Copy array with small changes Noob <root@127.0.0.1> - 2018-03-22 17:10 +0100
          Re: Copy array with small changes Tim Rentsch <txr@alumni.caltech.edu> - 2018-03-17 09:24 -0700
            Re: Copy array with small changes Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-03-17 18:04 +0000
              Re: Copy array with small changes Tim Rentsch <txr@alumni.caltech.edu> - 2018-03-26 22:55 -0700
                Re: Copy array with small changes Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-03-27 15:28 +0100
                  Re: Copy array with small changes Steven Petruzzellis <frelwizzen@gmail.com> - 2018-03-28 14:42 -0700
        Re: Copy array with small changes Jorgen Grahn <grahn+nntp@snipabacken.se> - 2018-03-13 12:46 +0000
    Re: Copy array with small changes Anton Shepelev <anton.txt@gmail.com> - 2018-03-12 22:36 +0300
    Re: Copy array with small changes Wouter Verhelst <w@uter.be> - 2018-03-12 23:32 +0100
      Re: Copy array with small changes Wouter Verhelst <w@uter.be> - 2018-03-13 10:42 +0100
      Re: Copy array with small changes Noob <root@127.0.0.1> - 2018-03-13 11:37 +0100
        Re: Copy array with small changes Wouter Verhelst <w@uter.be> - 2018-03-13 21:27 +0100
    Re: Copy array with small changes Tim Rentsch <txr@alumni.caltech.edu> - 2018-03-17 09:55 -0700

Page 2 of 3 — ← Prev page 1 [2] 3  Next page →

#127674

On Mon, 12 Mar 2018 15:25:13 +0100
Noob <root@127.0.0.1> wrote:
> On 11/03/2018 23:13, Spiros Bousbouras wrote:
> 
> > On Sun, 11 Mar 2018, Noob wrote:
> >
> >> I'm writing a toy program where I have a function that copies
> >> a small sorted array (less than 12 ints) while making two small
> >> changes: remove two elements, insert one element.
> >>
> >> The function prototype is:
> >>
> >> void update_array(int *arr, int n, int zi, int zj, int val);
> >>
> >> arr = the original array, sorted by increasing values
> >> n = number of elements < N = 12
> >> zi = 1st index to remove
> >> zj = 2nd index to remove
> >> val = new value to insert while keeping the array sorted
> >>
> >> Here's my current implementation:
> >>
> >> void update_array(int *arr, int n, int zi, int zj, int val)
> > 
> > void update_array(const int * const arr , const size_t n ,
> >                   const size_t zi , const size_t zj , const int val)
> > 
> > Actually something like  arrsz  is a better name than n. But since the
> > function is short it doesn't matter that much.
> > 
> >> {
> >>     int new_arr[N];
> > 
> > Where is  N  defined ?
> 
> N = 12

I meant in the code.

> >>     int i, j = 0, done = 0;
> > 
> > size_t i , j ;
> > int done = 0 ;
> > 
> >>     for (i = 0; i < n; +i)
> > 
> > ++i .It seems that you didn't cut and paste your code or you didn't run it
> > at all. It saves time for all of us if you do both before asking questions.
> 
> You caught me! I wrote the code on a different computer,
> and posted it from memory.
> 
> >>     {
> >> 	if (i == zi || i == zj) continue;
> >> 	int tmp = arr[i];
> > 
> > It looks nicer to me if you move this declaration outside the loop and just do
> > an assignment here.
> 
> OK, when I said the code looks ugly, I meant the algorithmic
> implementation, not the formatting. But point taken.
> 
> >> 	if (!done && val < tmp) {
> >> 	    new_arr[j++] = val;
> >> 	    done = 1;
> >> 	}
> >>         new_arr[j++] = tmp;
> >>     }
> >>     new_arr[j] = val;
> > 
> > if (done == 0) new_arr[j] = val;
> 
> In fact, this change makes the code 10% slower!

Wow. I thought without the check it was a bug because  val  may get assigned
in 2 different locations in the array. But considering the bigger picture , I
see now that it doesn't matter.

> Kind of like
> 	if (val != 0) sum += val;
> is slower than
> 	sum += val;

In this case it would have been obvious to me that the check is redundant ,
in the code above it wasn't.

> >>     do_something(new_arr);
> > 
> > How does  do_something()  know the size of  new_arr ?
> 
> You're right, it is, in fact
> 
> 	do_something(new_arr, n-1);
> 
> >> It's ugly IMO. Do you have suggestions for improvements?
> > 
> > I don't think it looks ugly but it has bugs.
> 
> What bugs?

The  +i  part and what I mention above which I thought was a bug but it wasn't.

[...]

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

#127659

On Sun, 2018-03-11, Noob wrote:
> Hello,
>
> I'm writing a toy program where I have a function that copies
> a small sorted array (less than 12 ints) while making two small
> changes: remove two elements, insert one element.
>
> The function prototype is:
>
> void update_array(int *arr, int n, int zi, int zj, int val);
>
> arr = the original array, sorted by increasing values
> n = number of elements < N = 12
> zi = 1st index to remove
> zj = 2nd index to remove
> val = new value to insert while keeping the array sorted
>
> Here's my current implementation:
...
> It's ugly IMO. Do you have suggestions for improvements?
> This function is called several billion times, so any performance
> improvement will be useful.

Because the function's task is so strange, I get the feeling that it
may be worth refactoring the code as a whole.  For example, it's
called "update_array" -- are you overwriting the same array with
basically the same data, over and over again?

I'm partly asking because with the requirements you have on
update_array(), I don't think it can be made internally elegant.

/Jorgen

-- 
  // Jorgen Grahn <grahn@  Oo  o.   .     .
\X/     snipabacken.se>   O  o   .

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

#127671

On 12/03/2018 07:59, Jorgen Grahn wrote:
> On Sun, 2018-03-11, Noob wrote:
>> Hello,
>>
>> I'm writing a toy program where I have a function that copies
>> a small sorted array (less than 12 ints) while making two small
>> changes: remove two elements, insert one element.
>>
>> The function prototype is:
>>
>> void update_array(int *arr, int n, int zi, int zj, int val);
>>
>> arr = the original array, sorted by increasing values
>> n = number of elements < N = 12
>> zi = 1st index to remove
>> zj = 2nd index to remove
>> val = new value to insert while keeping the array sorted
>>
>> Here's my current implementation:
> ...
>> It's ugly IMO. Do you have suggestions for improvements?
>> This function is called several billion times, so any performance
>> improvement will be useful.
> 
> Because the function's task is so strange, I get the feeling that it
> may be worth refactoring the code as a whole.  For example, it's
> called "update_array" -- are you overwriting the same array with
> basically the same data, over and over again?
> 
> I'm partly asking because with the requirements you have on
> update_array(), I don't think it can be made internally elegant.

OK, you want the big picture :-)

The task is to evaluate all arithmetic expressions involving
N numbers and the 4 arithmetic operators [+ - * /]

Given an array containing M values, I pick two values from
the array, v1 and v2; and compute v3 = v1 op v2
I "remove" v1 and v2 from the array, "add" v3 to the array,
and work on that new array with M-1 values.

Regards.

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

#127673

On 12/03/2018 14:55, Noob wrote:
> On 12/03/2018 07:59, Jorgen Grahn wrote:

>> I'm partly asking because with the requirements you have on
>> update_array(), I don't think it can be made internally elegant.
> 
> OK, you want the big picture :-)
> 
> The task is to evaluate all arithmetic expressions involving
> N numbers and the 4 arithmetic operators [+ - * /]
> 
> Given an array containing M values, I pick two values from
> the array, v1 and v2; and compute v3 = v1 op v2
> I "remove" v1 and v2 from the array, "add" v3 to the array,
> and work on that new array with M-1 values.

I think I once coded something similar, a program to solve the 'numbers' 
puzzle in the [UK] Countdown TV show. (There, there were only 6 numbers 
in total, so a brute force approach to examine all combinations would 
work. At least, within the 30 seconds you had if watching live.)

Looking at the code, there does indeed appear a loop a little like yours:

     for (k=0; k<n; ++k) {
         if (k != i && k != j) {
             newnos[m++] = (*nos)[k];
         }
     }

but this is a small part of it. However my numbers aren't sorted, and 
there is no equivalent of 'val' to be inserted. (And the number of 
elements is denoted by 'n' not 'arrsz'.)

-- 
bartc

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

#127681

On Monday, 12 March 2018 14:55:22 UTC, Noob  wrote:
> On 12/03/2018 07:59, Jorgen Grahn wrote:
> > On Sun, 2018-03-11, Noob wrote:
> >> Hello,
> >>
> >> I'm writing a toy program where I have a function that copies
> >> a small sorted array (less than 12 ints) while making two small
> >> changes: remove two elements, insert one element.
> >>
> >> The function prototype is:
> >>
> >> void update_array(int *arr, int n, int zi, int zj, int val);
> >>
> >> arr = the original array, sorted by increasing values
> >> n = number of elements < N = 12
> >> zi = 1st index to remove
> >> zj = 2nd index to remove
> >> val = new value to insert while keeping the array sorted
> >>
> >> Here's my current implementation:
> > ...
> >> It's ugly IMO. Do you have suggestions for improvements?
> >> This function is called several billion times, so any performance
> >> improvement will be useful.
> > 
> > Because the function's task is so strange, I get the feeling that it
> > may be worth refactoring the code as a whole.  For example, it's
> > called "update_array" -- are you overwriting the same array with
> > basically the same data, over and over again?
> > 
> > I'm partly asking because with the requirements you have on
> > update_array(), I don't think it can be made internally elegant.
> 
> OK, you want the big picture :-)
> 
> The task is to evaluate all arithmetic expressions involving
> N numbers and the 4 arithmetic operators [+ - * /]
> 
> Given an array containing M values, I pick two values from
> the array, v1 and v2; and compute v3 = v1 op v2
> I "remove" v1 and v2 from the array, "add" v3 to the array,
> and work on that new array with M-1 values.
> 
> Regards.

I wonder if an "in place" algorithm would work?
Assume v1 is in arr[x] and v2 is in arr[y] and for the sake of
simplicity x < y. Then would something like this work?

int temp = arr[x] <op> arr[y];
memmove(&arr[x], &arr[x+1], sizeof(int) * (y-x-1));
memmove(&arr[y-1], &arr[y+1], sizeof(int) * (n-y-1));
arr[n-1] = temp;

<Dons asbestos suit and ducks for cover>

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

#127694

Noob <root@127.0.0.1> writes:

> On 12/03/2018 07:59, Jorgen Grahn wrote:
<snip>
>> Because the function's task is so strange, I get the feeling that it
>> may be worth refactoring the code as a whole.  For example, it's
>> called "update_array" -- are you overwriting the same array with
>> basically the same data, over and over again?
>> 
>> I'm partly asking because with the requirements you have on
>> update_array(), I don't think it can be made internally elegant.
>
> OK, you want the big picture :-)
>
> The task is to evaluate all arithmetic expressions involving
> N numbers and the 4 arithmetic operators [+ - * /]

And it's Catalan numbers again!

Is the maximum value for N fixed?  In other words are the problem
instance mostly due to different sets of numbers, or can N be
arbitrarily large?  I'm guessing the latter because you talk of billions
of calls.

For smallish max N (six, in the case of the UK TV show Countdown that
BartC mentioned), I'd pre-compute the expression trees and apply them to
different permutation of the numbers and selections for the operands.

-- 
Ben.

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

#127716

On 12/03/2018 18:42, Ben Bacarisse wrote:

> Noob writes:
> 
>> The task is to evaluate all arithmetic expressions involving
>> N numbers and the 4 arithmetic operators [+ - * /]
> 
> And it's Catalan numbers again!
> 
> Is the maximum value for N fixed?  In other words are the problem
> instance mostly due to different sets of numbers, or can N be
> arbitrarily large?  I'm guessing the latter because you talk of billions
> of calls.

There's a combinatorial explosion as N grows, the number of
expressions to evaluate grows out of reach:

For N=7, ~4e7  evals
For N=8, ~5e9  evals
For N=9, ~6e11 evals
For N=10, 1e14 evals (extrapolated, didn't run it)

Therefore, as far as brute-force exhaustive search is concerned,
there is no point in supporting anything but a small value for N,
say 12 (which would require around 5e18 evaluations).

> For smallish max N (six, in the case of the UK TV show Countdown that
> BartC mentioned), I'd pre-compute the expression trees and apply them to
> different permutation of the numbers and selections for the operands.

For N=6, the code runs in a few milliseconds.

For N=8, it's in the 20-30 second range.

For N=9, the range climbs to 1-2 hours.

For N=10, it's probably 1-2 weeks.

I do note that the problem is embarrassingly parallel; it will
be a fun exercise to write multi-threaded code in order to get
a 24x speedup on the big server :-)

Regards.

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

#127717

On 12-03-18 23:33, Noob wrote:
> I do note that the problem is embarrassingly parallel; it will
> be a fun exercise to write multi-threaded code in order to get
> a 24x speedup on the big server :-)

Why threaded? Just make the program take two parameters -- the first the
initial state for the array of numbers, the second the number of arrays
to test. You test that array, bump the number of the lowest element of
the array (and the second-lowest if the lowest overflows, etc), and test
again. Print the output to stdout.

Once you've done that, you can just parallelize the problem in shell, no
need for the locks etc that multithreading needs.

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

#127947

Noob <root@127.0.0.1> writes:

> On 12/03/2018 18:42, Ben Bacarisse wrote:
>
>> Noob writes:
>>
>>> The task is to evaluate all arithmetic expressions involving
>>> N numbers and the 4 arithmetic operators [+ - * /]
>>
>> And it's Catalan numbers again!
>>
>> Is the maximum value for N fixed?  In other words are the problem
>> instance mostly due to different sets of numbers, or can N be
>> arbitrarily large?  I'm guessing the latter because you talk of billions
>> of calls.
>
> There's a combinatorial explosion as N grows, the number of
> expressions to evaluate grows out of reach:
>
> For N=7, ~4e7  evals
> For N=8, ~5e9  evals
> For N=9, ~6e11 evals
> For N=10, 1e14 evals (extrapolated, didn't run it)

Either I'm not understanding you, or something is off in these
numbers.  If N is 2, there are 6 possibilities - one for each of
the four operations, plus one more for each of the two asymmetric
ones.  If N is 3, there are 3*6*6, or 108.  And so forth.  This
gives a much larger value for N=7, about 2e9.  What am I missing?

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

#127966

On Saturday, March 17, 2018 at 9:49:01 AM UTC-7, Tim Rentsch wrote:
> Noob <root@127.0.0.1> writes:
> 
> > On 12/03/2018 18:42, Ben Bacarisse wrote:
> >
> >> Noob writes:
> >>
> >>> The task is to evaluate all arithmetic expressions involving
> >>> N numbers and the 4 arithmetic operators [+ - * /]
> >>
> >> And it's Catalan numbers again!
> >>
> >> Is the maximum value for N fixed?  In other words are the problem
> >> instance mostly due to different sets of numbers, or can N be
> >> arbitrarily large?  I'm guessing the latter because you talk of billions
> >> of calls.
> >
> > There's a combinatorial explosion as N grows, the number of
> > expressions to evaluate grows out of reach:
> >
> > For N=7, ~4e7  evals
> > For N=8, ~5e9  evals
> > For N=9, ~6e11 evals
> > For N=10, 1e14 evals (extrapolated, didn't run it)
> 
> Either I'm not understanding you, or something is off in these
> numbers.  If N is 2, there are 6 possibilities - one for each of
> the four operations, plus one more for each of the two asymmetric
> ones.  If N is 3, there are 3*6*6, or 108.  And so forth.  This
> gives a much larger value for N=7, about 2e9.  What am I missing?



Turns out Vennie 'The Fool' Bowden's non-stop flooding comments of Autumn Nissen met his own definition of trolling, so he accused Autumn Nissen of making that up. Autumn Nissen owns Vennie 'The Fool' Bowden in every way possible. Vennie 'The Fool' Bowden calls it "obsessing" over him, even though he continues to provoke that selfsame reaction. 

Are you being transparent on purpose? 

--
Top Ten Ways Vennie 'The Fool' Bowden Trolls!!
https://www.reddit.com/r/linux/comments/6sfkup/what_desktop_tasks_does_linux_handle_better_than/=
Jonas Eklundh Communication

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

#128196

On 17/03/2018 17:48, Tim Rentsch wrote:

> Noob writes:
> 
>> The task is to evaluate all arithmetic expressions involving
>> N numbers and the 4 arithmetic operators [+ - * /]
>>
>> There's a combinatorial explosion as N grows, the number of
>> expressions to evaluate grows out of reach:
>>
>> For N=7, ~4e7  evals
>> For N=8, ~5e9  evals
>> For N=9, ~6e11 evals
>> For N=10, 1e14 evals (extrapolated, didn't run it)
> 
> Either I'm not understanding you, or something is off in these
> numbers.  If N is 2, there are 6 possibilities - one for each of
> the four operations, plus one more for each of the two asymmetric
> ones.  If N is 3, there are 3*6*6, or 108.  And so forth.  This
> gives a much larger value for N=7, about 2e9.  What am I missing?

You're right in theory :-)

Let 'E' be the number of expressions to evaluate.

E = PROD{i=2..n}(4*C(2,i))

However, in most cases, the division is not possible
(remainder is non-zero), x*1 and y/1 are not evaluated,
a-b=0 is ignored.

In practice, the number of expressions to evaluate comes
out smaller than what theory "predicts".

I'll post my code next week for people to suggest improvements.

Regards.

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

#127945

Ben Bacarisse <ben.usenet@bsb.me.uk> writes:

> Noob <root@127.0.0.1> writes:
>
>> On 12/03/2018 07:59, Jorgen Grahn wrote:
>
> <snip>
>
>>> Because the function's task is so strange, I get the feeling that it
>>> may be worth refactoring the code as a whole.  For example, it's
>>> called "update_array" -- are you overwriting the same array with
>>> basically the same data, over and over again?
>>>
>>> I'm partly asking because with the requirements you have on
>>> update_array(), I don't think it can be made internally elegant.
>>
>> OK, you want the big picture :-)
>>
>> The task is to evaluate all arithmetic expressions involving
>> N numbers and the 4 arithmetic operators [+ - * /]
>
> And its Catalan numbers again!

Not quite Catalan numbers, because any of the N choose 2
possibilities can be combined, not just adjacent ones.
Right?

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

#127954

Tim Rentsch <txr@alumni.caltech.edu> writes:

> Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
>
>> Noob <root@127.0.0.1> writes:
>>
>>> On 12/03/2018 07:59, Jorgen Grahn wrote:
>>
>> <snip>
>>
>>>> Because the function's task is so strange, I get the feeling that it
>>>> may be worth refactoring the code as a whole.  For example, it's
>>>> called "update_array" -- are you overwriting the same array with
>>>> basically the same data, over and over again?
>>>>
>>>> I'm partly asking because with the requirements you have on
>>>> update_array(), I don't think it can be made internally elegant.
>>>
>>> OK, you want the big picture :-)
>>>
>>> The task is to evaluate all arithmetic expressions involving
>>> N numbers and the 4 arithmetic operators [+ - * /]
>>
>> And its Catalan numbers again!
>
> Not quite Catalan numbers, because any of the N choose 2
> possibilities can be combined, not just adjacent ones.
> Right?

I'm not sure what you mean.  If you build all the complete binary trees
with 0, 1, 2... operators you get the Catalan numbers.  Each of these
C(n) trees can then have 4^n operators "plugged" in, and each of these
can be applied to the permutations of N choose (n+1) numbers.

(Given what's now know about the problem, this is not a good way to do
it though.)

-- 
Ben.

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

#128415

Ben Bacarisse <ben.usenet@bsb.me.uk> writes:

> Tim Rentsch <txr@alumni.caltech.edu> writes:
>
>> Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
>>
>>> Noob <root@127.0.0.1> writes:
>>>
>>>> On 12/03/2018 07:59, Jorgen Grahn wrote:
>>>
>>> <snip>
>>>
>>>>> Because the function's task is so strange, I get the feeling that it
>>>>> may be worth refactoring the code as a whole.  For example, it's
>>>>> called "update_array" -- are you overwriting the same array with
>>>>> basically the same data, over and over again?
>>>>>
>>>>> I'm partly asking because with the requirements you have on
>>>>> update_array(), I don't think it can be made internally elegant.
>>>>
>>>> OK, you want the big picture :-)
>>>>
>>>> The task is to evaluate all arithmetic expressions involving
>>>> N numbers and the 4 arithmetic operators [+ - * /]
>>>
>>> And its Catalan numbers again!
>>
>> Not quite Catalan numbers, because any of the N choose 2
>> possibilities can be combined, not just adjacent ones.
>> Right?
>
> I'm not sure what you mean.  If you build all the complete binary trees
> with 0, 1, 2... operators you get the Catalan numbers.  Each of these
> C(n) trees can then have 4^n operators "plugged" in, and each of these
> can be applied to the permutations of N choose (n+1) numbers.

I see - you're thinking about it from the perspective of
a problem description, whereas I was thinking about it from
an operational perspective of how the algorithm works.  (Or
at least how I imagine the algorithm works, since we only
saw part of it.)  I think these two are equivalent numerically
but I haven't checked that carefully, especially since your
way of looking at it is so much simpler than mine.

> (Given what's now know about the problem, this is not a good way to do
> it though.)

An interesting question is What /is/ a good way to do it, given
that addition is associative and commutative, with subtraction
having the relationship to addition that it does, and similarly
multiplication and division (but not exactly, since fractions
apparently are not allowed).  The "binary operator tree combined
with permuting the inputs" scheme has lots of redundant values.
Is there some way of taking the input canonically so as to
eliminate the redundant structures?  (I'm willing to ignore the
matter of multiplication distributing over addition, etc, if
indeed that even comes into play.)

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

#128435

Tim Rentsch <txr@alumni.caltech.edu> writes:
<snip>
> An interesting question is What /is/ a good way to do it, given
> that addition is associative and commutative, with subtraction
> having the relationship to addition that it does, and similarly
> multiplication and division (but not exactly, since fractions
> apparently are not allowed).  The "binary operator tree combined
> with permuting the inputs" scheme has lots of redundant values.

Vast numbers!  Once you set "0 * ..." at the top you can cut all other
cases.

> Is there some way of taking the input canonically so as to
> eliminate the redundant structures?  (I'm willing to ignore the
> matter of multiplication distributing over addition, etc, if
> indeed that even comes into play.)

I think it's an interesting problem but I don't have any intuition about
what the best way to go about it is.  My "it's Catalan numbers again!"
was just a nod to the fact that they might show up in some solutions.

-- 
Ben.

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

#128507

On Tuesday, March 27, 2018 at 7:28:21 AM UTC-7, Ben Bacarisse wrote:
> Tim Rentsch <txr@alumni.caltech.edu> writes:
> <snip>
> > An interesting question is What /is/ a good way to do it, given
> > that addition is associative and commutative, with subtraction
> > having the relationship to addition that it does, and similarly
> > multiplication and division (but not exactly, since fractions
> > apparently are not allowed).  The "binary operator tree combined
> > with permuting the inputs" scheme has lots of redundant values.
> 
> Vast numbers!  Once you set "0 * ..." at the top you can cut all other
> cases.
> 
> > Is there some way of taking the input canonically so as to
> > eliminate the redundant structures?  (I'm willing to ignore the
> > matter of multiplication distributing over addition, etc, if
> > indeed that even comes into play.)
> 
> I think it's an interesting problem but I don't have any intuition about
> what the best way to go about it is.  My "it's Catalan numbers again!"
> was just a nod to the fact that they might show up in some solutions.
> 
> -- 
> Ben.



These types of trolls get their thrill out of triggering emotional responses to their crap, which is the very definition of a troll. 

No one here has ever read my code, much less found a bug; still, in the back of my mind, I'm thinking, "Did I do all the error checking I could". At one point, Audra Moore said a COLA denizen was "obsessing" over him, which was identified as replying to his posts. I still persist in being uncertain that these never ending posts are definitely scripted. What I do is certainly technically correct. Just about everything Audra Moore says about Takuya Saitoh is false. Who isn't aware of this by now? It won't matter because the FROM line on a post is irrelevant, we know it is from the stalker anyway. 

--
Top Ten Ways Audra Moore Trolls
https://redd.it/6sfkup
http://www.5z8.info/stalin-will-rise-again_j3h5uj_nakedgrandmas.jpg
https://youtu.be/Z5wo5aE7MUk
Jonas Eklundh Communication

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

#127742

On Mon, 2018-03-12, Noob wrote:
> On 12/03/2018 07:59, Jorgen Grahn wrote:
>> On Sun, 2018-03-11, Noob wrote:
>>> Hello,
>>>
>>> I'm writing a toy program where I have a function that copies
>>> a small sorted array (less than 12 ints) while making two small
>>> changes: remove two elements, insert one element.
>>>
>>> The function prototype is:
>>>
>>> void update_array(int *arr, int n, int zi, int zj, int val);
>>>
>>> arr = the original array, sorted by increasing values
>>> n = number of elements < N = 12
>>> zi = 1st index to remove
>>> zj = 2nd index to remove
>>> val = new value to insert while keeping the array sorted
>>>
>>> Here's my current implementation:
>> ...
>>> It's ugly IMO. Do you have suggestions for improvements?
>>> This function is called several billion times, so any performance
>>> improvement will be useful.
>> 
>> Because the function's task is so strange, I get the feeling that it
>> may be worth refactoring the code as a whole.  For example, it's
>> called "update_array" -- are you overwriting the same array with
>> basically the same data, over and over again?
>> 
>> I'm partly asking because with the requirements you have on
>> update_array(), I don't think it can be made internally elegant.
>
> OK, you want the big picture :-)
>
> The task is to evaluate all arithmetic expressions involving
> N numbers and the 4 arithmetic operators [+ - * /]
>
> Given an array containing M values, I pick two values from
> the array, v1 and v2; and compute v3 = v1 op v2
> I "remove" v1 and v2 from the array, "add" v3 to the array,
> and work on that new array with M-1 values.

Thanks. Well, with that task, maybe update_array() isn't extremely
far-fetched after all.  I see no obvious replacement.

/Jorgen

-- 
  // Jorgen Grahn <grahn@  Oo  o.   .     .
\X/     snipabacken.se>   O  o   .

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

#127701

Noob:

> void update_array(int *arr, int n, int zi, int zj, int val)
> {
>     int new_arr[N];
>     int i, j = 0, done = 0;
>
>     for (i = 0; i < n; +i)
>     {
>         if (i == zi || i == zj) continue;
>         int tmp = arr[i];
>         if (!done && val < tmp) {
>             new_arr[j++] = val;
>             done = 1;
>         }
>         new_arr[j++] = tmp;
>     }
>     new_arr[j] = val;
>     do_something(new_arr);
> }
> It's ugly IMO.

Does the performace gain countervail the ugliness?

#include<stdio.h>

static void doit( int a[], int n )
{  int i;
   for( i = 0; i < n; i = i + 1 )
   {  printf( "%i ", a[ i ] );  }
   printf("\n");
}

static void proc_array( int a[], int n, int ix1, int ix2, int inc )
{  int i, added, pos, scanned;
   int b[ n - 1 ];

   added   = 0;
   scanned = 0;
   pos     = 0;
   for( i = 0;; i++ )
   {  if( i == ix1 || i == ix2 )
      {  continue;
        }
      scanned = i == n;
      if( !added && (scanned || inc < a[i] ) )
      {  b[ pos++ ] = inc;
         added = 1;
      }

      if( scanned )
      {  break;  }

      b[ pos++ ] = a[ i ];
   }
   doit( b, n - 1 );
}

int main( int argc, char** argv )
{  int a[] = {0,2,4,6,8,10};
   proc_array( a, 6, 2, 4, 9 );
}

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

#127713

On 11-03-18 22:51, Noob wrote:
> void update_array(int *arr, int n, int zi, int zj, int val)
> {
>     int new_arr[N];
>     int i, j = 0, done = 0;
> 
>     for (i = 0; i < n; +i)
>     {
> 	if (i == zi || i == zj) continue;
> 	int tmp = arr[i];
> 	if (!done && val < tmp) {
> 	    new_arr[j++] = val;
> 	    done = 1;
> 	}
>         new_arr[j++] = tmp;
>     }
>     new_arr[j] = val;
>     do_something(new_arr);
> }

Personally, I think the "do_something()" at the end is pretty ugly. Yes,
tail call optimization and all that, but really, your update_array
function should do just that: update the array. The caller can run the
do_something wherever it wants, and then there's a bigger chance you can
reuse the update_array function to do other things.

Anyway, this is essentially a merge sort, except that one of the two
sorted lists is a single element and the other is one from which you
drop a few items. You can therefore reduce it to something along the
following:

int src, dst;
assert(zi < n && zj < n);
for(src=0, dst=0; src<n; dst++) {
  while(src==zi || src==zj)) src++; // skip elements we don't care about
  if(val >= arr[src]) {
    new_arr[dst] = val;
    val = 0;
  } else {
    new_arr[dst] = arr[src++];
  }
}

Drops the "done" boolean, which drops a conditional jump every time you
go through the loop, so should be a bit faster. Additionally, every loop
does exactly one assignment, so this code goes through the loop one time
less than your code, so that's another conditional jump gone.

I think the code is a bit easier to read that way too, but YMMV.

(it's possible to drop the assert and move that to the while() statement
as "&& src < n", but then you add another conditional jump again to the
inner loop, which really isn't necessary)

Haven't actually tried benchmarking this though, so I might be wrong here.

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

#127736

On 12-03-18 23:32, Wouter Verhelst wrote:
> On 11-03-18 22:51, Noob wrote:
>> void update_array(int *arr, int n, int zi, int zj, int val)
>> {
>>     int new_arr[N];
>>     int i, j = 0, done = 0;
>>
>>     for (i = 0; i < n; +i)
>>     {
>> 	if (i == zi || i == zj) continue;
>> 	int tmp = arr[i];
>> 	if (!done && val < tmp) {
>> 	    new_arr[j++] = val;
>> 	    done = 1;
>> 	}
>>         new_arr[j++] = tmp;
>>     }
>>     new_arr[j] = val;
>>     do_something(new_arr);
>> }
> 
> Personally, I think the "do_something()" at the end is pretty ugly. Yes,
> tail call optimization and all that, but really, your update_array
> function should do just that: update the array. The caller can run the
> do_something wherever it wants, and then there's a bigger chance you can
> reuse the update_array function to do other things.
> 
> Anyway, this is essentially a merge sort, except that one of the two
> sorted lists is a single element and the other is one from which you
> drop a few items. You can therefore reduce it to something along the
> following:
> 

Oops.

This actually introduces an array overrun if zi == n-1 || zj == n-1. To
fix, add:

> int src, dst;
> assert(zi < n && zj < n);

  while (zi == n-1 || zj == n-1) n--;

That way you drop a few more loops and avoid the overrun (sorry, it was
late last night).

> for(src=0, dst=0; src<n; dst++) {
>   while(src==zi || src==zj)) src++; // skip elements we don't care about
>   if(val >= arr[src]) {
>     new_arr[dst] = val;
>     val = 0;
>   } else {
>     new_arr[dst] = arr[src++];
>   }
> }

Anyway,

> Haven't actually tried benchmarking this though, so I might be wrong here.

That still applies.

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

Page 2 of 3 — ← Prev page 1 [2] 3  Next page →

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

csiph-web