Comments 36
Скажем добавлять-удалять (свигать-раздвигать) элементы в линейном массиве быстрее за счёт упреждающего чтения и кэширования, нежели в связанных списках из-за их рандомного размещения в памяти.
Более верно для Intel, менее верно для Apple.
Что, впрочем, только подтверждает вашу основную мысль.
Просто еще непонятно на каких данных они гоняют свои benches. Потому что, например, если нужно отсортировать массив из трех элементов, то очевидно, что самый быстрый способ это будет просто посравнивать их попарно :)
Обычно, там чётко описаны все ограничения по объёму и возможным значениям данных. Ошибка "Time Limit Exceeded", вроде бы не даёт конкретных входных значений. Но, всегда можно вставить if на входные данные и вывести их в консоль по своим критериям. Например, тому же размеру вектора в аргументе функции. Ещё можно уронить свою функцию заведомо неправильным ответом, тем же if-ом. Страничка с результатами выдаст входные значения.
То что ограничения прописаны это я знаю. Но, неизвестно на каких объемах данных они на самом деле проверяют когда сравнивают между собой два решения. Еще вот такая штука. Вот, например, упомянутая задача - сказано, что буквы могут быть только 'A', 'P', 'L', но лично я, если буду писать, то все равно поставлю в код проверку (просто с выбросом исключения) что не пришла какая-то другая буква кроме вышеупомянутых, потому что по хорошему так и надо - а это ведь тоже затраты.
Такие проверки занимают константное время - O(1). Они не играют роли на больших данных, когда сам алгоритм может стремительно замедляться, даже в десятки и сотни раз.
Однажды, я провалил собес в финтех из-за этого. Не смог оптимизировать свой, уже написанный на hackerrank алгоритм, что бы работал заметно быстрее. Хотя, те с кем было собеседование настойчиво просили меня подумать и придумать лучшее решение.
По моему мнению, leetcode тут ведёт себя вполне адекватно. Если вы поймёте тему сложности алгоритмов - сможете решать такие проблемы.
С другой стороны. Глюки с замерами времени выполнения там тоже есть. Даже для С++ кода. Два одинаковых сабмита могут иметь разницу около 20%.
Но в задаче не дана строка вообще. В задаче нужно подсчитать количество "хороших" строк заданной длины. Так что эти проверки вообще не могут быть в решении. Можно, конечно, проверить, что 1 <= n < = 100000, но эти два сравнения ни на что не повлияют.
Да, в данном случае вы правы абсолютно. Но, можно ведь другие задачи рассмотреть. Вот, например: https://leetcode.com/problems/longest-palindromic-substring/ - "s consist of only digits and English letters." - нужна ли проверка? Бог его знает: если совсем "по-правильному", то да. А это уже плюс O(n) к сложности.
Ну, в теории, эти задачи симулируют отдельные компоненты в программе. Допустим, проверку валидности строки может сделать другой компонент. Обычно в тестах ошибок нет и проверки все выполнять не надо.
А так, пример плохой. В этой задаче отдельные O(n) погоды особо не сделают. Там есть линейный алгоритм, но он далек от совсем тривиального, и его можно сильнее замедлить, просто неудачно пустив циклы или не там условный переход вставить, сломав какие-то оптимизации в CPU. Так что ваше решение с проверками может оказаться быстрее многих решений без проверок. Ну и главное, алгоритму вообще-то на то, что там только символы алфавита и цифры - пофигу. Он сработает, даже если там любой символ ASCII. Тут можно не проверять.
А так, пример плохой. В этой задаче отдельные O(n) погоды особо не сделают. Там есть линейный алгоритм, но он далек от совсем тривиального
По-моему, линейный алгоритм не так уж и сложно придумать. Что типа такого. Будем решать более общую задачу. Для строки искать три палиндрома - самый длинный вообще, самый длинный из тех которые начинаются с первого символа ("упираются" в левый край строки) и самый длинный из тех которые заканчиваются последним символом (то же что и предыдущий, только наоборот). Назовём их условно #0, #1, #2. В принципе, два из них, а то и все три могут и совпадать. Для того чтобы решить эту (обобщенную) задачу для строки длиной n мы поделим её пополам и решим её для каждой половины. Теперь получаем следующие варианты решения это #0 из левой половины, #0 из правой половины, #2 из левой половины дополненный слева и справа символами до тех пор пока будет все еще оставаться палиндромом, #1 из правой половины, тоже дополненный символами, и еще один вариант - это палиндром который расположен точно симметрично относительно середины строки (если такой есть). Из этих вариантов выбираем самый длинный. Сложность линейная (приводить доказательство тут для краткости не буду).
Не совсем понятно, как этот алгоритм работает. Как вы вычисляете палиндром №1 за линию? Он же может проходить через обе половинки. И при этом не совпадать центром вообще ни с одним более мелким палиндромом. Например, "zaababaaxx" - тут есть "aababaa", но он никак не получается из ответов для половинок дополнением символами с конца ("z", "aba, "aba" и "b", "aa", "xx")
И вообще, у вас тут O(n log n) получается. Рекуррентная формула для времени работы T(n) = 2T(n/2) + O(n). По мастер теореме о рекуррентных соотношениях, там получается O(n log n). Ну, или можно на глаз это определить: там будет log n уровней, и каждый из них суммарно будет O(n).
А настоящий линейный алгоритм основан на том, что вы считаете для каждого символа длину максимального палиндрома с центром в нем (для нечетных подстрок, для четных отдельно повторяем по аналогии). Считаете слева направо и используете факт, что если текущий центр лежит в каком-то уже известном ранее палиндроме, то вы можете переиспользовать вычисления для центра, симметричного в данном полиндроме. Ведь локально эти центры одинаковы - они же в палиндроме.
По мастер теореме о рекуррентных соотношениях,
Стоп, да, вот тут я ошибся, действительно. Даю заднюю - все-таки не линейный. И, еще, впрочем, да, походу кривой у меня и сам алгоритм . По ссылке посмотрю - коль уж есть готовое решение, которое еще даже и назвали в честь кого-то, мне в этой теме делать все равно нечего. У меня просто схожий подход сработал нормально на "соседней" задаче поиска самой длинной строки с уникальными символами, вот я как бы на этот "золотой молот" и попался :))
Кажется, вы не совсем правильно понимаете сложность алгоритма по O-нотации. O-нотация отражает не реальную вычислительную сложность, а асимптотическую, то есть показывает, как алгоритм ведет себя при разных объемах входных данных. В вашем случае, вы имеете дело с совершенно разными алгоритмами, хоть они и имеют линейную сложность O(n), т.е. время их выполнения линейно зависит от количества данных, но ресурсы затрачиваемые на одну операцию не равны. Эти алгоритмы могут существенно различаться в реализации, и их фактическое время выполнения может быть разным, даже если их асимптотическая сложность одинакова.
Возможно, я понимаю эту нотацию как-то по-другому, согласен. В моем представлении если сложность у алгоритмов одинаковая, то скорость их выполнения не будет отличаться на порядок. Ну то есть я ожидаю увидеть время выполнения, скажем, 3 секунды и 10 секунд, но никак не 30. Это меня и озадачило.
Хм, согласен. Получается при определенных ограничениях на входные данные можно написать алгоритм со сложностью O(n^2), который работал бы быстрее алгоритма со сложностью O(n) при достаточно большой константе c?
А по поводу определять сложность алгоритма за несколько прогонов. Наверное, так можно было бы попробовать сделать. Не знаю насколько это было бы точно и эффективно. Может так уже сделано где-то, но я везде (Yandex cup, Leetcode, codeforces) видел именно такой способ оценки алгоритма.
Time Limit нужен прежде всего для того, чтобы отловить случаи вроде бесконечного цикла в решении. Для конкретной задачи его просто подстраивают до значения, на котором решение успевает отработать на тестовых данных.
Кто-то писал в комментариях к статье про литкод, что входные данные подбирают так, чтобы использовав квадратичный алгоритм вместо линейного вы уперлись в лимит независимо от примененных оптимизаций, однако у меня был случай, когда решение, упавшее с time limit exceeded, было принято без изменений на второй попытке.
Почему топорна? Очень жизненна. В реальной жизни заказчика интересует именно time limit, а не асимптотическая сложность.
Я не отношусь к ценителям литкода, но здесь как раз всё верно придумано.
Программирование это не только знание алгоритмов, но и понимание стоимости абстракций используемого языка программирования, а иногда и нюансов аппаратной и программной среды исполнения.
Если задача не решается за отведённое время, то её решение неудовлетворительно, даже если асимптотическая сложность соответствует заданной.
то сложность по выполнению у них одинаковая O(n)
У вас операции в map за логарифм, поэтому O(nlogn).
Да, я это потом понял, что у обычной мапы в C++ вставка за логарифм выполняет. Тем не менее можно поменять на unordered_map и будет за константу
У меня подозрение, что задачу, на самом деле, можно свести к возведению в степень n какой-то матрицы, т.е. решить её вообще за O(log(n)) - детали пока что не продумывал.
Вот, типа, мой вариант решения (без кода, потому что я мудрая сова и занимаюсь только стратегией).
Если мы возьмем все строки длины 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 умножаем результат сам на себя и на исходную матрицу). Все операции упрощаются еще тем, что результат нам нужен "по модулю чего-то там", а, так как множество чисел "по модулю" (т.е. "множество вычетов") это "кольцо" по отношению к операциям сложения и умножения, то мы сразу можем просто все текущие операции производить по модулю этого числа.
В вашем случае всё-таки дело в сложности алгоритма.
Ваша первая версия: O(n * log(n)) - сложность, O(n) - память
Ваш финальный вариант: O(n) - сложность, О(n) - память
Можно заметно лучше:
(hint: динамическое программирование): O(n) - сложность, O(1) - память
(hint: динамическое программирование + возведение в степень за log(n)): O(log(n)) - сложность, O(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) в константной памяти
Сел, подумал. Накидал код на Си. 17мс. Причесал код. 2мс.
checkRecord() вызывает FillBuf(), которая единожды и линейно заполняет буфер числа хороших вариантов без учёта прогулов (приведение по модулю после сложения делается вычитанием).
checkRecord() остаётся в цикле перемножить значения для расчёта вариантов с учётом одного прогула (приведение по модулю после умножения делается делением).
"Отсутствие" считается "опозданием"? Т.е. последовательность "LAL" содержит 3 опоздания подряд?
Это проблема литкода и плохие тесты. Так-то не очень сложно выставить такой тайм-лимит и такие тесты, чтобы почти любое линейное решение проходило, а O(N log N) уже нет.
Это усугубляется тем, что там в C++ включены все возможные проверки и какие-то санитайзеры, и код на C++ чуть ли не медленнее аналогичного кода на других языках. А тайм лимит, похоже, один на задачу и все.
Иногда там наоборот, такие завышенные лимиты, что проходит даже сильно "неправильное" решение.
А так, да, используя "микро-оптимизации", не влияющие на сложность, можно ускорить программу в несколько раз. Но вы таким образом плохой алгоритм никогда не вгоните в тайм-лимит.
P.S. А вообще, в этой задаче есть решение за O(log n), через возведение матрицы в степень при пересчете следующей "строки" ДП из предыдущей (все значения при n зависят линейно от значений при n-1).
Time Limit Exceeded это не только про сложность алгоритма