2

在尝试优化模拟树结构的程序的速度时（“树”存储在 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()

谢谢！

4

4 回答 4

4

测试的权重不公平（因此存在时间差异）。format您在writeStrings循环中的调用次数是循环中的两倍，writeTuples并且在readStrings. 为了进行更公平的测试，您需要确保：

  • %两个写循环只对每个内部循环进行一次调用
  • 这readStrings两者都对每个内部循环readTuples进行一次或零次调用。%
于 2013-03-24T18:32:16.203 回答
1

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

这是一个预先计算所有字符串的快速版本......

在我的机器上，写字符串比写元组快 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)
于 2013-03-24T18:53:44.970 回答
0

我会说速度的差异是由于访问键的字符串格式。

在 writeTuples 你有这一行：

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

在传递给 k 的访问器之前，它会创建一个新元组并为其赋值 (x,y)。

在 writeStrings 你有这一行：

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

它执行与 writeTuples 中相同的所有计算，但也有解析字符串 "%s,%s" 的开销（这可能在编译时完成，我不确定）但它还必须构建一个新字符串从数字（例如“12,15”）。我相信正是这增加了运行时间。

于 2013-03-24T18:37:10.770 回答
0

我在 Core i5 1.8GHz 机器上运行了您的代码，结果如下

  • 0.076752与0.085863元组到字符串的循环
  • 写0.049446对比0.050731
  • 阅读0.027299对比0.035125

所以元组似乎赢了，但你在 write 函数中进行了两次字符串转换。更改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.101689与0.092957元组到字符串的循环
  • 写0.064933对比0.044578
  • 阅读0.036748对比0.048371

首先要注意的是结果有很大的变化，所以你可能想改成trials=100更大的，回想一下 python 的timeit默认值是 10000。我做了trials=5000

  • 0.081944与0.067829元组到字符串的循环
  • 写0.052264对比0.032866
  • 阅读0.029673对比0.034957

所以字符串版本更快，但正如其他帖子中已经指出的那样，它不是字典查找，而是字符串转换受到伤害。

于 2013-03-24T19:19:31.517 回答