Optimizing Code to less time complexity possible

  • (2 Pages)
  • +
  • 1
  • 2

16 Replies - 450 Views - Last Post: 11 October 2019 - 08:16 PM Rate Topic: -----

#1 FreddoMayano   User is offline

  • New D.I.C Head

Reputation: -2
  • View blog
  • Posts: 32
  • Joined: 11-October 19

Optimizing Code to less time complexity possible

Posted 11 October 2019 - 03:41 AM

extern short const_array[2000]
long fun(short x) {
static array[2000];
long res = 0;
for (int i=1999; i>0; i-) array[i] = array[i-1];
array[0] = x;
for (i=0; i<2000, i++) res += array[i]*const_array[i];
return res;
}

Hi guys,
writing to array is taking 5cycles, assigning and writing to variable takes 5cycles, other operation takes one cycle, assume that time of for loop itself is zero (ideal case), so the time complexity of this function that I calculated it is about 23n+6 (n is equal in my case to 2000), how do I reduce its time complexity more less? I tried to reduce its time complexity more and more and arrived to 18n, but I "reckon" we can arrive to about a half/quarter time complexity of 23n+6, any help/suggestion please?

thanks a lot !

Is This A Good Question/Topic? 0
  • +

Replies To: Optimizing Code to less time complexity possible

#2 Skydiver   User is online

  • Code herder
  • member icon

Reputation: 7095
  • View blog
  • Posts: 24,112
  • Joined: 05-May 12

Re: Optimizing Code to less time complexity possible

Posted 11 October 2019 - 03:57 AM

What are the contents of const_array? Are they under your control?

Also it looks like you are actually looking at the absolute number of operations, rather then the complexity. In time complexity you are already at O(n) regardless of 23n vs
18n.
Was This Post Helpful? 1
  • +
  • -

#3 FreddoMayano   User is offline

  • New D.I.C Head

Reputation: -2
  • View blog
  • Posts: 32
  • Joined: 11-October 19

Re: Optimizing Code to less time complexity possible

Posted 11 October 2019 - 04:27 AM

lets assume the arrays are including integers, about time complexity you're completely right(sorry about not including that in my question), I meant to reduce the exact and absolute number of operations ..

I didn't succeed to reduce the time complexity smaller than linear (o(n)) ..that's why Im posting here my question :)

but yeah, I'm looking to reduce the absolute operations number of my function/code as much as I can regarding to the time cycles that's given ...
Was This Post Helpful? 0
  • +
  • -

#4 Skydiver   User is online

  • Code herder
  • member icon

Reputation: 7095
  • View blog
  • Posts: 24,112
  • Joined: 05-May 12

Re: Optimizing Code to less time complexity possible

Posted 11 October 2019 - 04:39 AM

Asking for actual values in the const_array. How are the values initialized?
Was This Post Helpful? 0
  • +
  • -

#5 FreddoMayano   User is offline

  • New D.I.C Head

Reputation: -2
  • View blog
  • Posts: 32
  • Joined: 11-October 19

Re: Optimizing Code to less time complexity possible

Posted 11 October 2019 - 06:03 AM

Under my control , this is my choice to do whatever operations to reduce time complexity as far as I didn't change the code itself (not affecting/changing the output of the function) ..
Was This Post Helpful? 0
  • +
  • -

#6 Salem_c   User is offline

  • void main'ers are DOOMED
  • member icon

Reputation: 2389
  • View blog
  • Posts: 4,522
  • Joined: 30-May 10

Re: Optimizing Code to less time complexity possible

Posted 11 October 2019 - 10:54 AM

> for (int i=1999; i>0; i-) array[i] = array[i-1];
Getting rid of this, and keeping a suitable static index of where you are logically in the array might be better.

Copying the whole thing every time is probably bad.

Copying the whole thing backwards is also likely to be less optimal given most cache predictors favour going forwards in memory.
Was This Post Helpful? 1
  • +
  • -

#7 Skydiver   User is online

  • Code herder
  • member icon

Reputation: 7095
  • View blog
  • Posts: 24,112
  • Joined: 05-May 12

Re: Optimizing Code to less time complexity possible

Posted 11 October 2019 - 11:41 AM

Actually all that code that the OP presented can be narrowed down to:
extern short const_array[2000]
long fun(short x) {
    return x * const_array[0];
}



