python的list和tuple

iyth888

　　列表是python中简单而重要的数据结构
　　list_sample = [1, 2, 3]
　　超预分配的量大概只有总量的八分之一，保证不太浪费的情况下，也有线性的摊分复杂度。
　　new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6)
　　当增加或删除都有可能引起allocated的变化，当目前的allocated满足
　　allocated >= newsize && newsize >= (allocated >> 1)
　　这个关系时，allocated不变，不然更新分配值
　　allocated = new_allocated + newsize
　　由于python列表中的元素可以是任意的对象。
　　在底层实现上，由于对象大小未知，并不能像数组那样连续排在内存里。
　　python列表维护了一个指针数组，每个指针指向不同的对象，
　　这也造成了一些弊端，例如列表中对象大小一样的时候就很亏了，浪费空间不说，
　　跟C的数组相比，它离散的对象位置不能很好地利用CPU高速缓存，造成了遍历需要更多的CPU周期。
　　当然也有优点，例如在某个位置insert一个新的元素时，只要挪动部分指针的值就OK了。
　　一些操作的时间复杂度：
　　append:O(len(append_str))
　　insert:O(len(str) + len(insert_str))
　　tuple与list有什么区别？最重要的区别就是tuple是immutable，而list是mutable，
　　那么也就是说tuple大小将不会改变，就不用像list那样搞预分配了，更节省内存。
　　很多人说tuple比list快，真的如此吗？

size = 1000000
a = []
for i in xrange(0, size):
a.append(i)
b = tuple(a)
for t in xrange(0, 32):
sum = 0
for e in b:
sum += e
　　分别遍历list和tuple，跑得的时间是6.925s和6.771s
　　从实测看来，这个结论是不明显的。
　　list和tuple在c实现上是很相似的，对于元素数量大的时候，
　　都是一个数组指针，指针指向相应的对象，找不到tuple比list快的理由。
　　但对于小对象来说，tuple会有一个对象池，所以小的、重复的使用tuple还有益处的。
　　为什么要有tuple，还有很多的合理性。
　　实际情况中的确也有不少大小固定的列表结构，例如二维地理坐标等；
　　另外tuple也给元素天然地赋予了只读属性。
　　认为tuple比list快的人大概是把python的tuple和list类比成C++中的数组和列表了。
　　参考
　　python源码