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

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

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

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

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



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

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

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

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

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

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

Использование двумерных массивов в VBA на уроках...

Массив — набор однотипных переменных, объединенных одним именем и доступных через это имя и порядковый номер переменной в наборе. Организуем в электронных таблицах Excel двумерный массив А, состоящий из 20 х 10 = 200 элементов. Для этого в Excel создадим...

Методика проведения лабораторной работы по дисциплине...

Основные термины (генерируются автоматически) : элемент массива, одномерный массив, методическое пособие, образец результата выполнения программы, массив, значение переменной, последовательность операторов, Программист были, лабораторная работа...

Сортировка одномерного массива в языке программирования C++

В этом, элементы массива печатаются в порядке возрастания. Элементы массива в порядке возрастания можно сортировать, с помощью того метода, в котором создан метод Sort (), в языке программирования C++ для сортировки элементов массива в библиотеке <алгоритм>.

Анализ эффективности алгоритмов сортировки и вcтроенных...

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

Размножение объектов массивом в системе моделирования...

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

Маркелов Константин Дмитриевич — Информация об авторе

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

Библиографическое описание: Коптенок Е. В., Трунников М. В., Сухарев Е. А., Савенко А. В., Маркелов К. Д. Исследование эффективности способов представления...

Сравнительный анализ алгоритмов сортировки данных в массивах

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

К ним относятся алгоритм Демукрона, алгоритм сортировки для представления графа в виде

Статья посвящена вопросам эволюции способов и алгоритмов сортировки данных в массивах.

Использование алгоритмов нечеткого поиска при решении задачи...

В статье описан алгоритм устранения дубликатов записей в базе данных при наличии нескольких источников информации и ошибок операторского ввода. Предложен алгоритм вычисления функции релевантности на основании метода N-gram.

Обработка паспортных данных в среде Matlab | Статья в журнале...

Можно существенно уменьшить количество вычислений и время выполнения операций, если для обработки

Тогда для работы с таким изображением потребуется 3 двумерных массива (r,g,b

Самый просто и безошибочный способ — определить координаты прямоугольника.

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

Использование двумерных массивов в VBA на уроках...

Массив — набор однотипных переменных, объединенных одним именем и доступных через это имя и порядковый номер переменной в наборе. Организуем в электронных таблицах Excel двумерный массив А, состоящий из 20 х 10 = 200 элементов. Для этого в Excel создадим...

Методика проведения лабораторной работы по дисциплине...

Основные термины (генерируются автоматически) : элемент массива, одномерный массив, методическое пособие, образец результата выполнения программы, массив, значение переменной, последовательность операторов, Программист были, лабораторная работа...

Сортировка одномерного массива в языке программирования C++

В этом, элементы массива печатаются в порядке возрастания. Элементы массива в порядке возрастания можно сортировать, с помощью того метода, в котором создан метод Sort (), в языке программирования C++ для сортировки элементов массива в библиотеке <алгоритм>.

Анализ эффективности алгоритмов сортировки и вcтроенных...

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

Размножение объектов массивом в системе моделирования...

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

Маркелов Константин Дмитриевич — Информация об авторе

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

Библиографическое описание: Коптенок Е. В., Трунников М. В., Сухарев Е. А., Савенко А. В., Маркелов К. Д. Исследование эффективности способов представления...

Сравнительный анализ алгоритмов сортировки данных в массивах

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

К ним относятся алгоритм Демукрона, алгоритм сортировки для представления графа в виде

Статья посвящена вопросам эволюции способов и алгоритмов сортировки данных в массивах.

Использование алгоритмов нечеткого поиска при решении задачи...

В статье описан алгоритм устранения дубликатов записей в базе данных при наличии нескольких источников информации и ошибок операторского ввода. Предложен алгоритм вычисления функции релевантности на основании метода N-gram.

Обработка паспортных данных в среде Matlab | Статья в журнале...

Можно существенно уменьшить количество вычислений и время выполнения операций, если для обработки

Тогда для работы с таким изображением потребуется 3 двумерных массива (r,g,b

Самый просто и безошибочный способ — определить координаты прямоугольника.

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