Исследование эффективности способов представления двумерных массивов и методов индексации в них
Авторы: Коптенок Елизавета Викторовна, Трунников Максим Владиславович, Сухарев Евгений Александрович, Савенко Арсений Витальевич, Маркелов Константин Дмитриевич
Рубрика: Информатика и кибернетика
Опубликовано в Техника. Технологии. Инженерия №1 (15) февраль 2020 г.
Дата публикации: 31.01.2020
Статья просмотрена: 610 раз
Библиографическое описание:
Исследование эффективности способов представления двумерных массивов и методов индексации в них / Е. В. Коптенок, М. В. Трунников, Е. А. Сухарев [и др.]. — Текст : непосредственный // Техника. Технологии. Инженерия. — 2020. — № 1 (15). — С. 18-23. — URL: https://moluch.ru/th/8/archive/152/4852/ (дата обращения: 16.12.2024).
При программной реализации алгоритмов часто возникает необходимость хранения больших блоков однотипных данных. Для этой цели применяются массивы. Для хранения данных в табличном формате применяются двумерные массивы.
Массив — упорядоченное множество элементов одного типа, примитивного или ссылочного.
Двумерный массив — массив, элементами которого являются другие массивы; массив массивов.
Двумерные массивы можно представить следующими способами:
- статический двумерный массив;
- динамический одномерный массив (элементы строк располагаются друг за другом последовательно);
- динамический двумерный массив (создается массив указателей, каждый элемент которого содержит адрес отдельной строки).
Статический массив предполагает работу с фиксированным количеством элементов. Память для его хранения выделяется на этапе входа в область видимости. Динамические массивы предполагают программное выделение памяти в процессе выполнения программы и позволяют изменять размерность в течение работы программы.
Для доступа к элементу массива необходимо указать его номер, для двумерного массива — номера строки и столбца элемента.
Индексация двумерных массивов — механизм доступа к данным массива с помощью двух выражений, значения которых определяют положение элемента в массиве.
Как правило, доступ к элементам двумерного массива осуществляется с помощью механизмов вложенных циклов. Во внешнем цикле перебирается индекс строки. Для каждого номера строки во вложенных циклах перебираются все номера столбцов. Индексация может выполняться и наоборот — сначала перебираются номера столбцов, затем строки.
Индексация двумерных массивов бывает двух видов:
- индексация сначала по «строке», потом по «столбцу» (во внешнем цикле перебираются номера строк, во вложенном — столбцов);
- индексация сначала по «столбцу», потом по «строке» (на оборот, во внешнем цикле перебираются номера столбцов, во вложенном — строк).
От способов представления и способов индексации зависит эффективность работы алгоритмов, использующих двумерные массивы. Основная цель работы: исследовать эффективность способов представления двумерных массивов и методов индексации в них.
Для проведения исследования выполнены следующие действия:
- создание трех двумерных массивов целых чисел 10000 на 10000 элементов для каждого из способов представления;
- заполнение каждого из массивов случайными числами;
- для каждого способа представления и каждого метода индексации выполнение неоднократных замеров времени выполнения нескольких алгоритмов;
- замеры для каждого алгоритма производятся 10 раз, после чего берется среднее время работы;
- анализ полученных результатов, формулирование выводов.
Для выполнения исследования будут реализованы следующие алгоритмы на двумерных массивах:
- Поиск минимального элемента. Алгоритм включает в себя условную операцию сравнения для каждого элемента.
- Нахождение количества четных элементов. Алгоритм включает в себя условную операцию проверки элемента на четность (остаток от деления на 2 равен нулю).
- Обмен соседних столбцов попарно местами. Алгоритм включает в себя обмен значений соседних элементов попарно местами с использованием третьей (вспомогательной) переменной.
В результате исследования была создана программа, производящая необходимые расчеты времени работы вышеперечисленных алгоритмов для всех способов индексации и вариантов представления массивов.
Среднее время выполнения алгоритмов для каждого способа представления двумерного массива и каждого способа индексации в нем представлено на рис.1. Диаграммы, иллюстрирующие время выполнения алгоритмов для каждого из способов индексации, представлены на рис.2 и рис.3.
Рис. 1. Время выполнения алгоритмов
Рис. 2. Время выполнения алгоритмов при индексации «строка-столбец»
Рис. 3. Время выполнения алгоритмов при индексации «столбец- строка»
В результате проведенного эксперимента были сделаны следующие выводы:
- Для оптимального поиска минимального элемента следует использовать динамический двумерный массив с индексацией строка-столбец.
- Минимальное время подсчета количества четных элементов в массиве обеспечивает использование статического двумерного массива с индексацией строка-столбец.
- Для наиболее быстрой смены соседних столбцов попарно следует использовать статический двумерный массив с индексацией строка-столбец.
Таким образом, самым оптимальным и универсальным решением будет использование одномерного динамического массива с индексацией строка-столбец, т. к. в этом случае временные показатели незначительно превышают показатели с использование статического массива, но при этом есть возможность динамического расширения памяти.
Литература:
- Массивы (C++) [Электронный ресурс]. — https://docs.microsoft.com/ru-ru/cpp/cpp/arrays-cpp?view=vs-2017
- Павловская Т. А. П12 С#. Программирование на языке высокого уровня. Учебник для вузов. — СПб.: Питер, 2009. — 432 с: ил.
- Страуструп, Б. Язык программирования C++ / Б. Страуструп. — М.: Радио и связь, 2011. — 350 c.
- Керниган, Б. Язык программирования C. / Б. Керниган, Д. М. Ритчи. — М.: Вильямс, 2016. — 288 c.