Лучший алгоритм сортировки для сортировки структур с байтовыми сравнениями?

Question

У меня есть массив из 64 структур, которые содержат приличный объем данных (структура составляет около 128 байтов, так что это 8192 байта, которые должны быть перегруппированы).Массив должен быть отсортирован на основе одного байта без знака в каждой структуре.Интересным свойством моих данных является то, что, вероятно, будет много дубликатов отсортированного значения - это означает, что если вы избавитесь от всех дубликатов, массив может иметь длину только 10 уникальных элементов, но это не дано.

После сортировки мне нужно создать стек, в котором будут храниться размер и тип, с которого начинается каждый уникальный запуск байтов: так что если я получу отсортированные значения: 4,4,4,9,9,9,9,9,14,14 стек будет: (4,3), (9,5), (14,2)

Я подумал, что будет несколько хороших оптимизаций, которые я мог бы выполнить в этих условиях.Если я делаю heapsort, я могу создавать стек во время сортировки, но будет ли это быстрее, чем qsort, а затем создавать стек после слов?Будет ли какой-нибудь алгоритм сортировки работать медленнее из-за больших структур, которые я использую?Можно ли оптимизировать, потому что я сравниваю только байты?

Кстати: язык c ++

Спасибо.

Answer 1

Как правило, с большими объектами может быть быстрее сортировать массив указателей / индексов объектов, а не объектов.Или сортируйте массив узлов, где каждый узел содержит указатель / индекс объекта и ключ сортировки объекта (в этом случае ключ - один байт).Для этого в C ++ вы можете просто предоставить подходящий компаратор для std::sort или std::stable_sort.Затем, если вам нужны исходные объекты по порядку, а не просто нужно знать правильный порядок, наконец, скопируйте объекты в новый массив.

Копирование 128 байтов почти наверняка намного медленнее, чем сравнение байтов,даже с дополнительной косвенностью.Таким образом, для оптимальной производительности вам нужно следить за ходами, а не за сравнениями, и использование указателей - это один из способов избежать большинства перемещений.

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

Конечно, можно было бы пойти еще быстрее с некоторым пользовательским алгоритмом сортировки, который специально использует числа в вашем случае (64, «около 128» и 1).Но даже на простые вопросы, такие как «самый быстрый - интросортировка, сортировка кучи или сортировка слиянием», вообще невозможно ответить без написания и запуска кода.

Answer 2

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

Answer 3

Сортировка не будет медленнее, потому что вы будете сортировать указатель или ссылки на структуры, а не фактическую структуру в памяти.

Answer 4

Тот факт, что ваши ключи являются целыми числами, и их на самом деле не так много, шансы Bucket Sort , с размером корзины 1, были бы очень применимы.