如何解释字符串反转的三个python实现的性能

Question

我已经在一个相对非正式的级别上编程了大约两年，这不需要关心我的实现的性能或运行时。现在我想通过实际计算分析算法的运行时来提高我的计算精度，而不是仅仅通过分析。你知道吗

绘制字符串反转算法的各种实现的运行时会产生与我预期相反的结果。你知道吗

我在python中实现了四种反转字符串的方法：

1. 本机string[::-1]
2. 带串联的对数反转（使用与mergesort类似的原理）
3. 无串联对数反转
4. 使用循环

现在我的预期性能顺序是运行时native < log-pure < log-concat < loop

这是我的性能图（注意算法（1）太快了，在这个尺度上看不到）

3个

您在这里看到的是，性能顺序（在对数标度上）是native < loop < log-concat < log-pure，这与以下预期不一致：

• 循环：O(n)
• 对数concat:O(nlogn)
• 纯对数：O(logn)
• 本地人：？你知道吗

我真的不明白为什么我会得到这样的结果。你知道吗

使用本机函数

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

串联对数反转

def naive_fastreverse(string):
    strlen = len(string)

    # The recursion base case
    if strlen==1: 
        return string

    mid = ""
    a = strlen/2
    b = a

    if strlen%2==1: #i.e. strlen is odd
        mid = string[strlen/2]
        b+=1
    # else:
    #   use no mid letter
    #   use default b

    half_a = string[0:a]
    half_b = string[b:strlen] 

    return naive_fastreverse(half_b) + mid + naive_fastreverse(half_a)

非串联对数反转

def optimized_fastreverse(string):
    final = list(string)
    strlen = len(string)

    def computenode(start, end):
        if end-start==1: 
            final[strlen-end] = string[end-1]
        else: 
            computenode(start,start+(end-start)/2)
            computenode(start+(end-start)/2, end)

    computenode(0, strlen)
    return ''.join(final) 

基于循环的反转

def loopy_reverse(string):
    final=list(string)
    strlen=len(string)
    for i in xrange(strlen):
        final[strlen-i-1] = string[i]
        final[i] = string[strlen-i-1]
    return ''.join(final)

这是我的绘图代码：

import time
import math
import random
import string
import numpy
Num = 5
def rand_str_gen(N):
    return ''.join(
        random.choice(
            string.ascii_uppercase + string.digits) 
        for _ in range(N))

randstr = "a"*(10**Num) #rand_str_gen(10**Num)

def run(reverser, reversable):
    start = time.time()
    reverser(reversable)
    end = time.time()
    return end-start

def profile(reverser):
    xs = np.arange(1,Num+1,0.1)
    ys = []
    for i in xs:
        ys.append(run(reverser,randstr[1:int(10.**i)] ))
    return xs ,ys

functions = [
    native_reverse,
    naive_fastreverse,
    optimized_fastreverse,
    loopy_reverse]

reversers = {
    # Makes the function names look nice 
    (" ".join(
        map(lambda s: s.capitalize(),
            func.__name__.split("_")))): profile(func)
    for func in functions}

%matplotlib inline
lengths = ["$10^%d$"%i for i in range(Num+1)]

from pylab import *
fig = figure(figsize=(20,10))
ax = fig.add_subplot(1,1,1)  
plots = [
    ax.plot(*data, label=name)[0] 
    for (data, name) in zip(reversers.values(), reversers.keys())
]

legend(handles=plots,loc=2)
ax.set_title("Algorithm Runtime (ms) by String Length")
ax.set_xticklabels(lengths)

Answer 1

你不是在衡量算法的性能，而是衡量内存的行为。由于PC中有多个缓存级别，因此访问时间有很大的不同。这使实践与理论完全背离。你知道吗

同时还要对Python interpreter进行计时，这也会以未知的方式扭曲结果。你知道吗