11

Please look at the following code to solve the same set of problem, I do not think that mentioning the problem would anyhow help the purpose, it's yet another iteration of the Josephus problem:

Solution 1:

import sys
from math import log

cases= int(sys.stdin.readline())
current= 0
while current < cases:
    current += 1
    n = int(sys.stdin.readline())
    print 2*(n - 2**(int(log(n,2))))+1

This solution solves the given 10 test cases in cumulative 1.0912 seconds and consumes 4360KiB of memory.

Solution 2:

def josephus_2( n ):
    from math import log
    return 2*(n - 2**(int(log(n,2))))+1

import sys
cases= int(sys.stdin.readline())
current= 0
while current < cases:
    current += 1
    n = int(sys.stdin.readline())
    print josephus_2( n )

this solution solves the same 10 test cases in a total of 1.0497 seconds and 640KiB of memory.

Being a Python n00b I was wondering, while according to the online judge I earn same points for both, but what makes the solution 2 more faster than 1 and much more memory efficient? I know that the time difference can sound very less, but at the same time ranks me first on the fastest solution, even faster than c/c++/perl submissions

Can this Screenshot help?

4

1 回答 1

1

在我以前的经验中，我记得我发现有时将计算部分放在函数（方法）中可能会提高性能：
我刚刚重新体验了使用以下简单代码：

n = 1000000
def compute(n):
    j = 0
    for i in xrange(n):
        j += 1

tic()
compute(n)
toc()

>>> 0.271 s

tic()
j = 0
for i in xrange(n):
    j += 1
toc()

>>> 0.849 s

结果显示第一个（使用计算）为 0.271 秒，而内联代码为 0.849 秒。这是显着的改进，而无需更改主要计算部分的任何内容！所以重点是使用一种方法可以提高性能。

以下是您可用于性能比较的代码：

from __future__ import division
from time import clock

def compute(n):
    j = 0
    for i in xrange(n):
        j += 1

n = 1000000
print 'solution (2) using a method call...'
t0 = clock()
compute(n)
print clock()-t0
#>>> ~0.2415...                              #faster (solution 2)

print 'solution (1) all inline code...'
t0 = clock()
j = 0
for i in xrange(n):
    j += 1
print clock()-t0
#>>> ~0.6169...                              #slower (solution 1)
于 2013-03-08T04:50:58.160 回答