11

同じ問題のセットを解決するために次のコードを見てください。問題に言及することが目的に役立つとは思わない、それはヨセフス問題のさらに別の反復です：

解決策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

このソリューションは、累積1.0912秒で指定された10個のテストケースを解決し、4360KiBのメモリを消費します。

解決策2：解決策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 )

このソリューションは、同じ10個のテストケースを合計1.0497秒と640KiBのメモリで解決します。

Python n00bである私は疑問に思っていましたが、オンラインジャッジによると、両方で同じポイントを獲得していますが、ソリューション2が1よりも高速で、メモリ効率がはるかに高い理由は何ですか？時間差は非常に少なく聞こえるかもしれませんが、同時に、c / c ++ / perlの送信よりもさらに高速で、最速のソリューションで私を最初にランク付けします

このスクリーンショットは役に立ちますか？

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 に答える