更快的字符串排序与长公共前缀？

Question

更快的字符串排序与长公共前缀？

stringalgorithmsortingdata-structures

9

我有一组字符串，其中90％以“http://www。”开头。我想按字母顺序对它们进行排序。

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

是否有比普通快排/基数排序更好的算法解决这个问题？

- richselian

2

能否在排序之前删除前缀？ - Kyle Strand

使用基数树可能会增加一些效率。 - Hot Licks

6个回答

3

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

- Anil Vaitla

我想把一个字符串分割成树节点可能会很有帮助。树节点使得非连续访问更加容易。我并不是要避免O(nlogn * LEN)的最坏情况。我相信快速排序仍然比基于树的解决方案更快。 - richselian

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;
}

- richselian

我喜欢它！我以前没听说过这个。但是它如何帮助解决前缀问题呢？ - Anil Vaitla

在正常的快速排序中，它需要O(nlogn * L)的时间，其中L是平均公共前缀长度。在三向切分的快速排序中，我们需要O(n)来进行划分并移动到更深的层次，移动需要O(L)的时间。所以最坏情况下的性能是O(n * L)。 - richselian

@richselian 我认为你的大O分析有问题。左右分区按照快速排序进行排序，因为“深度”没有增加。中间分区的元素可以被视为在较短字符串上运行快速排序，我们发现在实践中可以更快地进行比较，但是比较时间仍然被认为是恒定的，除非我们想引入一个平均字符串长度的术语。 - Joel Nelson

1

@JoelNelson，你可以在http://www.larsson.dogma.net/ssrev-tr.pdf获取严格的证明。该算法是Jesper Larsson的qsufsort的一部分。 - richselian

@richselian 谢谢。我理解的方式是，它说这是O(n logn)。O(n * L) 明显比 O(n logn) 更好，所以如果 O(n * L) 真的是最坏情况，那将是相当了不起的事情。+1 非常酷的算法。在这种情况下，它可能是最快的通用排序算法。但是，40％的改进并没有指向渐近改进。 - Joel Nelson

@JoelNelson，也许我没有像std::sort那样进行优化（比如在小规模情况下切换到insert_sort）。我在https://github.com/richox/multiway-qsort上上传了一些测试用例。 - richselian

2

创建两个组：带有前缀和不带有前缀的。对于第一组，先删除前缀，再排序，最后添加回前缀。对于第二组，只进行排序。之后将第二组分成前缀之前和前缀之后两部分。现在将这三个列表（list_2_before、list_1、list_2_after）连接起来。

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

附注：如果您有多个共同的前缀，您可以进一步利用它们以加快速度。最好创建一个浅树，具有非常常见的前缀，并将它们合并。

- ElKamina

这将有助于提高性能。但是URL可以分成更小的组，例如http://www.google.com/xxxx或http://yahoo.com/xxxx。我们能否进一步改进它？ - richselian

只要前缀数量可控，您就可以进一步改进。对于更一般的情况，我建议使用非常浅的树形结构（例如修剪的trie）来跟踪各种前缀。 - ElKamina

你可以将前缀替换为单个指定字符，但是在维护未带前缀字符串的真实排序顺序时会遇到麻烦（假定这些字符串有一个“无前缀”指定字符）。实际上按字母顺序排序很重要吗？ - Hot Licks

2

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

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

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

最小/最大算法：每次扫描向量两个元素。对于每一对，首先将它们彼此比较，然后将较小的与运行中的最小值进行比较，将较大的与运行中的最大值进行比较。结果：两个元素的三次比较，或者每个元素1.5次比较。

- rici

这有点难理解，但我认为这是最好的答案。对我来说，这个想法的核心是，一旦你将列表分区超过一次，你可以找到相邻分区元素的公共前缀，并知道中间的元素共享该前缀。 - Joel Nelson

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的算法之间的临界点。

- KWillets

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Timothy Shields · Accepted Answer

我认为，当你考虑到URL的平均长度时，尝试利用大约10个字符的常见前缀来处理时间甚至不值得。

只需尝试完全标准的排序。如果速度不够快，可以考虑并行化或分发完全标准的排序。这是一个简单直接的方法，一定会奏效。