очередь приоритетов — Как получить коллекцию целых чисел с адаптивным упорядочением, основанным на прошлом успехе в C ++?
У меня есть набор целых чисел в C ++ 03, где целые числа представляют догадки относительно контрольной точки. Алгоритм проходит через длинный список элементов, и для каждого элемента он пробует каждое целочисленное предположение (дорогая операция) относительно контрольной точки этого элемента, пока не найдет совпадение или все догадки не будут исчерпаны. Элемент соответствует не более одного предположения, но может не соответствовать ни одному. Я хотел бы посчитать, сколько раз каждое относительное целочисленное предположение успешно находит совпадение, так что при каждом повторении следующего элемента набор догадок для этого элемента упорядочивается таким образом, чтобы эти предположения с наибольшим успехом предшествовали тем, которые имели меньший успех. на основе уже обработанных предметов.
Я мог бы представить себе использование std :: map, которое отображает каждую относительную догадку на количество раз, когда относительная догадка успешно нашла совпадение. Таким образом, на каждой итерации элемента я мог повернуть карту и отобразить все значения карты в обратном направлении к их ключам. Перебирая вторую мультикарту в обратном порядке, я мог обрабатывать догадки для каждого элемента, начиная с наиболее успешных догадок, пока не будет найдено совпадение. На этом этапе первая карта будет обновлена, чтобы указать, какое предположение теперь имеет еще один успех. Точно так же вторая мультикарта будет обновлена, чтобы удалить совпадающее предположение из его старого счетчика успеха и повторно вставить его в теперь увеличенный счетчик успеха.
Однако это кажется сложным, и я думаю, что есть более элегантный ответ. Хотя, может быть, стоит потраченных впустую усилий, чтобы сделать код проще для понимания, перестраивая мультикарту с нуля каждую итерацию вместо того, чтобы пытаться постепенно поддерживать ее?
Существует ли известная структура данных шаблона проектирования, которая хорошо подходит для этой проблемы? Как я могу наилучшим образом упорядочить свои догадки так, чтобы более удачные догадки поднимались до вершины? Имеет ли смысл применять приоритетную очередь здесь?
Решение
Я бы пошел с struct который содержит счет успеха и предположение. Начните с std::vector из всех начальных предположений, каждое с количеством успешных попыток 0. На каждом проходе начинайте с my_vec.begin() и итерации до my_vec.end(), Если предположение выполнено успешно, остановите итерацию, увеличьте счетчик успеха и поместите его в нужную позицию на основе счетчика успеха.
for (auto it = my_vec.begin(); it != my_vec.end(); ++it) {
if (try_it(it->guess)) {
++it->successes;
while (it != my_vec.begin() && it->successes > (it - 1)->successes) {
swap(*it, *(it - 1));
--it;
}
break;
}
}
Другие решения
std::vector из pairс (или structс) из (guess, correct).
инкремент correct, (бинарный?) поиск правильного места, сдвиньте элементы между правильным предположением и новым местом над 1. Возможно, скольжение в «глыбах» будет быстрее, чем скольжение их по одному, но, возможно, нет.
std::vector< std::pair< int, std::size_t > > guess_buffer;
template<typename TryGuess>
bool Try( guess_buffer& guesses, TryGuess const& try_guess ) {
for (guess_buffer::iterator it = guesses.begin(); it != guesses.end(); ++it) {
if (try_guess( it->first)) {
it->second++;
while (it != guesses.begin()) {
--it;
if (it->second < (it+1)->second) {
std::swap( *it, *(it+1) );
} else {
return true;
}
}
return true;
}
}
return false;
}
Учитывая, что вы перебрали все от начала до здесь, поиск и слайд будут достаточно быстрыми. Местность и скорость итерации компенсируют стоимость слайдов в два дюйма.
Если вам нужно меньше кода, мультикарта от подсчета до угадывания, итерация с запоминанием итератора, в случае успеха удалите с помощью итератора, увеличьте счетчик и заново вставьте. Вероятно, будет медленнее.
template<typename X>
struct reverse_order {
template<typename T, typename U>
bool operator()( T const& t, U const& u ) const {
return std::less<X>()( u, t );
}
};
typedef std::multi_map< std::size_t, int, reverse_order<std::size_t> > guess_map;
template<typename TryGuess>
bool Try( guess_map& guesses, TryGuess const& try_guess ) {
for( guess_map::iterator it = guesses.begin(); it != guesses.end(); ++it ) {
if( try_guess( it->second ) )
{
std::pair<std::size_t, int> modify = *it;
guesses.erase(it);
modify.first++;
guesses.insert(modify);
return true;
}
}
return false;
}