Lin Ma Lin Ma - 10 months ago 29
Python Question

performance of get a specific character of a string in Python 2.7

Suppose I want to get a specific character of a string in Python 2.7, suppose

a = 'abcdefg...' # a long string
print a[5]

Wondering when access any specific character of a string, for example, access the 5th element, wondering what is the performance, is it constant time O(1), or linear performance O(n) either according the 5 (the position of the character we are accessing), or linear performance O(n) to the whole string (len(a) in this example)?


>>> long_string_1M ="".join(random.choice(string.printable) for _ in xrange(1000000))
>>> short_string = "hello"
>>> timeit.timeit(lambda:long_string_1M[50000])
>>> timeit.timeit(lambda:short_string[4])
>>> timeit.timeit(lambda:short_string[random.randint(0,4)])
>>> timeit.timeit(lambda:long_string_1M[random.randint(50000,100000)])

looks like O(1) to me

they acheive it because a string is consecutive memory locations so indexing into it is simply a matter of offsetting ... there is no seek (at least that is my understanding) if you know c/c++ its something like *(pointer+offset) (its been a long time since ive done C so that might be a little wrong)