Python中的split('\n')方法是如何实现的？

Question

这是一个理论性的问题，目的是帮助理解Java和Python之间的区别。

在Java中，如果你想把一个文件的内容读入一个数组，你需要知道文件有多少行，这样才能在声明数组时定义它的大小。因为你无法提前知道这个数量，所以你需要用一些技巧来解决这个问题。

而在Python中，列表的大小是可以变化的，所以把文件的内容读入一个列表可以通过以下两种方式实现：

lines = open('filename').read().split('\n')

或者

lines = open('filename').readlines()

在这种情况下，split('\n')是怎么工作的呢？Python的实现是否也在背后做了一些技巧，比如在需要的时候自动扩大数组的大小等等？

任何能帮助理解这个问题的信息都非常感谢。

Answer 1

我觉得（虽然我没有重新检查代码）split()这个方法会计算字符串中的换行符数量，然后就分配一个合适大小的列表。

不过，所有的Python列表都会多分配一些空间，所以如果你不断往里面添加东西，整体的时间复杂度是线性的。

Answer 2

如果你想找实际的代码实现，可以试试这个链接：http://svn.python.org/view/python/trunk/Objects/stringlib/split.h?view=markup

关于“基本”的分割功能，可以从大约第148行开始查看。

简单总结一下：它会遍历字符串，寻找你定义的分割字符，然后把上一个找到的字符和当前找到的字符之间的字符串（对于第一个情况是从字符串开始）添加到输出的元组中，使用的是“PyList_Append”。最后，它会把字符串剩下的部分也添加到元组里。

代码里有一些占位符，用来在结果元组达到当前最大大小时分配更多的空间，还有一些单独的函数，用来检查一个分割字符和另一个分割字符串（比如说，如果你想用'/t'这两个字符来分割字符串，也是可以的，通过一个单独的函数）。

Answer 3

str.split() 的实现内部会调用 list.append()，而 list.append() 又会调用一个内部函数 list_resize()。在这个函数的源代码中，有这样一段注释：

这个函数会根据列表的大小进行过度分配，为将来的增长留出空间。虽然这种过度分配不是很多，但足以在长时间的 append() 操作中，确保性能不会因为系统重新分配内存的效率低下而受到影响。

它的增长模式是：0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...