About
RSS

Bit Focus


日常的算法 - 顺序统计

Posted at 2011-09-30 09:20:03 | Updated at 2024-12-09 17:35:16

    顺序统计指的是在一坨并没有排序的数据上找出跟顺序量有关的元素. 典型的顺序统计包括找最小值或最大值算法, 这两个算法可以说没有任何技巧而言, 暴力地遍历一次数据集合就行了, 如找最小值算法的实现 (以 C++ 面向迭代器的程序设计描述, 不考虑集合为空的情形. 以后的例子相同)
template <typename _Iterator>
_Iterator find_min(_Iterator begin, _Iterator end)
{
    _Iterator min = begin;
    for (++begin; begin != end; ++begin) {
        if (*begin < *min) {
            min = begin;
        }
    }
    return min;
}
    将这两件事情揉合在一起, 即从一个集合中同时找到最小值和最大值, 相比于分头寻找, 能够节省不少时间, 原因不仅仅是两次循环合并成一次循环, 运用一些技巧能显著地减少比较的次数.
    在每一次取出剩余元素时, 同时取出两个, 先将这两个比较大小, 然后将较小的元素与当前最小值比较, 而将较大的值与当前最大值比较取出

    +-------+-----------+-----
    | begin | begin + 1 | ...
    +-------+-----------+-----
        |         |
        +--( < )--+
            / \
           /   \
+----------+   +-------------+         +-----+
| less one |   | greater one |--( < )--| max |
+----------+   +-------------+         +-----+
      |
      |                                +-----+
      +-------------------------( < )--| min |
                                       +-----+

    这样每寻访 2 个元素, 需要 3 次元素比较, 加上判断循环是否结束需要 1 次比较, 而分开查找, 则每 1 个元素需要 2 次元素比较, 加上 1 次循环判断结束的比较. 之所以这么计较比较的次数, 因为目前计算机体系结构和分支语句非常不友好, 太多分支 (意味着大量的预测失败) 的程序会因为无法充分利用流水线而显著地降低实际执行效率.
    下面是实现的例子
template <typename _Iterator>
std::pair<_Iterator, _Iterator>
    _next_pair_min_max(_Iterator min, _Iterator max, _Iterator less, _Iterator greater)
{
    if (*less < *min) {
        min = less;
    }
    if (*max < *greater) {
        max = greater;
    }
    return std::make_pair(min, max);
}

template <typename _Iterator>
std::pair<_Iterator, _Iterator>
    _find_min_max(_Iterator min, _Iterator max, _Iterator begin, _Iterator end)
{
    std::pair<_Iterator, _Iterator> result(min, max);
    while (begin != end) {
        _Iterator next0 = begin++;
        _Iterator next1 = begin++;
        if (*next0 < *next1) {
            result = _next_pair_min_max(min, max, next0, next1);
        } else {
            result = _next_pair_min_max(min, max, next1, next0);
        }
    }
    return result;
}

template <typename _RandomAccessIterator>
std::pair<_RandomAccessIterator, _RandomAccessIterator>
    find_min_max(_RandomAccessIterator begin, _RandomAccessIterator end)
{
    if (std::distance(begin, end) % 2 == 1) {
        return _find_min_max(begin, begin, begin + 1, end);
    }

    return (*begin < *(begin + 1)) ? _find_min_max(begin, begin + 1, begin + 2, end)
                                   : _find_min_max(begin + 1, begin, begin + 2, end);
}
    算法的入口是 find_min_max 而核心是 _find_min_max, _find_min_max 要求提供初始的 minmax, 以及后续迭代的区间. 而找出初始的 minmax 迭代器其实是很困难的事情, 如果想要运用到通用情形; 而上述例子中, 从 find_min_max 就可以看出来这并不是什么通用情形, 它要求了一个 STL 中最高级别特化的迭代器类型 random access iterator, 这基本上就宣告了 "除了 vector 别来碰我" (我想实际运用中 deque 这样的容器替代 vector 并不是一个好主意).
    当然这里有一定故弄玄虚的成分, 实际上需求 random access iterator 是为了 std::distance 能够迅速求得迭代区间的长度, 从而确定元素个数的奇偶性, 确保传递给 _find_min_max 的区间中元素个数一定是偶数个, 同时传递初始的 minmax. 任何别的手段只要能提供这些信息, 那么调用 _find_min_max 即可. 但既然有这样的要求, 多多少少会对容器的选择有影响.

    求最小值, 最大值可以视作两个特化, 那就是, 在一堆元素中找到第 K 小的那个. 一般来说代入 K=1 时, 那么 "在一堆元素中找到第 1 小的那个", 也就是找 "最小" 的那个. 自然语言的表现确实直观, 可是翻译成程序员语, "最小" 其实意味着 K=0, 也就是说如果 N 表示元素个数, 那么 K 的取值范围应该介于 [0, N-1] 这个自然数区间内. 这样的 K 值意义将用于接下来的问题描述和分析.
    一个直观的解答方案是, 先找出第 0 小的数, 从集合中排除掉, 接下来是第 1 小的, 如此这般, 直到找到第 K 小的数. 在 K 值较小的时候这不失为一种简单而高效的方法. 当 K 值可能会很大, 或者不确定时, 可以考虑下面的方案.
    考虑一个实际情况, 假设现在要在下面这个表 (共 8 个元素) 中找到第 5 小的数
