Time Limit Exceeded это не только про сложность алгоритма

Приветствую всех пользователей Хабра!

Disclaimer: Я не какой-то Senior разработчик на C/C++ и не выигрывал ICPC. Я просто пишу код на Golang и иногда решаю алгоритмические задачки. И не претендую ни на что!

Предыстория

Вчера я как обычно зашел на Leetcode, чтобы решить ежедневную задачку. Условие:

An attendance record for a student can be represented as a string 
where each character signifies whether the student was absent, late, or present on that day. 
The record only contains the following three characters:

'A': Absent.

'L': Late.

'P': Present.

Any student is eligible for an attendance award if they meet both of the following criteria:

The student was absent ('A') for strictly fewer than 2 days total.

The student was never late ('L') for 3 or more consecutive days.

Given an integer n, return the number of possible attendance records of length n that make a student eligible for an attendance award. The answer may be very large, so return it modulo 109 + 7

Я написал код, проверил на тестовых значениях, все ок. Отправляю решение и получаю Time Limit Exceeded. Посидев и подумав еще немного, я не нашел решения лучше. Пошел смотреть решения. Наткнулся на следующее решение. Здесь человек пишет, что такое решение подходит, но оно не будет проходить по времени из-за большого количества вызовов функций. Он преобразовал это решение под итеративный подход.

Получилось два решения:

Мое (TLE):

class Solution {
public:
    int mod = 1e9+7;

    int checkRecord(int n) {
        map<tuple<int,int,int>, int> memo;
        return helper(n, 0, 0, memo);
    }

    int helper(int n, int absence, int consLate, map<tuple<int,int,int>,int>& memo) {
        if (n == 0) return 1;
        if (memo.find({n, absence, consLate}) != memo.end()) return memo[{n,absence, consLate}];

        int result = 0;
        result = (result + helper(n-1, absence, 0, memo)) % mod;
        if (absence < 1) {
            result = (result + helper(n-1, absence+1, 0, memo)) % mod;
        }
        if (consLate < 2) {
            result = (result + helper(n-1, absence, consLate+1, memo)) % mod;
        }

        memo[{n,absence, consLate}] = result;
        return result;
    }
}

Пользователя:

class Solution {
private:
    static const int MOD = 1000000000 + 7;

public:
    int checkRecord(int n) {
        vector<vector<int>> prevDP(2, vector<int>(3, 1));

        for (int i = 1; i <= n; i++) {
            vector<vector<int>> newDP(2, vector<int>(3, 0));
            for (int a = 0; a < 2; a++) {
                for (int l = 0; l < 3; l++) {
                    // Pick P
                    newDP[a][l] += prevDP[a][2];
                    newDP[a][l] %= MOD;
                    if (a > 0) {
                        // Pick A
                        newDP[a][l] += prevDP[a - 1][2];
                        newDP[a][l] %= MOD;
                    }
                    if (l > 0) {
                        // Pick L
                        newDP[a][l] += prevDP[a][l - 1];
                        newDP[a][l] %= MOD;
                    }
                }
            }
            prevDP = newDP;
        }

        return prevDP[1][2];
    }
};

Если так взглянуть на эти решения, то сложность по выполнению у них одинаковая O(n), то есть линейная. Тут я и решил поинтересоваться насколько же мое решение оказывается медленее.

Профилирование

Я написал самый простой бенчмарк и запускал функции 100 раз с максимальными по объему входными данными.

Профилирование я делал на Windows (каюсь) при помощи gprof. Профиль моего кода выдал следующий результат без учета внутренних функций самого gprof:

  2.03     27.47     0.66 505560900     0.00     0.00  std::__tuple_compare<std::tuple<int, int, int>, std::tuple<int, int, int>, 0ull, 3ull>::__less(std::tuple<int, int, int> const&, std::tuple<int, int, int> const&)
  1.57     27.98     0.51 1338627000     0.00     0.00  std::tuple_element<0ull, std::tuple<int, int, int> >::type const& std::get<0ull, int, int, int>(std::tuple<int, int, int> const&)
  1.26     28.39     0.41 1338627000     0.00     0.00  std::_Head_base<0ull, int, false>::_M_head(std::_Head_base<0ull, int, false> const&)
  1.08     28.74     0.35 1338627000     0.00     0.00  int const& std::__get_helper<0ull, int, int, int>(std::_Tuple_impl<0ull, int, int, int> const&)

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

