which one of the following code is efficient
in [Learn C or C++]
|
From: kris on 23 Jan 2008 01:22 Hi everyone I was writing a simple c code and was struck judging the efficiency. The code snippets are as follows: struct test { int a; int b; } struct test1 { char name[2]; struct test *testptr; } struct test1 table[100]; case 1: ====== for(i= 0;i<100;i++) { if(table[i].testptr->a == 1) found = 1; } for suppose table[99].testptr->a = 1 here one case arises if the name starts with "GM" we need not check those entries like this case 2: ======= char char_name[]= "GM"; for(i= 0;i<100;i++) { if(strcmp(table[i].name,char_name) == 0) continue; if(table[i].testptr->a == 1) found = 1; } Now my doubt is in anyway case 2 is more efficient than case 1. since i think that we need to access the memory everytime in case 1 whereas in case 2 we reduce memory access by one step.
From: Alf P. Steinbach on 23 Jan 2008 01:55 * kris: > Hi everyone I was writing a simple c code and was struck judging the > efficiency. The code snippets are as follows: > > struct test > { > int a; > int b; > } > > struct test1 > { > > char name[2]; > struct test *testptr; > } > > struct test1 table[100]; > > case 1: > ====== > > for(i= 0;i<100;i++) > { > > if(table[i].testptr->a == 1) > found = 1; > } > > for suppose table[99].testptr->a = 1 > here one case arises if the name starts with "GM" we need not check > those entries > > like this > > case 2: > ======= > > char char_name[]= "GM"; > > for(i= 0;i<100;i++) > { > if(strcmp(table[i].name,char_name) == 0) > continue; > > if(table[i].testptr->a == 1) > found = 1; > } > > Now my doubt is in anyway case 2 is more efficient than case 1. > since i think that we need to access the memory everytime in case 1 > whereas in case 2 we reduce memory access by one step. The short technical answer is: measure, for the typical kind of data and other cases, on the required operating systems and computers. The most important, though, is to write correct code, and not try to optimize prematurely. Even correcting for syntax errors the above is /not/ correct code. It's code that won't work. For the "name" member doesn't have room for a two-character nullterminated string. Cheers, & hth., - Alf -- A: Because it messes up the order in which people normally read text. Q: Why is it such a bad thing? A: Top-posting. Q: What is the most annoying thing on usenet and in e-mail?
From: Jim Langston on 23 Jan 2008 06:31 kris wrote: > Hi everyone I was writing a simple c code and was struck judging the > efficiency. The code snippets are as follows: > > struct test > { > int a; > int b; > } > > struct test1 > { > > char name[2]; > struct test *testptr; > } > > struct test1 table[100]; > > case 1: > ====== > > for(i= 0;i<100;i++) > { > > if(table[i].testptr->a == 1) > found = 1; > } > > for suppose table[99].testptr->a = 1 > here one case arises if the name starts with "GM" we need not check > those entries > > like this > > case 2: > ======= > > char char_name[]= "GM"; > > for(i= 0;i<100;i++) > { > if(strcmp(table[i].name,char_name) == 0) > continue; > > if(table[i].testptr->a == 1) > found = 1; > } > > Now my doubt is in anyway case 2 is more efficient than case 1. > since i think that we need to access the memory everytime in case 1 > whereas in case 2 we reduce memory access by one step. Okay, it sounds like what you are attempting to do is to check some condition out of 100 elements, but you don't need to check if the name is GM. Now, if each structure had an array of 100 elements that you had to check, I.E. one name with 100 elements, then it would be faster if you checked to see if they were a GM first so not having to check the 100 elements. However, since each name has one number (in your layout) then you are gaining nothing to check their name. Notice, though, that you're missing a continue if it' found. I.E. Instead of: if(table[i].testptr->a == 1) found = 1; It should be if(table[i].testptr->a == 1) { found = 1; continue; } because once one is found, nothing is gained by continuing to check. But, the logic you proposed, not setting found if they are a GM, is not the same logic your original code has shown. In your orignial code found will be set to true if one of the a's is set to 1, if they are a GM or not. If you do NOT want to set found to true for GMs, then perhaps something like this: if (table[i].testptr->a == 1 && strcmp( "GM", table[i].name ) { found = 1; continue; } Notice, this will only check if the name is "GM" if a is equal to 1. Because of short circuiting and it being an and statement the compiler will not check the status of name if it doesn't have to. -- Jim Langston tazmaster(a)rocketmail.com
From: Bart van Ingen Schenau on 23 Jan 2008 13:49 kris wrote: > Hi everyone I was writing a simple c code and was struck judging the > efficiency. The code snippets are as follows: > > struct test > { > int a; > int b; > } > > struct test1 > { > > char name[2]; This array can only hold single character names/strings. To store a string, you need one byte more than the length of the string. This extra byte is needed to store the '\0' character that markes the end of the string. To store a name like "GM", you need char name[3]; > struct test *testptr; > } > > struct test1 table[100]; > > case 1: > ====== > > for(i= 0;i<100;i++) > { > > if(table[i].testptr->a == 1) > found = 1; > } > > for suppose table[99].testptr->a = 1 > here one case arises if the name starts with "GM" we need not check > those entries > > like this > > case 2: > ======= > > char char_name[]= "GM"; > > for(i= 0;i<100;i++) > { > if(strcmp(table[i].name,char_name) == 0) > continue; > > if(table[i].testptr->a == 1) > found = 1; > } > > Now my doubt is in anyway case 2 is more efficient than case 1. > since i think that we need to access the memory everytime in case 1 > whereas in case 2 we reduce memory access by one step. Which algorithm is more efficient is hard to say, because it depends on the actual comparisons that you need to make to determine if an element matches. Comparing two strings is a relatively expensive operation, because you may end up comparing all the characters of the two strings. But if it can save you a lot of comparisons, it might be worth it to do the string compare first. For example, if two 100 character strings must be equal to save you a single comparison of a pair of integers, then it is not worth it. In this case, I would do the integer compare first and, if it is still needed, the string compare afterwards. But, if comparing two 4 character strings can save you a 100 comparisons of integers, then doing the string compare first will be worth it. In general, when you have to do multiple compares to reach a decision, the most efficient order of the compares depends largely on the characteristics of the data you feed into the program. The most efficient algorithms are the ones that, for a typical data set, decide with the minimum number of comparisons that there is *not* a match. And integer or floating point comparison counts as 1, but a string compare counts as N, where N is the typical length of the strings that are compared. Bart v Ingen Schenau -- a.c.l.l.c-c++ FAQ: http://www.comeaucomputing.com/learn/faq c.l.c FAQ: http://c-faq.com/ c.l.c++ FAQ: http://www.parashift.com/c++-faq-lite/
From: Francis Glassborow on 24 Jan 2008 05:40
Bart van Ingen Schenau wrote: > But, if comparing two 4 character strings can save you a 100 comparisons > of integers, then doing the string compare first will be worth it. > I know I should not really be exposing the innocent to hacks but if the strings really are 4 char only and you are willing to spend a bit extra time actually using therm as strings consider: union fourchar { char bytes[5]; int32 value; } example; Now you can write the name with strcpy(example.bytes, "GMXS"); and you can compare it with an integer comparison: if(example.value == test.value) ... |