Исследование эффективности способов представления двумерных массивов и методов индексации в них | Статья в журнале «Техника. Технологии. Инженерия»

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

Опубликовать статью в журнале

Библиографическое описание:

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



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

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

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

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

  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.
Основные термины (генерируются автоматически): время выполнения алгоритмов, массив, двумерный массив, индексация, способ индексации, способ представления, внешний цикл, номер столбцов, статический двумерный массив, элемент.

Похожие статьи

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

Исследование методической погрешности метода квазиэквивалентного укрупнения состояний марковских моделей

Исследование эффективности способов написания SQL запросов с использованием СТЕ и подзапросов

Исследование принципов работы программ распознавания музыки, используемых в современных приложениях

Характеристика метода моделирования в формировании пространственных представлений у детей старшего дошкольного возраста

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

Исследование формирования семантики цвета в онтогенезе

Применение экономико-статистических методов анализа и прогноза динамических рядов в исследовании социальных факторов населения

Изучение инфракрасного метода сушки зерна и зернистых материалов

Исследование математической модели первой краевой задачи для волнового уравнения методом регуляризации

Похожие статьи

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

Исследование методической погрешности метода квазиэквивалентного укрупнения состояний марковских моделей

Исследование эффективности способов написания SQL запросов с использованием СТЕ и подзапросов

Исследование принципов работы программ распознавания музыки, используемых в современных приложениях

Характеристика метода моделирования в формировании пространственных представлений у детей старшего дошкольного возраста

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

Исследование формирования семантики цвета в онтогенезе

Применение экономико-статистических методов анализа и прогноза динамических рядов в исследовании социальных факторов населения

Изучение инфракрасного метода сушки зерна и зернистых материалов

Исследование математической модели первой краевой задачи для волнового уравнения методом регуляризации

Задать вопрос