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

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

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

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

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



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

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

Умный указатель — это класс, предназначенный для управления динамически выделенной памятью и обеспечения освобождения выделенной памяти при выходе объекта этого класса из области видимости. Стандартная библиотека в C++11 имеет 4 класса умных указателей:

– std::auto_ptr (удалён в C++17);

– std::unique_ptr;

– std::shared_ptr;

– std::weak_ptr.

Указателем на уникальный объект является std::unique_ptr, а std::shared_ptr и std::weak_ptr — указатели на объекты, которыми могут владеть сразу несколько объектов.

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

  1. поиск минимального элемента;
  2. обмен местами соседних элементов;
  3. умножение отрицательных элементов на 10;
  4. циклический сдвиг на 5 позиций.

Использовались: обычный указатель, std::unique_ptr и std::shared_ptr. Для каждого из них был создан массив из 100000 случайных чисел. Выполнялись многократные замеры времени выполнения алгоритмов и вычислялось их среднее значение. В таблице 1 представлено, сколько секунд выполнялся каждый алгоритм в зависимости от типа указателя.

Таблица 1

Среднее время выполнения алгоритмов для 100000элементов

Тип указателя

Среднее время всекундах

Поиск минимума

Обмен соседних элементов

Умножение отрицательных элементов на 10

Циклический сдвиг

Обычный

0.0004

0.0009

0.0011

0.0023

Умный уникальный

0.0174

0.0625

0.0258

0.1532

Умный неуникальный

0.0101

0.0382

0.0187

0.0791

По диаграмме (рис.1) видно, что по времени наиболее эффективно использование обычных указателей. Умный неуникальный указатель менее эффективен, чем обычный, но более эффективен, чем умный уникальный указатель. Также можно заметить, что применение умных указателей при поиске минимума или умножении отрицательных элементов на число занимает в обоих случаях примерно одинаковое время, но умный неуникальный указатель все равно оказывается выгоднее.

Аналогичный эксперимент проведен для массива из 1000000 элементов. Результаты представлены в табл.2. и на диаграмме (рис.2).

Таблица 2

Среднее время выполнения алгоритмов для 1000000элементов

Тип указателя

Среднее время всекундах

Поиск минимума

Обмен соседних элементов

Умножение отрицательных элементов на 10

Циклический сдвиг

Обычный

0.0041

0.0076

0.0104

0.0282

Умный уникальный

0.1764

0.6594

0.2319

1.7386

Умный неуникальный

0.094

0.3377

0.1386

0.8397

Рис. 1. Среднее время выполнения алгоритмов для 100000 элементов

Диаграммы на рис.1 и рис.2. иллюстрируют одинаковую зависимость, следовательно, эффективность использования рассмотренных типов указателей аналогична предыдущему случаю.

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

Рис. 2. Среднее время выполнения алгоритмов для 1000000 элементов

Литература:

  1. Интеллектуальные указатели (современный C++) [Электронный ресурс]. — https://docs.microsoft.com/ru-ru/cpp/cpp/smart-pointers-modern-cpp?view=vs-2019
  2. Массивы (C++) [Электронный ресурс]. — https://docs.microsoft.com/ru-ru/cpp/cpp/arrays-cpp?view=vs-2017
  3. Павловская Т. А. П12 С#. Программирование на языке высокого уровня. Учебник для вузов. — СПб.: Питер, 2009. — 432 с: ил.
Основные термины (генерируются автоматически): время выполнения алгоритмов, указатель, элемент, поиск минимума, тип указателя, циклический сдвиг, выделенная память, обычный указатель, умный неуникальный указатель, участок памяти.

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

Разработка алгоритма нечеткого поиска на основе хэширования

В ходе выполнения работы был реализован алгоритм поиска на основе хэширования.

Данный алгоритм должен быть достаточно эффективным, чтобы сократить время поиска, так как

Другим важным аспектом является правильная индексация элементов для быстрого и...

Анализ поисковых алгоритмов при решении задач идентификации...

