Здравствуйте, Marty, Вы писали:
M>Всё равно же переменная локальная, она внешняя только для лямбды. Имхо корявенько как-то, но не ужас-ужас
Помню, в какой-то видеолекции какой-то профессор сказал студентам, что так делать нехорошо, и что такие решения не будут зачтены.
M>Да, согласен, не слишком долго думал. Но, думаю, линейный вариант можно сделать. Хотя, конечно, рекурсию налабать обычно проще
Единственный более-менее линейный вариант, который мне удалось найти, — это стек.
Re[6]: Принудительный выход из рекурсии в случае, если ответ
Здравствуйте, Stanislav V. Zudin, Вы писали:
SVZ>Но в любом случае мне кажется рекурсия тут лишняя.
Лишняя из-за слишком высокой time complexity? Или есть другие причины не использовать рекурсию? Я уже видел решения на основе DP и стека. И те, и другие заметно сложнее рекурсивных, не говоря уже о меньшей интуитивности.
Если функцию is_merge закэшировать, то получим рекурсию + динамику.
Это гарантирует максимальное время работы за O(N^2) от длины строки
from functools import lru_cache@lru_cache()def is_merge(s, part1, part2):
if part1 == '':
return s == part2
if part2 == '':
return s == part1
if s == '':
return False
return s[0] == part1[0] and is_merge(s[1:], part1[1:], part2) \
or s[0] == part2[0] and is_merge(s[1:], part1, part2[1:])
Потребляемую память можно уменьшить, если оперировать индексами (позициями символов), а не целыми строками
ДОБАВЛЕНО:
Вообще, т.к. в кэш передаются полные строки (длины N), то полная сложность здесь будет O(N^3)
Но если работать с индексами, то получим обозначенные O(N^2)
Немного оффтопик, но ты говоришь, что это решение принялось как верное?
Тогда вот совет: если хочешь научится решать подобные околоалгоритмические задачи, то забей на этот сайт.
И в предыдущих темах со ссылками на codewars я видел откровенно слабые проверки, через которые легко проходят плохие решения. Может это, конечно, ты так специфически эти задачи выбираешь, но закономерность всё равно должна настораживать.
В чём тут проблема в твоём решение: оно имеет экспоненциальное время работы. То есть для входных строк длины N может работать за время Ω(2N) (aka вечность).
пример таких входных данных
s = ("a" * 2 * N) + "uv"# 2N символов "a" за которыми следует "uv"
part1 = ("a" * N) + "x"
part2 = ("a" * N) + "y"
При скромных N == 100 уже будет невозможно дождаться ответа
Но поинт не в том, что решение плохое (в конце концов, это можно и нетрудно исправить), а в том, что проверяющая система этого не обнаружила.
То есть система говорит что ты молодец, а на самом деле она так говорит потому что даже не потрудилась проверит решение
Из-за этого трудно учится: как можно понять куда двигаться, если нет нормальной обратной связи?
Поэтому для обучения лучше взять задачи, тесты и систему проверки, которые хотя бы как-то проверялись (да, при составлении тестов нужно их тоже проверять, что они обеспечивают адекватное покрытие), например с мероприятий icpc и родственных.
Для начала можно выбрать любой сайт из этого списка. Да, везде есть вероятность, что какое-то решение "обманет" систему проверки, которая пропустит какой-то хитрый частный случай, на котором решение на самом деле сбоит. Но прямо такой халтуры на этих системах проверки быть не должно.
Re[7]: Принудительный выход из рекурсии в случае, если ответ
Здравствуйте, Lazytech, Вы писали:
SVZ>>Но в любом случае мне кажется рекурсия тут лишняя.
L>Лишняя из-за слишком высокой time complexity? Или есть другие причины не использовать рекурсию? Я уже видел решения на основе DP и стека. И те, и другие заметно сложнее рекурсивных, не говоря уже о меньшей интуитивности.
Рекурсия не добавляет Time complexity.
Она хороша в случае, когда каждый элемент массива рассматривается независимо, в отрыве от массива в целом. Либо когда надо свести задачу к предыдущей.
А когда надо рассматривать элемент в комплекте с соседями (например, следующий и предыдущий элементы), то рекурсия создаёт проблемы.
ЗЫ. Кстати, сказанное относится и к паттерну "визитёр".
_____________________
С уважением,
Stanislav V. Zudin
Re: Принудительный выход из рекурсии в случае, если ответ уж
Здравствуйте, Lazytech, Вы писали:
M>>Всё равно же переменная локальная, она внешняя только для лямбды. Имхо корявенько как-то, но не ужас-ужас
L>Помню, в какой-то видеолекции какой-то профессор сказал студентам, что так делать нехорошо, и что такие решения не будут зачтены.
Мало ли, что там профессора разные говорят. Вон, у нас Лаптев тоже частенько заговаривается
M>>Да, согласен, не слишком долго думал. Но, думаю, линейный вариант можно сделать. Хотя, конечно, рекурсию налабать обычно проще
L>Единственный более-менее линейный вариант, который мне удалось найти, — это стек.
Да.
Но. Был бы я Лаптевым, я бы своих студней заставлял бы каждую рекурсию переписывать на линейную версию с явным стеком. На плюсиках это просто:
Ещё явный стек даёт понятие об автоматах с памятью, что полезно. А рекурсия — хренак-хренак и в продакшн. Тоже гут, но не при обучении. Но ты же учишься?
Здравствуйте, Буравчик, Вы писали:
L>>Единственный более-менее линейный вариант, который мне удалось найти, — это стек.
Б>Решение со стеком не линейное — оно O(N^2) Б>Обрабатываются все пары i, j (возможные сочетания индексов двух строк)
Вообще, лень думать, но, вероятно, ты прав.
А ты дотошный
Тебе бы тесты писать
Но если ты так пишешь тесты для своего кода, то снимаю шляпу.
Хотя, имхо, для своего кода писать тесты так же годно, как для чужого — я не знаю как. Ну, то есть, это возможно, но не уверен, что это эффективнее, чем разделение обязанностей по написанию кода и написанию тестов. Хз где как, а я за то, чтобы тесты для кода писали бы специально обученные люди, а не авторы кода
Здравствуйте, watchmaker, Вы писали:
W>Для начала можно выбрать любой сайт из этого списка. Да, везде есть вероятность, что какое-то решение "обманет" систему проверки, которая пропустит какой-то хитрый частный случай, на котором решение на самом деле сбоит. Но прямо такой халтуры на этих системах проверки быть не должно.
Направление верное, но совет скорее вредительский. Во-первых, про сайты по линке, ткнул наугад в 3 из них — все 3 отваливаются по таймауту. Во-вторых, давайте предположим, что какой-то заработает... и человек решающий относительно простые задачи столкнется с на голову более высоким уровнем задач и куда как менее дружелюбным интерфейсом системы студенческой олимпиады.
Я не знаю что там с системой проверки на Codewars, но и на LeetCode и на HackerRank тесты отлавливают квадратичную и выше сложность решения для случаев где её быть не должно, может тоже не всегда, конечно. Так что да, сайт с задачами может и стоит сменить, но лучше не мудрить, а пойти по проторенной дороге, которую 99% разработчиков устраивающихся в компании с агрессивной сортировкой гномиков используют
Re[6]: Принудительный выход из рекурсии в случае, если ответ
Здравствуйте, Marty, Вы писали:
M>Мало ли, что там профессора разные говорят. Вон, у нас Лаптев тоже частенько заговаривается
ЕМНИП, это была бесплатно выложенная лекция Массачусетского технологического института (MIT).
M>На ЖиСкрипте — хз, может и тяжело
Стек — он и в Африке стек. На JS, если не хочется заморачиваться, можно использовать в качестве стека обычный массив (Array). К сожалению, удаление первого элемента массива — достаточно дорогая операция, если элементов много, зато работает из коробки. (Это я с очередью перепутал. Не-не-не, использование массива в качестве стека вполне себе оптимально, ведь растет или урезается только хвост массива.)
M>Ещё явный стек даёт понятие об автоматах с памятью, что полезно. А рекурсия — хренак-хренак и в продакшн. Тоже гут, но не при обучении. Но ты же учишься?
Здравствуйте, Stanislav V. Zudin, Вы писали:
SVZ>Рекурсия не добавляет Time complexity.
Насколько я понял, у рекурсивного решения обсуждаемой в этой теме задачи временнАя сложность O(2(m+n)), а у решения на основе динамического программирования — всего лишь O(m*n), где m и n — длины коротких строк, из частей которых, возможно, получается длинная строка.
Здравствуйте, watchmaker, Вы писали:
W>Немного оффтопик, но ты говоришь, что это решение принялось как верное?
Да, решение успешно прошло все тесты.
W>Тогда вот совет: если хочешь научится решать подобные околоалгоритмические задачи, то забей на этот сайт. W>И в предыдущих темах со ссылками на codewars я видел откровенно слабые проверки, через которые легко проходят плохие решения. Может это, конечно, ты так специфически эти задачи выбираешь, но закономерность всё равно должна настораживать.
Такие задачи делают все, кому не лень, так что...
W>В чём тут проблема в твоём решение: оно имеет экспоненциальное время работы. То есть для входных строк длины N может работать за время Ω(2N) (aka вечность).
Совершенно верно. Именно поэтому вчера я ознакомился с разъяснением работы алгоритма на основе DP, который выдает результат за время порядка O(m*n), где m и n — длины двух коротких строк.
W>Но поинт не в том, что решение плохое (в конце концов, это можно и нетрудно исправить), а в том, что проверяющая система этого не обнаружила. W>То есть система говорит что ты молодец, а на самом деле она так говорит потому что даже не потрудилась проверит решение W>Из-за этого трудно учится: как можно понять куда двигаться, если нет нормальной обратной связи?
Обратную связь я получаю, в частности, на этом форуме. Наверное, надоел уже со своими нескончаемыми задачами.
W>Поэтому для обучения лучше взять задачи, тесты и систему проверки, которые хотя бы как-то проверялись (да, при составлении тестов нужно их тоже проверять, что они обеспечивают адекватное покрытие), например с мероприятий icpc и родственных. W>Для начала можно выбрать любой сайт из этого списка. Да, везде есть вероятность, что какое-то решение "обманет" систему проверки, которая пропустит какой-то хитрый частный случай, на котором решение на самом деле сбоит. Но прямо такой халтуры на этих системах проверки быть не должно.
Спасибо за совет. Возможно, когда-нибудь попробую ему последовать. Хотя на данном этапе мне надо бы научиться уверенно решать задачи уровня 1 кю или хотя бы 3 кю на Codewars...
Здравствуйте, Буравчик, Вы писали:
Б>Решение со стеком не линейное — оно O(N^2) Б>Обрабатываются все пары i, j (возможные сочетания индексов двух строк)
Ну, пусть будет псевдолинейный вариант, потому что остальные совсем не линейные.
Re[3]: Принудительный выход из рекурсии в случае, если ответ
Здравствуйте, Буравчик, Вы писали:
Б>Если функцию is_merge закэшировать, то получим рекурсию + динамику.
Рекурсивный вариант с мемоизацией мне нравится больше, чем DP и стек, потому он проще и интуитивнее. А вообще, наверное, подходы с использованием DP и стека перспективнее, и их тоже неплохо бы освоить.
Здравствуйте, kaa.python, Вы писали:
KP>Направление верное, но совет скорее вредительский. Во-первых, про сайты по линке, ткнул наугад в 3 из них — все 3 отваливаются по таймауту. Во-вторых, давайте предположим, что какой-то заработает... и человек решающий относительно простые задачи столкнется с на голову более высоким уровнем задач и куда как менее дружелюбным интерфейсом системы студенческой олимпиады.
Не-не-не, я никаким боком не олимпиадник. Мне бы просто научиться решать алгоритмические задачи, пусть не всегда самым оптимальным способом.
KP>Я не знаю что там с системой проверки на Codewars, но и на LeetCode и на HackerRank тесты отлавливают квадратичную и выше сложность решения для случаев где её быть не должно, может тоже не всегда, конечно. Так что да, сайт с задачами может и стоит сменить, но лучше не мудрить, а пойти по проторенной дороге, которую 99% разработчиков устраивающихся в компании с агрессивной сортировкой гномиков используют
Смутно подозреваю, что и на Codewars можно найти кучу задач, в которых тесты не пропускают заведомо неоптимальные решения. Уровень задачи, обсуждаемой в этой теме, всего-то 5 кю (для сравнения, самым простым задачам обычно присваивается уровень 8 кю), так что...
Re[7]: Принудительный выход из рекурсии в случае, если ответ уже найден
Здравствуйте, Lazytech, Вы писали:
L>Так DP тоже неэкспоненциальный. А вариант со стеком хотя бы при поверхностном ознакомлении напоминает линейный.
Почему ты их разделяешь? Решение со стеком это и есть DP. И рекурсия с мемоизацией тоже DP.
В общем случае их сложность O(M*N), т.е. O(N^2)
А линейность появляется только на простых строках (когда очевиден выбор, от какой подстроки откусывать).
Но на таких строках даже наивная рекурсия дает линейность, хотя сама экспоненциальная
