分层优先级索引
Hierarchical priority index
我正在寻找一个 C++ 库,它具有以下问题的索引解决方案。我曾尝试过自己的解决方案,但得出的结论是我在这里发明了一个轮子。
我有一个可以接水的源桶。它需要在层次结构之间拆分水。我想它也可以表示为具有优先级的队列。在具有更高优先级的桶装满之前,其他桶不会接收任何水。有的水桶有children个水桶,应该从那里过水。所有 children 都可以拥有自己的 children,因此他们也是某些人的母亲。 妈妈水桶可以严格排队(一个接一个)传水,也可以按比例分水。
在下面的图片中,我试图说明情况。我们有 Bucket 作为层次结构的顶部。它有3children。他们根据优先级(1、2、3)严格按顺序接水。在桶 1 装满之前,桶 2 不会接收任何水。桶 1 也有 3 children。两个孩子具有相同的优先级和 50% 和 50% 的比例,第三个 child 只有在其他两个孩子吃饱后才会喝水。第一个孩子有了孩子,他们把水分成 20% 和 80%。
任意级别的整数 1 具有最高优先级。如果桶在同一层次上有相似的整数,我们可以认为它们的优先级相等,然后看分裂的比例。第一层编号为 1 的桶将首先接收水。然后它必须将水传递到第二级,在那里水将被分配 50%-50%,然后 50% 将在最后一级之间按 50%(20% 和 80%)分配。
+--------------+
| |
| Bucket |
+-+-----+----+-+
| | |
| | |
1 | | | 3
+----------------+ | +-----------------+
| | |
| |2 |
^ | ^
+------+ | +--+--+
| | | ^ | |
1 | | | 2 +--+--+ +-----+
0.5 | | | | |
+----------+ |1 +-------+ +-----+
| |0.5 |
^ ^ ^
+--+--+ +---+---+ +-+---+
| | | | | |
++-+--+ +-------+ +-----+
| |
1 0.2 | |
+----------+ |1 0.8
| |
| |
v v
+--+--+ +--+--+
| | | |
+-----+ +-----+
我需要索引所有孩子和他们的比例,这样,当我收到水时,我会根据所有优先级和共享权重拆分水。我的想法是使用 double
变量的整数部分的位来表示层次结构每个级别的优先级,并使用小数部分来存储比例。
您可以通过与访问者一起遍历 depth-first 您的树,将您的问题从树表示转换为队列:
#include <map>
#include <list>
struct Bucket
{
std::map<unsigned int, Bucket> children; // <priority, children>
template<class Visitor>
void visit(const Visitor& visitor)
{
for (auto it = children.rbegin(); it!= children.rend(); ++it)
{
visitor(&it->second);
it->second.visit(visitor);
}
}
};
int main()
{
Bucket root_bucket;
// populate root_bucket
// ...
// index root_bucket
std::list<Bucket*> indexed_buckets;
root_bucket.visit( [&](Bucket* b){ indexed_buckets.push_back(b); });
}
之后,indexed_buckets
将包含指向填充顺序中的桶的指针。只需将第一个装满,然后将剩余的水装满下一个。
我正在寻找一个 C++ 库,它具有以下问题的索引解决方案。我曾尝试过自己的解决方案,但得出的结论是我在这里发明了一个轮子。
我有一个可以接水的源桶。它需要在层次结构之间拆分水。我想它也可以表示为具有优先级的队列。在具有更高优先级的桶装满之前,其他桶不会接收任何水。有的水桶有children个水桶,应该从那里过水。所有 children 都可以拥有自己的 children,因此他们也是某些人的母亲。 妈妈水桶可以严格排队(一个接一个)传水,也可以按比例分水。
在下面的图片中,我试图说明情况。我们有 Bucket 作为层次结构的顶部。它有3children。他们根据优先级(1、2、3)严格按顺序接水。在桶 1 装满之前,桶 2 不会接收任何水。桶 1 也有 3 children。两个孩子具有相同的优先级和 50% 和 50% 的比例,第三个 child 只有在其他两个孩子吃饱后才会喝水。第一个孩子有了孩子,他们把水分成 20% 和 80%。
任意级别的整数 1 具有最高优先级。如果桶在同一层次上有相似的整数,我们可以认为它们的优先级相等,然后看分裂的比例。第一层编号为 1 的桶将首先接收水。然后它必须将水传递到第二级,在那里水将被分配 50%-50%,然后 50% 将在最后一级之间按 50%(20% 和 80%)分配。
+--------------+
| |
| Bucket |
+-+-----+----+-+
| | |
| | |
1 | | | 3
+----------------+ | +-----------------+
| | |
| |2 |
^ | ^
+------+ | +--+--+
| | | ^ | |
1 | | | 2 +--+--+ +-----+
0.5 | | | | |
+----------+ |1 +-------+ +-----+
| |0.5 |
^ ^ ^
+--+--+ +---+---+ +-+---+
| | | | | |
++-+--+ +-------+ +-----+
| |
1 0.2 | |
+----------+ |1 0.8
| |
| |
v v
+--+--+ +--+--+
| | | |
+-----+ +-----+
我需要索引所有孩子和他们的比例,这样,当我收到水时,我会根据所有优先级和共享权重拆分水。我的想法是使用 double
变量的整数部分的位来表示层次结构每个级别的优先级,并使用小数部分来存储比例。
您可以通过与访问者一起遍历 depth-first 您的树,将您的问题从树表示转换为队列:
#include <map>
#include <list>
struct Bucket
{
std::map<unsigned int, Bucket> children; // <priority, children>
template<class Visitor>
void visit(const Visitor& visitor)
{
for (auto it = children.rbegin(); it!= children.rend(); ++it)
{
visitor(&it->second);
it->second.visit(visitor);
}
}
};
int main()
{
Bucket root_bucket;
// populate root_bucket
// ...
// index root_bucket
std::list<Bucket*> indexed_buckets;
root_bucket.visit( [&](Bucket* b){ indexed_buckets.push_back(b); });
}
之后,indexed_buckets
将包含指向填充顺序中的桶的指针。只需将第一个装满,然后将剩余的水装满下一个。