| 操作 | 复杂度 |
|---|---|
| 复制 | O(N) |
| 添加元素(在尾部添加) | O(1) |
| 插入元素(在指定位置插入) | O(N) |
| 获取元素 | O(1) |
| 修改元素 | O(1) |
| 删除元素 | O(N) |
| 遍历 | O(N) |
| 获取长度为k的切片 | O(k) |
| 删除切片 | O(N) |
| 列表扩展 | O(k) |
| 测试是否在列表中 | O(N) |
| min()/max() | O(n) |
| 获取列表长度 | O(1) |
要习惯用列表推导，因为这更加高效和简短，涉及的语法元素少。在大型的程序中，这意味着更少的错误，代码也更容易阅读。
>>>[i for i in range(10) if i % 2 == 0] [0, 2, 4, 6, 8]
1.使用enumerate.在循环使用序列时，这个内置函数可以方便的获取其索引：
for i, element in enumerate(['one', 'two', 'three']): print(i, element)
result：
0 one 1 two 2 three
2.如果需要一个一个合并多个列表中的元素，可以使用zip()。对两个大小相等的可迭代对象进行均匀遍历时，这是一个非常常用的模式：
for item in zip([1, 2, 3], [4, 5, 6]): print(item)
(1, 4) (2, 5) (3, 6)
3.序列解包
#带星号的表达式可以获取序列的剩余部分 >>>first, second, *reset = 0, 1, 2, 3 >>>first 0 >>>second 1 >>>reset [2, 3]
字典是python中最通用的数据结构之一。dict可以将一组唯一的键映射到相应的值。
我们也可以用前面列表推导的方式来创建一个字典。
squares = {number: number**2 for number in range(10)}
print(squares)
result：
{0: 0, 1: 1, 2: 4, 3: 9, 4: 16, 5: 25, 6: 36, 7: 49, 8: 64, 9: 81}
在遍历字典元素时，有一点需要特别注意。字典里的keys(), values()和items()3个方法的返回值不再是列表，而是视图对象（view objects）。
keys(): 返回dict_keys对象，可以查看字典所有键
values():返回dict_values对象，可以查看字典的所有值
items():返回dict_items对象，可以查看字典所有的{key, value}二元元组。
视图对象可以动态查看字典的内容，因此每次字典发生变化的时候，视图都会相应的改变，见下面这个例子：
words = {'foo': 'bar', 'fizz': 'bazz'}
items= words.items()
words['spam'] = 'eggs'
print(items)
result：
dict_items([('foo', 'bar'), ('fizz', 'bazz'), ('spam', 'eggs')])
视图无需冗余的将所有值都保存在内存中，像列表那样。但你仍然可以获取其长度（使用len）,也可以测试元素是否包含在其中（使用in子句）。当然，视图是迭代的。
CPython使用伪随机探测(pseudo-random probing)的散列表(hash table)作为字典的底层数据结构。由于这个实现细节，只有可哈希的对象才能作为字典的键。
Python中所有不可变的内置类型都是可哈希的。可变类型（如列表，字典和集合）就是不可哈希的，因此不能作为字典的键。
字典的三个基本操作（添加元素，获取元素和删除元素）的平均事件复杂度为O(1)，但是他们的平摊最坏情况复杂度要高得多，为O(N).
| 操作 | 平均复杂度 | 平摊最坏情况复杂度 |
|---|---|---|
| 获取元素 | O(1) | O(n) |
| 修改元素 | O(1) | O(n) |
| 删除元素 | O(1) | O(n) |
| 复制 | O(n) | O(n) |
| 遍历 | O(n) | O(n) |
还有一点很重要，在复制和遍历字典的操作中，最坏的复杂度中的n是字典曾经达到的最大元素数目，而不是当前的元素数目。换句话说，如果一个字典曾经元素个数很多，后来又大大减小了，那么遍历这个字典可能会花费相当长的事件。
因此在某些情况下，如果需要频繁的遍历某个词典，那么最好创建一个新的字典对象，而不是仅在旧字典中删除元素。
使用字典的常见陷阱就是，它并不会按照键的添加顺序来保存元素的顺序。在某些情况下，字典的键是连续的，对应的散列值也是连续值（例如整数），那么由于字典的内部实现，元素的实现可能和添加的顺序相同：
keys = {num: None for num in range(5)}.keys()
print(keys)
result：
dict_keys([0, 1, 2, 3, 4])
但是，如果散列方法不同的其它数据类型，那么字典就不会保存元素顺序。
age = {str(i): i for i in range(100)}
keys = age.keys()
print(keys)
result：
dict_keys(['0', '1', '2', '3', '4', '5', '6', '7', '8', '9', '10', '11', '12', '13', '14', '15', '16', '17', '18', '19', '20', '21', '22', '23', '24', '25', '26', '27', '28', '29', '30', '31', '32', '33', '34', '35', '36', '37', '38', '39', '40', '41', '42', '43', '44', '45', '46', '47', '48', '49', '50', '51', '52', '53', '54', '55', '56', '57', '58', '59', '60', '61', '62', '63', '64', '65', '66', '67', '68', '69', '70', '71', '72', '73', '74', '75', '76', '77', '78', '79', '80', '81', '82', '83', '84', '85', '86', '87', '88', '89', '90', '91', '92', '93', '94', '95', '96', '97', '98', '99'])
理论上，键的顺序不应该是这样的，应该是乱序。。。具体为什么这样，等以后明白了再补充
如果我们需要保存添加顺序怎么办？python 标准库的collections模块提供了名为OrderedDicr的有序字典。
集合是一种鲁棒性很好的数据结构，当元素顺序的重要性不如元素的唯一性和测试元素是否包含在集合中的效率时，大部分情况下这种数据结构极其有用。
python的内置集合类型有两种：
set(): 一种可变的、无序的、有限的集合，其元素是唯一的、不可变的（可哈希的）对象。
frozenset(): 一种不可变的、可哈希的、无序的集合，其元素是唯一的，不可变的哈希对象。
set([set([1, 2, 3]), set([2, 3, 4])])
result:
Traceback (most recent call last): File "/pycharm_project/LearnPython/Part1/demo.py", line 1, in module> set([set([1, 2, 3]), set([2, 3, 4])]) TypeError: unhashable type: 'set'
set([frozenset([1, 2, 3]), frozenset([2, 3, 4])])
result:不会报错
set里的元素必须是唯一的，不可变的。但是set是可变的，所以set作为set的元素会报错。
CPython中集合和字典非常相似。事实上，集合被实现为带有空值的字典，只有键才是实际的集合元素。此外，集合还利用这种没有值的映射做了其它的优化。
由于这一点，可以快速的向集合中添加元素、删除元素、检查元素是否存在。平均时间复杂度为O(1),最坏的事件复杂度是O(n)。
以上为个人经验，希望能给大家一个参考，也希望大家多多支持脚本之家。如有错误或未考虑完全的地方，望不吝赐教。
标签：锡林郭勒盟 梅州 浙江 昆明 怀化 石家庄 西宁 文山
巨人网络通讯声明：本文标题《Python 列表(List)的底层实现原理分析》，本文关键词 Python,列表,List,的,底层,；如发现本文内容存在版权问题，烦请提供相关信息告之我们，我们将及时沟通与处理。本站内容系统采集于网络，涉及言论、版权与本站无关。