Быстрый способ частично сортировать объекты
У меня есть процедура, в которой я определяю группу объектов (около 20), называю их Jet, которые имеют определенный < что я использую, чтобы отсортировать их. После того, как они отсортированы, я беру два самых низких. Какой быстрый способ сделать это? Варианты, о которых я думал до сих пор:
boost::ptr_vector<Jet>использовать встроенный.sort()возьми первые два,boost::ptr_list<Jet>использовать.sort()возьми первые два- используйте список, как указано выше, но вместо сортировки используйте
max_element, удалите элемент и снова запустите.
Я предполагаю, используя std::vector<Jet> будет худшим вариантом, потому что: мне не нужен произвольный доступ; сортировка будет перемещать объекты в памяти; и объекты будут скопированы при вызове push_back(Jet), Из-за необходимости копирования, я бы также предположил, что std::list<Jet> будет хуже чем boost::ptr_list<Jet>, Я также предположил бы, что принимая max_element дважды будет быстрее, чем сортировка всего списка.
Моя логика звучит? Будет ли разница в производительности существенной? Есть ли какой-то другой вариант, о котором я не думаю?
3 ответа
Есть стандартный алгоритм библиотеки, чтобы сделать именно это:
std::vector<Jet> v;
// populate v
std::partial_sort(v.begin(), v.begin() + 2, v.end());
v[0] теперь самый маленький элемент и v[1] теперь второй наименьший элемент; остальные элементы находятся в неуказанном порядке. std::vector<> можно заменить на std::deque<>, так как последний также имеет итераторы с произвольным доступом.
(Обратите внимание, что сложность, упомянутая на странице, на которую я ссылаюсь, неверна; C++11 §25.4.1.3 говорит, что сложность (last - first) * log(middle - first).)
Одно из ваших предположений верно: хранение указателей вместо объектов будет быстрее.
Однако, если вам нужны только два самых маленьких элемента, вам не нужно ничего сортировать. Просто возьмите первые два элемента, а затем переберите элементы vector или же list и сохранить меньшие.
Если вам нужны два младших объекта, вы можете создать свою собственную функцию поиска, которая будет выполняться за O(N) времени. Использование сортировки - O(N log N) времени.