首页 文章

SPOJ在C中接受相同的算法，在Python中超出时间限制

提问于
浏览 次
3

我试图从SPOJ解决FCTRL问题 . 问题是在N中找到尾随零的数量！对于一些T测试用例 .

T ~ 1,00,000.
1 <= N <= 1000000000

我的问题很奇怪 . 如果我尝试以下C代码，它会被接受，时间为0.22秒，内存使用量为1.6M . 但是如果我提交等效的Python 3代码，它会说超出时间限制，内存使用量为11M .

C代码：

#include <stdio.h>

void fact_zeros(long int);

int main(void) {
    long int i,t,n;
    if (scanf("%ld",&t) > 0) {
        for (i=1;i<=t;i++) {
            if (scanf("%ld",&n) > 0) {
                fact_zeros(n);
            }
        }
    }
    return 0;
}

void fact_zeros(long int N) {
    long int zeros = 0;
    while (N>0) {
        N = N / 5;
        zeros += N;
    }
    printf("%ld\n",zeros);
}

Python 3代码：

"""
spoj11Factorial.py
This program calculates the number of zeroes at the 
end of the factorial of each number of the test case.
"""

def fact_zeroes( n ):
    count_5s = 0
    while (n > 0):
        n = n // 5
        count_5s += n
    return count_5s


T = int( input() )
while (T):
  T -= 1
  n = int( input() )
  zeroes = fact_zeroes( n )
  print( zeroes )

任何人都可以在Python代码中发现我正在做的不同/错误 . 它适用于我机器上的所有给定测试用例 .

谢谢 .

编辑：问题规格：

Added by:   Adrian Kosowski
Date:   2004-05-09
Time limit: 6s
Source limit:   50000B
Memory limit:   256MB
Cluster:    Pyramid (Intel Pentium III 733 MHz)
Languages:  All except: NODEJS PERL 6
Resource:   ACM Central European Programming Contest, Prague 2000
python c algorithm

1 回答

  • 5

    将此程序的速度提高一倍以上的一种非常简单的方法是转换：

    n = int( input() )

    至

    n = int( raw_input() )

    请注意raw_input()从输入中返回一个字符串，而input()在读取后在字符串上运行Python解释器 .

    在使用Python 2.7的计算机上，这将时间从1.6秒减少到0.7秒

    回复于

相关问题