Точный поиск по алгоритму СДВИГ-И (SHIFT-AND).Алгоритм СДВИГ-И показал хорошую скорость поиска и достаточно просто программируется. Кроме того, данный алгоритм обладает уникальной особенностью: он может быть легко модифицирован для задач нечеткого...

Статический анализатор кода на основе взаимодействия...

Сдвиг внутри объекта i определяет элемент сложного типа, на который указывает переменная-указатель, что дает возможность работать с массивами и структурами. В случае, если переменная-указатель указывает на первый элемент массива, смещение равно нулю.

Характеризация статических ячеек памяти | Статья в журнале...

Память — устройство хранение данных (информации), запоминающее устройство. Физическое устройство, используемое в вычислениях и хранении определённых данных в течение заданного времени.

Алгоритмы помехоустойчивого кодирования и их аппаратная...

Аппаратная реализация алгоритмов в первую очередь нужна для получения максимального быстродействия выполнения операций кодирования и декодирования в устройстве. Рис. 1. Функциональная схема для блока вычисляющий CRC код для одного байт, слово и двойное...

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

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

Обзор некоторых алгоритмов нестрогого сопоставления записей...

Нестрогий поиск является методом поиска строк, которые соответствуют шаблону приблизительно, а неточно, что позволяет находить строки с ошибками.

В таблице результатов показано время работы алгоритмов в сравнении с алгоритмом полного перебора.

Разработка способа представления длинных чисел в памяти...

Алгоритм сводится к выполнению следующих действий: Ссылки на младший разряд целой части

В результате выполнения такого алгоритма получится развернутая запись числа, которая

Сам алгоритм поиска простых делителей сводится к последовательному делению...

Увеличение производительности алгоритмов поиска дубликатов...

Сдвиг отпечатков нужен, например, для того, чтобы учесть тишину в начале трека или в

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

Изложенные методы позволяют увеличить устойчивость алгоритма поиска дубликатов...

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

Разработка алгоритма нечеткого поиска на основе хэширования

В ходе выполнения работы был реализован алгоритм поиска на основе хэширования.

Данный алгоритм должен быть достаточно эффективным, чтобы сократить время поиска, так как

Другим важным аспектом является правильная индексация элементов для быстрого и...

Анализ поисковых алгоритмов при решении задач идентификации...

Точный поиск по алгоритму СДВИГ-И (SHIFT-AND).Алгоритм СДВИГ-И показал хорошую скорость поиска и достаточно просто программируется. Кроме того, данный алгоритм обладает уникальной особенностью: он может быть легко модифицирован для задач нечеткого...

Статический анализатор кода на основе взаимодействия...

Сдвиг внутри объекта i определяет элемент сложного типа, на который указывает переменная-указатель, что дает возможность работать с массивами и структурами. В случае, если переменная-указатель указывает на первый элемент массива, смещение равно нулю.

Характеризация статических ячеек памяти | Статья в журнале...

Память — устройство хранение данных (информации), запоминающее устройство. Физическое устройство, используемое в вычислениях и хранении определённых данных в течение заданного времени.

Алгоритмы помехоустойчивого кодирования и их аппаратная...

Аппаратная реализация алгоритмов в первую очередь нужна для получения максимального быстродействия выполнения операций кодирования и декодирования в устройстве. Рис. 1. Функциональная схема для блока вычисляющий CRC код для одного байт, слово и двойное...

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

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

Обзор некоторых алгоритмов нестрогого сопоставления записей...

Нестрогий поиск является методом поиска строк, которые соответствуют шаблону приблизительно, а неточно, что позволяет находить строки с ошибками.

В таблице результатов показано время работы алгоритмов в сравнении с алгоритмом полного перебора.

Разработка способа представления длинных чисел в памяти...

Алгоритм сводится к выполнению следующих действий: Ссылки на младший разряд целой части

В результате выполнения такого алгоритма получится развернутая запись числа, которая

Сам алгоритм поиска простых делителей сводится к последовательному делению...

Увеличение производительности алгоритмов поиска дубликатов...

Сдвиг отпечатков нужен, например, для того, чтобы учесть тишину в начале трека или в

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

Изложенные методы позволяют увеличить устойчивость алгоритма поиска дубликатов...

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