教育网站改版方案,黄骅贴吧最新消息金鼎18号,网站接入激励视频广告,网站安全检测可以检测哪些内容风险信息ins ngladc文末左下方阅读原文指向了本人博客链接#xff0c;不含广告。参考资料中的相关链接#xff0c;可以在博客文章的最下方获取。推荐苹果手机用户使用浅色模式观看。前言 对于一些算法题#xff0c;可以使用Python自带的内置函数解决。但很多时候用就用了#xff0c… ins ngladc文末左下方阅读原文指向了本人博客链接不含广告。参考资料中的相关链接可以在博客文章的最下方获取。推荐苹果手机用户使用浅色模式观看。前言 对于一些算法题可以使用Python自带的内置函数解决。但很多时候用就用了根本不知道内部的细节。这样的话算时间复杂度和空间复杂度就很有问题。因此我最近几天查阅了网上相关资料并进行归纳和整理。开始我以为复制粘贴就行了但是呢我发现有很多东西都没解释得清楚与透彻在研读的过程中我经常很懵逼更有时候我都怀疑自己智商了。最后不得不逼自己读相关源码。越看源码越发现有很多可以分析的但是考虑到篇幅和时间就先打住以后再整个进阶版。整理完这个以后我认为呀不管什么东西还是得追本溯源这样才靠谱。目录前提说明性能总结1、列表(list)列表实现原理列表函数的时间复杂度列表函数讲解性能分析2、双端队列双端队列实现原理双端队列时间复杂度双端队列函数讲解性能分析3、字典(dict)字典实现原理字典函数的时间复杂度字典函数说明字典性能分析4、集合(set)集合函数的时间复杂度集合性能分析给自己留一个坑参考资料附录Cpython collections 部分源码注释Cpython dict源码部分注释前提说明 时间复杂度是参考官网:https://wiki.python.org/moin/TimeComplexity此页面记录了当前CPython中各种操作的时间复杂度(又名“Big O”或“大欧”)。其他Python实现(或CPython的旧版本或仍在开发版本)可能具有略微不同的性能特征。但是, 通常可以安全地假设它们的速度不超过O(log n)。在所有即将介绍的表格中n是容器中当前元素的数量k是参数的值或参数中的元素数。本文先上结论再进行分析有助于带着问题去思考答案。性能总结 1、Python 字典中使用了 hash table因此查找操作的复杂度为 O(1)而 list 实际是个数组在 list 中查找需要遍历整个 list其复杂度为 O(n)因此对成员的查找访问等操作字典要比 list 更快。2、set 的 union intersectiondifference 操作要比 list 的迭代要快。因此如果涉及到求 list 交集并集或者差的问题可以转换为 set 来操作。3、需要频繁在两端插入或者删除元素可以选择双端队列。1、列表(list) 可直接使用无须调用。列表实现原理列表是以数组(Array)实现的这个数组是 over-allocate 数组。顾名思义当底层数组容量满了而需要扩充的时候python依据规则会扩充多个位置出来。比如初始化列表array[1, 2, 3, 4]向其中添加元素23此时array对应的底层数组扩充后的容量不是5而是8。这就是over-allocate的意义即扩充容量的时候会多分配一些存储空间。如图1展示了l.insert(1,5) 的操作。图1. insert操作这里说下列表的增长模式为04816253546587288...列表函数的时间复杂度如果要更好地理解列表就必须熟悉数组这种数据结构。如图 2所示为列表相关函数的时间复杂度。图2. 列表函数的时间复杂度列表函数讲解append()方法是指在列表末尾增加一个数据项这里的表强调的是插入1个元素即没有扩容。extend()方法是指在列表末尾增加一个数据集合insert()方法是指在某个特定位置前面增加一个数据项需要移动其他元素位置len()方法获取列表内元素的个数因为在列表实现中其内部维护了一个 Py_ssize_t 类型的变量表示列表内元素的个数因此时间复杂度为O(1)sort()方法是排序网上有原理讲解使用的是 Timesort 排序该排序结合了合并排序(merge sort)和插入排序(insertion sort)而得出的排序算法它在现实中有很好的效率。空间复杂度为O(n)。其排序的过程大致为对输入的数字进行分区然后再进行合并性能分析通过对上表的分析可以发现列表不太适合做元素的查找、删除、插入等操作因为这些都要遍历列表对应的时间复杂度为O(n)。访问某个索引的元素、尾部添加元素(append)或删除(pop last)元素这些操作比较适合用列表做对应的时间复杂度为O(1)。根据官方上说列表最大的开销发生在超过了当前所分配的列表大小这是因为所有元素都需要移动或者是在起始位置附近插入或者删除元素这种情况下所有在该位置后面的元素都需要移动。如果你需要在一个队列的两端进行增删的操作应当使用collections.deque。如果我们要在业务开发中判断一个value是否在一个数据集中如果数据集用列表存储那此时的判断操作就很耗时如果我们用hash table(set or dict)来存储则比较轻松。2、双端队列 使用时需要导入from collection import deque双端队列实现原理deque(双端队列)是以双向链表的形式实现的。(好吧, 一个数组列表而不是对象, 以提高效率)。为了更好地理解这种结构可以参照 GitHub 上 CPython collections 模块的第二个 commit 的源码。注释在文末的附录下面。这里根据注释我画了一个不太准确的图其实leftblock和rightblock都是要存储数据的。但在下图没有标明。图3. 存储图参考资料4单个block的结构体示意图如下图4. block总结来说deque 内部将一组内存块组织成双向链表的形式每个内存块可以看成一个 Python 对象的数组 这个数组与普通数据不同它是从数组中部往头尾两边填充数据而平常所见数组大都是从头往后。正因为这个特性所以叫双端队列。双端队列时间复杂度如图所示为双端队列的相关函数的时间复杂度。图5. 双端队列时间复杂度双端队列函数讲解在这种数据结构下append方法是怎么实现的呢如果 rightblock 可以容纳更多的元素则放在 rightblock 中如果不能就新建一个 block然后更新若干指针将元素放在更新后的 rightblock 中。性能分析得益于 deque 这样的结构它的 pop/popleft/append/appendleft 四种操作的时间复杂度均是 O(1), 用它来实现队列、栈会非常方便和高效。虽然双端队列中的元素可以从两端弹出并且队列任意一端都可以入队和出队但其限定插入和删除操作在表的两端进行。由于这样查找双端队列中间的元素较为缓慢, 增删元素就更慢了。3、字典(dict) 可直接使用无须调用。字典实现原理在Python中字典是通过哈希表实现的。也就是说字典是一个数组而数组的索引是经过哈希函数处理后得到的。要理解字典必须对哈希表这种数据结构比较熟悉。下图6为哈希表的一个逻辑判断图6. 哈希表判断这里要注意几点使用散列值的一部分进行定位散列冲突时使用散列值的另一部分如果这一部分是包含原始Key的信息那么不同的Key通过比较就能区分出来。你可能会问取哈希值的一部分是怎么取得呢下图7给了一个种方式就是将计算得到哈希值 数组的长度。同时由这张图我们可以发现Python的哈希函数在键彼此连续的时候表现得很理想这主要是考虑到通常情况下处理的都是这类形式的数据。然而一旦我们添加了键z就会出现冲突因为这个键值并不毗邻其他键且相距较远。图7. 哈希映射先要声明的是针对python的不同版本dict的实现还有所不同较为详细的介绍请参考资料[6]。老字典只使用一张hash而新字典还使用了一张Indices表来辅助。这里的indices才是真正的散列表哦下来列出新的结构indices [None, None, index, None, index, None, index]enteies [ [hash0, key0, value0], [hash1, key1, value1], [hash2, key2, value2]]字典存储过程计算key的hash值 ( hash(key) )再和mask做与操作 ( mask字典最小长度(IndicesDictMinSize)- 1 )运算后会得到一个数字index这个index就是要插入的indices的下标位置(注具体算法与Python版本相关并不一定一样)得到index后会找到indices的位置但是此位置不是存的hash值而是存的len(enteies)表示该值在enteies中的位置如果出现hash冲突则会继续向下寻找空位置(略有变化的开放寻址)一直到找到剩余空位为止。字典查找过程计算 hash(key)得到hash_value ;计算 hash_value ( len(indices) - 1)得到一个数字index ;计算 indices[index] 的值得到 entry_index ;计算 enteies[entey_index] 的值 为最终值。为方便理解这里我做了一个图可以看到 indices 起到一个桥梁的作用。画完这个图再感叹一句设计还是挺巧妙的。图8. 字典示意图这里补充下关于哈希冲突是怎么寻找下一个数组位置的。源码中用到的是以下公式j ((5*j) 1) mod 2**i这里的 j 有两层含义赋值号左边的为数组的下一个下标赋值号右边的是当前发生冲突的下标。而 2 ** i可以理解数组长度。举例说明对于要给size大小为2 ** 3来说j_prev 0 ; j_next ((5 * 0) 1) mod 8 1 j_prev 1 ; j_next ((5 * 1) 1) mod 8 6j_prev 6 ; j_next ((5 * 6) 1) mod 8 7j_prev 7 ; j_next ((5 * 7) 1) mod 8 4j_prev 4 ; j_next ((5 * 4 ) 1) mod 8 5以此类推最后回到起点为0。以下就是哈希冲突的轨迹0 - 1 - 6 - 7 - 4 - 5 - 2 - 3 - 0字典函数的时间复杂度下列字典的平均情况基于以下假设对象的散列函数足够撸棒(robust), 不会发生冲突。字典的键是从所有可能的键的集合中随机选择的。图9. 字典函数的时间复杂度小窍门只使用字符串作为字典的键。这么做虽然不会影响算法的时间复杂度, 但会对常数项产生显著的影响, 这决定了你的一段程序能多快跑完。字典函数说明这些操作依赖于“摊销最坏情况”的“摊销”部分。根据容器的历史, 个别动作可能需要很长时间。对于这些操作, 最坏的情况n是容器达到的最大尺寸, 而不仅仅是当前的大小。例如, 如果一个N个元素的字典, 然后删除N-1个元素, 这个字典会重新为N个元素调整大小, 而不是当前的一个元素, 所以时间复杂度是O(n)。字典性能分析字典的查询、添加、删除的平均时间复杂度都是O(1)相比列表与元祖性能更优。但是如果发生散列冲突或者容器需要扩充那么时间复杂度就要考虑最差的情况 O(n)。所以说字典及其依赖哈希算法真正要灵活运用词典时还需要查看底层的哈希算法。4、集合(set) dict与set实现原理是一样的都是将实际的值放到list中。唯一不同的在于hash函数操作的对象对于dicthash函数操作的是其key而对于set是直接操作的它的元素。假设操作内容为x其作为因变量放入hash函数通过运算后取list的余数转化为一个list的下标此下标位置对于set而言用来放其本身。而对于dict则是创建了两个list一个listf存储哈希表对应的下标另一个list中存储哈希表具体对应的值。这里为了更好地理解对比上面字典那个图我尝试画一个图。图10. 集合映射集合函数的时间复杂度下图是函数的时间复杂度图11. 集合时间复杂度集合性能分析由源码得知, 求差集(s-t, 或s.difference(t))运算与更新为差集(s.difference_uptate(t))运算的时间复杂度并不相同第一个是O(len(s))(对于s中的每个元素, 如果不在t中, 将它添加到新集合中)。第二个是O(len(t))(对于t中的每个元素, 将其从s中删除)。因此, 必须注意哪个是首选, 取决于哪一个是最长的集合以及是否需要新的集合。集合的s-t运算中, s和t都要是set类型。如果t不是set类型, 但是是可迭代的, 你可以使用等价的方法达到目的, 比如 s.difference(l), l是个list类型。另外列表的一些集合运算可以转成集合类型来操作速度更快。给自己留一个坑 自己也尝试读了一下一些数据结构的源码虽然很多看不懂但是抓到一些关键信息。比如下面的代码和图片。static Py_ssize_tlist_length(PyListObject *a){return Py_SIZE(a);}下图为dictobject.c里的一个函数图12. 集合时间复杂度参考资料 [1] Python内置方法的时间复杂度[2] TimeComplexity[3] python list 之时间复杂度分析[4] How collections.deque works?[5] 深入 Python 列表的内部实现[6] Python字典dict实现原理附录 Cpython list 部分源码注释源码地址传送门https://github.com/python/cpython/blob/master/Objects/listobject.c/* This over-allocates proportional to the list size, making room* for additional growth. The over-allocation is mild, but is* enough to give linear-time amortized behavior over a long* sequence of appends() in the presence of a poorly-performing* system realloc().* Add padding to make the allocated size multiple of 4.* The growth pattern is: 0, 4, 8, 16, 24, 32, 40, 52, 64, 76, ...* Note: new_allocated wont overflow because the largest possible value* is PY_SSIZE_T_MAX * (9 / 8) 6 which always fits in a size_t.*/Cpython collections 部分源码注释源码地址传送门https://github.com/python/cpython/blob/master/Modules/_collectionsmodule.c/* The block length may be set to any number over 1. Larger numbers* reduce the number of calls to the memory allocator but take more* memory. Ideally, BLOCKLEN should be set with an eye to the* length of a cache line.*/#define BLOCKLEN 62#define CENTER ((BLOCKLEN - 1) / 2)/* A dequeobject is composed of a doubly-linked list of block nodes.* This list is not circular (the leftmost block has leftlinkNULL,* and the rightmost block has rightlinkNULL). A deque ds first* element is at d.leftblock[leftindex] and its last element is at* d.rightblock[rightindex]; note that, unlike as for Python slice* indices, these indices are inclusive on both ends. By being inclusive* on both ends, algorithms for left and right operations become* symmetrical which simplifies the design.* The list of blocks is never empty, so d.leftblock and d.rightblock* are never equal to NULL.* The indices, d.leftindex and d.rightindex are always in the range* 0 index BLOCKLEN.* Their exact relationship is:* (d.leftindex d.len - 1) % BLOCKLEN d.rightindex.* Empty deques have d.len 0; d.leftblockd.rightblock;* d.leftindex CENTER1; and d.rightindex CENTER.* Checking for d.len 0 is the intended way to see whether d is empty.* Whenever d.leftblock d.rightblock,* d.leftindex d.len - 1 d.rightindex.* However, when d.leftblock ! d.rightblock, d.leftindex and d.rightindex* become indices into distinct blocks and either may be larger than the* other.*/Cpython dict源码部分注释源码地址传送门https://github.com/python/cpython/blob/master/Objects/dictobject.c/*layout:---------------| dk_refcnt || dk_size || dk_lookup || dk_usable || dk_nentries |---------------| dk_indices || |---------------| dk_entries || |---------------dk_indices is actual hashtable. It holds index in entries, or DKIX_EMPTY(-1) orDKIX_DUMMY(-2).dk_entries is array of PyDictKeyEntry. Its size is USABLE_FRACTION(dk_size).DK_ENTRIES(dk) can be used to get pointer to entries.The first half of collision resolution is to visit table indices via thisrecurrence:But catering to unusual cases should not slow the usual ones, so we just take the last i bits anyway. Its up to collision resolution to do the rest. Ifwe *usually* find the key were looking for on the first try (and, it turns out, we usually do -- the table load factor is kept under 2/3, so the oddsare solidly in our favor), then it makes best sense to keep the initial index computation dirt cheap.j ((5*j) 1) mod 2**iFor any initial j in range(2**i), repeating that 2**i times generates eachint in range(2**i) exactly once (see any text on random-number generation forproof). By itself, this doesnt help much: like linear probing (settingj 1, or j - 1, on each loop trip), it scans the table entries in a fixedorder. This would be bad, except thats not the only thing we do, and itsactually *good* in the common cases where hash keys are consecutive.In an example thats really too small to make this entirely clear, for a table ofsize 2**3 the order of indices is:0 - 1 - 6 - 7 - 4 - 5 - 2 - 3 - 0 [and here its repeating]*/
