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!

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

All those hacky macros for code fragments make me ill.

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

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

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.

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