top k обычно немного лучше, чем n (log k)
template <class t,class ordering>
class TopK {
public:
typedef std::multiset<t,ordering,special_allocator> BEST_t;
BEST_t best;
const size_t K;
TopK(const size_t k)
: K(k){
}
const BEST_t& insert(const t& item){
if(best.size()<k){
best.insert(item);
return best;
}
//k items in multiset now
//and here is why its better - because if the distribution is random then
//this and comparison above are usually the comparisons that is done;
if(compare(*best.begin(),item){//item better than worst
erase(begin());//the worst
best.insert(item); //log k-1 average as only k-1 items in best
}
return best;
}
template <class it>
const BEST_t& insert(it i,const it last){
for(;i!=last;++i){
insert(*i);
}
return best;
}
};
Конечно, special_allocator, по сути, может быть просто массивом из k multiset value_types и списком тех узлов (в которых обычно ничего нет, так как другие k используются в мультимножестве до тех пор, пока не наступит время для установки нового один в и мы стираем, а затем сразу же многократно используем его. Хорошо иметь эту или другую память, выделяемую / освобождаемую в std :: multiset и хрень строки кэша убивает тебя. Это (очень) крошечная работа, чтобы придать ей статическое состояние без нарушения правил распределителя STL.
Не так хорошо, как специализированный алгоритм для ровно 2, но для фиксированного k<<n, я бы УГОВОРИЛ (2n + дельта * n), где дельта мала - мой DEK ACP vol3 S & S упакован, а оценка дельты немного больше работы, которую я хочу сделать.
среднее худшее, я бы догадался, n (log (k-1) + 2), когда в противоположном порядке и все различно.
best - 2n + k (log k) для k, являющегося первым