повысить производительность циркулярного буфера или сортировки кучи
Мне нужно отсортировать объекты, которые поступают в процесс X, прежде чем обрабатывать их.
Объект сортируется по временной отметке — 64-битному номеру.
Когда время истекает (несколько миллилитров) и сортируется, процесс X начинает на них смотреть.
Большую часть времени объект сортируется, между 3% и 5% объекты вышли из строя.
Поэтому мне нужна структура, которая позволит мне:
— вставьте быстро элементы
— удалить быстро истекающие элементы
Что должно быть лучше, чтобы отсортировать их, с точки зрения производительности?
Я начал реализовывать с boost :: round_buffer.
Если boost :: heap лучше для этого, какой boost :: heap я должен использовать? Потому что их несколько (фибоначчи, биномиальные, приоритетные очереди …)
Я использую boost 1_49, но я также могу использовать более новую версию.
С круговым буфером я вставляю большинство элементов в начало буфера. Но это может быть O (n) в некоторых случаях.
Но чтобы взять тайм-аут элемента, это O (1)
Решение
Вам нужно будет измерить, но я бы предположил, что std::priority_queue<T> имеет хороший шанс быть наиболее эффективным. Использование любой другой кучи не принесет вам большой пользы, потому что вам не нужны дополнительные операции (изменение приоритета элемента), но возможность использовать эти операции значительно увеличивает накладные расходы.
Особенно когда размер T немного больше, но даже если это просто intвы можете использовать d-куча с д == 8: хотя это приводит к большему количеству сравнений, оно уменьшает количество перемещений объекта.
Другие решения
Других решений пока нет …