使用itertools.islice获取collections.deque末尾N个元素的时间复杂度及实现原理

1. 获取deque末尾N个元素的时间复杂度 #

当使用itertools.islice(deque, len(deque)-N, len(deque))时，时间复杂度为O(M)，其中M是deque的总长度（即len(deque)）。

原因如下：

• deque基于双向链表实现，其默认迭代器是从头部向尾部顺序遍历的。
• islice要从len(deque)-N的位置开始取值，必须先逐个跳过前面的len(deque)-N个元素，这个过程耗时O(M-N)。
• 后续取N个元素的过程耗时O(N)。
• 总时间复杂度为O(M-N + N) = O(M)，与deque的总长度线性相关。

如果想更高效获取末尾N个元素，可结合反向迭代器使用islice：list(itertools.islice(reversed(deque), 0, N))[::-1]，这种方式时间复杂度为O(N)——因为reversed(deque)可直接从尾部开始遍历，无需跳过前面元素，仅需遍历N个元素即可。

2. itertools.islice的实现方式 #

itertools.islice是一个惰性迭代器，核心逻辑如下：

• 接收可迭代对象、起始位置start、结束位置stop（可选）、步长step（可选，默认1）。
• 首先遍历原可迭代对象，逐个跳过前start个元素（若start>0），此过程不会预先存储跳过的元素。
• 从当前位置开始，每经过step个元素就返回一个，直到到达stop位置或原可迭代对象耗尽。
• 它不会一次性生成所有结果，仅在每次迭代（如调用next()）时计算下一个元素，内存效率极高，适合处理大型可迭代对象。

在CPython底层，islice由C语言实现，内部维护位置计数器和步长计数器，每次迭代时更新计数器，判断是否返回当前元素或继续跳过。

内容的提问来源于stack exchange，提问作者iluvmath