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

в 12:39, , рубрики: benchmark, c++, merge sort, sorting, Алгоритмы, алгоритмы сортировки, бенчмарки, сортировка слиянием

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

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

image

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

image

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

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

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

Скрытый текст
Отсортированность определяется как

sortedness = counts/count

где count – общее количество пар подряд идущих чисел в последовательности, count – число таких пар, для которых точно известно, что в паре первое число меньше второго.

Таким образом, мера отсортированности находится на интервале [0, 1], причем, при sortedness = 0, получаем полностью случайную последовательность, при sortedness = 1 получаем полностью отсортированную последовательность.

image

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

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

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

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

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

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

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

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

Заключение

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

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

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

Автор: Wat_ZLuv

Источник

Поделиться новостью

* - обязательные к заполнению поля