Демонстративно вертим массивы для новичков

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

Цель этого поста — собрать некоторую информацию о массивах, которой когда-то не хватало мне. Пост для новичков.

Что такое массив?

Массив - это структура однотипных данных, расположенная в памяти одним неразрывным блоком.

Расположение одномерного массива в памяти
Расположение одномерного массива в памяти

Многомерные массивы хранятся точно также.

Расположение двухмерного массива в памяти
Расположение двухмерного массива в памяти

Знание этого позволяет нам по-другому обращаться к элементам массива. Например, у нас есть двухмерный массив из 9 элементов 3х3. Так что есть, как минимум два способа вывести его правильно:

1-й вариант (Самый простой):

int arr[3][3] {1, 2, 3, 4, 5, 6, 7, 8, 9};
int y = 3, x = 3;
for (int i = 0; i < y, ++i) {
	for (int j = 0; j < x; ++j) {
  	std::cout << arr[i][j];
  }
  std::cout << std::endl;
}

2-й вариант (Посложнее):

int arr [9] {1,2,3,4,5,6,7,8,9};
int x = 3, y = 3;
for (int i = 0; i < y; ++i) {
  for (int j = 0; j < x; ++j) {
		std::cout << arr[x * i + j]; // x - ширина массива
    }
  std::cout << std::endl;
}

Формула для обращения к элементу 2-размерного массива, где width - ширина массива, col - нужный нам столбец, а row - нужная нам строчка:

arr[width * col + row]

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

А вот так можно работать с трехмерным массивом
int arr[8] {1,2,3,4,5,6,7,8};
int x = 2, y = 2, z = 2;
for (int i = 0; i < x; ++i) {
	for (int j = 0; j < y; ++j) {
  	for (int k = 0; k < z; ++z) {
    	std::cout << arr[x * y * i + y * j + k];
    }
    std::cout << std::endl;
  }
  std::cout << std::endl;
} 

Этим способом можно обходить трехмерные объекты, например.

Формула доступа к элементам в трехмерном массиве, где height - высота массива, width - ширина массива, depth - глубина элемента(наше новое пространство), col - столбец элемента, а row - строка элемента:

arr[height * width * depth + width * col + row]

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

Алгоритмы обработки массивов

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

Изображения - это целый комплекс из разных заголовков и информации о изображении, и самого изображения хранящемся в виде двухмерного массива.

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

1) Зеркальное отражение.

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

int data[3][4] = {1,2,3,4,5,6,7,8,9,10,11,12};
int newArray[3][4];
int height = 3, width = 4;
for (int i = 0; i < height; ++i) {
	for (int j = 0; j < width; ++j) {
  	newArray[i][j] = data[i][width - j - 1];
  }
}

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

int data[3][4] = {1,2,3,4,5,6,7,8,9,10,11,12};
int newArray[3][4];
int height = 3, width = 4;
for (int i = 0; i < height; ++i) {
	for (int j = 0; j < width; ++j) {
  	newArray[i][j] = data[height - i - 1][j];
  }
}

2) Поворот изображения на 90 градусов.

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

Пошаговое выполнение алгоритма
Пошаговое выполнение алгоритма

Такой алгоритм появился, когда я нарисовал график координат c точками.

График, приведший к решению
График, приведший к решению
int data[3][2] = {1,2,3,4,5,6};							
int newArray[2][3];					
int height = 3, width = 2; 	// Размеры массива (изображения)
int newHeight = width, newWidth = height;

// Транспонируем матрицу
for (int i = 0; i < newHeight; ++i) {
	for (int j = 0; j < newWidth; ++j) {
  	newArray[i][j] = data[j][i];			// data - массив изображения
  }
}

// Зеркально отражаем по горизонтали матрицу
for (int i = 0; i < newHeight; ++i) {
	for (int j = 0; j < newWidth/2; ++j) {
  	int temp = newArray[i][j];
    newArray[i][j] = newArray[i][newWidth - j - 1];
    newArray[i][newWidth - j - 1] = temp;
  }
}

Хочу обратить ваше внимание, что здесь я применяю другой способ переворота изображения. Вместо выделения памяти под новый массив, здесь просто меняем местами первые и последние элементы.

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

Заключение

Этот небольшой пост не претендует на невероятные открытия мира информатики, но надеюсь успешно поможет немного вникнуть в устройство массивов падаванам мира IT.

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

Я надеюсь этот пост будет полезен, и если это будет так, то я напишу продолжение этой темы.

