Разница во времени выполнения (между функцией с передачей по ссылке и передачей по значению) значима в C ++? - PullRequest
Новая
       72

Разница во времени выполнения (между функцией с передачей по ссылке и передачей по значению) значима в C ++?

1 голос
/ 09 апреля 2020

В вопросе Leetcode 1312 я реализовал решение по количеству проходов, и мое время выполнения для тестового набора было выше 120 мс, для того же тестового примера в проходе по ссылке время выполнения резко сократилось примерно до 8 мс, КАК? Вот оба решения:

120 мс + решение / не принято: 

 class Solution {
public:
    vector< vector<int> > dp;
    int insert(string s,int l,int r)
    {

        if(dp[l][r]!=-1)
            return dp[l][r];
        else if(l>=r)
            return 0;

        if(s[l]==s[r])
            dp[l][r] = insert(s,l+1,r-1)  ;
        else 
            dp[l][r] = 1 + min(  insert(s,l+1,r), insert(s,l,r-1) ) ;

        return dp[l][r];
    }

    int minInsertions(string s) {
        dp.resize(s.length()+1, vector<int> (s.length()+1,-1) );
        return insert(s,0,s.length()-1);
    }
};

~ 8 мс решение: 

   class Solution {
public:
    vector< vector<int> > dp;
    int insert(string& s,int l,int r)
    {

        if(dp[l][r]!=-1)
            return dp[l][r];
        else if(l>=r)
            return 0;

        if(s[l]==s[r])
            dp[l][r] = insert(s,l+1,r-1)  ;
        else 
            dp[l][r] = 1 + min(  insert(s,l+1,r), insert(s,l,r-1) ) ;

        return dp[l][r];
    }

    int minInsertions(string& s) {
        dp.resize(s.length()+1, vector<int> (s.length()+1,-1) );
        return insert(s,0,s.length()-1);
    }
};

У меня есть пара вопросов:

  • Почему разница настолько значительна?
  • Это происходит только для строк, я имею в виду, примитивные / встроенные типы данных ведут себя одинаково?
  • Будет ли передача по указателю приведет к тому же выполнению, что и передача по ссылке?
  • Кроме того, согласно моему пониманию ссылочной переменной, она указывает на тот же адрес, за исключением того, что у нее есть другое имя, это правильно?

Спасибо.

1 Ответ

6 голосов
/ 09 апреля 2020

Является ли разница во времени выполнения (между функцией с передачей по ссылке и передачей по значению) значимой в C ++?

Это может быть значительным и незначительным. Это зависит.

Я реализовал решение передачи по значению, и мое время выполнения для тестового набора было выше 120 мс, для того же тестового примера в проходе по ссылке время выполнения резко сократилось до примерно 8 мс

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

Почему разница настолько значительна?

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

Это происходит? только для строк

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

Я имею в виду, примитивные / встроенные типы данных ведут себя одинаково?

Возможно, нет.

Сколько времени занимает копирование целого числа? Целые числа обычно составляют 1-8 байт. Требуется примерно одна инструкция.

Сколько времени занимает копирование строки? Насколько большой даже строка? Даже sizeof(std::string) - это больше, чем самый большой целочисленный тип в вашей системе. Затем есть массив Dynami c, который может быть размером в гигабайты. Копирование гигабайта занимает больше времени, чем копирование 8 байтов. Даже если строка не настолько массивна, ее копия может включать динамическое распределение c. Динамическое выделение c намного медленнее, чем простое копирование целого числа.

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

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

...