code optimizatio

This is a discussion on code optimizatio within the C++ Programming forums, part of the General Programming Boards category; could anyone tell me why code 1 is slower than the second code- Code: #define sz(a) int((a).size()) #define pb push_back ...

  1. #1
    Registered User
    Join Date
    Jan 2008
    Posts
    30

    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!

  2. #2
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  3. #3
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,452
    All those hacky macros for code fragments make me ill.

    I lost interest in the rest of it at that point.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  4. #4
    Registered User
    Join Date
    Oct 2001
    Posts
    2,934
    >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.

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,295
    Quote Originally Posted by Salem View Post
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  6. #6
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by swoopy View Post
    >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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Enforcing Machine Code Restrictions?
    By SMurf in forum Tech Board
    Replies: 21
    Last Post: 03-30-2009, 07:34 AM
  2. Obfuscated Code Contest: The Results
    By Stack Overflow in forum Contests Board
    Replies: 29
    Last Post: 02-18-2005, 04:39 PM
  3. Obfuscated Code Contest
    By Stack Overflow in forum Contests Board
    Replies: 51
    Last Post: 01-21-2005, 03:17 PM
  4. Interface Question
    By smog890 in forum C Programming
    Replies: 11
    Last Post: 06-03-2002, 05:06 PM
  5. Replies: 0
    Last Post: 02-21-2002, 05:05 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21