Замена пустых строк в строке

Question

я случайно обнаружил, что в питона, операция формы

string1.join(string2) 

Может быть эквивалентно выражено как

string2.replace('', string1)[len(string1):-len(string1)] 

Кроме того, после попытки timeit с несколькими различными размерный вход, этот странный способ присоединиться, кажется, более чем в два раза быстрее.

1. Почему метод соединения должен быть медленнее?
2. Является ли замена пустой строки такой безопасной/четко определенной вещью?

Answer 1

Итак, прежде всего, давайте разберемся, почему это работает.

>>> string1 = "foo" 
>>> string2 = "bar" 
>>> string1.join(string2) 
'bfooafoor' 

Это операция ввода string1 между каждым пунктом (характер) string2.

Так заменить пустую строку делает что-то вроде интересно, он считает разрыв между пустыми символами, как пустая строка, и, следовательно, делает по существу ту же самую задачу, за исключением дополнительного сепаратора в начале и конце:

>>> string2.replace('', string1) 
'foobfooafoorfoo' 

так нарезка из них дает тот же результат, как str.join():

>>> string2.replace('', string1)[len(string1):-len(string1)] 
'bfooafoor' 

Очевидно, что это решение гораздо, гораздо менее читабельным, чем str.join(), и поэтому я всегда рекомендую против него. str.join() также был разработан, чтобы быть эффективным на всех платформах. Замена пустой строки может быть намного менее эффективной для некоторых версий Python (я не знаю, так ли это, но это возможно - так же, как повторное конкатенация достаточно быстро в CPython, но это не обязательно в другом месте.)

я даже не могу ничего найти в документации, что наводит на мысль, что это поведение заменив пустую строку должна функционировать таким образом, the docs for str.replace() просто сказать:

возвращает копию строки со всеми вхождениями подстроки старым заменен новым. Если задан параметр необязательного аргумента, заменяются только первые совпадения.

Я не вижу причин, почему мы должны предполагать, что зазоры между ними буквами следует рассчитывать как возникновение пустой строки (возможно, вы могли бы поместиться бесконечные пустые строки в любом месте в строке), и как таковой, опираясь на это может быть плохой идеей.

Эта операция также довольно редка - чаще встречается последовательность строк для объединения - объединение отдельных символов строки - это не то, что я лично должен был делать часто.

Интересно, что это x.replace("", y) кажется, особыми обсаженным в the Python source:

2347 /* Algorithms for different cases of string replacement */ 
2348 
2349 /* len(self)>=1, from="", len(to)>=1, maxcount>=1 */ 
2350 Py_LOCAL(PyStringObject *) 
2351 replace_interleave(PyStringObject *self, 
2352 const char *to_s, Py_ssize_t to_len, 
2353 Py_ssize_t maxcount) 
2354 { 
... 

Это вполне может быть это специальный кожух заставляет его хорошо выполнять.Опять же, как это не упоминается в документации, это деталь реализации, и если предположить, что она будет работать так же быстро (или вообще) в других версиях Python, это будет ошибкой.

Answer 2

Как упоминалось в Lattyware, для замены пустой строки, его специальный случай, replace_interleave, его прямая прямая петля, где альтернативный символ из источника и из строки копируется в результирующую строку. Петля кодируется как как можно быстрее.

count = self_len+1; 

count -= 1; 
Py_MEMCPY(result_s, to_s, to_len); 
result_s += to_len; 
for (i=0; i<count; i++) { 
    *result_s++ = *self_s++; 
    Py_MEMCPY(result_s, to_s, to_len); 
    result_s += to_len; 
} 

/* Copy the rest of the original string */ 
Py_MEMCPY(result_s, self_s, self_len-i); 

Соединить метод также имеет петлю, но есть области улучшения (через я не нашел все аспекты по той причине, что был закодирован следующим образом) и причины узких мест.

char *sep = PyString_AS_STRING(self); 
seq = PySequence_Fast(orig, ""); 
/* Catenate everything. */ 
p = PyString_AS_STRING(res); 
for (i = 0; i < seqlen; ++i) { 
    size_t n; 
    item = PySequence_Fast_GET_ITEM(seq, i); 
    n = PyString_GET_SIZE(item); 
    Py_MEMCPY(p, PyString_AS_STRING(item), n); 
    p += n; 
    if (i < seqlen - 1) { 
     Py_MEMCPY(p, sep, seplen); 
     p += seplen; 
    } 
} 

Как Вы можете видеть здесь, внутри цикла

• Каждый элемент строки индексируется
• размер элемента определяется
• индексированных Пункт конвертируется в строку

Вышеуказанные три операции, даже если они могут быть выложены, имеют значительные накладные расходы. Примечание Это объясняет также, почему использование списка имеют различный результат по сравнению с использованием строковых, как заметил Blended

Кроме того, сравнивающие обе петли,

Бывшая

• может легко be auto vectorized
• Кэш дружественный.

Final Примечание

str.join была написана, имея в виду, для всех форм итерацию и последовательностей, а не только строки, и не вдаваясь в много детали, ее вполне ожидаемо, что обобщенная процедура не может выполнить так же быстро, как специализированная процедура для обслуживания конкретной формы данных.