-5

希望保持一组数字排序（升序或降序，但下面的示例仅显示升序）。最大速度的数据结构表示是个问题。

假设一个聚合程序不断地从许多不同的监控代理（例如通过网络）获取数字包。我们的想法是让它们始终快速分类。例如，您可能会按顺序获取这些数据包（使用整数，但实际情况是双精度）：

A = [1, 3, 4, 6]
B = [1, 2, 3]
C = [2, 3, 5]
A = [2, 4, 7, 8]

等等。在第一个数据包之后，您的聚合器中的数据结构将已经排序（数据结构会记住排序中每个数字所指的来源）：

[1, 3, 4, 6] => 事件

在下一个数据包之后，由于是新源，数据结构将如下所示

[1, 1, 2, 3, 3, 4, 6] => 事件

在下一个数据包之后，

[1, 1, 2, 2, 3, 3, 3, 4, 5, 6] => 事件

现在由于 A 发送了新数据包，我们必须找到 A 的旧值，并用新值替换它们，最后以新排序结束。替换和排序可以单独发生也可以不（就地）发生，目标是极速：

[1, 2, 2, 2, 3, 3, 4, 5, 7, 8] => 事件

请注意，当您获得第二个 A 时，所有旧的 As 都必须被新的 As 数据包“替换”，同时保持排序。每个数据包被排序到数据结构后，被复制并需要作为“事件”发送。这些数据包每隔几微秒就会在合并排序算法中疯狂而连续地到来。

* 最好的数据结构是什么？也许是 Splay 树或 AVL 树？*

4

1 回答 1

1

我猜这对于您的特定目的不会是最快的数据结构和算法，但它可能足够快。自己测试一下。

请注意，根据实际情况，astd::forward_list甚至 a可能会更快（-> big-O-notation 中的常数因子）。std::vector

tmyklebu在评论中提到了另一种方法：根据场景，按需合并可能会更快，例如单独存储所有数据集并将它们合并到 avector中以传递给事件处理程序，甚至使用“合并”迭代器（其增量获取单个数据集的下一个元素）。

通过使用自定义内存池 -> 自定义分配器可以进一步提高性能。

#include <set>
#include <iostream>
#include <iterator>
#include <algorithm>

// inserts a sorted range into the `to` container
template < typename To, typename InputIt >
void insert_new_sorted(To& to,
                       InputIt beg_old, InputIt end_old,
                       InputIt beg_new, InputIt end_new)
{
    auto const& comp = to.value_comp();
    typename To::iterator i = to.begin();

    // might improve performance: don't remove elements which are in both
    // ranges (old and new)
    while(beg_old != end_old && beg_new != end_new)
    {
        if(comp(*beg_old, *beg_new))
        {
            // remove old element
            i = to.find(*beg_old);  // "slow", no hint :(
            i = to.erase(i);
            ++beg_old;
        }else if(comp(*beg_new, *beg_old))
        {
            // insert new element
            // using the hint to achieve better performance
            i = to.insert(i, *beg_new);
            ++beg_new;
        }else
        {
            // both equal, do nothing
            ++beg_new;
            ++beg_old;
        }
    }

    // remove remaining old elements
    for(; beg_old != end_old; ++beg_old)
    {
        to.erase(to.find(*beg_old));  // "slow", no hint :(
    }

    // insert remaining new elements
    for(; beg_new != end_new; ++beg_new)
    {
        i = to.insert(i, *beg_new);
    }

    std::copy(to.begin(), to.end(),
        std::ostream_iterator<typename To::value_type>(std::cout, ", "));
    std::cout << std::endl;
}

int main()
{
    using set_t = std::multiset<double>;

    set_t const A = {1, 3, 4, 6};
    set_t const B = {1, 2, 3};
    set_t const C = {2, 3, 5};
    set_t const A2 = {2, 4, 7, 8};

    set_t result;
    insert_new_sorted(result, A.end(), A.end(), A.begin(), A.end());
    insert_new_sorted(result, B.end(), B.end(), B.begin(), B.end());
    insert_new_sorted(result, C.end(), C.end(), C.begin(), C.end());
    insert_new_sorted(result, A.begin(), A.end(), A2.begin(), A2.end());
}

输出：

1, 3, 4, 6,
1, 1, 2, 3, 3, 4, 6,
1, 1, 2, 2, 3, 3, 3, 4, 5, 6,
1, 2, 2, 2, 3, 3, 4, 5, 7, 8,

另一种方法：存储插入元素的迭代器，以加快擦除速度。

于 2013-08-04T19:31:21.393 回答