为什么 tuple.index() 的性能与 list.index() 相似？

Question

我编写了一个简单的函数，它接收实现 .index() 的内容和要检查的字符列表。

我的假设是，由于字符串和元组都是不可变的，因此它们将具有相似的性能（或者至少，元组会优于列表）。相反，元组似乎等同于列表。这是为什么？

from string import ascii_lowercase
from random import randint
from timeit import Timer


def check_index(st, guesses):
    for i in guesses:
        st.index(i)

if __name__ == "__main__":
    num_checks = 10
    lst = [n for n in ascii_lowercase]
    st = ascii_lowercase
    tup = tuple(lst)
    guesses = [ascii_lowercase[randint(0, len(ascii_lowercase)-1)]
               for n in xrange(num_checks)]

    def run_string():
        check_index(st, guesses)

    def run_list():
        check_index(lst, guesses)

    def run_tuple():
        check_index(tup, guesses)

    t2 = Timer(run_list)
    print "List", t2.timeit()
    t3 = Timer(run_tuple)
    print "Tuple", t3.timeit()
    t = Timer(run_string)
    print "String", t.timeit()

示例运行 (Python 2.7.6)

List 5.26431703568
Tuple 5.28769207001
String 3.16058015823

List 5.30263400078
Tuple 5.17412590981
String 3.17718791962

List 5.21962976456
Tuple 5.35261583328
String 3.22652792931

Answer 1

tl;dr：字符串index调用在底层有很多优化，并且不必进行“丰富的比较”。lists 和tuples都必须这样做；可变性并不重要。

如果你打开stringobject.c，你可以看到那个index电话string_find_internal，哪个电话stringlib_find_slice，哪个电话stringlib_find，哪个电话fastsearch。

fastsearch评论中有指向此页面的链接，如果您感兴趣，请查看。它有一些关于如何在 python 中实现Boyer-Moore子串搜索的有趣内容。但这在 1 字符子字符串搜索中并不重要，它fastsearch明确表示特殊情况：

    } else if (mode == FAST_SEARCH) {
        for (i = 0; i < n; i++)
            if (s[i] == p[0])
                return i;
    }

非常紧的循环，并且紧循环在 C 中非常快。

好的，这涵盖了字符串。那么tuples和lists呢？

这次要简单得多；这是两种类型都必须执行的循环：

for (i = start; i < stop && i < Py_SIZE(self); i++) {
    int cmp = PyObject_RichCompareBool(self->ob_item[i], v, Py_EQ);
    if (cmp > 0)
        return PyInt_FromSsize_t(i);

==该循环必须执行PyObject_RichCompareBool循环中的每次迭代，而不仅仅是检查与 的相等性。我不会详细介绍代码（object.c如果您好奇的话，请查看），但本质上这必须进行一些类型检查，然后查看类型是否实现丰富的比较，然后调用该比较函数，检查它是否返回NotImplemented单例，最后返回比较。

因此，该循环是调用中完成的大部分工作index，列表和元组都必须完成它。字符串会作弊。