python - Python辞書の文字列キーは、タプルよりも書き込み/読み取りが遅いのはなぜですか?

Question

ツリー構造を模倣するプログラムの速度を最適化しようとすると (「ツリー」はデカルト座標 x、y 座標のペアをキーとして DICT に格納されます)、一意のアドレスをタプルとしてディクショナリに格納することを発見しました。文字列よりも実行時間が大幅に短縮されます。

私の質問は、Python が辞書とハッシュの文字列キー用に最適化されている場合、この例でタプルを使用する方がはるかに高速なのはなぜですか? 文字列キーは、まったく同じタスクを実行するのに 60% 長くかかるようです。私の例で単純なものを見落としていますか？

私は質問の基礎としてこのスレッドを参照していました（および文字列の方が高速であるという同じ主張をする他のスレッドも同様です）：文字列を辞書のキーとして使用する方が常に高速ですか？

以下は、メソッドをテストして時間を計るために使用していたコードです。

import time

def writeTuples():
    k = {}
    for x in range(0,500):
        for y in range(0,x):
            k[(x,y)] = "%s,%s"%(x,y)
    return k

def readTuples(k):
    failures = 0
    for x in range(0,500):
        for y in range(0,x):
            if k.get((x,y)) is not None: pass
            else: failures += 1
    return failures

def writeStrings():
    k = {}
    for x in range(0,500):
        for y in range(0,x):
            k["%s,%s"%(x,y)] = "%s,%s"%(x,y)
    return k

def readStrings(k):
    failures = 0
    for x in range(0,500):
        for y in range(0,x):
            if k.get("%s,%s"%(x,y)) is not None: pass
            else: failures += 1
    return failures

def calcTuples():
    clockTimesWrite = []
    clockTimesRead = []
    failCounter = 0
    trials = 100

    st = time.clock()
    for x in range(0,trials):
        startLoop = time.clock()
        k = writeTuples()
        writeTime = time.clock()
        failCounter += readTuples(k)
        readTime = time.clock()
        clockTimesWrite.append(writeTime-startLoop)
        clockTimesRead.append(readTime-writeTime)

    et = time.clock()

    print("The average time to loop with tuple keys is %f, and had %i total failed records"%((et-st)/trials,failCounter))
    print("The average write time is %f, and average read time is %f"%(sum(clockTimesWrite)/trials,sum(clockTimesRead)/trials))
    return None

def calcStrings():
    clockTimesWrite = []
    clockTimesRead = []
    failCounter = 0
    trials = 100

    st = time.clock()
    for x in range(0,trials):
        startLoop = time.clock()
        k = writeStrings()
        writeTime = time.clock()
        failCounter += readStrings(k)
        readTime = time.clock()
        clockTimesWrite.append(writeTime-startLoop)
        clockTimesRead.append(readTime-writeTime)

    et = time.clock()
    print("The average time to loop with string keys is %f, and had %i total failed records"%((et-st)/trials,failCounter))
    print("The average write time is %f, and average read time is %f"%(sum(clockTimesWrite)/trials,sum(clockTimesRead)/trials))
    return None

calcTuples()
calcStrings()

ありがとう！

score 4 · Accepted Answer

テストは公平に重み付けされていません (したがって、タイミングの不一致が生じます)。ループ内でループ内formatの2 倍の呼び出しを行っており、で無限に多くの呼び出しを行っています。より公平なテストを行うには、次のことを確認する必要があります。writeStringswriteTuplesreadStrings

両方の書き込みループは、%内側のループごとに 1 つの呼び出しのみを行います
それと両方ともreadStrings、内部ループごとに 1readTuples回または 0 回の呼び出しを行います。%

score 1 · Accepted Answer

他の人が言ったように、文字列のフォーマットが問題です。

これは、すべての文字列を事前に計算する簡単なバージョンです...

私のマシンでは、文字列の書き込みはタプルの書き込みよりも約 27% 高速です。書き込み/読み取りは約 22% 高速です。

