1

readFile、prepDict、test の 3 つの関数で速度テストを行っています。テストは単純に prepDict(readFile) です。次に、timeit モジュールを使用してこれらを何度も実行しています。

ループ数を 10 倍にすると、関数 prepDict は ~100 倍長くかかりますが、関数 prepDict を使用する関数テストは 10 だけ増加します。

ここに関数とテストがあります。

def readFile(filepath):
    tempDict = {}
    file = open(filepath,'rb')
    for line in file:
        split = line.split('\t')
        tempDict[split[1]] = split[2]
    return tempDict

def prepDict(tempDict):
    for key in tempDict.keys():
        tempDict[key+'a'] = tempDict[key].upper()
        del tempDict[key]
    return tempDict

def test():
    prepDict(readFile('two.txt'))

if __name__=='__main__':
    from timeit import Timer
    t = Timer(lambda: readFile('two.txt'))
    print 'readFile(10000): ' + str(t.timeit(number=10000))

    tempDict = readFile('two.txt')
    t = Timer(lambda: prepDict(tempDict))
    print 'prepDict (10000): ' + str(t.timeit(number=10000))

    t = Timer(lambda: test())
    print 'prepDict(readFile) (10000): ' + str(t.timeit(number=10000))

    t = Timer(lambda: readFile('two.txt'))
    print 'readFile(100000): ' + str(t.timeit(number=100000))

    tempDict = readFile('two.txt')
    t = Timer(lambda: prepDict(tempDict))
    print 'prepDict (100000): ' + str(t.timeit(number=100000))

    t = Timer(lambda: test())
    print 'prepDict(readFile) (100000): ' + str(t.timeit(number=100000))

私が得る結果は次のとおりです。

readFile(10000): 0.61602914474
prepDict (10000): 0.200615847469
prepDict(readFile) (10000): 0.609288647286
readFile(100000): 5.91858320729
prepDict (100000): 18.8842101717
prepDict(readFile) (100000): 6.45040039665

何度も実行すると、同様の結果が得られます。prepDict 関数を使用しているにもかかわらず、prepDict(readFile) は 10 倍しか増加しないのに、なぜ prepDict は最大 100 倍増加するのですか?

two.txt は、次のデータ ポイントを含む表形式の区切りファイルです。

Item    Title   Hello2
Item    Desc    Testing1232
Item    Release 2011-02-03
4

3 に答える 3

3

ここでの問題は、prepDict関数が入力を拡張することです。順番に呼び出すたびに、処理するデータが増えます。そして、そのデータは直線的に増加するため、10000 回目の実行には最初の実行の約 10000 倍の時間がかかります。*

を呼び出すとtest、毎回新しいdictが作成されるため、時間は一定です。

prepDictこれは、テストを毎回 dict の新しいコピーで実行するように変更することで、非常に簡単に確認できます。

t = Timer(lambda: prepDict(tempDict.copy()))

ところで、prepDict実際には指数関数的に増加しているわけではありません** number、二次関数的です。一般に、何かが非常に直線的に成長していて、アルゴリズムのコストを見積もりたい場合、実際には 2 つ以上のデータ ポイントを取得する必要があります。


* これは正確ではありません文字列とハッシュ操作 (線形的に増加する) にかかる時間が、他のすべての操作 (すべて一定) にかかる時間よりも長くなり始めると、線形的に増加し始めます。

**ここでは指数関数的成長については何も言及していませんが、前の質問では言及したため、実際の問題で同じ不当な仮定を行った可能性があります。

于 2013-06-19T19:12:30.970 に答える
1

への呼び出しprepDictは、隔離された環境では発生していません。prepDict変更するたびtempDictにキーが少し長くなります。prepDictそのため、キーへの 10**5 回の呼び出しの後prepDictは、かなり大きな文字列になります。にprintステートメントを入れると、これを(大量に)見ることができますprepDict

def prepDict(tempDict):
    for key in tempDict.keys():
        tempDict[key+'a'] = tempDict[key].upper()
        del tempDict[key]
    print(tempDict)
    return tempDict

これを修正する方法は、各呼び出しprepDict(より一般的には、タイミングを計っているステートメント) が、タイミングを計っている次の呼び出し (またはステートメント) に影響を与えないようにすることです。abarnert はすでに解決策を示しています: prepDict(tempDict.copy()).

ところで、 a を使用for-loopしてコードの重複を減らすことができます。

import timeit
import collections    

if __name__=='__main__':
    Ns = [10**4, 10**5]
    timing = collections.defaultdict(list)
    for N in Ns:
        timing['readFile'].append(timeit.timeit(
            "readFile('two.txt')",
            "from __main__ import readFile",
            number = N))
        timing['prepDict'].append(timeit.timeit(
            "prepDict(tempDict.copy())",
            "from __main__ import readFile, prepDict; tempDict = readFile('two.txt')",
            number = N))
        timing['test'].append(timeit.timeit(
            "test()",
            "from __main__ import test",
            number = N))

    print('{k:10}: {N[0]:7} {N[1]:7} {r}'.format(k='key', N=Ns, r='ratio'))
    for key, t in timing.iteritems():
        print('{k:10}: {t[0]:0.5f} {t[1]:0.5f} {r:>5.2f}'.format(k=key, t=t, r=t[1]/t[0]))

次のようなタイミングが得られます

key       :   10000  100000 ratio
test      : 0.11320 1.12601  9.95
prepDict  : 0.01604 0.16167 10.08
readFile  : 0.08977 0.91053 10.14
于 2013-06-19T19:12:29.163 に答える
0

これは、をテストしているときにtempDictへのすべての呼び出しを再利用しているためです。指定されたディクショナリ内のすべての項目をループし、基本的に各文字列キーの長さを 1 ずつ増やすだけなので、最終的には非常に長いキーの束になります。進行するにつれて、文字列連結操作がますます巨大な文字列を使用/再作成するため、関数の速度が低下し始めます。prepDictprepDictprepDict

test毎回辞書を再初期化するので問題ありません。

于 2013-06-19T19:15:20.007 に答える