<datalist id="bgabf"></datalist>
    <textarea id="bgabf"></textarea><q id="bgabf"><del id="bgabf"><canvas id="bgabf"></canvas><strong id="bgabf"></strong><legend id="bgabf"></legend></del></q>
    <col id="bgabf"><blockquote id="bgabf"><caption id="bgabf"><noscript id="bgabf"><em id="bgabf"><col id="bgabf"><kbd id="bgabf"></kbd><datalist id="bgabf"><colgroup id="bgabf"></colgroup></datalist></col><em id="bgabf"><rp id="bgabf"></rp></em><label id="bgabf"></label></em><canvas id="bgabf"><bdo id="bgabf"><q id="bgabf"></q><ul id="bgabf"><figure id="bgabf"><select id="bgabf"></select></figure><div id="bgabf"></div></ul><style id="bgabf"></style></bdo><param id="bgabf"><small id="bgabf"></small></param></canvas><style id="bgabf"></style><code id="bgabf"></code><aside id="bgabf"><ins id="bgabf"><ins id="bgabf"><div id="bgabf"><rp id="bgabf"></rp><i id="bgabf"></i></div></ins><del id="bgabf"></del></ins></aside></noscript></caption><object id="bgabf"></object></blockquote></col><embed id="bgabf"></embed>
    <tr id="bgabf"></tr><figcaption id="bgabf"></figcaption>
          <rp id="bgabf"></rp>

            <legend id="bgabf"><style id="bgabf"></style><canvas id="bgabf"></canvas><dfn id="bgabf"><cite id="bgabf"><acronym id="bgabf"></acronym></cite></dfn></legend>

          1. <progress id="bgabf"><li id="bgabf"></li><select id="bgabf"><samp id="bgabf"><dl id="bgabf"></dl></samp></select></progress><q id="bgabf"><noframes id="bgabf"><small id="bgabf"><mark id="bgabf"><del id="bgabf"></del><figcaption id="bgabf"><dl id="bgabf"><em id="bgabf"><datalist id="bgabf"></datalist></em></dl></figcaption></mark><map id="bgabf"></map><form id="bgabf"><dl id="bgabf"><blockquote id="bgabf"><figure id="bgabf"></figure></blockquote><span id="bgabf"><link id="bgabf"></link></span></dl></form><span id="bgabf"></span></q>

          2. Python 再牛,在字符串排序上还是被 Julia 和 R 碾压AI学院

            来源:未知 / 作者:zz / 2018-09-07 10:58
            感谢 radixsort 让 Julia 的字符串排序速度更快了 一个新的字符串排序算法 radixsort 已作为 SortingLab.jl 的一部分发布了。 这个新算法能让 Julia 的字符串排序速度快3倍

            《实例对比 Julia, R, Python,谁是狼语言?》我们简单介绍了 Julia 的背景,以及通过优化一个似然函数的参数 μ 和 σ,来对比 Julia、R、Python 三门语言,谁更快,谁的输出更舒适。

            有读者表示看得不够爽,所以小编找到了一名拥有10年金融领域开发经验的数据科学家戴卓嘉,并获授权翻译他的文章《Julia vs R vs Python: string-sort performance + an unfinished journey to optimizing Julia's performance》。

            废话不多说,马上开讲。

            感谢 radixsort 让 Julia 的字符串排序速度更快了

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

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

            用法示例

            谁更快?Julia、R、Python

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

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

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

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

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

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

            Julia:

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

            R + Python:

            http://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个字节,然后使用较慢的加载器。

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

            1. 数据以特定大小的页面加载到内存中(在大多数64位机器上,大小至少为4kb)。

            2. 当字节加载时,可以从同一页面内的任何位置加载,但跨页边界加载可能会导致程序崩溃。

            3. 因此,只有那些距页面边界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 字符串基数排序的实现可能不是最优解。

            结束语

            其实无论是人,机器,算法,追求的都是更快、更高、更强。不断地发现极限,不断地突破极限,不断有新技术、新算法被创造出来。我们向着星辰大海,不断的前进。

            这篇文章更准确的说,是作者做基准测试时候的一些随笔,而不是一个教程,所以中间省去了很多解释的环节,直接上来就是思路和结论。

            中间好像也没有太多的起承转合,这就对读者对算法的理解程度,提出了一定的考验。
             

            阅读延展

            1
            3

            2m彩票 |2m彩票网 |2m彩票官网 | |手机版 | | LG彩票|盛彩彩票网|极速分分彩官网|0365cc彩票下载|万和彩票网|国际彩票网|