Чтобы правильно применить любой алгоритм, очень важно выбрать правильную структуру данных. Это связано с тем, что конкретная операция, выполняемая над структурой данных, может занять больше времени по сравнению с той же операцией, выполняемой над другой структурой данных.
Пример. Для доступа к i- му элементу в наборе с использованием массива может потребоваться постоянное время, но при использовании связанного списка время, необходимое для выполнения той же операции, может стать полиномом.
Следовательно, выбор структуры данных должен выполняться с учетом архитектуры и типа выполняемых операций.
Следующие структуры данных обычно используются в параллельном программировании —
- Связанный список
- Массивы
- Сеть гиперкубов
Связанный список
Связанный список — это структура данных, имеющая ноль или более узлов, связанных указателями. Узлы могут занимать или не занимать последовательные области памяти. Каждый узел состоит из двух или трех частей — одна часть данных, в которой хранятся данные, а две другие — это поля ссылок , в которых хранится адрес предыдущего или следующего узла. Адрес первого узла хранится во внешнем указателе, называемом головой . Последний узел, известный как tail, обычно не содержит никакого адреса.
Есть три типа связанных списков —
- Единственный связанный список
- Двусвязный список
- Круговой связанный список
Единственный связанный список
Узел односвязного списка содержит данные и адрес следующего узла. Внешний указатель с именем head хранит адрес первого узла.
Двусвязный список
Узел двусвязного списка содержит данные и адрес как предыдущего, так и следующего узла. Внешний указатель с именем head хранит адрес первого узла, а внешний указатель с именем tail хранит адрес последнего узла.
Круговой связанный список
Круговой связанный список очень похож на односвязный список за исключением того факта, что последний узел сохранил адрес первого узла.
Массивы
Массив — это структура данных, в которой мы можем хранить похожие типы данных. Это может быть одномерный или многомерный. Массивы могут быть созданы статически или динамически.
-
В статически объявленных массивах размер и размер массивов известны во время компиляции.
-
В динамически объявленных массивах размер и размер массива известны во время выполнения.
В статически объявленных массивах размер и размер массивов известны во время компиляции.
В динамически объявленных массивах размер и размер массива известны во время выполнения.
При программировании с общей памятью массивы можно использовать как общую память, а при параллельном программировании данных их можно использовать путем разбиения на подмассивы.
Сеть гиперкубов
Архитектура гиперкуба полезна для тех параллельных алгоритмов, где каждая задача должна взаимодействовать с другими задачами. Топология гиперкуба может легко встраивать другие топологии, такие как кольцо и сетка. Это также известно как n-кубов, где n — число измерений. Гиперкуб может быть построен рекурсивно.