My reasoning behind this is that static variables are initialized to 0. So all the first for loop does is copy the 0's to the adjacent element. So we end up with just array[0] being assigned the value of x.

Zero times anything is zero. So the only multiplication that matters is the first element.
Was This Post Helpful? 1
  • +
  • -

#8 Skydiver   User is online

  • Code herder
  • member icon

Reputation: 7095
  • View blog
  • Posts: 24,112
  • Joined: 05-May 12

Re: Optimizing Code to less time complexity possible

Posted 11 October 2019 - 11:47 AM

Of course that is only true for the first call of fun(). On succeeding calls of fun(), the first element moves to the second element, and there is a new first element.

I suggest a circular queue implementation to skip the shifting of elements around as originally suggested by Salem_c.
Was This Post Helpful? 0
  • +
  • -

#9 FreddoMayano   User is offline

  • New D.I.C Head

Reputation: -2
  • View blog
  • Posts: 32
  • Joined: 11-October 19

Re: Optimizing Code to less time complexity possible

Posted 11 October 2019 - 11:49 AM

So @Skydriver the time complexity in your case is about half of 23n +6 right? I'm just wondering .. by the way you're right that I could change my code to what you wrote above, but in suspicious if we get the most optimal time complexity in your case (in your code)..
Was This Post Helpful? 0
  • +
  • -

#10 Skydiver   User is online

  • Code herder
  • member icon

Reputation: 7095
  • View blog
  • Posts: 24,112
  • Joined: 05-May 12

Re: Optimizing Code to less time complexity possible

Posted 11 October 2019 - 11:54 AM

I think this is part of the reason why modern programming techniques discourages side effects. It makes reasoning with the code harder when there are side effects. Assume that const_array is filled with 1's. The first time you call fun(5) you get back 5, but the second time you call fun(5) you get back 10. Doesn't make sense unless fun() were renamed RunningSum() or something that would hint that each call would change the return value even if given the same inputs.
Was This Post Helpful? 1
  • +
  • -

#11 FreddoMayano   User is offline

  • New D.I.C Head

Reputation: -2
  • View blog
  • Posts: 32
  • Joined: 11-October 19

Re: Optimizing Code to less time complexity possible

Posted 11 October 2019 - 12:19 PM

I appreciate your effort to help me, but I really didn't understand your last answer .. maybe provide examples that simplify your explanation ?
Was This Post Helpful? 0
  • +
  • -

#12 Skydiver   User is online

  • Code herder
  • member icon

Reputation: 7095
  • View blog
  • Posts: 24,112
  • Joined: 05-May 12

Re: Optimizing Code to less time complexity possible

Posted 11 October 2019 - 02:58 PM

Here is how I would implement things with a circular buffer

#define MAX_SIZE 2000

extern short const_array[MAX_SIZE];

long fun(short x)
{
    static short buffer[MAX_SIZE] = { 0 };
    static size_t head = 0;
    static size_t count = 0; 

    if (head == 0)
        head = MAX_SIZE;
    buffer[--head] = x;

    if (count < MAX_SIZE)
        count++;

    long res = 0;
    for (size_t i = 0, j = head; i < count; i++, j = (j + 1) % MAX_SIZE)
        res += buffer[j] * const_array[i];
    return res;
}


Was This Post Helpful? 0
  • +
  • -

#13 FreddoMayano   User is offline

  • New D.I.C Head

Reputation: -2
  • View blog
  • Posts: 32
  • Joined: 11-October 19

Re: Optimizing Code to less time complexity possible

Posted 11 October 2019 - 03:46 PM

but here the time complexity (absolute operation number) is the same as the prime code, am I wrong? in your code it's 23n

so we didn't reduce the time complexity ..we just changed the code :) !
Was This Post Helpful? 0
  • +
  • -

#14 FreddoMayano   User is offline

  • New D.I.C Head

Reputation: -2
  • View blog
  • Posts: 32
  • Joined: 11-October 19

Re: Optimizing Code to less time complexity possible

Posted 11 October 2019 - 03:56 PM

Hi @skydiver, Much appreciated, Understand everything !
Was This Post Helpful? 0
  • +
  • -

#15 Skydiver   User is online

  • Code herder
  • member icon

Reputation: 7095
  • View blog
  • Posts: 24,112
  • Joined: 05-May 12

Re: Optimizing Code to less time complexity possible

Posted 11 October 2019 - 06:04 PM

How did you come up with 23n operations for the code in post #12?
Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2