c - 获取 Spoj 中超出的时间限制

Question

我正在尝试解决这个问题http://www.spoj.com/problems/TSORT/但我收到此错误时间限制已超出。我的代码在我的计算机上编译和排序正确，但是当我提交到 spoj 时它返回此错误。

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



void random_shuffle(int arr[],unsigned long int tamanho)
{
    srand(time(NULL));
    int i, j, temp;
    for (i = tamanho - 1; i > 0; i--)
    {
        j = rand()%(i + 1);
        temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

void swap(int *a, int *b)
{
    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
}
int partion(int arr[], int p, int r)
{
    int pivotIndex = p + rand()%(r - p + 1); 
    int pivot;
    int i = p - 1;
    int j;
    pivot = arr[pivotIndex];
    swap(&arr[pivotIndex], &arr[r]);
    for (j = p; j < r; j++)
    {
        if (arr[j] < pivot)
        {
            i++;
            swap(&arr[i], &arr[j]);
        }

    }
    swap(&arr[i+1], &arr[r]);
    return i + 1;
}

void quick_sort(int arr[], int p, int q)
{
    int j;
    if (p < q)
    {
        j = partion(arr, p, q);
        quick_sort(arr, p, j-1);
        quick_sort(arr, j+1, q);
    }
}
int main()
{
    int  *arr;
    int size = 0;
    int n;
    int i = 0;    

    scanf("%d",&size);
    arr = (int*)malloc(size*sizeof(int));

    while(scanf("%d",&n) != EOF){
        arr[i++] = n;
    }

    random_shuffle(arr,size); 
    quick_sort(arr, 0, size-1); 
    for (i = 0; i < size; i++)
         printf("%d\n", arr[i]);

    return 0;

}

Answer 1

以下建议的代码可以干净地编译和链接

注意:它使用的是我尚未测试过的 OPs 算法。

为了加速代码:

1. 使用“fastRead()”函数而不是“scanf()”
2. 使用“fastWrite()”函数而不是“printf()”
3. 使用 3 个异或语句(作为宏)而不是“swap()”函数
4. 在编译器允许时将函数设置为“内联”
5. 使用 stdio.h 中的 'getchar_unlocked()'、'putchar_unlocked()' 而不是慢得多的 'getchar() 和 'putchar()'

现在建议的代码:

#include <stdio.h>


// prototypes
size_t partion( size_t arr[], size_t p, size_t r);
void quick_sort(size_t arr[], size_t p, size_t q);

void fastRead( size_t *a );
void fastWrite( size_t a );


size_t array[ 1000000 ];

#define swap( x, y ) \
        *(x) = *(x)^*(y);  \
        *(y) = *(y)^*(x);  \
        *(x) = *(x)^*(y);


inline void fastRead(size_t *a)
{
    int c=0;
    // note: 32 is space character
    while (c<33) c=getchar_unlocked();

    // initialize result value
    *a=0;

    // punctuation parens, etc are show stoppers
    while (c>47 && c<58)
    {
        *a = (*a)*10 + (size_t)(c-48);
        c=getchar_unlocked();
    }
    //printf( "%s, value: %lu\n", __func__, *a );
} // end function: fastRead


inline void fastWrite(size_t a)
{
    char snum[20];
    //printf( "%s, %lu\n", __func__, a );

    int i=0;
    do
    {
        // 48 is numeric character 0
        snum[i++] = (char)((a%10)+(size_t)48);
        a=a/10;
    }while(a>0);

    i=i-1; // correction for overincrement from prior 'while' loop

    while(i>=0)
    {
        putchar_unlocked(snum[i--]);
    }
    putchar_unlocked('\n');
} // end function: fastWrite


int main( void )
{
    size_t numEntries;
    fastRead(&numEntries);

    for( size_t i = 0; i<numEntries; i++ )
    {
        fastRead( &array[i++] );
    }

    quick_sort(array, 0, numEntries-1);

    for (size_t i = 0; i < numEntries; i++)
    {
         fastWrite( array[i]);
    }

    return 0;
} // end function: main


void quick_sort(size_t arr[], size_t p, size_t q)
{
    size_t j;

    if (p < q)
    {
        j = partion(arr, p, q);
        quick_sort(arr, p, j-1);
        quick_sort(arr, j+1, q);
    }
} // end function: quick_sort


size_t partion(size_t arr[], size_t p, size_t r)
{
    size_t pivotIndex = r >> 1;
    size_t pivot;
    size_t i = p - 1;
    size_t j;

    pivot = arr[pivotIndex];
    swap(&arr[pivotIndex], &arr[r]);

    for (j = p; j < r; j++)
    {
        if (arr[j] < pivot)
        {
            i++;
            swap(&arr[i], &arr[j]);
        }

    }
    swap(&arr[i+1], &arr[r]);
    return i + 1;
} // end function: partion

消除任何重复数字输出此代码块:

    for (size_t i = 0; i < numEntries; i++)
    {
         fastWrite( array[i]);
    }

可以替换为:

    // prime the 'pump'
    fastWrite( array[0] );
    size_t lastOutput = array[0];

    // 'pump' all the rest
    for (size_t i = 1; i < numEntries; i++)
    {
         if( lastOutput != array[i] )
         {
             fastWrite( array[i]);
             lastOutput = array[i];
         }
    }