Является ли понимание списков действительно намного медленнее, чем str.replace?

Question

Я тестирую различные варианты дезинфекции струн и обнаружил эффект ниже. Что мне трудно сказать, действительно ли это результат кеширования, как предупреждает 44366082354994437355898954468888 IPython или если это реально. Пожалуйста, посоветуйте:

str.replace:

def sanit2(s):  
    for c in ["'", '%', '"']: 
     s=s.replace(c,'') 
    return s 


In [44]: %timeit sanit2(r""" ' ' % a % ' """) 
The slowest run took 12.43 times longer than the fastest. This could mean that an intermediate result is being cached 
1000000 loops, best of 3: 985 ns per loop  

Список понимание:

def sanit3(s):  
    removed = [x for x in s if not x in ["'", '%', '"']] 
    return ''.join(removed) 


In [42]: %timeit sanit3(r""" ' ' % a % ' """) 
The slowest run took 8.95 times longer than the fastest. This could mean that an intermediate result is being cached 
100000 loops, best of 3: 2.12 µs per loop   

Это, кажется, держит для относительно длинных строк тоже:

In [46]: reallylong = r""" ' ' % a % ' """ * 1000 

In [47]: len(reallylong) 
Out[47]: 22000 


In [48]: %timeit sanit2(reallylong) 
The slowest run took 4.94 times longer than the fastest. This could mean that an intermediate result is being cached 
10000 loops, best of 3: 96.9 µs per loop 


In [49]: %timeit sanit3(reallylong) 
1000 loops, best of 3: 1.9 ms per loop   

UPDATE: Я предположил, что str.replace также имеет больше или меньше O (n), поэтому я ожидал, что и sanit2, и sanit3 будут иметь сложность O (n^2).

Я проверил стоимость str.replace в зависимости от длины строки:

In [59]: orig_str = r""" ' ' % a % ' """ 


In [60]: for i in range(1,11): 
    ....:  longer = orig_str * i * 1000 
    ....:  %timeit longer.replace('%', '') 
    ....: 
10000 loops, best of 3: 44.2 µs per loop 
10000 loops, best of 3: 87.8 µs per loop 
10000 loops, best of 3: 131 µs per loop 
10000 loops, best of 3: 177 µs per loop 
1000 loops, best of 3: 219 µs per loop 
1000 loops, best of 3: 259 µs per loop 
1000 loops, best of 3: 311 µs per loop 
1000 loops, best of 3: 349 µs per loop 
1000 loops, best of 3: 398 µs per loop 
1000 loops, best of 3: 435 µs per loop 


In [61]: t="""10000 loops, best of 3: 44.2 s per loop 
    ....: 10000 loops, best of 3: 87.8 s per loop 
    ....: 10000 loops, best of 3: 131 s per loop 
    ....: 10000 loops, best of 3: 177 s per loop 
    ....: 1000 loops, best of 3: 219 s per loop 
    ....: 1000 loops, best of 3: 259 s per loop 
    ....: 1000 loops, best of 3: 311 s per loop 
    ....: 1000 loops, best of 3: 349 s per loop 
    ....: 1000 loops, best of 3: 398 s per loop 
    ....: 1000 loops, best of 3: 435 s per loop""" 

кажется линейным, но я вычислил, чтобы быть уверенным:

In [63]: averages=[] 


In [66]: for idx, line in enumerate(t.split('\n')): 
    ....:  repl_time = line.rsplit(':',1)[1].split(' ')[1] 
    ....:  averages.append(float(repl_time)/(idx+1)) 
    ....: 

In [67]: averages 
Out[67]: 
[44.2, 
43.9, 
43.666666666666664, 
44.25, 
43.8, 
43.166666666666664, 
44.42857142857143, 
43.625, 
44.22222222222222, 
43.5] 

Да, str.replace почти совершенно O (п). Таким образом, поверх итерации над списком символов, подлежащих замене, sanit2 должен иметь сложность O (n^2) точно так же, как sanit3 (x for x in s => итерация символов, подлежащих замене, O (n). ...x in ["'", '%', '"'] должно быть O (n), а также дано list.__contains__. Всего O (n^2)).

Таким образом, в ответ на chepner, да, sanit2 делает фиксированное количество вызовов функций (и мало, как раз 3 в данном примере), но из-за внутренней стоимости str.replace похоже sanit2 должен иметь аналогичный порядок сложности для sanit3 ,

Является ли разница все из-за того, что str.replace реализована на C или, может быть, функция вызова (list.__contains__) также играет важную роль?

Answer 1

sanit2 делает фиксированное количество вызовов, независимо от длины s к способу строки, реализованному в С.

sanit3 делает переменное число вызовов (один для каждого элемента в s) к list.__contains__, который сам по себе использует алгоритм O (n), а не O (1). Он также должен построить объект list, а затем вызвать ''.join в этом списке.

Неудивительно, что sanit2 работает быстрее.