python&C实现数字位数计数的不同效率

Question

我试着写一个函数来计算数字位数，顺便说一下，我试着比较不同方法的效率。 1.lenstr（i）方法：

def nDigits(i):
    return len(str(i))
for i in range(100000):
    print nDigits(i)

大约需要143.75秒

2.log10方式：

^{pr2}$

大约需要144.35秒

3.划分方式：

def nDigits(i):
    t = 0
    while i > 0:
        t += 1
        i /= 10
    return t
for i in range(100000):
    print nDigits(i)

大约需要143.43秒

4.c中的划分方式：

#include<stdio.h>

int digits(int num){
    int i = 0;
    while (num > 0){
        i += 1;
        num /= 10;
    }
    return i;
} 

void main(){
    int i = 0;
    while (i < 100000){
        i += 1;
        printf("%d",digits(i));    
    }
}

大约需要0.07秒

是C比python好2000倍…还是python有更好的方法来计算数字位数。各位，帮帮我。在

Answer 1

那么慢？？如果您将for i in range(100000):更改为for i in xrange(100000):，则速度更快，至少在我的计算机上（1秒或2或3秒）。在

我怀疑是你使用range(100000)造成的

xrange效率更高，因为它不生成对象列表，一次只生成一个对象。在这种情况下，您应该喜欢它而不是range。在

编辑：在@cge提到这个问题后，我测试了您的原始代码（使用range(100000)），而且它也很快就完成了，在一两秒钟内，所以这可能不是您问题的原因（发生了一些可疑的事情，从您发布的代码中我看不出来），但是我建议您无论如何都使用xrange。在

Answer 2

简化测试用例并删除所有这些print：

import math

def num_digits1(n):
    return len(str(n))

def num_digits2(n):
    return int(math.log10(n)) + 1

def num_digits3(n):
    t = 0

    while n:
        t += 1
        n /= 10

    return t

以下是我的结果：

^{pr2}$

减去生成随机数所需的时间，我得到：

num_digits1  0.35 us
num_digits2  0.58 us
num_digits3  1.20 us

和我的C代码比较（我希望这是公平的）：

#include <stdlib.h>

int rand_int(int min, int max) {
    return min + (rand() / (double) RAND_MAX) / (max - min);
}

int num_digits(int num) {
    int i = 0;

    while (num > 0){
        i += 1;
        num /= 10;
    }

    return i;
} 

int main() {
    int i;

    for (i = 0; i < 10000000; i++) {
        num_digits(rand_int(1, 100000000));
    }

    return 0;
}

我运行它：

$ gcc test.c -o test
$ time ./test./test
0.15s user 0.00s system 97% cpu 0.154 total

我的时间是：

  0.154 s / 10,000,000
= 0.0154 us (0.0138 us with -O3)

C代码比Python解决方案快23倍，这似乎很正常。希望我的C随机数生成器可以工作。在

使用PyPy，我得到66.7 ns（不是us），它只慢了4.3倍。在

Answer 3

我认为你的瓶颈是打印声明。尝试将结果保存在列表中。在

def nDigits(i):
    return len(str(i))
results = []
for i in xrange(1000000):
    results.append(nDigits(i))
print len(results)

我使用了xrange而不是range，并添加了一个额外的0。它在我的机器上只需0.45秒。在

使用列表理解可以将时间缩短到0.37秒。在

^{pr2}$

除去函数调用开销可以将时间缩短到0.31秒。在

results = [len(str(i)) for i in xrange(1000000)]
print len(results)