# code optimizatio

• 07-08-2008
eklavya8
code optimizatio
could anyone tell me why code 1 is slower than the second code-
Code:

```#define sz(a) int((a).size()) #define pb push_back #define all(c) (c).begin(),(c).end() #define REP(i,n) for(i=0;i<n;++i) #define FOREACH(it,c) for(typeof((c).begin()) it=(c).begin();it!=(c).end();++it) using namespace std; vector <string> rel; vector <long long> sums(51,0),used(51,0); class CorporationSalary { public:         long long calc(int i) {                 long long sum=0,j;         REP(j,sz(rel[0]))         {                 if(rel[i][j]=='Y')                 {                 if(!used[j])                         sums[j]=calc(j);                         sum+=sums[j];                         }         }         if(sum==0)         {         sums[i]=1;         used[i]=1;         return 1;         }         else         {         used[i]=1;         return sum;         } }         long long totalSalary(vector <string>);                 }; long long CorporationSalary::totalSalary(vector <string> relations) { long long sum=0,i; rel.resize(sz(relations)); copy(all(relations),rel.begin()); REP(i,sz(relations)) {                 sum+=calc(i);                 } return sum;         }```

code 2

Code:

```#define FOR(i,a,b) for(typeof(a) i=a;i!=b;i++) #define REP(i,n) FOR(i,0,n) #define EACH(x,v) for(typeof(v.begin()) x=v.begin();x!=v.end();x++) #define EXISTS(f,x) ({int _=0; f if(x) _=1;_;}) #define pb push_back #define mp make_pair using namespace std;   class CorporationSalary { public:   long long totalSalary(vector <string>); }; long long dp[50];   long long foo(int i,vector<string> relations) {   long long ans=0;   REP(k,relations[i].length()) if(relations[i][k]=='Y'){ if(dp[k]!=-1) ans+=dp[k]; else {dp[k] = foo(k,relations); ans+=dp[k];} }   return ans==0? 1:ans; }   long long CorporationSalary::totalSalary(vector <string> relations) {   memset(dp,-1,sizeof(dp));   long long sal = 0;   int n = relations.size();   REP(i,n) sal += foo(i,relations);   return sal; }```

the first code to the best of my knowledge uses the same technique as the second but it does not complete some of the larger test cases in time.

cheers!
• 07-08-2008
matsp
Is this an entry for an obfuscated C++ competition? [Not that it would win - but all those macros that really doesn't make any sense other than PERHAPS saving a bit of typing - but I even doubt that for the code segments shown, as there are only a couple of occurrences of each macro]. Yes, I do realize that this is code snippets out of a bigger chunk of code, but those sort of "make my own language" is really horribly confusing to everyone who isn't intimately familiar with those macros - and replacing push_back with pb to save 7 letters worth of typing, when you can (in most editors) expand the current expression with one or two keypresses, is really not a good idea.

The code:
Code:

`memset(dp,-1,sizeof(dp));`
is also somewhat risky, as multiples of -1 bytes are not guaranteed to make long long values of -1 - seeing as there's only 50 entries, why not just make a little for-loop?

The second code is probably faster because it uses a single array to hold both "uses" and "sums", instead of two different ones - it makes the compiled code simpler, and thus easier for the compiler to optimize (as it requires only one register to walk the array).

The first code also appears to make a copy of relations into the variable rel [and why do the copy in this way, rather than as a straight string assignment? - it makes no sense], which the second code doesn't. rel being a global variable doesn't make matters better, since global variables have less possibility for optimization.

However, I would suggest that relations is passed as a const reference in all places, as that would improve the performance of the code, avoiding a copy of the string.

--
Mats
• 07-08-2008
Salem
All those hacky macros for code fragments make me ill.

I lost interest in the rest of it at that point.
• 07-08-2008
swoopy
>long long foo(int i,vector<string> relations)
You might want to pass relations as a const reference:
long long foo(int i,vector<string> &relations)

>could anyone tell me why code 1 is slower than the second code-
That's a difficult question to answer, since you're probably the only one who can understand the code, and you haven't explained what it does.
• 07-08-2008
iMalc
Quote:

Originally Posted by Salem
All those hacky macros for code fragments make me ill.

I lost interest in the rest of it at that point.

I second this. When someone uses a for-loop we can immediately know what the code does. When you hack up macros like REP it is a bugger of a job for anyone else to understand what's going on.

I you want us to spend time helping, then don't do this! As with Salem, I will also decline to help you at this stage.
• 07-09-2008
matsp
Quote:

Originally Posted by swoopy
>long long foo(int i,vector<string> relations)
You might want to pass relations as a const reference:
long long foo(int i,vector<string> &relations)

I did mention this...

As with everyone elses answers, I somewhat regret spending time on this, since it's HORRIBLE code.

--
Mats