c - 提高 C 程序的性能

Question

我正在为一项作业编写程序，目前我的程序只慢了大约 30 毫秒。但是，我不完全确定如何加快我的程序。我试图在我的循环中预先计算一些函数，但我不确定它是否有帮助...

该程序的目的是接收一堆输入并确定特定数字是否在输入中占多数，并作为后续确定任何亚军。

示例输入可能是:1 2 2 2 1 0

程序会输出:

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

这是你可以做的:

1. 使用合并排序对数组进行排序。
2. 遍历数组，一次比较两个元素。所以首先将 0 与 1 进行比较，然后将 1 与 2 进行比较... 检查元素 n 是否等于 n-1。这样做时，确定每个数字出现了多少次。如果您看到一个新数字，将其计数设置为 1，如果与它后面的数字匹配，则增加其计数。否则，为下一个数字创建一个新计数。

因此，作为示例，请考虑数组 0, 1, 1。首先，您将查看值 0(在索引 0 处)并将其计数存储在某处。然后将它与 1(在索引 1 处)进行比较，看看它们是否匹配。如果是，则增加 0 的计数，否则，将 1 的计数作为 1 存储在另一个变量中。由于它们不匹配，您将创建一个变量来存储 1 的计数。现在在比较索引 1 和 2 处的 1 时重复此过程...您最终会得到保存 0 和 1 计数的变量.您可以通过它们找到大多数事件的排名。

如果您希望算法能够处理的不仅仅是两个最高计数，则可以使用包含数字及其计数的结构数组。

另一方面，如果您知道您只需要两个数字，那么您可以只跟踪四个变量中具有两个最高计数的数字(firstNum，firstCount，secondNum，secondCount)。