Отправьте статью сегодня! Журнал выйдет 26 июля, печатный экземпляр отправим 30 июля
Опубликовать статью

Молодой учёный

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

Информатика и кибернетика
31.01.2020
670
Поделиться
Библиографическое описание
Исследование эффективности способов представления двумерных массивов и методов индексации в них / Е. В. Коптенок, М. В. Трунников, Е. А. Сухарев [и др.]. — Текст : непосредственный // Техника. Технологии. Инженерия. — 2020. — № 1 (15). — С. 18-23. — URL: https://moluch.ru/th/8/archive/152/4852/.


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

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

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

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

  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.
Можно быстро и просто опубликовать свою научную статью в журнале «Молодой Ученый». Сразу предоставляем препринт и справку о публикации.
Опубликовать статью

Молодой учёный