c++ - 维护一个对象容器，该容器按该对象的成员与其邻居的成员之间的差异排序

Question

我正在努力实现直方图，关键点之一是快速合并直方图 bin。因为我对直方图近似的数据集没有先验知识，所以我需要想出一种方法，在超过最大 bin 数后快速合并相邻的 bin。

因此，举例来说，如果您使用五个直方图 bin 对数据流 23、19、10、16、36、2、9、32、30、45 进行近似，则您需要读入前五个元素, 获得:

(23, 1), (19,1), (10,1), (16,1), (36,1)

添加 bin (2,1) 会导致问题，因为我们已经超过了 bin 的最大数量。因此，我们添加 (2,1) 并合并两个最近的 bins -- (16,1) 和 (19,1) -- 以获得一个新的 bin (17.5,2) 来替换这两个 bins。

对直方图的其余部分重复此方法可以得到最终输出:

(2,1)、(9.5,2)、(19.33,3)、(32.67,3)、(45,1)。

在不考虑复杂性问题的情况下实现这一点是微不足道的。但是，我真的很担心针对大型数据集优化它，因为我的“微不足道”的实现最终需要 15 秒才能在 100,000 个高斯分布值的流上运行。

我目前的想法是使用 boost::multi_index 来跟踪我的 HistogramBin 结构，它被定义为:

struct HistogramBin
{
    double bin;
    unsigned long count;
    bool isNull;

    HistogramBin(double x, bool n = false)
    : bin(x), count(1), isNull(n) {}

    bool operator<(const HistogramBin &other) const
    { return (bin < other.bin); }

    // Merges other with this histogram bin
    // E.g., if you have (2.0,1) and (3.0,2), you'd merge them into (2.67,3)
    void merge(const HistogramBin &other)
    {
        unsigned long old_count = count;
        count += other.count;
        bin = (bin*old_count + other.bin*other.count)/count;
    }

    // Gets the difference between two histogram bins
    const double getDifference(const HistogramBin &other) const
    { return (double)abs(bin - other.bin); }
};

因此，multi_index 将使用 ordered_unique<> 对 HistogramBin::bin 进行排序。

现在，这并没有解决根据相邻 bin 之间的差异对 bin 进行排序的问题。 HistogramBin::bin 的索引为我们提供了 HistogramBin 对象的有序列表，但下一步是计算当前 bin 与下一个 bin 之间的差异，然后对那些值进行排序.

有没有办法对这些值进行排序，同时保持列表的完整性，并且不引入新的容器(例如差异/迭代器键/值对的多重映射)？

维护这个列表是我目前关于复杂性问题的近乎最优的解决方案的想法，因为它只需要在有合并时更改，而合并只有在添加新值时才会发生。

任何想法或见解将不胜感激。

Answer 1

我看到的主要问题是，您创建了一个不断重新计算直方图的系统，最坏的情况是对每个新元素进行重新计算。

像这样的事情怎么样:

1. 对于 N 个 bins，Bin_min 到 Bin_max，将它们分配给您输入的初始值
2. 对于每个新数字 X，如果 X 是 < Bin_min 设置 Bin_min = X 否则如果 X > Bin_max 设置 Bin<子>最大 = X
3. 如果您更改了 2 中的边界，请设置每个 bin 的值，使得 Bin_L = (Bin_max - Bin_min)/N * L，其中 L 是 bin 序号
4. 将 X 添加到与 X 最接近的值的容器中。

这是餐巾纸的背面，所以我确定某处有误。这个想法是仅在值落在直方图之外时才“重构”直方图，因此您需要做的正常情况就是将 X 添加到最匹配它的容器中。我相信这应该会产生一个非常相似的直方图，如果不相等的话。第1步是你的初始化，第2-4步是一个循环，如果不清楚。