4 9 7 3 8 3 6 1
    拿出这个序列的开头那个数 4, 将剩下的成两个部分, 一个部分的数全部小于 4, 另一部分全部不小于 4
3 3 1 - 9 7 8 6
    两个部分中元素的相对排列跟原来容器一致, 或者, 随便怎么排列, 总之不需要排序, 因为排序实在是太耗时了.
    较小的那一坨中有 3 个, 那么 4 本身是第 3 小的数 (再说一次, 最小的数是第 0 小的数), 而要找的是第 5 小的数, 因此较小坨和 4 本身都可以直接弃掉, 现在去较大坨找第 (5 - 3 - 1 =) 1 小的数.
    与之前类似, 用首个数 9 将序列分开, 结果是
7 8 6 -
    显然需要找的那个数在现在的较小坨中, 弃掉 (空的) 较大坨和 9, 继续.
6 - 8
    较小坨中有 1 个数, 因此 7 正是第 1 小的数, 答案产生, 就是 7 自己.
    这是个典型的分而治之加上撞大运的算法, 将区间按照是否小于首个数 A 分成三部分 (包括 A 自身一部分), 如果这时 A 恰好是要找的数, 那么撞大运成功返回 A 即可, 否则就看要找的数落在较小那一边还是较大那一边, 然后去递归去找那一边就好了. 下面是实现示例 (为了避免在分元素时产生大量的元素复制操作, 实际存放的是迭代器)
template <typename _Iterator>
_Iterator _find_k_th(std::vector<_Iterator> const& iters, int k)
{
    std::vector<_Iterator> lessers;
    std::vector<_Iterator> greaters;
    typename std::vector<_Iterator>::const_iterator begin = iters.begin();
    _Iterator first = *begin;
    for (++begin; begin != iters.end(); ++begin) {
        if (**begin < *first) {
            lessers.push_back(*begin);
        } else {
            greaters.push_back(*begin);
        }
    }
    if (k == lessers.size()) {
        return first;
    }
    if (k < lessers.size()) {
        return _find_k_th(lessers, k);
    }
    return _find_k_th(greaters, k - lessers.size() - 1);
}

template <typename _Iterator>
_Iterator find_k_th(_Iterator begin, _Iterator end, int k)
{
    std::vector<_Iterator> iters;
    for (; begin != end; ++begin) {
        iters.push_back(begin);
    }
    return _find_k_th(iters, k);
}
    在递归过程中, 撇开直接 bingo 到要找的数这种情况, 平均每次查找的范围可以收敛一半左右, 所以这个算法的时间开销大约会与区间中元素的个数呈线性比例 --- 跟直接找最值差不多咯.

    将这个算法做一些推广, 便能得到大名鼎鼎的快速排序了. 在分堆之后, 如果不是去递归找第某小的数, 而是将分开的两堆递归地排个序, 然后将三个部分重新连在一起, 那么就可以得到一个排序过的序列不是么?
template <typename _Iterator>
std::vector<_Iterator> _sort(std::vector<_Iterator> const& iters)
{
    if (iters.empty()) {
        return std::vector<_Iterator>();
    }
    std::vector<_Iterator> lessers;
    std::vector<_Iterator> greaters;
    typename std::vector<_Iterator>::const_iterator begin = iters.begin();
    _Iterator first = *begin;
    for (++begin; begin != iters.end(); ++begin) {
        if (**begin < *first) {
            lessers.push_back(*begin);
        } else {
            greaters.push_back(*begin);
        }
    }
    std::vector<_Iterator> sorted_lessers = _sort(lessers);
    std::vector<_Iterator> sorted_greaters = _sort(greaters);

    sorted_lessers.push_back(first);
    sorted_lessers.insert(sorted_lessers.end(), sorted_greaters.begin(), sorted_greaters.end());
    return sorted_lessers;
}

template <typename _Iterator>
std::vector<_Iterator> sort(_Iterator begin, _Iterator end)
{
    std::vector<_Iterator> iters;
    for (; begin != end; ++begin) {
        iters.push_back(begin);
    }
    return _sort(iters);
}
    如快速排序这样的算法在 STL 中自带是很日常的行为. 不过, STL 中快速排序的算法直接在待排序区间上动手术, 即通过修改原区间上元素的排列来体现排序, 这样一来就要求待排序区间对应的容器本身不得是 const 修饰的. 此外 std::sort 要求传入的是 random access iterator.

Post tags:   Generic Programming  STL  C++  Order Statistic  Algorithm  Template

Leave a comment:




Creative Commons License Your comment will be licensed under
CC-NC-ND 3.0


. Back to Bit Focus
NijiPress - Copyright (C) Neuron Teckid @ Bit Focus
About this site