Профиль решения пользователя выдал что-то следующее:

  1.63      1.10     0.02  1000100     0.00     0.00  std::vector<int, std::allocator<int> >* std::__do_uninit_fill_n<std::vector<int, std::allocator<int> >*, unsigned long long, std::vector<int, std::allocator<int> > >(std::vector<int, std::allocator<int> >*, unsigned long long, std::vector<int, std::allocator<int> > const&)
  0.81      1.11     0.01 12000600     0.00     0.00  __gnu_cxx::__normal_iterator<int const*, std::vector<int, std::allocator<int> > >::base() const
  0.81      1.12     0.01  9000000     0.00     0.00  __gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >::__normal_iterator(int* const&)

И код выполнялся около одной с четвертью секунды.

Раз такое дело, я решил убрать tuple из своего кода. Я представил этот tuple в виде int, считая, что tuple это просто три индекса. Таким образом, tuple(i, j, k) = i*6 + j*3 + k. Значения 6 и 3 выходят из условия задачи.

Операции с получением значений из tuple и сравнения должны уйти. Делаю профиль, получаю:

  2.40      9.72     0.27 505560900     0.00     0.00  std::less<int>::operator()(int const&, int const&) const
  2.32      9.98     0.26 25994400     0.00      0.00  std::_Rb_tree<int, std::pair<int const, int>, std::_Select1st<std::pair<int const, int> >, std::less<int>, std::allocator<std::pair<int const, int> > >::_M_lower_bound(std::_Rb_tree_node<std::pair<int const, int> >*, std::_Rb_tree_node_base*, int const&)
  1.51     10.15     0.17 503228700     0.00     0.00  std::_Rb_tree<int, std::pair<int const, int>, std::_Select1st<std::pair<int const, int> >, std::less<int>, std::allocator<std::pair<int const, int> > >::_S_key(std::_Rb_tree_node<std::pair<int const, int> > const*)
  1.42     10.31     0.16 503228700     0.00     0.00  std::_Rb_tree_node<std::pair<int const, int> >::_M_valptr() const
  1.25     10.45     0.14 503228700     0.00     0.00  __gnu_cxx::__aligned_membuf<std::pair<int const, int> >::_M_ptr() const

Здесь я увидел деревья. Погуглив, я узнал, что map в C++ - это дерево, а мне нужно было unordered_map (правда сделал я это после написания дальнейшего решения). Получается сложность моего первого алгоритма все-таки была O(n*logn), а не O(n).

Хорошо, заменил map на unordered_map, сложность стала O(n). Т.к. эта структура данных использует std::hash для вычисления хэша, вернуть tuple не получилось, оставляю int. Делаю профиль:

  2.17      2.47     0.07 25554600     0.00     0.00  std::__detail::_Hash_node<std::pair<int const, int>, false>::_M_next() const
  1.55      2.52     0.05 24994400     0.00     0.00  std::_Hashtable<int, std::pair<int const, int>, std::allocator<std::pair<int const, int> >, std::__detail::_Select1st, std::equal_to<int>, std::hash<int>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<false, false, true> >::_M_find_before_node(unsigned long long, int const&, unsigned long long) const
  1.55      2.57     0.05      100     0.50     7.74  helper(int, int, int, std::unordered_map<int, int, std::hash<int>, std::equal_to<int>, std::allocator<std::pair<int const, int> > >&)

Получаю большое количество вызовов std::hash, но время все-таки уменьшилось. Нужно думать дальше.

Зная максимальное значение входных данных, можно посчитать максимальное количество возможных комбинаций и вместо мапы использовать вектор. Так как запись и чтение из вектора это O(1) и по факту просто чтение из памяти со сдвигом, то это должно ускорить этот код.

Заменил мапу на вектор, выделив ему (1e6+1)*6 интов. Делаю профиль, получаю:

100.00      0.01     0.01      100   100.00   100.00  __gnu_cxx::__enable_if<std::__is_scalar<int>::__value, void>::__type std::__fill_a1<int*, int>(int*, int*, int const&)
  0.00      0.01     0.00      300     0.00     0.00  std::__new_allocator<int>::~__new_allocator()
  0.00      0.01     0.00      200     0.00     0.00  std::__new_allocator<int>::_M_max_size() const
  0.00      0.01     0.00      200     0.00     0.00  std::allocator<int>::~allocator()

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

Заключение

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

Можно ли как-то проверять по-другому время выполнения решения? Наверное, можно, но не нужно. Всегда можно придумать какой-нибудь велосипед, который не понятно как работал бы. С точки зрения автоматической проверки проще всегда проверить, что код выполняется за определенное время, чем магическими способами высчитывать сложность алгоритма.

И в защиту себя от негативных комментариев хочу сказать, что я не хотел высказать какую-то свою обиду или нажаловаться :)

Просто делюсь своим таким вот опытом.

P.S. Этой второй раз, когда решение не принимается, потому что я не доглядел (передал вектор по значению, а не по ссылке) или просто что-то не знал.