CODEWITHSUNDEEP
pythonslice
Martin Thoma
Martin Thoma

Reputation: 136187

Why is reversing a string with the extended slice so fast?

I just timed a couple of string reversal methods and of course the extended slice is super fast. In fact, using Python 3.6.7, I have the impression it has constant time:

enter image description here

20 chars            : min:   0.6μs, mean:   0.7μs, max:    3.7μs
2000 chars          : min:   0.5μs, mean:   0.6μs, max:    5.8μs
200000 chars        : min:   0.5μs, mean:   0.6μs, max:    2.5μs
200000000 chars     : min:   0.5μs, mean:   0.6μs, max:    2.5μs

Why is that the case? I assumed that it would at least need to iterate over all of the elements and thus have linear time? Is there some pointer-magic of cPython involved? Is there a bug in my evaluation?

Code

#!/usr/bin/env python

import numpy as np
import random
import timeit
random.seed(0)


def main():
    string_20 = ''.join(random.choices("ABCDEFGHIJKLM", k=20))
    string_2000 = ''.join(random.choices("ABCDEFGHIJKLM", k=2000))
    string_200000 = ''.join(random.choices("ABCDEFGHIJKLM", k=200000))
    string_200000000 = ''.join(random.choices("ABCDEFGHIJKLM", k=200000000))
    functions = [(list_comprehension, '20 chars', string_20),
                 (list_comprehension, '2000 chars', string_2000),
                 (list_comprehension, '200000 chars', string_200000),
                 (list_comprehension, '200000000 chars', string_200000000),
                 ]
    duration_list = {}
    for func, name, params in functions:
        durations = timeit.repeat(lambda: func(params), repeat=100, number=3)
        duration_list[name] = list(np.array(durations) * 1000)
        print('{func:<20}: '
              'min: {min:5.1f}μs, mean: {mean:5.1f}μs, max: {max:6.1f}μs'
              .format(func=name,
                      min=min(durations) * 10**6,
                      mean=np.mean(durations) * 10**6,
                      max=max(durations) * 10**6,
                      ))
        create_boxplot('Reversing a string of various lengths', duration_list)


def list_comprehension(string):
    return string[::1]


def create_boxplot(title, duration_list, showfliers=False):
    import seaborn as sns
    import matplotlib.pyplot as plt
    import operator
    plt.figure(num=None, figsize=(8, 4), dpi=300,
               facecolor='w', edgecolor='k')
    sns.set(style="whitegrid")
    sorted_keys, sorted_vals = zip(*duration_list.items())
    flierprops = dict(markerfacecolor='0.75', markersize=1,
                      linestyle='none')
    ax = sns.boxplot(data=sorted_vals, width=.3, orient='h',
                     flierprops=flierprops,
                     showfliers=showfliers)
    ax.set(xlabel="Time in ms", ylabel="")
    plt.yticks(plt.yticks()[0], sorted_keys)
    ax.set_title(title)
    plt.tight_layout()
    plt.savefig("output-string-list-comp.png")


if __name__ == '__main__':
    main()

Upvotes: 1

Views: 68

Answers (1)

Manuel
Manuel

Reputation: 542

Just checked it. The list_comprehension method must be

def list_comprehension(string):
    return string[::-1]

I left out the largest list because it took a long time. This is my output:

/usr/bin/python3 ./boxplot.py 
20 chars            : min:   1.7μs, mean:   2.0μs, max:    7.5μs
2000 chars          : min:   6.7μs, mean:   6.8μs, max:   13.4μs
200000 chars        : min: 567.6μs, mean: 609.9μs, max:  997.2μs

Seems to be not constant as expected:-)

enter image description here

Nice boxplot by the way!

Upvotes: 1

Related Questions