9

我有一组字符串。其中 90% 是以 . 开头的 URL "http://www."。我想按字母顺序对它们进行排序。

目前我使用 C++ std::sort()。但是 std::sort 是基于比较的快速排序的一种变体，比较两个具有长公共前缀的字符串效率不高。但是（我认为）基数排序也不起作用，因为大多数字符串都放在同一个桶中，因为公共前缀很长。

对于这个问题，有没有比普通快速排序/基数排序更好的算法？

4

6 回答 6

4

我怀疑，当您考虑 URL 的平均长度时，您尝试利用每个 URL 大约 10 个字符的公共前缀所花费的处理时间甚至不会为自己付出代价。

只需尝试完全标准的排序。如果这还不够快，请考虑并行化或分发完全标准的排序。这是一种可行的简单方法。

于 2013-04-26T23:09:59.247 回答
3

Common Prefixes 似乎自然地暗示了 trie 数据结构可能是有用的。所以想法是构建所有单词的 trie，然后对每个节点进行排序。排序应该是特定节点的子节点驻留在列表中并进行排序。这可以很容易地完成，因为在特定节点上我们只需要对子节点进行排序，因此自然会出现递归解决方案。更多灵感请参见：http: //goanna.cs.rmit.edu.au/~jz/fulltext/acsc03sz.pdf

于 2013-04-26T22:12:36.457 回答
2

最后我发现三元快速排序效果很好。我在www.larsson.dogma.net/qsufsort.c找到了该算法。

这是我修改后的实现，具有与 std::sort 类似的接口。它比我的机器和数据集上的 std::sort 快约 40%。

#include <iterator>

template<class RandIt> static inline void multiway_qsort(RandIt beg, RandIt end, size_t depth = 0, size_t step_len = 6) {
    if(beg + 1 >= end) {
        return;
    }

    struct { /* implement bounded comparing */
        inline int operator() (
                const typename std::iterator_traits<RandIt>::value_type& a,
                const typename std::iterator_traits<RandIt>::value_type& b, size_t depth, size_t step_len) {

            for(size_t i = 0; i < step_len; i++) {
                if(a[depth + i] == b[depth + i] && a[depth + i] == 0) return 0;
                if(a[depth + i] <  b[depth + i]) return +1;
                if(a[depth + i] >  b[depth + i]) return -1;
            }
            return 0;
        }
    } bounded_cmp;

    RandIt i = beg;
    RandIt j = beg + std::distance(beg, end) / 2;
    RandIt k = end - 1;

    typename std::iterator_traits<RandIt>::value_type key = ( /* median of l,m,r */
            bounded_cmp(*i, *j, depth, step_len) > 0 ?
            (bounded_cmp(*i, *k, depth, step_len) > 0 ? (bounded_cmp(*j, *k, depth, step_len) > 0 ? *j : *k) : *i) :
            (bounded_cmp(*i, *k, depth, step_len) < 0 ? (bounded_cmp(*j, *k, depth, step_len) < 0 ? *j : *k) : *i));

    /* 3-way partition */
    for(j = i; j <= k; ++j) {
        switch(bounded_cmp(*j, key, depth, step_len)) {
            case +1: std::iter_swap(i, j); ++i;      break;
            case -1: std::iter_swap(k, j); --k; --j; break;
        }
    }
    ++k;

    if(beg + 1 < i) multiway_qsort(beg, i, depth, step_len); /* recursively sort [x > pivot] subset */
    if(end + 1 > k) multiway_qsort(k, end, depth, step_len); /* recursively sort [x < pivot] subset */

    /* recursively sort [x == pivot] subset with higher depth */
    if(i < k && (*i)[depth] != 0) {
        multiway_qsort(i, k, depth + step_len, step_len);
    }
    return;
}
于 2013-04-27T23:08:01.390 回答
2

创建两个组：有前缀的和没有前缀的。对于第一组删除前缀，排序并添加前缀。对于第二组只是排序。之后将第二组分为前前缀和后前缀。现在连接三个列表（list_2_before、list_1、list_2_after）。

您可以编写自己的自定义代码，在前缀之后开始比较（即在比较时忽略前缀部分），而不是删除和添加第一个列表的前缀。

附录：如果您有多个公共前缀，您可以进一步使用它们来加快速度。最好创建一个带有非常常见前缀的浅树并将它们连接起来。

于 2013-04-26T22:39:05.830 回答
2

如果在开始快速排序之前找出向量中的最小值和最大值，那么您总是知道每次调用 partition() 的值的范围，因为分区值要么是最小值，要么是最大值（或至少接近每个子范围的最小值/最大值）和包含分区的最小值和最大值是每个子范围的另一端。

如果子范围的最小值和最大值共享一个公共前缀，那么您可以从公共前缀后面的字符位置开始进行所有分区比较。随着快速排序的进行，范围越来越小，因此它们的公共前缀应该越来越长，并且在比较时忽略它们将节省越来越多的时间。多少，我不知道；你必须对此进行基准测试，看看它是否真的有帮助。

无论如何，额外的开销是相当小的；一次遍历向量以找到最小和最大字符串，每个字符串花费 1.5 次比较 (*)，然后检查每个分区以找到该分区的最大共享前缀；检查相当于比较，它可以从包含前缀的最大共享前缀开始，所以它甚至不是一个完整的字符串比较。

  • 最小/最大算法：一次扫描向量两个元素。对于每一对，首先将它们相互比较，然后将较小的与运行最小值进行比较，将较大的与运行最大值进行比较。结果：两个元素进行 3 次比较，或每个元素进行 1.5 次比较。
于 2013-04-27T02:52:13.770 回答
1

令人惊讶的是，工程并行字符串排序论文在 URL 数据集上对大量单线程算法进行了基准测试（参见第 29 页）。Rantala 的带有缓存的多键快速排序变体领先；您可以在本文引用的这个存储库中测试 multikey_cache8 。

我在那篇论文中测试了数据集，如果有任何迹象表明你在前十个字符中几乎看不到一点熵，并且区分了 100 个字符范围内的前缀。执行 100 次基数排序将破坏缓存而几乎没有什么好处，例如，对一百万个 url 进行排序意味着您要在每个键中寻找约 20 个可区分位，代价是约 100 次缓存未命中。

虽然一般基数排序在长字符串上表现不佳，但 Kärkkäinen 和 Rantala 在Engineering Radix Sort for Strings中描述的优化对于 URL 数据集来说已经足够了。特别是他们提前读取了 8 个字符并用字符串指针缓存它们；对这些缓存值进行排序会产生足够的熵来解决缓存未命中问题。

对于较长的字符串，请尝试该存储库中的一些基于 LCP 的算法；根据我的经验，URL 数据集大约处于高度优化的基数类型排序和基于 LCP 的算法之间的收支平衡点，这些算法在较长的字符串上渐进地做得更好。

于 2017-06-10T18:22:27.283 回答