Приветствую всех пользователей Хабра!
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. Этой второй раз, когда решение не принимается, потому что я не доглядел (передал вектор по значению, а не по ссылке) или просто что-то не знал.
