0

As you know, collections.deque does not support regular slicing in Python, and so I have to use itertools.islice instead.

However, I know that index access to elements in collections.deque are not constant time in general (they are linear in terms of how far away the index is from the head/tail).

If I want to get the last N elements of a deque. What is the time complexity of itertools.islice(deque, len(deque) - N, len(deque))? How is itertools.islice implemented?

iluvmath
  • 177
  • 4
  • It's linear, itertools islice simply iterates over the collection – juanpa.arrivillaga Sep 25 '22 at 20:00
  • If you want to see how islice is implemented, you can check the source code, it is in C. But in the itertools docs they provide an equivalent Python version: https://docs.python.org/3/library/itertools.html#itertools.islice – juanpa.arrivillaga Sep 25 '22 at 20:02
  • A faster approach is likely ```itertools.islice(reversed(deque), N)``` because it doesn't need to skip the first elements. Not to be confused with ```deque.reverse()``` – Homer512 Sep 25 '22 at 20:04
  • @Homer512 Got it. Yea. Your approach looks better. – iluvmath Sep 25 '22 at 20:22

0 Answers0