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, int> memo;
return helper(n, 0, 0, memo);
}
int helper(int n, int absence, int consLate, map,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> prevDP(2, vector(3, 1));
for (int i = 1; i <= n; i++) {
vector> newDP(2, vector(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, 0ull, 3ull>::__less(std::tuple const&, std::tuple const&)
1.57 27.98 0.51 1338627000 0.00 0.00 std::tuple_element<0ull, std::tuple >::type const& std::get<0ull, int, int, int>(std::tuple 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 >* std::__do_uninit_fill_n >*, unsigned long long, std::vector > >(std::vector >*, unsigned long long, std::vector > const&)
0.81 1.11 0.01 12000600 0.00 0.00 __gnu_cxx::__normal_iterator > >::base() const
0.81 1.12 0.01 9000000 0.00 0.00 __gnu_cxx::__normal_iterator > >::__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::operator()(int const&, int const&) const
2.32 9.98 0.26 25994400 0.00 0.00 std::_Rb_tree, std::_Select1st >, std::less, std::allocator > >::_M_lower_bound(std::_Rb_tree_node >*, std::_Rb_tree_node_base*, int const&)
1.51 10.15 0.17 503228700 0.00 0.00 std::_Rb_tree, std::_Select1st >, std::less, std::allocator > >::_S_key(std::_Rb_tree_node > const*)
1.42 10.31 0.16 503228700 0.00 0.00 std::_Rb_tree_node >::_M_valptr() const
1.25 10.45 0.14 503228700 0.00 0.00 __gnu_cxx::__aligned_membuf >::_M_ptr() const Здесь я увидел деревья. Погуглив, я узнал, что map в C++ — это дерево, а мне нужно было unordered_map (правда сделал я это после написания дальнейшего решения). Хорошо, заменил map на unordered_map. Т.к. эта структура данных использует std: hash для вычисления хэша, вернуть tuple не получилось, оставляю int. Делаю профиль:
2.17 2.47 0.07 25554600 0.00 0.00 std::__detail::_Hash_node, false>::_M_next() const
1.55 2.52 0.05 24994400 0.00 0.00 std::_Hashtable, std::allocator >, std::__detail::_Select1st, std::equal_to, std::hash, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits >::_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, std::equal_to, std::allocator > >&) Получаю большое количество вызовов std: hash, но время все-таки уменьшилось. Нужно думать дальше.
Зная максимальное значение входных данных, можно посчитать максимальное количество возможных комбинаций и вместо мапы использовать вектор. Так как запись и чтение из вектора это O (1) и по факту просто чтение из памяти со сдвигом, то это должно ускорить этот код.
Заменил мапу на вектор, выделив ему (1e6+1)*6 интов. Делаю профиль, получаю:
100.00 0.01 0.01 100 100.00 100.00 __gnu_cxx::__enable_if::__value, void>::__type std::__fill_a1(int*, int*, int const&)
0.00 0.01 0.00 300 0.00 0.00 std::__new_allocator::~__new_allocator()
0.00 0.01 0.00 200 0.00 0.00 std::__new_allocator::_M_max_size() const
0.00 0.01 0.00 200 0.00 0.00 std::allocator::~allocator() Вуаля, это решение работает еще быстрее, чем то, что предложил пользователь.
Заключение
Что я хотел сказать этой статьей. Я хотел поделиться со всеми вами тем, что даже знание правильного подхода не гарантирует, что ваше решение примут, как произошло со мной на Leetcode. Ведь по сути разные только подходы, а сложность самих решений одинакова.
Можно ли как-то проверять по-другому время выполнения решения? Наверное, можно, но не нужно. Всегда можно придумать какой-нибудь велосипед, который не понятно как работал бы. С точки зрения автоматической проверки проще всегда проверить, что код выполняется за определенное время, чем магическими способами высчитывать сложность алгоритма.
И в защиту себя от негативных комментариев хочу сказать, что я не хотел высказать какую-то свою обиду или нажаловаться :)
Просто делюсь своим таким вот опытом.
P.S. Этой второй раз, когда решение не принимается, потому что я не доглядел (передал вектор по значению, а не по ссылке) или просто что-то не знал.
