0

我实现了合并排序并将其用作此 codechef 问题的解决方案。这是提交的内容。代码放在下面。

我认为导致执行缓慢的问题是我的 IO 在main函数中很慢。我知道输入的元素数量，因此必须有一些更快的方式来读取输入，而不是我正在做的方式。

是否有更快的 IO 方法而不是我在main函数中使用的方法？我听说过使用缓冲区，fgets但sscanf我不知道它们是否更快。

任何代码示例都会有所帮助。

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

void merge_parts(int arr[], int length)
{
    int *ans;
    int i, j, k;
    int temp = length/2;

    ans = malloc(sizeof(int) * length);

    //This while and next if-else puts the merged array into temporary array ans
    for (j = temp, i = k = 0; (i < temp && j < length); k++){
        ans[k] = (arr[i] < arr[j]) ? arr[i++] : arr[j++];
    }

    if(i >= temp){
        while(j < length){
            ans[k++] = arr[j++];
        }
    }
    else{
        while(i < temp){
            ans[k++] = arr[i++];
        }
    }

    //This while loops puts array ans into original array arr
    for(i = 0; i < length; i++){
        arr[i] = ans[i];
    }

    free(ans);
}

void merge_sort(int arr[], int length)
{
    if(length > 1)
    {
        merge_sort(&arr[0], (length/2));
        merge_sort(&arr[length/2], (length - length/2));
        merge_parts(arr, length);
    }
}

int main()
{
    int length;
    int *arr;
    scanf("%d", &length);
    arr = malloc(sizeof(int) * length);

    for(int i = 0; i < length; i++)
        scanf("%d", &arr[i]);

    merge_sort(arr, length);

    for(int i = 0; i < length; i++)
        printf("%d ", arr[i]);

    free(arr);
    return 0;
}

编辑3：

[我删除了 EDIT 和 EDIT2 因为它们不再相关]

我正在使用的 merge_sort 算法

void merge_parts(int arr[], int length)
{
    int ans[length];
    int i, j, k;
    int temp = length/2;
    //This while and next if-else puts the merged array into temporary array ans
    for (j = temp, i = k = 0; (i < temp && j < length); k++){
        ans[k] = (arr[i] < arr[j]) ? arr[i++] : arr[j++];
    }

    if(i >= temp){
        while(j < length){
            ans[k++] = arr[j++];
        }
    }
    else{
        while(i < temp){
            ans[k++] = arr[i++];
        }
    }

    //This while loops puts array ans into original array arr
    for(i = 0; i < length; i++){
        arr[i] = ans[i];
    }
}

void merge_sort(int arr[], int length)
{
    if(length > 1)
    {
        merge_sort(&arr[0], (length/2));
        merge_sort(&arr[length/2], (length - length/2));
        merge_parts(arr, length);
    }
}

合并1.c

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

#define SORTING_ALGO_CALL merge_sort

char buffer[4096];
int bufcount;
int bufpos;

int get_next_char()
{
    if (!bufcount)
    {
        bufcount = fread(buffer, 1, 4096, stdin);
        bufpos = 0;
        if (!bufcount){
            return EOF;
        }
    }
    bufcount--;
    return buffer[bufpos++];
}

int readnum()
{
    int res = 0;
    char ch;
    do
    {
        ch = get_next_char();
    } while (!isdigit(ch) && ch != EOF);

    if (ch == EOF){
            return 0xbaadbeef;    // Don't expect this to happen.
    }

    do
    {
        res = (res * 10) + ch - '0';
        ch = get_next_char();
    } while(isdigit(ch));
    return res;
}


