Can you optimize this code/algorithm even furthur?

[prahladyeri]

Well, this is part of an assignment where we have to work upon a problem and create a C program as a solution. The problem this: There is a bunch of guys standing in a row in sequence. The idea is that if I am taller than a person standing further to me, then I can exchange my place with his. So, we have to calculate how many total such exchanges are possible.

The input is a string array containing heights of the people with hash (#) as a splitter. eg. ("6#2", "5#5", "6#3", "3#3").
In above example person 1 (with 6.2 feet) is exchangeable with the one with 5.5 and 3.3, since he is taller than them - so total here is 2.
Similarly, the person 2 (5.5 ft) can exchange with person 4 (3.3 ft) - so total 1.
Lastly, the one with 6.3 can exchange with 3.3 - total again 1.

So grand total is 2+1+1=4. This is the value my function has to return. I've written the below algorithm which solves the problem at hand, but is not the most optimum. Our assignment servers have an automated system that compiles the code, and performs several performance tests on the fly and awards marks based on that - faster the code runs, the better. Multiple submissions are allowed. By optimizing until now, I've reached 99.99%, but can't seem to be able to get to 100%. I've tried some things like making the function inline, using bitwise shift (>>) instead of division, etc. but no results, its stuck at 99.99%. However, I know this could be optimized better as there are people who have received 100% marks.

Could you have a look at this and see if this can be optimized better for speed?

inline int get_height(char* input1[])
{
	int len=0,sum=0,ft,inc,j=0;
	int* narray = (int*)malloc(0*sizeof(int));
	char* s;
	
	while (strchr(*input1,(int)'#')!=NULL)
	{
		narray = (int*)realloc(narray,(len+1) * sizeof(int));
		
		s=(char*)malloc(strlen(*input1)*sizeof(char));
		//printf("len=%d sizeof=%d",strlen(*input1),sizeof(char));
		
		//narray[len] = 12* ( ft = atoi(strtok(strdup(*input1),"#")) );
		strcpy(s,*input1);
		narray[len] = 12* ( ft = atoi(strtok(s,"#")) );
		narray[len]+= inc = atoi(strtok(NULL,"#"));
		
		//validations:
		if (!(ft>=4 && ft<=7) || !(inc>=0 && inc<=11))
			return -1;
		
		for(j=len-1;j!=-1;j--)
		{
			if ( narray[len] < narray[j] )
				sum++; //interchange:
		}
		
		if (s!=NULL)
			free(s);
		
		len++;
		input1++;
	}
	
	free(narray);
	
	return sum;
};

[cire]

Your sample input will cause your get_height function to return -1, not 4, as the condition on line 20 will evaluate to true for "3#3".

You have a mistake on line 11 -- you don't allocate enough memory for the nul terminator.

s = malloc(strlen(*input1)+1) ; /* No need for a cast in C */

One thing you could do is to stop calling malloc and realloc every iteration of the loop. Another thing you could do is avoid using strtok/strcpy. Is the validation necessary?

[prahladyeri]

@cire - "Your sample input will cause your get_height function to return -1, not 4, as the condition on line 20 will evaluate to true for "3#3" ."
- This is just an example. There will be several inputs.

You have a mistake on line 11 -- you don't allocate enough memory for the nul terminator.
- Yes, I realized. But then, how come its working!!

s = malloc(strlen(*input1)+1) ; /* No need for a cast in C */

One thing you could do is to stop calling malloc and realloc every iteration of the loop. Another thing you could do is avoid using strtok/strcpy. Is the validation necessary?
- I use strtok to split the string which is in the format "5#2" (5 feet, 2 inches), so its necessary.

[htirwin]

Do you really need s? Do you really need to allocate n more than once?

[prahladyeri]

I need s because I want to pass it to strtok(). Because when I directly pass *input to it, it causes an error, (segmentation fault), thats why I copy it to a buffer called s, then pass s instead.

[prahladyeri]

If I don't use malloc() to s and then do strcpy(), I would have to use strdup() instead:

char* s = strdup(*input1);

which method do you think gives better performance ?

Also, I call realloc inside each loop is because I don't know the size of input1! array in advance - this is incremented by len variable and known only at the end. Hence, I have to keep allocating space to my parallel narray[] which is numeric inside this loop.

[htirwin]

I would suggest that you try and figure out a way to solve the problem without allocating any memory. If you can't do that, then at least minimize calls to malloc or realloc.

[ne555]

Your algorithm is O(n^2) always. It doesn't get advantage if the input is sorted (or partially sorted)
Instead of that, consider performing `insertion sort' counting the number of swaps.


scanf("%d#%d", &feet, &inches);

> I call realloc inside each loop is because I don't know the size of input1! array in advance
¿can't you compute it? ¿don't you have an estimate?

[htirwin]

Instead of that, consider performing `insertion sort' counting the number of swaps.

That wouldn't give you the solution.

[ne555]

> The idea is that if I am taller than a person standing further to me,
> then I can exchange my place with his.
> So, we have to calculate how many total such exchanges are possible.
In other words, how many people are taller than me and are at my left.

You maintain the sorter set of individuals to your left, and try to insert yourself in order.
The number of swaps is the individuals that are smaller, so n-swaps is what you want.