替换字符串中的空字符串

Question

我不小心发现在python中,一个表单的操作

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中重复连接相当快,但在其他地方并不一定如此.)

我甚至无法在文档中找到任何暗示替换空字符串的行为应该以这种方式运行的内容,文档str.replace()简单地说:

返回字符串的副本,其中所有出现的substring old都替换为new.如果给出可选参数计数,则仅替换第一次计数.

我没有理由认为我们应该假设字母之间的间隙应该算作空字符串的出现(可以说,你可以在字符串中的任何地方放置无限空字符串),因此,依赖这种行为可能是一个坏事理念.

这个操作也很少见 - 将一系列字符串连接在一起更为常见 - 连接字符串的各个字符并不是我个人经常要做的事情.

有趣的是,这x.replace("", y)似乎是Python源代码中的特殊内容:

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它是一个直接循环,其中源和字符串中的替换字符被复制到结果字符串.Loop被编码为尽可能快.

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);

Join方法也有一个循环,但有一些改进的地方(由于我没有找到所有方面,因为以下方式编码)和瓶颈的原因.

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;
    }
}

正如你在这里看到的,在一个循环中

• 字符串的每个项目都是索引的
• 确定项目的大小
• 索引项转换为字符串

上述三种操作即使可能是内嵌的,也会产生相当大的开销.注意这也解释了为什么使用List与使用STring相比具有不同的结果,如Blended所观察到的

同时比较两个循环,

前者

• 可以轻松自动矢量化
• 缓存友好.

最后的说明

在str.join写于牢记各种形式的迭代和顺序,而不只是字符串,并没有在很大程度上细节去,它很期待一般化程序可能没有那么快进行的专门程序提供数据的一种特殊形式.