Is Python list indexing constant time?
Accidentally inefficient list code with is very common and can be hard to spot, but when the list grows your code grinds to a halt. Show
This text takes a detailed look at the performance of basic array operations and discusses alternatives to a standard array. It also includes cheat sheets of expensive list operations in Java and Python. Array basicsAn array is the most fundamental collection data type. It consists of elements of a single type laid out sequentially in memory. You can access any element in constant time by integer indexing. Arrays are available in all major languages. In Java you can either use PerformanceIn general, arrays have excellent performance. To optimize array performance is a major goal of memory hardware design and OS memory management.
Dynamic arrayIn a dynamic array, elements are stored at the start of an underlying fixed array, and the remaining positions are unused.
Here’s a view of the memory when appending the elements 2, 7, 1, 3, 8, 4 to an initially empty dynamic array with capacity 2. The time to append an element is linear in the worst case, since it involves allocating new memory and copying each element. However, if we expand the array by a constant proportion, e.g. by doubling its size, the total time to insert n elements will be O(n), and we say that each insertion takes constant amortized time. See Amortized time complexity for more on how to analyze data structures that have expensive operations that happen only rarely. Expensive list operationsTo add or remove an element at a specified index can be expensive, since all elements after the index must be shifted. The worst-case time complexity is linear. Similarly, searching for an element for an element can be expensive, since you may need to scan the entire array. In this Python code example, the linear-time
To avoid this type of performance problems, you need to know the difference between constant and linear time list operations. Expensive Java ArrayList methodsThe following ArrayList methods operate on a subset of the elements, but still have time complexity that depends on the size add(int i, E element) n - i remove(int i) n - i [] 0n - i [] 2n [] 4n [] 6n [] 8n Note: Expensive Python list operationsThe following Python list operations operate on a subset of the elements, but still have time complexity that depends on ArrayList 2n - i ArrayList 4n - i ArrayList 6n - i ArrayList 8n - i pop(0) 0n pop(0) 2n Note: AlternativesNo other data structure can compete with the efficiency of array indexing and array iteration. However, you may need to take a different approach if other operations are performance critical. Maps and dictionariesThe hash table, often in the form of a map or a dictionary, is the most commonly used alternative to an array. It implements an unordered collection of key-value pairs, where each key is unique.
In Java, hash tables are part of the standard library (HashSet and HashMap). Many modern languages, such as Python and Go, have built-in dictionaries and maps implemented by hash tables. Sorted arraysIf search is important for performance, you may want to use a sorted array.
The Java Arrays class contains implementations of binary search, Python offers a similar bisect algorithm, and Go also has several binary search methods. Linked listsIf you need to repeatedly add or remove elements at the start or end of a list, you may want to consider a linked list.
The Java LinkedList class implements a doubly linked list, Python offers a , and Go also has a list package. Binary search treesBalanced binary search trees store items in sorted order and offer efficient lookup, addition and removal of items.
In Java, search trees are part of the standard library (TreeSet and TreeMap), while Python and Go don’t support them out of the box. What is the time complexity of list indexing in Python?The index() method has linear runtime complexity in the number of list elements. For n elements, the runtime complexity is O(n) because in the worst-case you need to iterate over each element in the list to find that the element does not appear in it.
Are Python lists constant time?Python lists are variable-length arrays, which store references rather than the objects themselves. Thus, indexing the elements takes constant-time.
Is array indexing constant time?As Arrays are allocated contiguously in memory, Fetching a value via an index of the array is an arithmetic operation. All arithmetic operations are done in constant time i.e., O(1).
Is Python pop constant time?pop() with no arguments removes the last element. Accessing that element can be done in constant time. There are no elements following so nothing needs to be shifted.
|