fastest way to achieve collection.deque

tung 0
Viewed 29

I want to limit the length of the list in python, whenever len(list) > limit, the first item will be removed, I knew collection.deque can achieve the same way, however, will it be slower than just do something like:

list_A = [2,4,6,8,11]
length_limit = 5
while True:
    # do something to the list, for example, list_A.append(2)
    if len(list_A) > length_limit:
        list_A = list_A[1:]

And besides, do something like this or collection.deque, is any other way to achieve it much readable and efficient?

maxlength deque collections list python
1 Answers

A fact you need to know is that list and deque are different implementations at the bottom. In Cpython, the former is a dynamic array, and the latter is a doubly linked list. Arrays are good at accessing element through indexes but are not good at inserting or removing elements from inside. On the contrary, linked lists are good at inserting or removing elements from anywhere (but the node should be determined first) but are not good at accessing element through indexes.

As for what you have described so far, if you don't need your list to have efficient random access, deque is indeed the most suitable choice. When you use slicing for a list, python will copy the references in the list according to the range specified by the slicing and store them in a new list. In your case, this is an O(n) operation (that is, the time required is proportional to the length of the list). For deque, when the length exceeds the specified maxlen, It only needs to simply discard the header node (Cpython also optimizes deque with maxlen restriction). This is an O(1) operation, which is obviously more efficient than the list.

Mechanic Pig0
Related