Анализ использования избыточности данных в качестве требуемой дополнительной памяти при сортировке алгоритмом слияния

Алгоритмы сортировки

В этой статье речь пойдет о сравнении некоторых алгоритмов сортировки, реализованных на C++ для последовательности не упакованных BCD чисел большого размера.

Данный анализ я проводил в качестве летней практики в компании «Программные технологии» ^[1].
Сортируемая последовательность не имеет заголовка, числа в ней имеют различную разрядность и хранятся без выравнивания. Между числами стоят разделители (0xFF).

Для осуществления сортировки с помощью библиотечной функции вводится дополнительный уровень данных – контейнер, содержащий указатели на области памяти, каждая из которых содержит одно BCD число. В сравнении участвуют:

1. Сортировка слиянием;
2. Сортировка слиянием без использования буфера;
3. Естественная сортировка слиянием;
4. Естественная сортировка слиянием без использования буфера;
5. Модифицированная естественная сортировка слиянием;
6. Модифицированная естественная сортировка слиянием без использования буфера;
7. std::sort.

Некоторые особенности используемых алгоритмов

При реализации сортировки слиянием без дополнительного буфера памяти для хранения временных данных используются не занятые 4 бита каждого числа в контейнере (для первой итерации — верхние 4 бита, далее соответственно буферная часть и рабочая меняются местами). Реализации сортировок слиянием с и без использования буфера – восходящие ^[2].

При реализации естественной сортировки границы отсортированных участков каждую итерацию находятся заново.

Модификация естественной сортировки заключается в запоминании минимального размера отсортированной подпоследовательности на предыдущей итерации. На следующей итерации, при поиске подпоследовательности этот размер пропускается, затем находится текущее BCD число (или предыдущее, если переход был осуществлен на границу между числами) и далее происходит обычная процедура поиска конца подпоследовательности, как в естественной сортировке.

Тестирование

При проведении тестирования я ориентировался на «эту статью» ^[3], за что большое спасибо ее автору.

Все тесты были исполнены на компьютере со следующими характеристиками:

процессор – Intel core 2 duo e7400,
оперативная память – 4 гибибайт.

Для каждого варьируемого значения проводилось по три замера, на графике отображено среднее арифметическое всех трех замеров.

На каждом из замеров на вход всем сортировкам подавались равнозначные данные. Время указано в миллисекундах (сбоку), память в мегабайтах(снизу). Сортировки идут под своими порядковыми номерами.

Скорость обработки от 1 до 1000 Мб BCD чисел, для чисел по значению, не превышающих их количество в последовательности.

Скорость обработки от 1 до 1000 Мб BCD чисел, для чисел по значению не превышающих MAX_INT (в данной системе — 2 в степени 32).

Расход памяти для сортировки 10 и 100 Мб BCD чисел.

Скорость обработки контейнера, содержащего 100Мб BCD чисел различной степени отсортированности.

Скорость обработки контейнера, содержащего 100Мб BCD чисел различной разрядности.

Различия во времени сортировки для различных компьютеров для 100 Мб BCD чисел.

Характеристики компьютера 1:

— процессор – Intel core 2 duo e7400,
— оперативная память – 4 гибибайт.

Характеристики компьютера 2:

— процессор – AMD A10-7300,
— оперативная память – 4 гибибайт.

Заключение

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

Сортировки без использования дополнительных буферов в среднем работают дольше своих аналогов и использованием дополнительных буферов на 25%.

Натуральная сортировка уступает в быстродействии обычной сортировке слиянием на 15%, хотя ее модификация устраняет этот разрыв.

Автор: Wat_ZLuv

Источник ^[4]