Python 在这点上竟被 Julia 和 R 碾压？！

本文作者戴卓嘉，拥有 10 年开发经验的数据科学家，以下是他对 Julia、R、Python 分别在字符串排序速度上的示例与对比，Python 为何会被碾压？废话不多说，马上开讲。

一、Radix Sort 让 Julia 的字符串排序速度更快了

一个新的字符串排序算法 RadixSort 已作为 SortingLab.jl 的一部分发布了。

这个新算法能让 Julia 的字符串排序速度快3倍！特别是对固定长度的字符串。

用法示例

二、Julia、R、Python 谁更快？

当单个字符串的数量接近数字字符串时，Julia 是最快的，用了 Numpy 排序的 Python 第二，R 最慢。

而当存在大量重复值（或者如果单一字符串与字符串的比例很小，例如1：100）并且如果存在大数元素，R 是最快的。

但如果要排序的数字元素很小（例如1000万），Julia 有时会比 R 更快，即使有很多重复项。

三、为什么 R 面对大量重复值时排序这么快？

R 使用的是一种字符串驻留形式，理论上讲，这种方法需要更多的安装时间。Julia 默认没有字符串驻留，因此无法执行 R 使用开箱即用的优化。

对应的排序算法代码获取地址：

Julia：

https://gist.github.com/xiaodaigh/d2014bb892134d8636a0af1bce0db859#file-string_sort_perf-jl

R + Python：

https://github.com/Rdatatable/data.table/wiki/Benchmarks-:-Grouping

效果展示

能够快速排序字符串是现代数据操作的关键支柱。虽然我们承认对字符串向量进行排序时，真正想要的其实是分组，但是能够快速排序字符串仍然很有价值。

然而，最初的调查显示，在对具有大量重复值的字符串进行排序时，与 R 相比，Julia 中的字符串排序较慢。这可能是通过 R 将 Julia 与 C 进行比较，但从用户的角度来看，直言不讳地说，他们可能并不关心。

对 Julia 来说，虽然有 radixsort 的 3 倍性能加持，但毕竟还是比不过 R。此外，Python 也很慢（参见上面的基准测试），希望 pandas2 可以帮助解决这个问题 。

但是我觉得，这只是明确地证实 Julia 生态系统目前还不完善，而并不能因此认为 Julia 一定就慢，一定就比不过 R。

四、还能不能更快？

考虑到这一点，我想调研 Julia 进行字符串排序的速度，能否和 R 并驾齐驱，至少能够接近 R 在字符串排序中的表现。研究后发现 R 使用基数排序对字符串进行排序，因此是字符串基数排序的 Julia 实现就是顺理成章的事。

我的大部分研究都指向了字符串的最高有效数字(MSD)基数排序的一些变体。此外，对于已在 SortingAlgorithms.jl 中实现的某些位类型(但不是字符串)，存在 LSD 基数排序。 所以我已经实现了 MSD 和 LSD 变种的基数排序算法。

五、基数排序测试结果

以下是我在开发基数字符串排序算法时遇到的几个问题。

问题 1：访问底层字节

要执行基数排序，需要访问基础字节。 在字符串中加载第 n 个字符的字节的一种方法是通过代码单元 codeunit(s, n) 。例如：

但是根据我的计算，这个会很慢，赶不上 R。经过多次实验，我发现一次加载 8 个字节几乎与加载 1 个字节一样快，因此这成了我的首选方法。

这种方法也有两个情况：

1. 字符串短于 8 个字节的情况

短于 8 字节的时候，我们需要特别小心。如果无论如何都加载 8 个字节，并将不需要的位设置为 0，我的经验来看大部分情况下是可行的。但仍然可能导致尝试访问程序不可用的内存并导致崩溃。目前解决它的方法是测试长度是否短于 8 个字节，然后使用较慢的加载器。

而一般出现崩溃的情况，都是发生在跨页面边界加载数据的时候。要搞清楚到底什么时候程序会崩溃，需要了解内存的加载方式。我的理解是：

