Исследование эффективности способов представления двумерных массивов и методов индексации в них
Авторы: Коптенок Елизавета Викторовна, Трунников Максим Владиславович, Сухарев Евгений Александрович, Савенко Арсений Витальевич, Маркелов Константин Дмитриевич
Рубрика: Информатика и кибернетика
Опубликовано в Техника. Технологии. Инженерия №1 (15) февраль 2020 г.
Дата публикации: 31.01.2020
Статья просмотрена: 457 раз
Библиографическое описание:
Исследование эффективности способов представления двумерных массивов и методов индексации в них / Е. В. Коптенок, М. В. Трунников, Е. А. Сухарев [и др.]. — Текст : непосредственный // Техника. Технологии. Инженерия. — 2020. — № 1 (15). — С. 18-23. — URL: https://moluch.ru/th/8/archive/152/4852/ (дата обращения: 25.04.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.
Похожие статьи
Использование двумерных массивов в 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
Самый просто и безошибочный способ — определить координаты прямоугольника.