0

反転の計算を行うためのPythonコードを書いたことがあります。

そして、楽しみのために、c がランタイム言語よりも本当に速いかどうかを確認したいので、c で同様の python コードを書きました。

Python コードの実行には 3 秒もかかりませんでした。

しかし、私のCコードは約8秒かかりました。

どこが間違っていたのか、Cコードをどのように変更/改善すべきか教えてもらえますか?

ありがとうございました！！

入力ファイルは、1 から 100000 までのランダムな順序で繰り返されるのではなく、ちょうど 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

Python ではinversion、次のものがあります。 

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

私には大きな違いのように見えます。Pythonがすべての要素をコピーして
実装するとは思いません。pop

于 2012-07-05T06:31:19.727 に答える