"Stable" k-最大元素算法
"Stable" k-largest elements algorithm
相关:priority queue with limited space: looking for a good algorithm
我正在寻找一种算法,该算法 return 是列表中的 k 个最大元素,但不会更改 k 个最大元素的顺序,例如对于 k=4
和给定 5,9,1,3,7,2,8,4,6
,算法应该 return 9,7,8,6
.
更多背景信息,我的输入数据大约有 200 对 (distance,importance)
,它们按 w.r.t distance
排序,我需要 select 其中最重要的 32 个。性能在这里至关重要,因为我必须 运行 这个 selection 算法几千次。
目前我有以下两种想法,但似乎都不是最好的。
- 迭代删除最小元素,直到剩下 32 个元素(即执行 selection 排序)
- 使用 quickselect 或 median-of-medians 搜索第 32 大元素。之后,对剩余的 31 个元素再次排序w.r.t。距离.
我需要用 C++ 实现它,所以如果有人想写一些代码但不知道使用哪种语言,C++ 是一个选择。
使用 heap-based 算法找到第 k 个最大值,即使用 min 堆(不是最大堆),其大小永远不会超过 k。一旦超过这个大小,继续从中拉根以将其恢复到 k.
的大小
最后堆的根将是 k 最大值。我们称它为 m.
然后您可以再次扫描原始输入以收集至少等于 m 的所有值。这样你就会得到它们原来的顺序。
当 m 不唯一时,您可能收集了太多值。因此检查结果的大小并确定它比 k 长多少。向后浏览该列表并将具有值 m 的那些标记为已删除,直到达到正确的大小。最后收集 non-deleted 件物品。
所有这些扫描都是 O(n)。最昂贵的步骤是第一步:O(nlogk).
受到 @trincot 解决方案的启发,我想出了一个与工作实施略有不同的变体。
算法
使用Floyd算法构建最大堆或者相当于构建priority_queue在 C++ 中使用我们一次传递整个 array/vector 的构造函数,而不是单独添加元素。如果内置 O(N) 时间复杂度,则为最大堆。
现在,从最大堆中弹出项目 K-1 次,直到我们得到第 K 个最大重要性项目。将第 K 个最大重要性项的值存储在变量 Kth_Max_Importance_Item
.
中
从原始输入扫描所有重要性值大于Kth_Max_Importance_Item
重要性值的节点,并将它们推入输出向量。
通过从k
中减去输出向量的当前大小,计算重要性值等于Kth_Max_Importance_Item
重要性值的必需项的剩余计数。将其存储在变量 left_Over_Count
.
中
从原始输入中扫描 left_Over_Count
个项目值,其重要性值如果等于 Kth_Max_Importance_Item
的重要性值,并将它们推入输出向量。
注意: 如果 importance
值不唯一,则此条件由 step 3和4的算法。
时间复杂度:O(N + K*log(N))。假设 K<
实施:
#include <iostream>
#include <vector>
#include <queue>
#include <math.h>
typedef struct Item{
int distance;
double importance;
}Item;
struct itemsCompare{
bool operator() (const Item& item1, const Item& item2){
return ((item1.importance < item2.importance) ? true : false);
}
};
bool compareDouble(const double& a, const double& b){
return (fabs(a-b) < 0.000001) ? true : false;
}
int main(){
//Original input
std::vector<Item> items{{10, 2.1}, {9, 2.3}, {8, 2.2}, {7, 2.2}, {6, 1.5}};
int k = 4;
//Min Heap
std::priority_queue<Item, std::vector<Item>, itemsCompare> maxHeap (items.begin(), items.end());
//Checking if the order of original input is intact
/*for(int i=0;i<items.size();i++){
std::cout<<items[i].distance<<" "<<items[i].importance<<std::endl;
}*/
//Pulling the nodes until we get Kth Max Importance Node
int count = 0;
while(!maxHeap.empty()){
if(count == k-1){
break;
}
maxHeap.pop();
count++;
}
Item Kth_Max_Importance_Item = maxHeap.top();
//std::cout<<Kth_Max_Importance_Item.importance<<std::endl;
//Scanning all the nodes from original input whose importance value is greater than the importance value of Kth_Max_Importance_Item.
std::vector<Item> output;
for(int i=0;i<items.size();i++){
if(items[i].importance > Kth_Max_Importance_Item.importance){
output.push_back(items[i]);
}
}
int left_Over_Count = k - output.size();
//std::cout<<left_Over_Count<<std::endl;
//Adding left_Over_Count number of values of items whose importance value if equal to importance value of Kth_Max_Importance_Item
for(int i=0;i<items.size();i++){
if(compareDouble(items[i].importance, Kth_Max_Importance_Item.importance)){
output.push_back(items[i]);
left_Over_Count--;
}
if(!left_Over_Count){
break;
}
}
//Printing the output:
for(int i=0;i<output.size();i++){
std::cout<<output[i].distance<<" "<<output[i].importance<<std::endl;
}
return 0;
}
输出:
9 2.3
8 2.2
7 2.2
10 2.1
相关:priority queue with limited space: looking for a good algorithm
我正在寻找一种算法,该算法 return 是列表中的 k 个最大元素,但不会更改 k 个最大元素的顺序,例如对于 k=4
和给定 5,9,1,3,7,2,8,4,6
,算法应该 return 9,7,8,6
.
更多背景信息,我的输入数据大约有 200 对 (distance,importance)
,它们按 w.r.t distance
排序,我需要 select 其中最重要的 32 个。性能在这里至关重要,因为我必须 运行 这个 selection 算法几千次。
目前我有以下两种想法,但似乎都不是最好的。
- 迭代删除最小元素,直到剩下 32 个元素(即执行 selection 排序)
- 使用 quickselect 或 median-of-medians 搜索第 32 大元素。之后,对剩余的 31 个元素再次排序w.r.t。距离.
我需要用 C++ 实现它,所以如果有人想写一些代码但不知道使用哪种语言,C++ 是一个选择。
使用 heap-based 算法找到第 k 个最大值,即使用 min 堆(不是最大堆),其大小永远不会超过 k。一旦超过这个大小,继续从中拉根以将其恢复到 k.
的大小最后堆的根将是 k 最大值。我们称它为 m.
然后您可以再次扫描原始输入以收集至少等于 m 的所有值。这样你就会得到它们原来的顺序。
当 m 不唯一时,您可能收集了太多值。因此检查结果的大小并确定它比 k 长多少。向后浏览该列表并将具有值 m 的那些标记为已删除,直到达到正确的大小。最后收集 non-deleted 件物品。
所有这些扫描都是 O(n)。最昂贵的步骤是第一步:O(nlogk).
受到 @trincot 解决方案的启发,我想出了一个与工作实施略有不同的变体。
算法
使用Floyd算法构建最大堆或者相当于构建priority_queue在 C++ 中使用我们一次传递整个 array/vector 的构造函数,而不是单独添加元素。如果内置 O(N) 时间复杂度,则为最大堆。
现在,从最大堆中弹出项目 K-1 次,直到我们得到第 K 个最大重要性项目。将第 K 个最大重要性项的值存储在变量
中Kth_Max_Importance_Item
.从原始输入扫描所有重要性值大于
Kth_Max_Importance_Item
重要性值的节点,并将它们推入输出向量。通过从
中k
中减去输出向量的当前大小,计算重要性值等于Kth_Max_Importance_Item
重要性值的必需项的剩余计数。将其存储在变量left_Over_Count
.从原始输入中扫描
left_Over_Count
个项目值,其重要性值如果等于Kth_Max_Importance_Item
的重要性值,并将它们推入输出向量。
注意: 如果 importance
值不唯一,则此条件由 step 3和4的算法。
时间复杂度:O(N + K*log(N))。假设 K< 实施: 输出:#include <iostream>
#include <vector>
#include <queue>
#include <math.h>
typedef struct Item{
int distance;
double importance;
}Item;
struct itemsCompare{
bool operator() (const Item& item1, const Item& item2){
return ((item1.importance < item2.importance) ? true : false);
}
};
bool compareDouble(const double& a, const double& b){
return (fabs(a-b) < 0.000001) ? true : false;
}
int main(){
//Original input
std::vector<Item> items{{10, 2.1}, {9, 2.3}, {8, 2.2}, {7, 2.2}, {6, 1.5}};
int k = 4;
//Min Heap
std::priority_queue<Item, std::vector<Item>, itemsCompare> maxHeap (items.begin(), items.end());
//Checking if the order of original input is intact
/*for(int i=0;i<items.size();i++){
std::cout<<items[i].distance<<" "<<items[i].importance<<std::endl;
}*/
//Pulling the nodes until we get Kth Max Importance Node
int count = 0;
while(!maxHeap.empty()){
if(count == k-1){
break;
}
maxHeap.pop();
count++;
}
Item Kth_Max_Importance_Item = maxHeap.top();
//std::cout<<Kth_Max_Importance_Item.importance<<std::endl;
//Scanning all the nodes from original input whose importance value is greater than the importance value of Kth_Max_Importance_Item.
std::vector<Item> output;
for(int i=0;i<items.size();i++){
if(items[i].importance > Kth_Max_Importance_Item.importance){
output.push_back(items[i]);
}
}
int left_Over_Count = k - output.size();
//std::cout<<left_Over_Count<<std::endl;
//Adding left_Over_Count number of values of items whose importance value if equal to importance value of Kth_Max_Importance_Item
for(int i=0;i<items.size();i++){
if(compareDouble(items[i].importance, Kth_Max_Importance_Item.importance)){
output.push_back(items[i]);
left_Over_Count--;
}
if(!left_Over_Count){
break;
}
}
//Printing the output:
for(int i=0;i<output.size();i++){
std::cout<<output[i].distance<<" "<<output[i].importance<<std::endl;
}
return 0;
}
9 2.3
8 2.2
7 2.2
10 2.1