int main()
{
    clock_t time1, time2;
    double time_taken;

//FIRST READ
    time1 = clock();

    int length = readnum();
    while (length < 1)
    {
        printf("\nYou entered length = %d\n", length);
        printf("\nEnter a positive length: ");
        length = readnum();
    }

//SECOND READ, PRINT AND NEXT FIRST READ
    time2 = clock();
    time_taken = (double)(time2 - time1) / CLOCKS_PER_SEC;
    printf("\nReading length = %f\n", time_taken);
    time1 = clock();

    int *arr;
    if ((arr = malloc(sizeof(int) * length)) == NULL)
    {
        perror("The following error occurred");
        exit(-1);
    }

//SECOND READ, PRINT AND NEXT FIRST READ
    time2 = clock();
    time_taken = (double)(time2 - time1) / CLOCKS_PER_SEC;
    printf("\nAllocating array = %f\n", time_taken);
    time1 = clock();

    for (int i = 0; i < length; i++){
        arr[i] = readnum();
    }

//SECOND READ, PRINT AND NEXT FIRST READ
    time2 = clock();
    time_taken = (double)(time2 - time1) / CLOCKS_PER_SEC;
    printf("\nReading array = %f\n", time_taken);
    time1 = clock();

    SORTING_ALGO_CALL(arr, length);

//SECOND READ, PRINT AND NEXT FIRST READ
    time2 = clock();
    time_taken = (double)(time2 - time1) / CLOCKS_PER_SEC;
    printf("\nSorting array = %f\n", time_taken);
    time1 = clock();
/*
    for (int i = 0; i < length; i++){
        printf("%d ", arr[i]);
    }
*/
//SECOND READ, PRINT AND NEXT FIRST READ
    time2 = clock();
    time_taken = (double)(time2 - time1) / CLOCKS_PER_SEC;
    printf("\nPrinting Sorted array = %f\n", time_taken);
    time1 = clock();

    free(arr);

//SECOND READ, PRINT
    time2 = clock();
    time_taken = (double)(time2 - time1) / CLOCKS_PER_SEC;
    printf("\nFreeing array = %f\n", time_taken);

    return 0;
}

合并2.c

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

#define SORTING_ALGO_CALL merge_sort

int main()
{
    clock_t time1, time2;
    double time_taken;

//FIRST READ
    time1 = clock();

    int length;
    scanf("%d", &length);
    while (length < 1)
    {
        printf("\nYou entered length = %d\n", length);
        printf("\nEnter a positive length: ");
        scanf("%d", &length);
    }

//SECOND READ, PRINT AND NEXT FIRST READ
    time2 = clock();
    time_taken = (double)(time2 - time1) / CLOCKS_PER_SEC;
    printf("\nReading length = %f\n", time_taken);
    time1 = clock();

    int *arr;
    if ((arr = malloc(sizeof(int) * length)) == NULL)
    {
        perror("The following error occurred");
        exit(-1);
    }

//SECOND READ, PRINT AND NEXT FIRST READ
    time2 = clock();
    time_taken = (double)(time2 - time1) / CLOCKS_PER_SEC;
    printf("\nAllocating array = %f\n", time_taken);
    time1 = clock();

    for (int i = 0; i < length; i++){
        scanf("%d", &arr[i]);
    }

//SECOND READ, PRINT AND NEXT FIRST READ
    time2 = clock();
    time_taken = (double)(time2 - time1) / CLOCKS_PER_SEC;
    printf("\nReading array = %f\n", time_taken);
    time1 = clock();

    SORTING_ALGO_CALL(arr, length);

//SECOND READ, PRINT AND NEXT FIRST READ
    time2 = clock();
    time_taken = (double)(time2 - time1) / CLOCKS_PER_SEC;
    printf("\nSorting array = %f\n", time_taken);
    time1 = clock();
/*
    for (int i = 0; i < length; i++){
        printf("%d ", arr[i]);
    }
*/
//SECOND READ, PRINT AND NEXT FIRST READ
    time2 = clock();
    time_taken = (double)(time2 - time1) / CLOCKS_PER_SEC;
    printf("\nPrinting Sorted array = %f\n", time_taken);
    time1 = clock();

    free(arr);

//SECOND READ, PRINT
    time2 = clock();
    time_taken = (double)(time2 - time1) / CLOCKS_PER_SEC;
    printf("\nFreeing array = %f\n", time_taken);

    return 0;
}

merge1.c 和 merge2.c 都包含合并排序的 2 个函数。

我用于为 2 个文件生成最坏情况（递减顺序）输入的文件。

#include<stdio.h>

int main()
{
    int j = 100000;
    printf("%d\n", j);
    for(int i = j; i > 0; i--)
        printf("%d\n", i);

    return 0;
}

merge1.c 的计时结果

Reading length = 23.055000

