尝试在 Python 中查找字符串的长度时获得不一致的结果(使用 timeit)

Question

我试图通过将字符串与不同的字符串进行比较来找到字符串的长度。Python按如下方式比较字符串:

if (op == Py_EQ) {
    /* Supporting Py_NE here as well does not save
       much time, since Py_NE is rarely used.  */
    if (Py_SIZE(a) == Py_SIZE(b)
        && (a->ob_sval[0] == b->ob_sval[0]
        && memcmp(a->ob_sval, b->ob_sval, Py_SIZE(a)) == 0)) {
        result = Py_True;
    } else {
        result = Py_False;
    }
    goto out;
}

在我看来(也许我错了)，比较长度不同的字符串应该比长度相同的字符串花费更少的时间。我已经建立了这个函数:

def find_length(string, possible_length = xrange(1, 33)):
    l = []
    for i in possible_length:
        temp = '*' * i
        l.append(timeit.timeit(lambda: temp == string, number=10**5))
    return l.index(max(l)) + 1

当像这样使用它时:print find_length('test')我期望得到4的结果，但相反我得到(在我运行它5次之后):20,10,26,22,8。首先，我想也许是因为我处理的时间太短，10 ^5是不够的，但它给出了相同的结果(不是20,10,26…但结果也不一致)。有人在我的代码/逻辑中发现错误吗?

Answer 1

您测试的字符串太短，无法说明测试长度和内容之间的速度差异。此外，通过测试第一个字符可以看出temp字符串是不相等的。

所以你要么只测试len(temp) == len(string)，否则你只添加一个测试来看看temp[0] == string[0]。这确实是一个非常小的差异。

使用长的随机字符串，并使用同一字符串的切片进行测试，使它们几乎等于:

>>> import random
>>> import string
>>> from timeit import timeit
>>> target = ''.join(random.choice(string.ascii_letters) for _ in range(10000))
>>> almost_equal = target[:-1]
>>> equal = almost_equal + target[-1]
>>> timeit(lambda: target == almost_equal)
0.11822915077209473
>>> timeit(lambda: target == equal)
0.48569512367248535

现在的区别在于测试一个10000个字符的字符串与一个9999个字符长的字符串之间的区别，并且除了在末尾缺少一个字符之外，它与相等，与测试一个完全相等的字符串之间的区别。第二次测试需要4倍多的时间。

通过测试一个相等的字符串，你遇到了最坏的情况;必须比较这10000个字符中的每一个字符，以确定字符串确实具有相同的值。

如果您希望通过对越来越长的字符串进行测试来推断字符串长度，并找到耗时最长的比较，那么您根本无法做到。仅仅测试长度和确定同样长的字符串在值上不同之间没有足够的区别，至少当仅从第一个字符检测它们不相等时没有足够的区别。