CODEWITHSUNDEEP
cfunctionrecursioniteration
user19617564
user19617564

Reputation:

How to improve recursive function in C?

i have a program with various recursive functions. I now need to optimize the code to run the program faster: i checked with profiler and, a part from the biggest function with lots of checks, i have two functions that require a lot of time every run. One (Unmarked_Nodes) is like this:

typedef struct node* tree;

struct node{
char* data;
tree left;
tree right;
int marker;
};

static int remaining = 0;

int main(){
...
}

int Unmarked_Nodes(tree root) {
  if (root != NULL) {
    Unmarked_Nodes(root->left);
    if (root->marker == 0)
      remaining++;
    Unmarked_Nodes(root->right);
  }
return remaining;
}

The other is similar but instead of the if cycle it has a printf of data. The other, however, is faster than this... why? Or instead: how can i improve the code to make it run faster? Thanks in advance

Upvotes: 1

Views: 224

Answers (2)

Fe2O3
Fe2O3

Reputation: 8344

In the absence of more information, it would seem that you likely "visit" the tree three times: once for 'marking' nodes (for whatever purpose), once to 'print' marked (or unmarked) nodes, and once more to reset those marks.

Presuming that 'marked nodes' are the interesting ones, consider using a dynamic array of pointers (malloc/realloc in suitable increments) to build a list of only those nodes, print from that list (no 2nd tree traversal), then free() the list (no 3rd tree traversal).

You wouldn't need to 'mark/unmark' anything. Interesting nodes added to the suggested list mean that those nodes are 'marked', and 'unmarked' when the list is erased.

You may need to consider if 'marking' may encounter unwanted duplicates.

Another suggestion is to consider transforming the tree into a list once it is filled. Then, use conventional binary search of that list to mark 'nodes', and a sweep through to erase marks (presuming the same list is to be reused multiple times.

Another suggestion relates to whether you are marking to include or to exclude from the print traversal. If marked nodes are included, then simply 'unmark' them as you print them. If marked nodes are excluded, then mark all those other unmarked nodes being printed that haven't previously been 'excluded' and remember whether '0' means 'marked' or if '1' means marked for the next time it comes to searching/marking.

Upvotes: 1

chux
chux

Reputation: 153348

Candidate improvements: might help a little although answer remains O(n).

Recurse less often

Loop inside the function for one of the children.

Avoid global

Simply not needed.

Use const

No so much a speed improvement, yet allows for use with constant data.

Avoid hiding pointers

int Unmarked_Nodes(const struct node *root) {
  int remaining = 0;
  while (root != NULL) {
    remaining += Unmarked_Nodes(root->left);
    if (root->marker == 0) {
      remaining++; 
    }
    root = root->right;
  } 
  return remaining;
}

Perhaps only recurse when both children are non-NULL. Test null-ness at the end of the loop since it is initially false for all recursive entry.

static int Unmarked_Nodes2r(const struct node *root) {
  int remaining = 0;
  do {
    if (root->marker == 0) {
      remaining++; 
    }
    if (root->left) {
      if (root->right) {
        remaining += Unmarked_Nodesr(root->right);
      }
      root = root->left;
      // continue;  // Could skip loop test.
    } else {
      root = root->right;
    }
  } while (root);
  return remaining;
}

int Unmarked_Nodes2(const struct node *root) {
  return root ? Unmarked_Nodes2r(root) : 0;
}

Upvotes: 2

Related Questions