Блог

Главная - Вопросы по программированию - Использование векторного контейнера зависает, в то время как использование массива быстро вычисляет для 2D-массива

Использование векторного контейнера зависает, в то время как использование массива быстро вычисляет для 2D-массива

#c #arrays

#c #массивы

Вопрос:

Я наткнулся на пример из leetcode и, глядя на решения, я попытался реализовать его на C , используя vector следующим образом,

 class Solution {
public:
  int minScoreTriangulation(std::vector<int>amp; A) {
    std::vector<std::vector<int>> memo(A.size(), std::vector<int>(A.size(), 0));
    return tri(A, 0, A.size() - 1, memo);
    }
    
  int tri(std::vector<int>amp; A, int i, int k, std::vector<std::vector<int>> memo) {
        if( k - i < 2) return 0;
        if( k - i == 2) return A[i] * A[i 1] * A[k];
        if( memo[i][k] != 0) return memo[i][k];
        int min = ((unsigned int) ~0) >> 1; // max positive number
        for(int j = i   1; j < k; j  ) {
          min = std::min(A[i] * A[j] * A[k]   tri(A, i, j, memo)   tri(A, j, k, memo), min);
        }
        memo[i][k] = min;
        return min;
    }
};

Программа работает на небольших входных данных, но зависает при больших входных данных,

 int main() {
  std::vector<int> v0 = {35,73,90,27,71,80,21,33,33,13,48,12,68,70,80,36,66,3,70,58}; // hangs
  std::vector<int> v1 = {3,7,4,5}; // works fine
  Solution t = Solution();
  std::cout << t.minScoreTriangulation(v0) << std::endl;
  return 0;
}

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

 class Solution {
public:
  int minScoreTriangulation(std::vector<int>amp; A) {
    int** memo = new int*[A.size()];
    for(int i=0; i<A.size(); i  ) memo[i] = new int[A.size()]{0};
    
    return tri(A, 0, A.size() - 1, memo);
    }
    
  int tri(std::vector<int>amp; A, int i, int k, int** memo) {
        if( k - i < 2) return 0;
        if( k - i == 2) return A[i] * A[i 1] * A[k];
        if( memo[i][k] != 0) return memo[i][k];
        int min = ((unsigned int) ~0) >> 1; // max positive number
        for(int j = i   1; j < k; j  ) {
          min = std::min(A[i] * A[j] * A[k]   tri(A, i, j, memo)   tri(A, j, k, memo), min);
        }
        memo[i][k] = min;
        return min;
    }
};

Можно ли заставить вектор запускаться в разумные сроки? Или это зависит от других факторов, таких как кэш?

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

1. Этот код допускает утечку памяти. Вы вызываете new для создания массива, но там нет delete[]

2. std::vector<std::vector<int>> memo — Вы каждый раз проходите memo по значению. Это должно быть передано по ссылке, т. е. tri(std::vector<int>amp; A, int i, int k, std::vector<std::vector<int>>amp; memo) . Ваш второй пример, как указывалось, приводит к утечке памяти.

3. @PaulMcKenzie ах, это сработало. БОЖЕ!

4. @phoxd — остается ли массив в памяти даже после выхода из программы или до выхода? — Не пишите код таким образом. Что, если эта функция вызывается в программе, которая должна выполняться 24 часа в сутки, семь дней в неделю? Хотели бы вы, чтобы посреди ночи вам звонили и говорили, что ваша программа съела всю память?

5.Примечание: int** не имеет никакого отношения к массиву. Это одиночный указатель, который указывает на выделенный блок, содержащий указатели. Это указатель на указатель на int .

Ответ №1:

Проблема в том, что вы передаете std::vector<std::vector<int>> по значению, а не по ссылке:

 int tri(std::vector<int>amp; A, int i, int k, 
        std::vector<std::vector<int>> memo) // <-- Passed by value

Это приведет к копированию при каждой передаче memo .

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

 int tri(std::vector<int>amp; A, int i, int k, 
        std::vector<std::vector<int>>amp; memo) // <-- Now passed by reference