рекурсия — что быстрее? Передача по ссылке против передачи по значению Переполнение стека

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

Но рассмотрим следующий код C ++:

#include <iostream>
#include <cassert>
#include <cmath>

using namespace std;

// do not use pass by reference& with this function, it will become so slow
unsigned long long computePascal(const unsigned int row, const unsigned int position) {
if (position == 1 || position == row)
return 1L;
unsigned long long left = computePascal(row-1, position-1);
unsigned long long right = computePascal(row-1, position);
unsigned long long sum = left + right;
return sum;
}

int main() {
int row, position;
cout << "Input row and position: ";
cin >> row >> position;
assert(position > 0 && position <= row);
unsigned long long pascalNumber = computePascal(row, position);
cout << pascalNumber << endl;
return 0;
}

Теперь этот код — просто обычная программа, которая рекурсивно вычисляет паскальское число, вводя желаемую строку и положение треугольника.

Я попытался поместить строку 50 и позицию 7, и она вычисляет около 1 секунды (передача по значению). Выход составляет около 13 миллионов, что является правильным. Поэтому я подумал, что это может быть быстрее, если я перейду по ссылке, потому что не нужно копировать много данных. Но это очень неправильно, и я не знаю, почему это заняло больше времени, примерно в 3 раза больше, чем за прохождение по стоимости.
Вопрос в том …

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

Имеет ли значение, что, поскольку рекурсивная функция является исключением, вы должны передавать ее по значению, а не по константной ссылке?

-2

Решение

Ответ на вопрос «Что быстрее» обычно «зависит».

Если вместо передачи четырех байтов данных вы передаете восьмибайтовый указатель на данные, то вы не можете ожидать, что это ускорит процесс. Если вместо передачи 100 байтов данных вы передаете восьмибайтовый указатель на данные, это не так.

Но теперь функция не имеет данных, она имеет только ссылку. Поэтому, когда ему нужно прочитать данные, он должен сделать это косвенно через ссылку. Это занимает больше времени. Если вы пропустите 100-байтовый объект и прочитаете только восемь байт, вы все равно, вероятно, выиграете. Но если вы на самом деле читаете все данные, и, возможно, несколько раз, тогда легко будет передать значение даже для больших объектов.

Реальная разница возникает, когда вы передаете объект, и передача по значению означает, что будет вызван более или менее сложный конструктор. Передача по ссылке означает отсутствие конструктора. Но у int нет конструктора в любом случае.

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

И тогда есть правило оптимизации: «Измерь это». Вы измерили это и нашли что быстрее. Иногда дела идут быстрее или медленнее без веской причины.

5

Другие решения


По вопросам рекламы [email protected]