获得std::set的中间（中位数）的有效方法？
Efficient way to get middle (median) of an std::set?
std::set 是排序树。它提供了 begin 和 end 方法，所以我可以获得最小值和最大值以及 lower_bound 和 upper_bound 进行二进制搜索。但是，如果我想让迭代器指向中间元素（如果那里有偶数个元素，则指向其中之一）怎么办？
有没有有效的方法（O(log(size)) 不是 O(size)）来做到这一点？
{1} => 1
{1,2} => 1 or 2
{1,2,3} => 2
{1,2,3,4} => 2 or 3 (but in the same direction from middle as for {1,2})
{1,312,10000,14000,152333} => 10000
得到二叉搜索树的中间部分需要O(size)。您可以使用 std::advance() 获取它，如下所示：
std::set<int>::iterator it = s.begin();
std::advance(it, s.size() / 2);
取决于您 insert/remove 项目与查找 middle/median 项目的频率，一个可能比显而易见的解决方案更有效的解决方案是将持久迭代器保留到中间元素并在您随时更新它集合中的 insert/delete 项。有很多边缘情况需要处理（奇数项与偶数项、删除中间项、空集等），但基本思想是当您插入一个小于当前中间项的项时，你的中间迭代器可能需要递减，而如果你插入一个更大的迭代器，你需要递增。移除的方式正好相反。
在查找时，这当然是 O(1)，但它在每个 insertion/deletion 上也有一个本质上 O(1) 的成本，即 N 次插入后的 O(N)，这需要分摊到足够数量的查找中，使其比暴力破解更有效。
如果您的数据是静态的，您可以对其进行预先计算并且不插入新元素 - 使用 vector 对其进行排序并仅按 O(1) 中的索引访问中位数会更简单
vector<int> data;
// fill data
std::sort(data.begin(), data.end());
auto median = data[data.size() / 2];
请注意 std::set 不存储重复值。如果您插入以下值 {1, 2, 3, 3, 3, 3, 3, 3, 3}，您将检索到的中位数是 2.
std::set<int>::iterator it = s.begin();
std::advance(it, s.size() / 2);
int median = *it;
如果您想在考虑中位数时包括重复项，您可以使用 std::multiset（{1, 2, 3, 3, 3, 3, 3, 3, 3} 中位数为 3）：
std::multiset<int>::iterator it = s.begin();
std::advance(it, s.size() / 2);
int median = *it;
如果您希望对数据进行排序的唯一原因是获得中位数，那么我认为您最好使用普通的旧 std::vector + std::sort。
在大量测试样本和多次迭代的情况下，我用 std::vector 和 std::sort 在 5 秒内完成了测试，用 std::set 或 std::multiset 在 13 到 15 秒内完成了测试。您的里程可能会有所不同，具体取决于您拥有的重复值的大小和数量。
这个建议是纯粹的魔术，如果有一些重复的项目就会失败
Depending on how often you insert/remove items versus look up the middle/median, a possibly more efficient solution than the obvious one is to keep a persistent iterator to the middle element and update it whenever you insert/delete items from the set. There are a bunch of edge cases which will need handling (odd vs even number of items, removing the middle item, empty set, etc.), but the basic idea would be that when you insert an item that's smaller than the current middle item, your middle iterator may need decrementing, whereas if you insert a larger one, you need to increment. It's the other way around for removals.
建议
- 第一个建议是使用 std::multiset 而不是 std::set，这样当项目可以重复时它可以很好地工作
- 我的建议是使用 2 个 multisets 来跟踪较小的药水和较大的药水并平衡它们之间的大小
算法
1。保持集合平衡，以便 size_of_small==size_of_big 或 size_of_small + 1 == size_of_big
void balance(multiset<int> &small, multiset<int> &big)
{
while (true)
{
int ssmall = small.size();
int sbig = big.size();
if (ssmall == sbig || ssmall + 1 == sbig) break; // OK
if (ssmall < sbig)
{
// big to small
auto v = big.begin();
small.emplace(*v);
big.erase(v);
}
else
{
// small to big
auto v = small.end();
--v;
big.emplace(*v);
small.erase(v);
}
}
}
2。如果集合是平衡的，中间项总是大集合中的第一项
auto medium = big.begin();
cout << *medium << endl;
3。添加新项目时要小心
auto v = big.begin();
if (v != big.end() && new_item > *v)
big.emplace(new_item );
else
small.emplace(new_item );
balance(small, big);
复杂性解释
- 找到中间值是O(1)
- 添加一个新项目需要 O(log n)
- 你仍然可以在 O(log n) 中搜索一个项目，但你需要搜索 2 组
正如@pmdj 所说，我们使用迭代器来跟踪中间元素。以下是以下代码实现：
class RollingMedian {
public:
multiset<int> order;
multiset<int>::iterator it;
RollingMedian() {
}
void add(int val) {
order.insert(val);
if (order.size() == 1) {
it = order.begin();
} else {
if (val < *it and order.size() % 2 == 0) {
--it;
}
if (val >= *it and order.size() % 2 != 0) {
++it;
}
}
}
double median() {
if (order.size() % 2 != 0) {
return double(*it);
} else {
auto one = *it, two = *next(it);
return double(one + two) / 2.0;
}
} };
请随意复制和使用此代码的任何部分。此外，如果没有重复，您可以使用 set 而不是 multiset。
std::set 是排序树。它提供了 begin 和 end 方法，所以我可以获得最小值和最大值以及 lower_bound 和 upper_bound 进行二进制搜索。但是，如果我想让迭代器指向中间元素（如果那里有偶数个元素，则指向其中之一）怎么办？
有没有有效的方法（O(log(size)) 不是 O(size)）来做到这一点？
{1} => 1
{1,2} => 1 or 2
{1,2,3} => 2
{1,2,3,4} => 2 or 3 (but in the same direction from middle as for {1,2})
{1,312,10000,14000,152333} => 10000
得到二叉搜索树的中间部分需要O(size)。您可以使用 std::advance() 获取它，如下所示：
std::set<int>::iterator it = s.begin();
std::advance(it, s.size() / 2);
取决于您 insert/remove 项目与查找 middle/median 项目的频率，一个可能比显而易见的解决方案更有效的解决方案是将持久迭代器保留到中间元素并在您随时更新它集合中的 insert/delete 项。有很多边缘情况需要处理（奇数项与偶数项、删除中间项、空集等），但基本思想是当您插入一个小于当前中间项的项时，你的中间迭代器可能需要递减，而如果你插入一个更大的迭代器，你需要递增。移除的方式正好相反。
在查找时，这当然是 O(1)，但它在每个 insertion/deletion 上也有一个本质上 O(1) 的成本，即 N 次插入后的 O(N)，这需要分摊到足够数量的查找中，使其比暴力破解更有效。
如果您的数据是静态的，您可以对其进行预先计算并且不插入新元素 - 使用 vector 对其进行排序并仅按 O(1) 中的索引访问中位数会更简单
vector<int> data;
// fill data
std::sort(data.begin(), data.end());
auto median = data[data.size() / 2];
请注意 std::set 不存储重复值。如果您插入以下值 {1, 2, 3, 3, 3, 3, 3, 3, 3}，您将检索到的中位数是 2.
std::set<int>::iterator it = s.begin();
std::advance(it, s.size() / 2);
int median = *it;
如果您想在考虑中位数时包括重复项，您可以使用 std::multiset（{1, 2, 3, 3, 3, 3, 3, 3, 3} 中位数为 3）：
std::multiset<int>::iterator it = s.begin();
std::advance(it, s.size() / 2);
int median = *it;
如果您希望对数据进行排序的唯一原因是获得中位数，那么我认为您最好使用普通的旧 std::vector + std::sort。
在大量测试样本和多次迭代的情况下，我用 std::vector 和 std::sort 在 5 秒内完成了测试，用 std::set 或 std::multiset 在 13 到 15 秒内完成了测试。您的里程可能会有所不同，具体取决于您拥有的重复值的大小和数量。
这个建议是纯粹的魔术，如果有一些重复的项目就会失败
Depending on how often you insert/remove items versus look up the middle/median, a possibly more efficient solution than the obvious one is to keep a persistent iterator to the middle element and update it whenever you insert/delete items from the set. There are a bunch of edge cases which will need handling (odd vs even number of items, removing the middle item, empty set, etc.), but the basic idea would be that when you insert an item that's smaller than the current middle item, your middle iterator may need decrementing, whereas if you insert a larger one, you need to increment. It's the other way around for removals.
建议
- 第一个建议是使用 std::multiset 而不是 std::set，这样当项目可以重复时它可以很好地工作
- 我的建议是使用 2 个 multisets 来跟踪较小的药水和较大的药水并平衡它们之间的大小
算法
1。保持集合平衡，以便 size_of_small==size_of_big 或 size_of_small + 1 == size_of_big
void balance(multiset<int> &small, multiset<int> &big)
{
while (true)
{
int ssmall = small.size();
int sbig = big.size();
if (ssmall == sbig || ssmall + 1 == sbig) break; // OK
if (ssmall < sbig)
{
// big to small
auto v = big.begin();
small.emplace(*v);
big.erase(v);
}
else
{
// small to big
auto v = small.end();
--v;
big.emplace(*v);
small.erase(v);
}
}
}
2。如果集合是平衡的，中间项总是大集合中的第一项
auto medium = big.begin();
cout << *medium << endl;
3。添加新项目时要小心
auto v = big.begin();
if (v != big.end() && new_item > *v)
big.emplace(new_item );
else
small.emplace(new_item );
balance(small, big);
复杂性解释
- 找到中间值是O(1)
- 添加一个新项目需要 O(log n)
- 你仍然可以在 O(log n) 中搜索一个项目，但你需要搜索 2 组
正如@pmdj 所说，我们使用迭代器来跟踪中间元素。以下是以下代码实现：
class RollingMedian {
public:
multiset<int> order;
multiset<int>::iterator it;
RollingMedian() {
}
void add(int val) {
order.insert(val);
if (order.size() == 1) {
it = order.begin();
} else {
if (val < *it and order.size() % 2 == 0) {
--it;
}
if (val >= *it and order.size() % 2 != 0) {
++it;
}
}
}
double median() {
if (order.size() % 2 != 0) {
return double(*it);
} else {
auto one = *it, two = *next(it);
return double(one + two) / 2.0;
}
} };
请随意复制和使用此代码的任何部分。此外，如果没有重复，您可以使用 set 而不是 multiset。