Другие языки программирования и технологии

Перебор двумерного массива. Вопрос на засыпку.

Создаем двумерный массив чисел. Перебираем его поэлементно вложенными циклами FOR. Почему перебор массива по строкам оказывается на порядок быстрее, чем перебор по столбцам?Напомню, что ОЗУ представляет собой одномерную линейку адресованых ячеек памяти. Время доступа к любому случайному адресу одинаково.
Сергей Сутковенко
Сергей Сутковенко
7 465
Дело как раз-таки в ОЗУ.

Писать много не буду, найдите книгу
"Техника оптимизации программ" К. Касперски.

Там все подробно про это написано.

add:
Впрочем, дело не только в RAM, а в процессоре, точнее, в кеше
и конвеере.
Николай Степанов
Николай Степанов
3 846
Лучший ответ
перебор всего массива включает циклы И по строкам И по столбцам.
что именно вы имели сказать?
что значит "на порядок"?
скорости работы программ по времени сравнивать не совсем правильно. сравнивают порядки (уровни сложности) кода. Для двойного вложенного цикла (где каждый из циклов бежит от 1 до N) порядок составляет N^2 и это не зависит от порядка вложенности циклов.

если же вам время работы сравнить надо, то разберитесь - в каком порядке массив хранится в памяти.. . Если хранится строка за строкой, то никакого перескакивания туда-сюда по ОЗУ не будет - всё будет работать от начала до конца постоянно в одном направлении.. .

в любом случае, это всё условно и относится лишь к одно-процессорным системам выполняющим операции последовательно...
ЕМ
Евгений Михеев
97 203
Сергей Сутковенко По строкам - значит перебор идет в напрвлении строк. Ясное дело, что переход на следующий столбец после прохождения i-й строки необходим.

На порядок - понятие из математики. Так условно говорят о том, что одно число в ~10 раз отлично от другого.

Не понимаю, при чем тут скорость работы программы в целом или понятие сложности кода, основанное на количестве операций. Вопрос был о времени прохождения одного участка кода (вложенных циклов) при прочих равных условиях.

Массив хранится в памяти линейкой. ОЗУ имеет одинаковое время доступа к произвольной ячейке. i-я ячейка в любом случае вычисляется по базовому адресу + смещению с учетом количества байт на одну ячейку. Процессору, как я понимаю, все равно как складывать, поскольку порядки адресов при разных способах перебора близки. А+1 или А+25 - я думаю, нет разницы.

Отличие на 1 порядок - это уже не условность, да и какая разница, на скольких процессорах это реализуется, если операция А оптимальнее Б.
for i:=1 to 10 do
for j:=1 to 10 do
write(n[i,j]);

естественно, цикл о (внутренний) будет выполняться гораздо быстрее цикла i (внешнего) .
ИД
Иван Долгов
1 994
да насчёт строк и столбцов, еси после каждого перехода в цикле строк писать слово "перешли" а после перехода цикла по столбцам писать "+", то мы получим из массива a[2][2] получим нечто подобное:
перешли+++першли+++перешли+++
следовательно считаем сколько раз за примерно одно и тоже время отработал каждый из массивов, первый тоесть его вообщето называют строки :) отработал всего три раза, а второй на удивление аш девять раз :) , однаку шустрый масив столбцов некажется ли?
Если рассматривать жизненный цикл программы с аппаратной части, то после входа в первый цикл мы выйдем из него только тагда когда уловие станет ложным тоесть for(init;question;даже хоть ничего непоставьте) -сёравно условие будет проверяться всегда впоследнюю очередь и только потом произойдёт выход
Геннадий Бондаренко
Геннадий Бондаренко
389

Похожие вопросы