为什么Python字典中的字符串键读写速度比元组慢？

Question

我在尝试优化一个模拟树结构的程序速度时发现，把树的唯一地址存储为元组（Tuple），而不是字符串（String），在运行时速度明显更快。这个树结构是用字典（DICT）存储的，字典的键是坐标对（x,y）。

我想问的是，既然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()

谢谢！

Answer 1

我觉得速度差异主要是因为访问键的字符串格式化。

在writeTuples这个函数里，有这么一行代码：

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

这行代码创建了一个新的元组，并把它的值（x,y）赋值好，然后再传给k的访问器。

而在writeStrings这个函数里，有这么一行代码：

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

这行代码做的计算和writeTuples里的一样，但它还要处理字符串"%s,%s"的解析（这可能在编译时就完成了，我不太确定），然后还要从数字构建一个新的字符串（比如"12,15"）。我认为正是这个过程导致了运行时间的增加。

Answer 2

正如其他人所说，问题出在字符串格式化上。

这里有一个快速的版本，它提前计算了所有的字符串……

在我的电脑上，写字符串的速度比写元组快大约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)

Answer 3

测试的权重不公平（所以会有时间上的差异）。在你的 writeStrings 循环中，你调用 format 的次数是 writeTuples 循环的两倍，而在 readStrings 中，你调用它的次数则多得多。为了让测试更公平，你需要确保：

• 两个写入循环每次内部循环只调用一次 %
• readStrings 和 readTuples 每次内部循环要么调用一次 %，要么不调用。