0

Given a list of strings in python, for ex:

list_str = ['aa', 'bb', 'abc'].

What is the cost/complexity of replacing an element of the list as given below :

list_str[i] = 'xyz'

(Assume length of the list to be n, and length of a string is at most m)

Mazdak
  • 105,000
  • 18
  • 159
  • 188
avngr
  • 323
  • 3
  • 12
  • 1
    It's [O(1)](https://wiki.python.org/moin/TimeComplexity#list). Note that a list only contains reference to the object not the actual objects. – Ashwini Chaudhary Jun 21 '15 at 12:30
  • 2
    There is a [TimeTable](https://wiki.python.org/moin/TimeComplexity), this could help you. You are, probably, looking for a `Set Item` row. – awesoon Jun 21 '15 at 12:30
  • If there was a better way than simple assignment why Python doesn't use that itself? – Mazdak Jun 21 '15 at 12:34

5 Answers5

3

Using simple tests, it seems to be constant time -

In [1]: list_str = ['aaa' for _ in range(100000)]

In [2]: %timeit list_str[0] = 'aab'
10000000 loops, best of 3: 77.7 ns per loop

In [3]: %timeit list_str[9999] = 'aab'
10000000 loops, best of 3: 77.2 ns per loop

In [4]: %timeit list_str[99999] = 'aab'
10000000 loops, best of 3: 78.7 ns per loop

In [5]: %timeit list_str[9] = 'aab'
10000000 loops, best of 3: 77.7 ns per loop
Anand S Kumar
  • 88,551
  • 18
  • 188
  • 176
2

Since CPython implements lists as arrays, operations like l[i] = x take constant (O(1)) time.

See the table of operations here: https://wiki.python.org/moin/TimeComplexity

ron rothman
  • 17,348
  • 7
  • 41
  • 43
2

O(1) time complexity to replace an element by index in a list

jamylak
  • 128,818
  • 30
  • 231
  • 230
1

The cost of replacing an element is independent of the length of the list and independent of the length of the string. In Python lists contain only references to the object. So basically, replacing an element is overwriting a memory portion of size pointer.

Daniel
  • 42,087
  • 4
  • 55
  • 81
1

Lists in Python are implemented as dynamically allocated arrays of pointers to the contained values.

Replacing an element with another is just pointer fiddling and reference count adjustment and requires a constant time (independent on the size of the list).

6502
  • 112,025
  • 15
  • 165
  • 265
  • Is that guaranteed to be true by the python specification, or is it just how it is implemented in CPython? – Eric Appelt Jun 21 '15 at 12:36
  • @EricAppelt: What official python specification? – 6502 Jun 21 '15 at 12:42
  • good point - I guess what I am asking is there anything in the Python Language Reference that would imply that a `list` needs to be a contiguous array in some sense. I don't see anything that would imply this, but I could have missed something. – Eric Appelt Jun 21 '15 at 13:23