不同效率的數字數字計數與蟒蛇＆C

Question

我嘗試編寫一個函數來計算數字位數，順便說一下，我嘗試比較不同方式的效率。 1. lenstr（ⅰ）的方法：

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

約需143.75s

2.日誌10方式：

import math 
def nDigits(i): 
    if i > 0: 
     n = int(math.log10(i)) + 1 
    elif i == 0: 
     n = 1 
    else: 
     n = int(math.log10(-i)) + 2 
    return n 

for i in range(100000): 
    print nDigits(i) 

約需144.35s

3。劃分方式：

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

大約需要143.43s

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.07s

是對C比Python的更好的2000倍......或者是有python更好的方法來計數數字。 thx傢伙，PLZ幫助我。

Answer 1

我認爲你的瓶頸是印刷聲明。嘗試將結果保存在列表中。

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秒。

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

刪除函數調用開銷得到的時間降到0.31秒。

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

Answer 2

那慢？如果您將for i in range(100000):更改爲for i in xrange(100000):，則速度會更快，至少在我的計算機上（1秒或2或3）。

我懷疑是緩慢的由您的range(100000)

xrange更有效，因爲不是生成對象的列表，它只是產生一次一個對象使用造成的。在這種情況下，您應該優先於range。

編輯：在@cge提到這個問題後，我測試了你的原代碼（使用range(100000)），它在一兩秒內完成得相當快，所以這可能不是你問題的原因，我從你在這裏發佈的代碼中看不到），但我建議你無論如何都使用xrange。

Answer 3

簡化你的測試用例，並刪除所有這些print S的：

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 

這裏是我的結果：

>>> %timeit num_digits1(random.randint(1, 100000000)) 
100000 loops, best of 3: 1.64 us per loop 
>>> %timeit num_digits2(random.randint(1, 100000000)) 
100000 loops, best of 3: 1.87 us per loop 
>>> %timeit num_digits3(random.randint(1, 100000000)) 
100000 loops, best of 3: 2.49 us per loop 
>>> %timeit random.randint(1, 100000000) 
1000000 loops, best of 3: 1.29 us per loop 

減去它需要生成一個隨機數的時候，我得到：

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）爲num_digits1，它只是慢了4.3倍。