Высокопроизводительная сортировка кучи
У меня есть вектор размером более 5 миллионов, каждый раз, когда я хотел бы выбрать один элемент с наименьшим ключом из вектора и выполнить некоторый процесс для этого элемента. Однако при обработке этого конкретного элемента все остальные элементы в векторе также будут затронуты, так что их ключ обновится. Поэтому в следующий раз, если я захочу забрать элемент с наименьшим ключом из вектора, я должен снова отсортировать вектор. Проблема заключается в том, что число подбора самого маленького элемента вектора будет достигать 0,5 миллиона, поэтому программа работает так медленно. Для вашего более ясного понимания я мог бы написать следующий код для иллюстрации:
void function(vector<MyObj*>& A)
{ //A.size() is near 5 million, maybe even more such as 50 million.
make_heap(A.begin(), A.end(), compare); // compare function is self-defined.
for (int i=0; i<500000; i++)
{
MyObj* smallest_elem = A.front();
pop_heap(A.begin(), A.end());
A.pop_back();
Process_MyObj(smallest_elem); // here all of the elements
// in A will be affect, causing
// their keys changed.
make_heap(A.begin(), A.end()); // Since all elements' keys in A changed,
// so heap sorting A once again is
// necessary in my viewpoint.
}
}
Есть ли способы сделать код максимально эффективным? Любая идея приветствуется, не ограничиваясь улучшением алгоритма, например, параллельное или что-либо еще. Спасибо вам большое!
Решение
Если Process_MyObj действительно влияет на ключи всех элементов в A, я не думаю, что вы многое можете сделать. Если бы он изменил только некоторые ключи, вы могли бы написать код для обновления отдельных элементов в куче.
Поскольку ваш код сейчас, я не вижу, что вы получите от построения кучи. Я бы просто сделал линейное сканирование, чтобы найти минимальный элемент, поменять его местами с последним, а затем вытолкнул последний элемент.
Другие решения
Вы можете попробовать отсортировать вектор и выбрать элементы по порядку вместо использования кучи.
Это не улучшит сложность биг-о, но может улучшить постоянный фактор.
Сколько времени в Process_MyObjи сколько в куче операций —
50/50%, 80/20%?
Это важно, потому что вы хотите сбалансировать два.
Рассмотрим следующую общую настройку:
Make a Todo list
Loop:
work on items ...
update the Todo list
Слишком много времени для обновления списка означает, что не хватает времени на реальную работу.
Поэтому сначала измерьте соотношение времени обработки / кучи.
Дешевый способ сделать это, чтобы сделать второй запуск с
Process_MyObj а также compare сделано дважды, например
P + H = 1.0 sec
2P + H = 1.7 sec
=> P = .7, H = .3: P / H = 70 % / 30 %.
make_heap работает за линейное время —
увидеть как-кан-stdmake-куча-быть внедрено-то время решений, в-самых-3n-сравнения —
так что ускорение там будет жестким.
Если значения постоянны, куча
64-битный <32 значение, 32 индекс> будет более эффективным кеш, чем указатели.
Что-новый-в-чисто-функционально-структур данных-Since-okasaki
на cstheory.stack перечислены десятки статей, в основном теоретических,
но один или два могут иметь отношение к вашей проблеме.
Реальные ускорения почти всегда связаны с конкретными проблемами, а не с общими.
Можете ли вы рассказать нам больше о реальной проблеме?
Добавлено: если большинство попсов маленькие, а толчки большие,
попробуйте поместить небольшую кеш-кучу перед большим отсортированным списком. псевдокод:
push:
push( cacheheap )
pop:
return min( cacheheap, bigsortedlist )
Это может быть эффективным если cacheheap остается в реальном кэше процессора; YMMV.
(Вы могли бы обмануть, и оставить bigsortedlist неточно вместо того, чтобы сортировать его каждый раз.)