logic

h/w · 12-24-2003, 07:13 PM

trying to optimize code here, and no using recursion.
hereis one way,

Code:

myfunc() {
  int a;
  if (a==0) {
     stmt1;
     stmt3;
     stmt2;
  }
  else {
     stmt1;
     stmt4;
     stmt2;
  }
}

heres's another:

Code:

myfunc() {
  int a;

  stmt1;
  if (a==0) {
     stmt3;
  }
  else {
     stmt4;
  }
  stmt2;
}

now, from the above, stmt3 and stmt4 are blocks inside a loop - something like:

Code:

for (start; condition; incr/decr) {
  if (var i > var j {}  // this could become    if (var i < var j) {}
}

the first one involves duplication of code (i would have a lot of lines which are just the same, except for maybe one conditional stmt), but it involves only one check at the beginnning, to decide which of the conditionals will be taken inside the for loop depending upon the value of 'a'.

the second one involves no duplication of code, but everytime the loop is true, a check is made to see the value of 'a'.

is there an alternate way for this where i can achieve a balance between efficiency in code-size and statements executed by my code?

thanks.

wapcaplet · 12-24-2003, 09:59 PM

Could you clarify a bit? Where is the loop, in relation to the rest of myfunc()?

h/w · 12-24-2003, 10:07 PM

ok, heres a sample code. sorting in either ascending/descending.

Code:

  // ascending
  if (sort_order == 0) {
    for (i = num_items - 1; i >= 0; i--) {	
      for (j = 1; j <= i ; j++) {
        if (dataset[j-1] > dataset[j])
          swap (&dataset[j-1], &dataset[j]); 
      }
    }
  }
  // descending
  else {
    for (i = num_items - 1; i >= 0; i--) {	
      for (j = 1; j <= i ; j++) {
        if (dataset[j-1] < dataset[j])
          swap (&dataset[j-1], &dataset[j]); 
      }
    }
  }

this is what i meant by the first algo i wrote above. the code is duplicated because of 1 conditional. i could have not duplicated by putting the check for sort_order inside the loop, but that is not good, as it will lead to n checks.
im sure there must be some other way to do it.
is there an alternate way for this where i can achieve a balance between efficiency in code-size and statements executed by my code?

i hope that clarifies my question a bit.
thanks.

wapcaplet · 12-24-2003, 10:29 PM

Ah, I see what you're saying. The only thing different between the two is the greater-than or less-than comparison. You're comparing (j) with (j-1) every time, so what you could do is replace the (j-1) with, say, (j+x) where x is either +1 or -1, depending on what sort order you want to do. That way, you can just use one kind of comparison. In one case (when x is +1), you'd be comparing (j) with the next-higher index; in the other (when x is -1), you'd be comparing with the next-lower index.

You'd have to do some other small manipulations to avoid off-by-one errors, to make sure j starts out and finishes with the right values each time.

Did that make sense?

edit: Also, if you're hoping to make this an efficient sort algorithm, I'd recommend using something other than bubble-sort. That's one of the slowest ways to sort! Do a google search on sorting, for other ideas.

h/w · 12-24-2003, 10:38 PM

hey, thanks.
well, not complete sense to me (maybe im a bit tired), but I'm failing to see how the array index manipulation can help in modifying the conditional to check the values at those array indices. its not really a comparison between a higher/lower index, as it is between the values between consecutive indices.

is that a tired question on my behalf? thanks man.

h/w · 12-24-2003, 10:39 PM

yes, that is bubblesort. i just posted that here cos its the shortest.

im lookin at O(nlogn) sorting algos now (done with n^2)

well, its really late here now, and i should head home. please write back with your suggestion on this.
wish y'all a merry christmas. see you day after now.

codedv · 12-25-2003, 05:54 AM

This is a very useful link. The source is in Java, but its nice to actually be able it see the different kinds of sort algorithms graphically:
http://www.cs.ubc.ca/spider/harrison...ting-demo.html

wapcaplet · 12-25-2003, 09:02 AM

What I meant is, you can convert this statement:

Code:

if (dataset[j-1] > dataset[j])

into this statement

Code:

if (dataset[j+1] < dataset[j])

as long as j begins and ends with the correct index (j must be one less in the second example, to avoid going out of bounds). In both cases, you're asking "is the current value greater than the next value?" The +1 in the second example is the value of "x" I suggested; you just make x = -1 in order to get the correct behavior for the descending sort.

h/w · 01-02-2004, 04:44 PM

thanks wapcaplet, i see what you meant, and have it working that way.
for some reason, i seem to be having fun just trying these algos out.