Allocating array = 0.000000

Reading array = 0.010000

Sorting array = 0.020000

Printing Sorted array = 0.000000

Freeing array = 0.000000

merge2.c 的计时结果

Reading length = 22.763000

Allocating array = 0.000000

Reading array = 0.020000

Sorting array = 0.020000

Printing Sorted array = 0.000000

Freeing array = 0.000000
4

4 回答 4

2

您几乎可以scanf通过编写自己的小函数来读取数字来击败。

如果所有数字都由decimal非数字的东西分隔，这将起作用：

 char buffer[4096]; 
 int bufcount;
 int bufpos;

 int get_next_char()
 {
     if (!bufcount)
     {
         bufcount = fread(buffer, 1, 4096, stdin);
         bufpos = 0;
         if (!bufcount){
            return EOF;
         }
     }
     bufcount--;
     return buffer[bufpos++]; 
 }


 int is_digit(int ch)
 {
     if (ch >= '0' && ch <= '9')
        return 1;
     return 0;
 }

 int readnum()
 {
     int res = 0;
     int ch;
     do
     {
         ch = get_next_char();
     } while(!is_digit(ch) && ch != EOF);
     if (ch == EOF)
     {
        return 0xbaadbeef;    // Don't expect this to happen. 
     }
     do
     {
         res = (res * 10) + (ch - '0');
         ch = get_next_char();
     } while(is_digit(ch));
     return res;
 }

scanf 中的代码比这复杂得多，并且很可能调用getcor fgetc，这比上面的代码效率要低一些。但是，值得准确衡量您在哪里花费时间。打印每个函数的时间作为输出的一部分。

于 2013-07-06T23:58:03.573 回答
1

我会通过使用stdin文件名作为输入来补充 Mats 的答案，而不是使用 。然后打开文件（如果在 Windows 上，则为二进制格式）。获取文件长度，malloc足够大的缓冲区，将整个文件读入其中，然后关闭文件。然后我会使用一个字符指针解析到缓冲区。这样，获取下一个字符不需要函数调用。速度很难被击败。

解析整数的代码是：

num = 0;
while(isdigit(*pc)){
  num = num*10 + (*pc++ - '0');
}
于 2013-07-07T01:30:34.683 回答
0 
static char buff[8*1000000];
int i, length, blen;
int *ap, *p;
int n = 0;
char ch, *cp = buff;

scanf("%d%*c", &length);
p = ap = malloc(sizeof(*ap) * length);

blen = fread(buff, 1, 8*1000000, stdin);
while(blen--){
    if(isdigit(ch=*cp++)){
        n = n * 10 + ch - '0';
    } else {
        *p++ = n;
        n = 0;
    }
}
于 2013-07-07T10:34:41.083 回答
0

  • 在优化问题中，经验法则是最好的。尝试获取每一步所花费时间的数值。加载-排序-等...您可以为此使用分析器（例如gprof）。

  • 为了加快您的 IO，您应该考虑减少对 scanf 的调用。由于您有 scanf 要求的数量，您可以为这个特定部分设计更好的算法。

  • scanf 做了很多事情，解析第一个 arg，然后读取字节并将其转换为格式。如果我们想走得更快，我们将使用“数据问题”来跳过一些步骤。首先，我们知道我们只是在 N（数学）上使用数字定义。其次，我们知道每个字节都是数字或分隔符。我们可以使用这个。

所以我们使用 read() 系统调用，它可以从文件描述符中读取一些字节。标准输入的文件描述符在操作系统之间变化，但通常为 0。

宏算法可以是：

index = 0
buffer = new array[10000];
numberOfByteRead = 1
while there is byte that have been read at last call of read.
      numberOfByteRead = read said 10000 byte to buffer;
      parse the buffer
;;

parse(buffer,numberOfByteRead)
for all true byte in buffer :
   switch (buffer[0])
      case '0': { the mathematical operation on arr[index] that fit for '0'; break;  }
      case '1': { ... break;}
      case ' ': {index++; break;}
;;

代码不是一个真正有趣的部分，但比 scanf 更快。大于 10000 的值会减少 IO 时间，但会增加内存。你必须平衡。

于 2013-07-06T17:40:06.933 回答