Improving the performance of a program in C

Question

I'm writing a program for an assignment, and my program is currently only about 30ms too slow. However, I'm not entirely sure how to speed up my program. I tried to precompute some of the functions inside my loops, but I'm not really sure it helped...

The purpose of the program is to receive a bunch of inputs and determine whether a specific number is the majority in the input, and as a follow-up determine any runners up.

An example input might be: 1 2 2 2 1 0

The program would output:

majority: 2
runner-up: 1

#include <stdio.h> 
#include <stdlib.h>

int majorityCheck (int length, int arrMajority[]);
int runnerCheck (int length, int arrRunner[]);

unsigned int var, x, y;

int majorityCheck(int length, int arr[]){ //checks for maj
    int var, x, y;
    for(x=0;x<length-1;x++){
        var=0;
        for(y=0;y<length-1;y++){
            if(arr[y]==arr[x]){
                var++;
            }
        }
        if(2*var>length-1){
            return arr[x];
        }
    }
    return -1;
}

int runnerCheck(int length, int arr[]){ //checks for runnerup
    for(x=0;x<length-1;x++){
        var=0;
        for(y=0;y<length-1;y++){
            if(arr[y]==arr[x]){
                var++; //var is just a random incrementing tool
            }
        }
        if(2*var<length-1 && 4*var>length-1){
            return arr[x];
        }
    }
    return -1;
}

int main(int argc, char *argv[])
{
    unsigned int input;
    int *list=malloc(sizeof(int));
    int size=1;
    int numRunner;

    while(scanf("%u", &input)){
        if(input==0){
            break;}
            list[size-1]=input;
            size++;
            list=(int*)realloc(list, size*sizeof(int));
        }

    int numMajority=majorityCheck(size, list);
    if(numMajority==(-1)){
        printf("majority: NONE");}
        else{
            numRunner=runnerCheck(size, list);

            if(numRunner==(-1)){
                printf("majority: %d\nrunner-up: NONE", numMajority);
                }else{
                    printf("majority: %d\nrunner-up: %d", numMajority, numRunner);
                }
            }
            return 0;
        }

Answer 1

To speed this up properly, first realise that you don't need to store the numbers but could store how many times each number has occurred instead, and that this can be done with very little expense (none of the overhead of malloc(), realloc() or building and iterating through linked lists). For a crude and untested example:

#define MAX_VALUE 1234

int occurrences[MAX_VALUE+1];

int main(int argc, char *argv[])
{
    unsigned int input;
    unsigned int total = 0;
    unsigned int currentMostFrequent = 0;
    unsigned int currentSecondMostFrequent = 0;

    while(scanf("%u", &input)){
        if(input==0){
            break;
        } else if(input > MAX_VALUE) {
            break;
        } else {
            total++;
            occurrences[input]++;
            if(occurrences[input] > currentSecondMostFrequent) {
                if(occurrences[input] > currentMostFrequent) {
                    currentSecondMostFrequent = currentMostFrequent;
                    currentMostFrequent = input;
                } else {
                    currentSecondMostFrequent = input;
                }
            }
        }
    }
    if(occurrences[currentMostFrequent] > total/2) {
        printf("majority: %d\n", currentMostFrequent);
        if(currentSecondMostFrequent > 0) {
            printf("runner up: %d\n", currentSecondMostFrequent);
        } else {
            printf("runner up: NONE\n");
        }
    } else {
        printf("majority: NONE\n");
        if(currentMostFrequent > 0) {
            printf("runner up: %d\n", currentMostFrequent);
        } else {
            printf("runner up: NONE\n");
        }
    }
 }

Answer 2

Apart from all the answers if we have the range of the number and all the input numbers are positive, then we can solve this problem in linear time.

We will count the occurrence of each number in an auxiliary array and then we will scan the auxiliary array to get the majority and runner-up element.

In this example, I'm assuming the range of the input number is 0-1000.

Drawbacks of this technique:

This could run in linear time but in terms of space complexity,
this technique is not that efficient if the range is too high. We need to know the range of input in advance to allocate the memory
for the auxiliary array. If all the elements are unique then this algorithm will give you any two random number unless you handle all the cases properly.

#include <stdio.h>