• 数据以特定大小的页面加载到内存中(在大多数 64 位机器上，大小至少为 4 kb)。
• 当字节加载时，可以从同一页面内的任何位置加载，但跨页边界加载可能会导致程序崩溃。只有那些距页面边界 8 个字节或更少的字符串才会引起问题。

因此 Julia 布道者 @stevengj 指出，可以使用(UInt(pointer(s)) & 0xfff) > 0xff8 来检查字符串是否在边界附近

2. 字符串超过 8 个字节的情况

如果字符串超过 8 个字节，可以一次迭代地对字符串向量进行 8 字节排序。 在基数排序的 MSD 和 LSD 变体中都有很多方法，在此不再赘述。

问题 2：在排序基数时置换字符串

一旦将基础字节加载到字节向量中，就可以使用基数排序对字节向量进行排序，这非常快。但是还需要同时置换原始的字符串向量。为此，我编写了 sorttwo!(bytesvec, stringvec) 函数，用来给字节向量 bytesvec 进行排序，并以在排序过程中置换 bytesvec 相同的方式置换字符串向量。

sorttwo! 函数是对 SortingAlgorithms.jl 中现有基数排序函数的简单修改。对于 R 用户， sortperm 相当于 R 的 order。

六、MSD 和 LSD 算法的实现

我已经实现了 MSD 和 LSD 变量。 根据我的研究，通常情况是 MSD 算法对于可变长度字符串支持更好，并且 LSD 算法对固定长度算法最有效。有些人甚至声称 LSD 不适用于可变长度字符串向量。 我认为这不正确，因为你可以用 0 表示一个空字节(即使技术上是 null)。

例如，如果我使用 8 字节加载器加载字符串“abc”，则它变为十六进制格式，0x6162630000000000 其中 6162 和 63 是 ASCII 码“a”，“b”和“c”十六进制表示形式。

我可以使用基数排序和其他字符串对其进行排序，但这是否是最有效的是真正的问题，还不确定。我对 MSD radixsort 的实现基于 radix 3-way 快速排序。

从基准测试来看，即使对于可变长度字符串，我的 MSD 实现也不像 LSD 算法那样高效，这就有点奇怪了。因为我的大多数研究都认为 MSD 比 LSD 更具性能。这可能表明我对 MSD 基数排序的实现不是最理想的。

七、为什么 R 在大量重复值的排序上比 Julia 和 Python 都快？

许多人指出 R 使用一种字符串驻留来存储其字符串。我对其工作原理的理解是这样的：例如，考虑 a = c("abcdefghi", "abcdefghi") 是包含相同内容的两个字符串的向量，因此 a[1] 和 a[2] 只指向“abcdefghi”的一个存储空间，而不是存储相同字符串的两个副本。

如果相同的字符串仅存储一次，很显然是可以提高空间效率。此外，更重要的是，人们能够利用它来制作更高性能的算法。

此外，这有可能简化分组操作。如果用户知道具有相同内容的所有字符串具有相同的指针，那么我们可以直接给固定大小的指针进行分组，从而可以更快地进行排序和分组。

但是，Julia 默认没有驻留的字符串(虽然有一个包InternedStrings.jl )，因此这些类型的优化并不容易获得，导致 Julia 可能很难在所有情况下匹配 R 的字符串排序性能。

八、收获

这开辟了另一种看待事物的方式：R 需要更长的时间来加载这些字符串，因为它们还需要将它加载到全局缓存中；加载时间越长，分拣速度越快。 那么，Julia 就可能会创建一个模仿 R 行为并导致更高性能排序的数据结构。

尽管现在 R 最快，未来还真不好说。有研究论文表明，最有效加快排序算法速度的方法，就是并行技术，因此我对 MSD 字符串基数排序的实现可能不是最优解。

九、结束语

这篇文章主要是作者的思路和结论。省去了中间的起承转合，很考验读者对算法的理解程度。其实无论是人，机器，算法，追求的都是更快、更高、更强。不断地发现并突破极限，才会有新技术、新算法被创造出来。

如果你也想投入算法的星辰大海中，王晓华的《算法应该怎么“玩”？》千万不要错过，它既能帮助你掌握各种常用的基础算法、算法设计的常用思想和模式，还能让你拥有建模的能力。