黄兵的个人博客

Python字符串

在其他语言中，如 Java，有可变的字符串类型，比如 StringBuilder，每次添加、改变或删除字符（串），无需创建新的字符串，时间复杂度仅为 O(1)。这样就大大提高了程序的运行效率。

但可惜的是，Python 中并没有相关的数据类型，我们还是得老老实实创建新的字符串。因此，每次想要改变字符串，往往需要 O(n) 的时间复杂度，其中，n 为新字符串的长度。

你可能注意到了，上述例子的说明中，我用的是“往往”、“通常”这样的字眼，并没有说“一定”。这是为什么呢？显然，随着版本的更新，Python 也越来越聪明，性能优化得越来越好了。

这里，我着重讲解一下，使用加法操作符'+='的字符串拼接方法。因为它是一个例外，打破了字符串不可变的特性。

str1 += str2  # 表示str1 = str1 + str2

我们来看下面这个例子：

s = ''
for n in range(0, 100000):
    s += str(n)

你觉得这个例子的时间复杂度是多少呢？

每次循环，似乎都得创建一个新的字符串；而每次创建一个新的字符串，都需要 O(n) 的时间复杂度。因此，总的时间复杂度就为 O(1) + O(2) + … + O(n) = O(n^2)。这样到底对不对呢？乍一看，这样到底对不对呢？

乍一看，这样分析确实很有道理，但是必须说明，这个结论只适用于老版本的 Python 了。自从 Python2.5 开始，每次处理字符串的拼接操作时（str1 += str2），Python 首先会检测 str1 还有没有其他的引用。如果没有的话，就会尝试原地扩充字符串 buffer 的大小，而不是重新分配一块内存来创建新的字符串并拷贝。这样的话，上述例子中的时间复杂度就仅为 O(n) 了。

因此，以后你在写程序遇到字符串拼接时，如果使用’+='更方便，就放心地去用吧，不用过分担心效率问题了。

另外，对于字符串拼接问题，除了使用加法操作符，我们还可以使用字符串内置的 join 函数。string.join(iterable)，表示把每个元素都按照指定的格式连接起来。

l = []
for n in range(0, 100000):
    l.append(str(n))
l = ' '.join(l) 

由于列表的 append 操作是 O(1) 复杂度，字符串同理。因此，这个含有 for 循环例子的时间复杂度为 n*O(1)=O(n)。

接下来，我们看一下字符串的分割函数 split()。string.split(separator)，表示把字符串按照 separator 分割成子字符串，并返回一个分割后子字符串组合的列表。它常常应用于对数据的解析处理，比如我们读取了某个文件的路径，想要调用数据库的 API，去读取对应的数据，我们通常会写成下面这样：

def query_data(namespace, table):
    """
    given namespace and table, query database to get corresponding
    data         
    """

path = 'hive://ads/training_table'
namespace = path.split('//')[1].split('/')[0] # 返回'ads'
table = path.split('//')[1].split('/')[1] # 返回 'training_table'
data = query_data(namespace, table) 

字符串性能测试：

# 测试 1000 条数据，方式一
import time
start_time = time.perf_counter()
s = ''
for n in range(0, 1000):
    s += str(n)
end_time = time.perf_counter()
print('Time elapse: {}'.format(end_time - start_time))
返回结果: Time elapse: 0.0004374515265226364

# 测试 1000 条数据，方式二
import time
start_time = time.perf_counter()
s = []
for n in range(0, 1000):
    s.append(str(n))
''.join(s)
end_time = time.perf_counter()
print('Time elapse: {}'.format(end_time - start_time))
返回结果: Time elapse: 0.0004917513579130173

# 测试 1000 条数据，方式三
import time
start_time = time.perf_counter()
s = ''.join(map(str, range(0, 1000)))
end_time = time.perf_counter()
print('Time elapse: {}'.format(end_time - start_time))
返回结果：Time elapse: 0.00021015387028455734

分别测试一百万和一千万条数据，结果如下：
100万:
方式一：Time elapse: 0.3384760869666934
方式二：Time elapse: 0.34538754168897867
方式三：Time elapse: 0.2445415174588561

1000万：
方式一：Time elapse: 4.24716751743108
方式二：Time elapse: 3.1754934675991535
方式三：Time elapse: 2.2939002392813563