Комментарии 17

    +13

    Я уж подумал что будут разбирать почему тривиальное транспонирование работает медленно и как его написать быстро, а оказалось что статья про B[i, j] = A[j, i].

      0
      Эта статья рассчитана на совсем новичков, поэтому здесь и не рассматриваются вопросы быстродействия. Однако, я учту.
      +8
      Я уж подумал что будут разбирать почему поворот на произвольный угол работает медленно и как компенсировать искажения, а оказалось что статья про B[i, j] = A[j, i]. (простите не удержался)
        +12

        Я уж подумал что будут разбирать, как можно эффективно поворачивать изображения с помощью векторных инструкций (SSE, AVX, AVX512) и нюансов работы кэша и сравнивать реализацию, например, с Intel MKL, а оказалось что статья про B[i, j] = A[j, i]. (простите меня тоже)

          +2

          Простите, я не в тренде, но я для начала хотя бы думал, что автор понимает, почему в двумерном массиве "две звёздочки". Но нет, у автора "двумерный массив лежит в памяти одним блоком". Нет. В общем случае, не лежит.

            0
            Не всё так однозначно. Если двухмерный (многомерный в в общем случае) массив объявлен так, как это показано в статье, то он однозначно «лежит в памяти одним блоком».

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

            совершенно неправильно. «Указатели на указатели на указатели» появляются только в том случае, когда многомерный массив размерности n реализуется с помощью массива указателей на массивы с размерностью n-1. И, да, в этом случае данные массива будут разбросаны по памяти. Обычно это бывает при создании многомерного массива в куче при размерах массива, неизвестных на этапе компиляции. Хотя и в этом случае, если чуть-чуть напрячься и заморочиться с адресной арифметикой, можно написать класс, реализующий многомерный массив, данные которого будут лежать в куче единым блоком.
              0

              Ну так вот поэтому я и написал "в общем случае". А у автора двумерные массивы лежат одним блоком. Мой комментарий как раз про то, что не всё так однозначно.

              0
              Я понимаю, что двумерный динамический массив с «двумя звёздочками» состоит из блоков в произвольном месте. Но это не тема статьи. Тема статьи — принцип простейших алгоритмов. То, во что часто упираются новички
              +6
              Примечание: создать массив размерностью высоты и ширины реального изображения на стеке не выйдет. Только на куче с помощью оператора new.

              Я уж подумал, что статья про то, как передать линкеру флаг -Wl,--stack,10485760 чтобы задать размер стека и сравнить скорость переворота с реализацией на куче.

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

                Хм, а функция alloca тогда что делает?

                  –2
                  Во-первых, такой функции нет в стандарте С++. Т.е. сразу непереносимо.
                  Во-вторых, в данном случае, использование этой функции эквивалентно объявлению локальной переменной-массива. С теми же потенциальными граблями и, возможно, дополнительными ключами компиляции.
                  А оно надо?
                    +1
                    Во-первых, такой функции нет в стандарте С++. Т.е. сразу непереносимо.

                    Вам шашечки или ехать? AVX-интринсиков тоже нет в стандарте C++, а их почему-то используют.


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

                    Да, с помощью C++ добиться высокой производительности, но можно и выстрелить в ногу.

                  +1
                  Я уж подумал, что будут разбирать почему важна локальность памяти, методы inplace транспонирования и почему может быть эффективнее пройти по матрице несколько раз чем делать транспонирование за один проход, а оказалось что статья про B[i, j] = A[j, i]. (тоже не удержался)
                    0
                    Простите, это статья про A[i, j] = B[j, i] или B[i, j] = A[j, i]?
                      +1
                      Меня аж ностальгия пробила.

                      Выкопал старые исходники (а то вдруг память подводит), примерно 93-го года сочинения. Была у меня там библиотека для работы с матрицами. И таки да, адресная арифметика, переопределение операторов и операции типа транспонирования… Помню, поражал препода лабораторкой, где в main было ((A+B)*C).print(); в те времена, когда новички писали это всё многосложными циклами.

                      К чему это я? Даже в те лохматые коды то, что описано автором, преподавалось в школе (пусть и не в каждой), как азы, в чистом виде не применимые в нормальной разработке.
                      И если уж у сферических новичков возникают проблемы с массивами, то не надо показывать циклы на уровне школьной арифметики. Им это не поможет.
                        0
                        Хороший комментарий, но я вас разочарую — не во всех школах преподают информатику. Меня в школе абсолютно не учили не информатике, ни программированию на протяжении 3 лет. Всё приходилось самому.
                        преподавалось в школе (пусть и не в каждой), как азы, в чистом виде не применимые в нормальной разработке.

                        А с чего-то же надо начинать. Сомневаюсь, что какой-нибудь новичок сможет уже через месяц заниматься нормальной разработкой.
                          0
                          С этого надо начинать, но не здесь.

                          И, если уж начинать с азов, то не с этих. Совсем новичка тут много собьёт с толку.

                      Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                      Самое читаемое