私はすぐにあなたのものをtimeitに再フォーマットして単純化しました。ロジックが少し異なる場合は、読み取りと書き込みの違いを計算できます。

import timeit

samples = []
for x in range(0,360):
   for y in range(0,x):
        i = (x,y)
        samples.append( ( i, "%s,%s"%i) ) 


def write_tuples():
    k = {}
    for pair in samples:
        k[pair[0]] = True
    return k

def write_strings():
    k = {}
    for pair in samples:
        k[pair[1]] = True
    return k


def read_tuples(k):
    failures = 0
    for pair in samples:
        if k.get(pair[0]) is not None: pass
        else: failures += 1
    return failures

def read_strings(k):
    failures = 0
    for pair in samples:
        if k.get(pair[1]) is not None: pass
        else: failures += 1
    return failures


stmt_t1 = """k = write_tuples()"""
stmt_t2 = """k = write_strings()"""
stmt_t3 = """k = write_tuples()
read_tuples(k)"""
stmt_t4 = """k = write_strings()
read_strings(k)"""


t1 = timeit.Timer(stmt=stmt_t1, setup = "from __main__ import samples, read_strings, write_strings, read_tuples, write_tuples")
t2 = timeit.Timer(stmt=stmt_t2, setup = "from __main__ import samples, read_strings, write_strings, read_tuples, write_tuples")
t3 = timeit.Timer(stmt=stmt_t3, setup = "from __main__ import samples, read_strings, write_strings, read_tuples, write_tuples")
t4 = timeit.Timer(stmt=stmt_t4, setup = "from __main__ import samples, read_strings, write_strings, read_tuples, write_tuples")

print "write tuples       : %s" % t1.timeit(100)
print "write strings      : %s" % t2.timeit(100)
print "write/read tuples  : %s" % t3.timeit(100)
print "write/read strings : %s" % t4.timeit(100)

score 0 · Accepted Answer

Core i5 1.8GHz マシンでコードを実行したところ、次の結果が得られました

0.076752vs.0.085863ループの文字列へのタプル
書き込み0.049446vs.0.050731
読む0.027299対。0.035125

そのため、タプルが勝っているように見えますが、書き込み関数で文字列変換を 2 回行っています。writeStringsに変更

def writeStrings():
    k = {}
    for x in range(0,360):
        for y in range(0,x):
            s = "%s,%s"%(x,y) 
            k[s] = s
    return k

0.101689vs.0.092957ループの文字列へのタプル
書き込み0.064933vs.0.044578
読む0.036748対。0.048371

最初に気付くことは、結果にはかなりのばらつきがあるということです。そのため、trials=100より大きなものに変更することをお勧めします。Python のtimeit場合はデフォルトで 10000 になると思います。やったtrials=5000

0.081944vs.0.067829ループの文字列へのタプル
書き込み0.052264vs.0.032866
読む0.029673対。0.034957

そのため、文字列バージョンの方が高速ですが、他の投稿で既に指摘されているように、問題があるのは辞書ルックアップではなく、文字列変換です。

score 0 · Accepted Answer

速度の違いは、アクセサーキーの文字列形式によるものだと思います。

writeTuples には、次の行があります。

        k[(x,y)] = ...

k のアクセサに渡す前に、新しいタプルを作成し、その値 (x,y) を割り当てます。

writeStrings には、次の行があります。

        k["%s,%s"%(x,y)] = ...

これは writeTuples と同じ計算をすべて行いますが、文字列 "%s,%s" を解析するオーバーヘッドもあります (これはコンパイル時に行われる可能性がありますが、よくわかりません)。しかし、新しい文字列を作成する必要もあります。数字から (例: "12,15")。これが走行時間の伸びにつながっていると思います。

python - Python辞書の文字列キーは、タプルよりも書き込み/読み取りが遅いのはなぜですか?

4 に答える 4

Related

Reference