python - 为什么 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: String index 调用在底层进行了大量优化，不必进行“丰富的比较”。 list 和 tuple do 都必须这样做；可变性无关紧要。

---

如果你打开stringobject.c ，可以看到index调用了string_find_internal，后者调用了stringlib_find_slice，后者又调用了stringlib_find，后者又调用了快速搜索。

fastsearch 链接到 this page在其评论中，如果您有兴趣，请查看。关于如何 Boyer-Moore 有一些有趣的内容子字符串搜索是在 python 中实现的。但这在您的 1 字符子字符串搜索中并不重要，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 调用中完成的大部分工作，列表和元组都必须这样做。字符串会作弊。