Исследование эффективности способов представления двумерных массивов и методов индексации в них



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

Массив — упорядоченное множество элементов одного типа, примитивного или ссылочного.

Двумерный массив — массив, элементами которого являются другие массивы; массив массивов.

Двумерные массивы можно представить следующими способами:

1. статический двумерный массив;
2. динамический одномерный массив (элементы строк располагаются друг за другом последовательно);
3. динамический двумерный массив (создается массив указателей, каждый элемент которого содержит адрес отдельной строки).

Статический массив предполагает работу с фиксированным количеством элементов. Память для его хранения выделяется на этапе входа в область видимости. Динамические массивы предполагают программное выделение памяти в процессе выполнения программы и позволяют изменять размерность в течение работы программы.

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

Индексация двумерных массивов — механизм доступа к данным массива с помощью двух выражений, значения которых определяют положение элемента в массиве.

Как правило, доступ к элементам двумерного массива осуществляется с помощью механизмов вложенных циклов. Во внешнем цикле перебирается индекс строки. Для каждого номера строки во вложенных циклах перебираются все номера столбцов. Индексация может выполняться и наоборот — сначала перебираются номера столбцов, затем строки.

Индексация двумерных массивов бывает двух видов:

1. индексация сначала по «строке», потом по «столбцу» (во внешнем цикле перебираются номера строк, во вложенном — столбцов);
2. индексация сначала по «столбцу», потом по «строке» (на оборот, во внешнем цикле перебираются номера столбцов, во вложенном — строк).

От способов представления и способов индексации зависит эффективность работы алгоритмов, использующих двумерные массивы. Основная цель работы: исследовать эффективность способов представления двумерных массивов и методов индексации в них.

Для проведения исследования выполнены следующие действия:

1. создание трех двумерных массивов целых чисел 10000 на 10000 элементов для каждого из способов представления;
2. заполнение каждого из массивов случайными числами;
3. для каждого способа представления и каждого метода индексации выполнение неоднократных замеров времени выполнения нескольких алгоритмов;
4. замеры для каждого алгоритма производятся 10 раз, после чего берется среднее время работы;
5. анализ полученных результатов, формулирование выводов.

Для выполнения исследования будут реализованы следующие алгоритмы на двумерных массивах:

1. Поиск минимального элемента. Алгоритм включает в себя условную операцию сравнения для каждого элемента.
2. Нахождение количества четных элементов. Алгоритм включает в себя условную операцию проверки элемента на четность (остаток от деления на 2 равен нулю).
3. Обмен соседних столбцов попарно местами. Алгоритм включает в себя обмен значений соседних элементов попарно местами с использованием третьей (вспомогательной) переменной.

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

Среднее время выполнения алгоритмов для каждого способа представления двумерного массива и каждого способа индексации в нем представлено на рис.1. Диаграммы, иллюстрирующие время выполнения алгоритмов для каждого из способов индексации, представлены на рис.2 и рис.3.

Рис. 1. Время выполнения алгоритмов

Рис. 2. Время выполнения алгоритмов при индексации «строка-столбец»

Рис. 3. Время выполнения алгоритмов при индексации «столбец- строка»

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

1. Для оптимального поиска минимального элемента следует использовать динамический двумерный массив с индексацией строка-столбец.
2. Минимальное время подсчета количества четных элементов в массиве обеспечивает использование статического двумерного массива с индексацией строка-столбец.
3. Для наиболее быстрой смены соседних столбцов попарно следует использовать статический двумерный массив с индексацией строка-столбец.

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

Литература:

1. Массивы (C++) [Электронный ресурс]. — https://docs.microsoft.com/ru-ru/cpp/cpp/arrays-cpp?view=vs-2017
2. Павловская Т. А. П12 С#. Программирование на языке высокого уровня. Учебник для вузов. — СПб.: Питер, 2009. — 432 с: ил.
3. Страуструп, Б. Язык программирования C++ / Б. Страуструп. — М.: Радио и связь, 2011. — 350 c.
4. Керниган, Б. Язык программирования C. / Б. Керниган, Д. М. Ритчи. — М.: Вильямс, 2016. — 288 c.