Приветствую всех пользователей Хабра!
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. Этой второй раз, когда решение не принимается, потому что я не доглядел (передал вектор по значению, а не по ссылке) или просто что-то не знал.
Комментарии (27)
Ukrainskiy
28.05.2024 15:18+10Кажется, вы не совсем правильно понимаете сложность алгоритма по O-нотации. O-нотация отражает не реальную вычислительную сложность, а асимптотическую, то есть показывает, как алгоритм ведет себя при разных объемах входных данных. В вашем случае, вы имеете дело с совершенно разными алгоритмами, хоть они и имеют линейную сложность O(n), т.е. время их выполнения линейно зависит от количества данных, но ресурсы затрачиваемые на одну операцию не равны. Эти алгоритмы могут существенно различаться в реализации, и их фактическое время выполнения может быть разным, даже если их асимптотическая сложность одинакова.
diPhantxm Автор
28.05.2024 15:18Возможно, я понимаю эту нотацию как-то по-другому, согласен. В моем представлении если сложность у алгоритмов одинаковая, то скорость их выполнения не будет отличаться на порядок. Ну то есть я ожидаю увидеть время выполнения, скажем, 3 секунды и 10 секунд, но никак не 30. Это меня и озадачило.
kbnrjlvfrfrfrf
28.05.2024 15:18+4В моем представлении если сложность у алгоритмов одинаковая, то скорость их выполнения не будет отличаться на порядок.
Почему нет? Один алгоритм ищем максимальное в массиве, а другой PBKDF2 каждого элемента вычисляет. Оба O(n). По-хорошему это обозначается c*O(n). Другое дело что на литкоде топорна сама концепция Time Limit. Не правильнее ли было бы прогонять алгоритм два раза с разными N чтобы оценить линейно, квадратично или логарифически изменилось время его выполнения.
diPhantxm Автор
28.05.2024 15:18Хм, согласен. Получается при определенных ограничениях на входные данные можно написать алгоритм со сложностью O(n^2), который работал бы быстрее алгоритма со сложностью O(n) при достаточно большой константе c?
А по поводу определять сложность алгоритма за несколько прогонов. Наверное, так можно было бы попробовать сделать. Не знаю насколько это было бы точно и эффективно. Может так уже сделано где-то, но я везде (Yandex cup, Leetcode, codeforces) видел именно такой способ оценки алгоритма.
9982th
28.05.2024 15:18Time Limit нужен прежде всего для того, чтобы отловить случаи вроде бесконечного цикла в решении. Для конкретной задачи его просто подстраивают до значения, на котором решение успевает отработать на тестовых данных.
Кто-то писал в комментариях к статье про литкод, что входные данные подбирают так, чтобы использовав квадратичный алгоритм вместо линейного вы уперлись в лимит независимо от примененных оптимизаций, однако у меня был случай, когда решение, упавшее с time limit exceeded, было принято без изменений на второй попытке.
vadimr
28.05.2024 15:18+5Почему топорна? Очень жизненна. В реальной жизни заказчика интересует именно time limit, а не асимптотическая сложность.
Я не отношусь к ценителям литкода, но здесь как раз всё верно придумано.
kbnrjlvfrfrfrf
28.05.2024 15:18Я не отношусь к ценителям литкода, но здесь как раз всё верно придумано.
Наверно да. Тот случай когда даже хорошо что не смогли сделать правильно. гг.
onyxmaster
28.05.2024 15:18+6Программирование это не только знание алгоритмов, но и понимание стоимости абстракций используемого языка программирования, а иногда и нюансов аппаратной и программной среды исполнения.
Если задача не решается за отведённое время, то её решение неудовлетворительно, даже если асимптотическая сложность соответствует заданной.
code_panik
28.05.2024 15:18+5то сложность по выполнению у них одинаковая O(n)
У вас операции в map за логарифм, поэтому O(nlogn).
diPhantxm Автор
28.05.2024 15:18Да, я это потом понял, что у обычной мапы в C++ вставка за логарифм выполняет. Тем не менее можно поменять на unordered_map и будет за константу
nronnie
28.05.2024 15:18У меня подозрение, что задачу, на самом деле, можно свести к возведению в степень
nкакой-то матрицы, т.е. решить её вообще заO(log(n))- детали пока что не продумывал.nronnie
28.05.2024 15:18+1Вот, типа, мой вариант решения (без кода, потому что я мудрая сова и занимаюсь только стратегией).
Если мы возьмем все строки длины
n, то все "подходящие" можно разбить на 6 непересекающихся классов:"Класс 0": строки в которых нет 'A' и которые заканчиваются на 'P'
"Класс 1": строки в которых нет 'A' и которые заканчиваются на 'L'
"Класс 2": строки в которых нет 'A' и которые заканчиваются на 'LL'
"Класс 3": строки в которых есть (одна) 'A' и которые заканчиваются на 'A' или 'P'
"Класс 4": строки в которых есть (одна) 'A' и которые заканчиваются на ''L"
"Класс 5": строки в которых есть (одна) 'A' и которые заканчиваются на ''LL"
Теперь если мы будет к этим строкам добавлять один (разный) символ, то:
-
"Класс 0" даст нам:
1 строку "Класса 0" (добавили P)
1 строку "Класса 3" (добавили A)
1 строку "Класса 1" (добавили L)
-
"Класс 1" даст нам:
1 строку "Класса 0" (добавили P)
1 строку "Класса 3" (добавили A)
1 строку "Класса 2" (добавили L)
.... и так далее для всех 6 классов строк
То есть, если мы для
nимеем шестимерный векторр из количества "подходящих" строк для каждого из шести классов, то дляn + 1мы можем такой вектор получить умножением этого вектора на одну и ту же предопределенную матрицу 6x6 (которую мы вывели в предыдущем абзаце). А решение для произвольногоnможно получить возведя эту матрицу в нужную степень и умножив её на вектор дляn = 3. Возведение матрицы в степень можно делать заO(log(n))методом "разделяй и овладевай" (т.е. для четногоnвозводим в степеньn / 2, потом результат умножаем сам на себя, для нечетногоnвозводим в степень(n - 1) / 2умножаем результат сам на себя и на исходную матрицу). Все операции упрощаются еще тем, что результат нам нужен "по модулю чего-то там", а, так как множество чисел "по модулю" (т.е. "множество вычетов") это "кольцо" по отношению к операциям сложения и умножения, то мы сразу можем просто все текущие операции производить по модулю этого числа.
tenzink
28.05.2024 15:18<sarcasm on>Так статью на хабре про литкод вы не напишете</sarcasm on>
В остальном +1
tenzink
28.05.2024 15:18В вашем случае всё-таки дело в сложности алгоритма.
Ваша первая версия: O(n * log(n)) - сложность, O(n) - память
Ваш финальный вариант: O(n) - сложность, О(n) - память
Можно заметно лучше:
(hint: динамическое программирование): O(n) - сложность, O(1) - память
(hint: динамическое программирование + возведение в степень за log(n)): O(log(n)) - сложность, O(1) - память
tenzink
28.05.2024 15:18+1Чтобы не быть голословным вот основная идея: Динамическое программирование
Предположим вы посчитали для заданного
nследующие 6 чисел (количествоeligibleпоследовательностей длиныn):в последовательности 0 пропусков, в конце 0 опозданий
в последовательности 0 пропусков, в конце 1 опоздание
в последовательности 0 пропусков, в конце 2 опоздания
в последовательности 1 пропуск, в конце 0 опозданий
в последовательности 1 пропуск, в конце 1 опоздание
в последовательности 1 пропуск, в конце 2 опоздания
Зная эти 6 чисел для длины
nлегко посчитать эти 6 чисел дляn+1, причём они линейно выражаются через предыдущие. На каждом шаге достаточно хранить только эти 6 чисел.Вторая идея - посмотрите как считается
n-е число Фибоначчи за log(n). Здесь абсолютно тоже самое. Можно представить переход отnкn+1как умножение на матрицу. Тогда вычислениеn-го элемента сводится к возведение матрицы6x6в степеньn, что делается заlog(n)в константной памятиdiPhantxm Автор
28.05.2024 15:18Да, я знаю что такое динамическое программирование. Это вроде как раз то, что я применял.
Я выше к другому комментарию ответил, что все-таки сложность была O(nlogn), но если заменить map на unordered_map, то результат все равно не близок к приемлимуму.
tenzink
28.05.2024 15:18+1По моему опыту у литкода очень расслабленные лимиты по времени. Зачастую (как и в вашем случае) можно взять заведомо неоптимальный алгоритм, и он пройдёт проверку.
AlB80
28.05.2024 15:18Сел, подумал. Накидал код на Си. 17мс. Причесал код. 2мс.
checkRecord() вызывает FillBuf(), которая единожды и линейно заполняет буфер числа хороших вариантов без учёта прогулов (приведение по модулю после сложения делается вычитанием).
checkRecord() остаётся в цикле перемножить значения для расчёта вариантов с учётом одного прогула (приведение по модулю после умножения делается делением).
Alexandroppolus
28.05.2024 15:18"Отсутствие" считается "опозданием"? Т.е. последовательность "LAL" содержит 3 опоздания подряд?
diPhantxm Автор
28.05.2024 15:18Нет, не считается. Такая последовательность вполне подходит, т.к. отсутствий меньше 2 и в ней меньше 3 последовательных опозданий
Alexandroppolus
28.05.2024 15:18Понял, спасибо. Забавные условия - если опаздываешь третий день подряд, то лучше развернуться и уйти )
kbnrjlvfrfrfrf
Лишнее доказательство что литкод это фуфло для сферических теоретиков. Реальная разработка гораздо сложнее и непредсказуемее. Скажем добавлять-удалять (свигать-раздвигать) элементы в линейном массиве быстрее за счёт упреждающего чтения и кэширования, нежели в связанных списках из-за их рандомного размещения в памяти. Хотя у первого O(n), а у второго O(1). А O(n^2) на GPU отработает быстрее чем "оптимизированная" O(n) на CPU (и тем более GPU).
vadimr
Более верно для Intel, менее верно для Apple.
Что, впрочем, только подтверждает вашу основную мысль.
nronnie
Просто еще непонятно на каких данных они гоняют свои benches. Потому что, например, если нужно отсортировать массив из трех элементов, то очевидно, что самый быстрый способ это будет просто посравнивать их попарно :)
stanislav888
Обычно, там чётко описаны все ограничения по объёму и возможным значениям данных. Ошибка "Time Limit Exceeded", вроде бы не даёт конкретных входных значений. Но, всегда можно вставить if на входные данные и вывести их в консоль по своим критериям. Например, тому же размеру вектора в аргументе функции. Ещё можно уронить свою функцию заведомо неправильным ответом, тем же if-ом. Страничка с результатами выдаст входные значения.
nronnie
То что ограничения прописаны это я знаю. Но, неизвестно на каких объемах данных они на самом деле проверяют когда сравнивают между собой два решения. Еще вот такая штука. Вот, например, упомянутая задача - сказано, что буквы могут быть только 'A', 'P', 'L', но лично я, если буду писать, то все равно поставлю в код проверку (просто с выбросом исключения) что не пришла какая-то другая буква кроме вышеупомянутых, потому что по хорошему так и надо - а это ведь тоже затраты.