Высокопроизводительная сортировка кучи

У меня есть вектор размером более 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.
    }
}

Есть ли способы сделать код максимально эффективным? Приветствуется любая идея, не ограничиваясь улучшением алгоритма, например, параллельным или чем-то еще. Большое спасибо!


c++ performance sorting parallel-processing binary-heap
person C. Wang    schedule 10.03.2014    source источник
comment
Есть ли какая-то закономерность в том, как обработка влияет на все остальные элементы? Это действительно все они (и в этом случае ваша нижняя граница, очевидно, O (N)) или только некоторые? Можно ли их как увеличивать, так и уменьшать?   -  person Alan Stokes    schedule 11.03.2014

Ответы (3)


arrow_upward
2
arrow_downward

Если Process_MyObj действительно влияет на ключи всех элементов в A, я не думаю, что вы можете что-то сделать. Если бы он изменил только некоторые из ключей, вы могли бы написать код для обновления отдельных элементов в куче.

Поскольку сейчас ваш код, я не вижу, что вы получите от создания кучи. Я бы просто проделал линейное сканирование, чтобы найти минимальный элемент, поменять его местами на последний, а затем выдвинуть последний элемент.

person user515430    schedule 10.03.2014
comment
Да - линейное сканирование O (N), следовательно, лучше, чем сортировка O (N log N). - person Alan Stokes; 11.03.2014
comment
@ user515430 Согласен. Создание кучи кажется бесполезным. Я сделал это только потому, что это было из известной газеты, что меня тоже смущает. - person C. Wang; 11.03.2014

arrow_upward
0
arrow_downward

Вы можете попробовать отсортировать вектор и выбрать элементы по порядку вместо использования кучи.

Это не улучшит большую сложность, но, возможно, может улучшить постоянный коэффициент.

person riklund    schedule 10.03.2014

arrow_upward
0
arrow_downward

Сколько времени уходит на 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-heap-be -olved-while-Making-at-most-3n-compresses - так что ускорить работу будет непросто. Если значения постоянны, куча из 64-битных ‹32 значений, 32 index> будет более эффективно кэшировать, чем указатели.

что-новое-в-чисто-функциональном- data-structure-Since-okasaki на cstheory.stack содержит десятки статей, в основном теоретических, но одна или две могут иметь отношение к вашей проблеме.

Реальное ускорение почти всегда связано с конкретной проблемой, а не с общими. Не могли бы вы рассказать нам больше о реальной проблеме?

Добавлено: если большинство всплывающих окон маленькие, а толкает большие, попробуйте поместить маленькую кеш-память перед большим отсортированным списком. Псевдокод:

push:
    push( cacheheap )
pop:
    return min( cacheheap, bigsortedlist )

Это может быть эффективным, если cacheheap остается в реальном кэше ЦП; ymmv.
(Вы можете обмануть и оставить bigsortedlist неточным вместо того, чтобы каждый раз сортировать.)

person denis    schedule 26.03.2014