code optimizatio

**eklavya8** · 07-08-2008

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!

**matsp** · 07-08-2008

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

**Salem** · 07-08-2008

All those hacky macros for code fragments make me ill.

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

**swoopy** · 07-08-2008

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

**iMalc** · 07-08-2008

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.

**matsp** · 07-09-2008

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

Thread: code optimizatio

Thread Tools

Search Thread

Display

code optimizatio

Similar Threads

Enforcing Machine Code Restrictions?

Obfuscated Code Contest: The Results

Obfuscated Code Contest

Interface Question

Who will map the scan code (inserted by VKD_Force_keys) to virtual key code?