0

有一次我写了一段 python 代码来计算反演。

只是为了好玩加上想看看 c 是否真的比运行时语言快得多，我用 c 编写了类似的 python 代码。

python代码运行时间不到3秒，

但我的 c 代码花了大约 8 秒。

谁能告诉我哪里做错了以及我应该如何更改/改进我的 C 代码？

谢谢！！

输入文件只是 100000 行数字，不重复，从 1 到 100000 以随机顺序排列。

蟒蛇代码：

import time

def lookup(arr, num):
    lower=0
    upper=len(arr)-1
    while 1:
        if arr[upper]==num:
            return upper
        mid=(upper+lower)/2
        if arr[mid]==num:
            return mid
        elif arr[mid]<num:
            lower=mid+1
        else:
            upper=mid

def main():
    time.clock()
    f=open("IntegerArray.txt", "r").read().strip().split('\n')
    array=[int(i) for i in f]
    array.reverse()
    s=sorted(array)
    v=0
    while(array):
        i=lookup(s, array.pop())
        v+=i
        s.pop(i)
    print v
    print time.clock()
    raw_input()

main()

C代码：

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

#define limit 100000

int comp(const void *, const void *);
void inversion(int *, int *, int);
int lookup(int *, int, int);

int main(void){
    FILE *f = fopen("IntegerArray.txt", "r");
    int n=0, array[limit], copy[limit];
    while(n<limit){
        fscanf(f, "%d", array+n);
        copy[n]=array[n];
        n++;
    }
    qsort(copy, limit, sizeof(int), comp);
    // int i;
    // for(i=limit-100;i<limit;i++)printf("%d %d\n", array[i], copy[i]);
    inversion(array, copy, limit);
    // getchar();
    return 0;
}

int comp(const void  *a, const void *b){
    return (*(int*)a>*(int*)b)?1:-1;
}

void inversion(int *a, int *b, int n){
    int c=0, index;
    unsigned int v=0;
    while(c<n){
        // if(c%1000==0)printf("%d %d\n", c, b[n-c-1]);
        index=lookup(b, *a, n-c);
        v+=index;
        if((n-c)/2<index)
            for(;index<n-c-1;index++)
                b[index]=b[index+1];
        else{
            for(;index>0;index--)
                b[index]=b[index-1];
            b++;
        }
        a++;
        c++;
    }
    printf("%u\n", v);
}

int lookup(int *arr, int num, int n){
    int lower=0, upper=n-1, mid;
    // if(arr[upper]==num)return upper;
    // if(arr[lower]==num)return lower;
    while(1){
        // printf("%d %d %d\n", lower, upper, num);
        mid=(lower+upper)/2;
        // if(lower==upper && arr[mid]!=num){
        //  printf("%d %d %d\n", lower, upper, num);
        //  exit(1);
        // }
        if(arr[mid]==num)return mid;
        else if(arr[mid]<num)
            lower=mid+1;
        else
            upper=mid;
    }
}
4

1 回答 1

2

在 Pythoninversion中，您有： 

s.pop(i)

在 C 中，您有：

if((n-c)/2<index)
    for(;index<n-c-1;index++)
        b[index]=b[index+1];
else{
    for(;index>0;index--)
        b[index]=b[index-1];
    b++;
}

对我来说似乎有很大的不同。
我不认为 Pythonpop通过复制所有元素来实现。

于 2012-07-05T06:31:19.727 回答