int main()
{
    int number,i;
    scanf("%d",&number);
    int num[number];

    for(i=0;i<number;i++)
        scanf("%d",&num[i]);

    //create an array of 1000 elements
    int size = 1000;
    int auxiliary[size];

    for(i=0;i<size;i++)
        auxiliary[i]=0; //initialize count with 0
    for(i=0;i<number;i++)
        auxiliary[num[i]]++;  //count the occurrence 

    int majority,runner_up;  

     majority = 0;
     runner_up = 0;  

    for(i=1;i<size;i++)
       {
            if(auxiliary[i]>auxiliary[majority])
            {
                majority = i;
            }

       }

   for(i=1;i<size;i++)
       {

            if(auxiliary[i]>auxiliary[runner_up] && i!=majority)
            {
                runner_up = i;
            }

       }   

       if(runner_up==0)
            {
                printf("MAJORITY>> %d",majority);
                return 0;
            }


      printf("MAJORITY >> %d , RUNNER UP>>%d",majority,runner_up);

    return 0;
}

Answer 3

First of all, you must realize that your two functions majorityCheck and runnerCheck are practically identical. They only differ by one line: the single if statement. In short, they do exactly the same work but return an expected value on different conditions.

Since you only have two expected values (majority and runner-up), you can surely imagine combining your functions into one that returns both of these values. How you return two values is your choice; you can return a structure representing a pair of int, or you can add "out" parameters to the function. The only part left is storing these values instead of directly returning from the function. Here is an example.

int majorityRunnerUpCheck(int array[], int length, int* majority, int* runnerUp) {
    int count, i, j;
    *majority = -1;
    *runnerUp = -1;

    // Note: if you use '<' (less than), then you want "length", not "length-1"
    for (i = 0; i < length; i++) {
        count = 0;
        // Note: here as well
        for (j = 0; j < length; j++) {
            if (array[i] == array[j]) {
                count++;
            }
        }
        // Note: and here, too;
        // otherwise you could have a majority with 3 out of 6
        // (unless you do want that)
        // Also, length/2 conveys the meaning better than var*2 (or count*2)
        if (count > length/2) {
            // Store the majority
            *majority = array[i];
        }
        // Note: are you sure you need the runner-up occurences to be more than a
        // fourth of the input? I don't think that's the definition of a runner-up...
        else if (count < length/2 && count > length/4) {
            // Store the runner-up
            *runnerUp = array[i];
        }
    }

    // Make the return value useful: let it be the number of expected values
    // you got, that is 2 for both, 1 for a majority but no runner-up, and 0
    // for no majority.
    if (*majority != -1) {
        if (*runnerUp != -1) {
            return 2;
        }
        return 1;
    }
    return 0;
}

Of course, this can be further improved. But it would require redesigning the algorithm. Here is what I would have done, inspired by counting-sort. I assume the values in your array are between 0 and 100. If that's not the case, you can still use some other inspiration, like radix-sort, or hash-sort (counting-sort but using a hash table instead of an array), or even bucket-sort...

int majorityRunnerUpCheck(int array[], int length, int* majority, int* runnerUp) {
    int counts[101] = {0};
    int i, r = 0;
    *majority = -1;
    *runnerUp = -1;

    for (i = 0; i < length; i++) {
        counts[array[i]]++;
        if (counts[array[i]] > length/2) {
            *majority = array[i];
            r+=2;
        } else if (counts[i] < length/2 && counts[i] > length/4) {
            *runnerUp = array[i];
            r++;
        }
    }

    return r != 0 ? r-1 : 0;
}

Answer 4

Alright so I basically solved this by precomputing the functions inside the loops and using #include <math.h>

For some reason that shaved almost a second off the execution of my program.

Answer 5

Here is what you could do:

1. Sort the array using merge sort.
2. Go through the array comparing two elements at a time. So first compare 0 with 1, then 1 with 2... Check if element n equals n-1. In doing so, determine how many times each number shows up. If you see a new number, set its count to 1 and if matches the number after it then increment its count. Otherwise, create a new count for the next number.

So, as an example, consider array 0, 1, 1. First you will look at value 0 (at index 0) and store it's count somewhere. Then you will compare it to 1 (at index 1) and see if they match. If they do, then increment the count for 0, otherwise, store the count of 1 as 1 in another variable. Since they don't match, you'll create a variable where you'll store the count of 1. Now repeat this process when comparing 1 at index 1 and 2... You'll end up with variables that hold counts for 0 and 1. You can just go through them to find the rankings of most occurrences.

You can use an array of structs that holds the number and its count if you want algorithm to be able to handle more than just the two highest counts.

On the other hand, if you know you will only need two numbers then you can just keep track of the numbers that have the two highest counts in four variables (firstNum, firstCount, secondNum, secondCount).