c - Cでより高速なIOの他のオプションは何ですか

Question

私はマージソートを実装し、それをこの 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;
}

EDIT3：

[EDIT AND 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);
    }
}

merge1.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;
}

merge2.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 の両方に、merge-sort の 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

Answer 1

stdinファイル名を入力として使用するのではなく、Mats の回答を補足します。次に、ファイルを開きます (Windows の場合はバイナリ形式)。ファイルの長さ、malloc十分な大きさのバッファーを取得し、ファイル全体を読み取り、ファイルを閉じます。次に、バッファへの文字ポインタを使用して解析します。そうすれば、次の文字を取得するために関数呼び出しは必要ありません。それはスピードで打ち負かすのは難しいです。

整数を解析するためのコードは次のとおりです。

num = 0;
while(isdigit(*pc)){
  num = num*10 + (*pc++ - '0');
}

Answer 2

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;
    }
}

Answer 3

• 最適化問題では、経験則が最適です。各ステップに費やされた時間の数値を取得してみてください。ロード - ソート - など...そのためにプロファイラーを使用できます（gprofなど）。

• IO を高速化するには、scanf の呼び出しを減らすことを検討する必要があります。scanf の数が必要なため、この特定の部分に対してより良いアルゴリズムを設計できます。

• Scanf は多くのことを行い、最初の引数を解析してから、バイトを読み取り、フォーマットに変換します。より速く進みたい場合は、「データの問題」を使用していくつかのステップをスキップします。まず、N (数学) に対して数値定義を使用していることがわかります。第 2 に、すべてのバイトが数字またはセパレータであることがわかっています。これを使用できます。

そのため、ファイル記述子からバイトを読み取ることができる 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 時間が短縮されますが、メモリが増加します。バランスを取る必要があります。