为什么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

index这个函数会把每个元素都和你给定的对象进行比较。因为元组的存储方式和列表一样，所以比较的时间差不多。字符串比较起来更快，因为比较字符要比比较对象快。

Answer 2

总结：在调用字符串的 index 方法时，背后有很多优化，不需要进行“复杂比较”。而对于 list（列表）和 tuple（元组），它们确实需要进行这些比较；可变性并不影响这一点。

---

如果你打开 stringobject.c 文件，你会看到 index 调用了 string_find_internal，然后又调用了 stringlib_find_slice，接着是 stringlib_find，最后是 fastsearch。

fastsearch 在评论中链接了 这个页面，如果你感兴趣可以去看看。页面上有一些关于 Boyer-Moore 子串搜索在 Python 中是如何实现的有趣内容。但这对于你进行单字符子串搜索来说并不重要，因为 fastsearch 对此进行了特别处理：

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

这是一个非常紧凑的循环，而在 C 语言中，紧凑的循环执行得非常快。

好了，这部分讲完了字符串。那么 tuple 和 list 呢？

这次简单多了；这就是 两者 都需要执行的循环：

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 调用中大部分的工作，而列表和元组都需要执行这个循环。字符串则可以“作弊”。