Принудительный выход из рекурсии в случае, если ответ уже найден - Алгоритмы

Здравствуйте, Lazytech, Вы писали:

L>Простенькая задача: Merged String Checker | Codewars
L>[Мое решение на JavaScript]

Немного оффтопик, но ты говоришь, что это решение принялось как верное?

Тогда вот совет: если хочешь научится решать подобные околоалгоритмические задачи, то забей на этот сайт.
И в предыдущих темах со ссылками на codewars я видел откровенно слабые проверки, через которые легко проходят плохие решения. Может это, конечно, ты так специфически эти задачи выбираешь, но закономерность всё равно должна настораживать.

В чём тут проблема в твоём решение: оно имеет экспоненциальное время работы. То есть для входных строк длины N может работать за время Ω(2^N) (aka вечность).

	пример таких входных данных
	`s = ("a" * 2 * N) + "uv" # 2N символов "a" за которыми следует "uv" part1 = ("a" * N) + "x" part2 = ("a" * N) + "y"` При скромных N == 100 уже будет невозможно дождаться ответа

Но поинт не в том, что решение плохое (в конце концов, это можно и нетрудно исправить), а в том, что проверяющая система этого не обнаружила.
То есть система говорит что ты молодец, а на самом деле она так говорит потому что даже не потрудилась проверит решение

Из-за этого трудно учится: как можно понять куда двигаться, если нет нормальной обратной связи?

Поэтому для обучения лучше взять задачи, тесты и систему проверки, которые хотя бы как-то проверялись (да, при составлении тестов нужно их тоже проверять, что они обеспечивают адекватное покрытие), например с мероприятий icpc и родственных.
Для начала можно выбрать любой сайт из этого списка. Да, везде есть вероятность, что какое-то решение "обманет" систему проверки, которая пропустит какой-то хитрый частный случай, на котором решение на самом деле сбоит. Но прямо такой халтуры на этих системах проверки быть не должно.

Здравствуйте, Lazytech, Вы писали:

L>Что скажете, имеет ли такой подход с превентивным выходом из рекурсии право на существование? Оговорюсь, что вышеприведенный лог относится к единственному подвернувшемуся мне тестовому случаю, в котором этот подход мог быть мало-мальски полезен. Вполне возможно, что я чего-то недопонимаю...

Если понадобится "резко" завершить рекурсивные вызовы — такой подход норм.

Но, думаю, такая необходимость встречается редко. Если проблема появилась, скорее всего неверно спроектирована функция рекурсии.

Питон (без флагов остановки)

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:])

Здравствуйте, Lazytech, Вы писали:

L>Единственный более-менее линейный вариант, который мне удалось найти, — это стек.

Решение со стеком не линейное — оно O(N^2)
Обрабатываются все пары i, j (возможные сочетания индексов двух строк)

Здравствуйте, Lazytech, Вы писали:

SVZ>>Но в любом случае мне кажется рекурсия тут лишняя.

L>Лишняя из-за слишком высокой time complexity? Или есть другие причины не использовать рекурсию? Я уже видел решения на основе DP и стека. И те, и другие заметно сложнее рекурсивных, не говоря уже о меньшей интуитивности.

Рекурсия не добавляет Time complexity.

Она хороша в случае, когда каждый элемент массива рассматривается независимо, в отрыве от массива в целом. Либо когда надо свести задачу к предыдущей.
А когда надо рассматривать элемент в комплекте с соседями (например, следующий и предыдущий элементы), то рекурсия создаёт проблемы.

ЗЫ. Кстати, сказанное относится и к паттерну "визитёр".

Здравствуйте, Pzz, Вы писали:

Pzz>Если обе подходят, откусываем от обеих, и считаем, сколько раз мы откусили от обеих. Когда доходим до того места, когда начинает подходить только одна, откусываем от нее, а другую проматываем назад на столько, сколько мы насчитали, пока откусывали от обеих.

Похоже, снова не верно

Вот такой контрпример:
 s = **a*
s1 = *a
s2 = **

Откусываем от обоих:
 s = *a*
s1 = a
s2 = *
(держим в уме откусанную от обоих *)

Теперь только s2 подходит, откусываем ее, s1 проматываем назад
 s = a*
s1 = *a
s2 =

FAIL

P.S. Гадания без пройденных тестов больше не принимаются

Здравствуйте, Lazytech, Вы писали:

L>Опять я со своими нескончаемыми дилетантскими вопросами...

Увидел видео и сразу подумал о тебе:

	Видео

Если функцию 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)

Есть забавный способ принудительного выхода из рекурсии — кинуть исключение с результатом.

Здравствуйте, Lazytech, Вы писали:

L>В моем понимании классическое динамическое программирование — это такой подход, когда в простейшем случае решение можно получить, последовательно заполняя таблицу. По крайней мере, такое мнение мне где-то попадалось.

Так все они заполняют таблицу, но:
1. Во-первых, таблицу можно заполнять не полностью, а только те клетки, которые нужны.
2. Во-вторых, не обязательно хранить всю таблицу, достаточно только какие-то последние клетки, необходимые для дальнейших расчетов.
3. В-третьих, не обязательно заполнять таблицу по-порядку.

За счет первого и третьего пункта достигается линейность на простых строках. За счет второго достигается экономия памяти.

Алгоритм со стеком использует все три пункта.
— рассматривает только те варианты, в которые смогли попасть
— удаляет из стека варианты, которые уже были обработаны
— порядок заполнения таблицы определяется верхушкой стека

Алгоритм с рекурсия+мемоизацией
— не использует второй пункт, т.к. хранит в кэше даже те клетки, которые не нужны.
— но при этом использует первый и третий пункт

Твой алгоритм DP не использует ни одного пункта, поэтому он никогда не будет линейным, но максимум будет ограничен размером таблицы — O(M*N), как по времени, так и по памяти.

P.S. Может у меня слишком общий взгляд на динамическое программирование, но я все же считаю это DP

Здравствуйте, Lazytech, Вы писали:

M>>Всё равно же переменная локальная, она внешняя только для лямбды. Имхо корявенько как-то, но не ужас-ужас

L>Помню, в какой-то видеолекции какой-то профессор сказал студентам, что так делать нехорошо, и что такие решения не будут зачтены.

Мало ли, что там профессора разные говорят. Вон, у нас Лаптев тоже частенько заговаривается

M>>Да, согласен, не слишком долго думал. Но, думаю, линейный вариант можно сделать. Хотя, конечно, рекурсию налабать обычно проще

L>Единственный более-менее линейный вариант, который мне удалось найти, — это стек.

Да.
Но. Был бы я Лаптевым, я бы своих студней заставлял бы каждую рекурсию переписывать на линейную версию с явным стеком. На плюсиках это просто:

#include <stack>
//...
    std:"stack<State> stateStack;
//...

На ЖиСкрипте — хз, может и тяжело

Ещё явный стек даёт понятие об автоматах с памятью, что полезно. А рекурсия — хренак-хренак и в продакшн. Тоже гут, но не при обучении. Но ты же учишься?

Здравствуйте, watchmaker, Вы писали:

W>Для начала можно выбрать любой сайт из этого списка. Да, везде есть вероятность, что какое-то решение "обманет" систему проверки, которая пропустит какой-то хитрый частный случай, на котором решение на самом деле сбоит. Но прямо такой халтуры на этих системах проверки быть не должно.

Направление верное, но совет скорее вредительский. Во-первых, про сайты по линке, ткнул наугад в 3 из них — все 3 отваливаются по таймауту. Во-вторых, давайте предположим, что какой-то заработает... и человек решающий относительно простые задачи столкнется с на голову более высоким уровнем задач и куда как менее дружелюбным интерфейсом системы студенческой олимпиады.

Я не знаю что там с системой проверки на Codewars, но и на LeetCode и на HackerRank тесты отлавливают квадратичную и выше сложность решения для случаев где её быть не должно, может тоже не всегда, конечно. Так что да, сайт с задачами может и стоит сменить, но лучше не мудрить, а пойти по проторенной дороге, которую 99% разработчиков устраивающихся в компании с агрессивной сортировкой гномиков используют

Здравствуйте, Lazytech, Вы писали:

L>Так DP тоже неэкспоненциальный. А вариант со стеком хотя бы при поверхностном ознакомлении напоминает линейный.

Почему ты их разделяешь? Решение со стеком это и есть DP. И рекурсия с мемоизацией тоже DP.
В общем случае их сложность O(M*N), т.е. O(N^2)

А линейность появляется только на простых строках (когда очевиден выбор, от какой подстроки откусывать).
Но на таких строках даже наивная рекурсия дает линейность, хотя сама экспоненциальная

Здравствуйте, kov_serg, Вы писали:

_>А зачем понадобилась рекурсия?

А как иначе решать такие задачи? Из альтернативных подходов могу назвать только лишь динамическое программирование, но рекурсивное решение в данном случае вроде проще.

Здравствуйте, Lazytech, Вы писали:

_>>А зачем понадобилась рекурсия?

L>А как иначе решать такие задачи? Из альтернативных подходов могу назвать только лишь динамическое программирование, но рекурсивное решение в данном случае вроде проще.

На первый взгляд задача очень похожа на сортировку слиянием — два линейных прохода по двум массивам.

Здравствуйте, Pzz, Вы писали:

Pzz>Идешь по выходной строке по символам, по порядку, и смотришь, если очередной символ является началом строки s1, откусываешь его от начала строки s1, если началом строки s2, то откусываешь от начала строки s2, а иначе выходишь из цикла.

А если буквы одинаковые в s1 и s2, то какую из строк откусывать?

Здравствуйте, Pzz, Вы писали:

Pzz>Вроде как не важно, но математическое доказательство изобретать лениво

Важно.

Пример:

s = aman
s1 = am
s2 = an

Если откусишь s2 вместо s1, то ошибешься

Здравствуйте, Nuzhny, Вы писали:

N>

Увидел это видео, и сразу подумал об этом:

	Скрытый текст
	https://www.youtube.com/watch?v=8DKaXwCSgow

L>Я вообще не то, чтобы знаю много подходов к решению задач.

Я тоже

Опять я со своими нескончаемыми дилетантскими вопросами...

Простенькая задача: Merged String Checker | Codewars

Мое решение на JavaScript

function isMerge(s, part1, part2) {
  if (s.length !== part1.length + part2.length) {
    return false;    
  }
  
  const last = s.length - 1;
  let mergeConfirmed = false;
  
  const tryMerge = (pos1=0, pos2=0) => {
    if (mergeConfirmed) {
      return;
    }
    
    const pos = pos1 + pos2;
    
    if (pos > last) {
      mergeConfirmed = true;
      return;
    }

    if (part1[pos1] === s[pos]) {
      tryMerge(pos1 + 1, pos2);
    }

    if (part2[pos2] === s[pos]) {
      tryMerge(pos1, pos2 + 1);
    }
  }  
  
  tryMerge();
  return mergeConfirmed;
}

Обратите внимание на проверку в самом начале рекурсивной функции tryMerge:

    if (mergeConfirmed) {
      return;
    }

Наверное, любой бывалый программист скажет, что подобные фрагменты в подавляющем большинстве случаев лишь засоряют код (поправьте, если это не так). Однако, как мне кажется, в некоторых (редких?) случаях они могут быть полезны.

Немного модифицированное решение

function isMerge(s, part1, part2) {
  console.log("s =", s)
  console.log("part1 =", part1)
  console.log("part2 =", part2)
  
  if (s.length !== part1.length + part2.length) {
    return false;    
  }
  
  const last = s.length - 1;
  let mergeConfirmed = false;
  
  const tryMerge = (pos1=0, pos2=0) => {
    console.log("pos1, pos2, mergeConfirmed =", pos1, pos2, mergeConfirmed)
    
    if (mergeConfirmed) {
      // return;
      console.log("PREVENTIVE EXIT COULD BE HERE!")
    }
    
    const pos = pos1 + pos2;
    
    if (pos > last) {
      mergeConfirmed = true;
      return;
    }

    if (part1[pos1] === s[pos]) {
      tryMerge(pos1 + 1, pos2);
    }

    if (part2[pos2] === s[pos]) {
      tryMerge(pos1, pos2 + 1);
    }
  }  
  
  tryMerge();
  console.log("mergeConfirmed =", mergeConfirmed)
  
  return mergeConfirmed;
}

Один из логов модифицированного решения

s = <!qTG<<!qoi3ndI
part1 = <!qoi
part2 = <!qTG<3ndI
pos1, pos2, mergeConfirmed = 0 0 false
pos1, pos2, mergeConfirmed = 1 0 false
pos1, pos2, mergeConfirmed = 2 0 false
pos1, pos2, mergeConfirmed = 3 0 false
pos1, pos2, mergeConfirmed = 0 1 false
pos1, pos2, mergeConfirmed = 0 2 false
pos1, pos2, mergeConfirmed = 0 3 false
pos1, pos2, mergeConfirmed = 0 4 false
pos1, pos2, mergeConfirmed = 0 5 false
pos1, pos2, mergeConfirmed = 1 5 false
pos1, pos2, mergeConfirmed = 1 6 false
pos1, pos2, mergeConfirmed = 2 6 false
pos1, pos2, mergeConfirmed = 3 6 false
pos1, pos2, mergeConfirmed = 4 6 false
pos1, pos2, mergeConfirmed = 5 6 false
pos1, pos2, mergeConfirmed = 5 7 false
pos1, pos2, mergeConfirmed = 5 8 false
pos1, pos2, mergeConfirmed = 5 9 false
pos1, pos2, mergeConfirmed = 5 10 false
pos1, pos2, mergeConfirmed = 0 6 true
PREVENTIVE EXIT COULD BE HERE!
pos1, pos2, mergeConfirmed = 1 6 true
PREVENTIVE EXIT COULD BE HERE!
pos1, pos2, mergeConfirmed = 2 6 true
PREVENTIVE EXIT COULD BE HERE!
pos1, pos2, mergeConfirmed = 3 6 true
PREVENTIVE EXIT COULD BE HERE!
pos1, pos2, mergeConfirmed = 4 6 true
PREVENTIVE EXIT COULD BE HERE!
pos1, pos2, mergeConfirmed = 5 6 true
PREVENTIVE EXIT COULD BE HERE!
pos1, pos2, mergeConfirmed = 5 7 true
PREVENTIVE EXIT COULD BE HERE!
pos1, pos2, mergeConfirmed = 5 8 true
PREVENTIVE EXIT COULD BE HERE!
pos1, pos2, mergeConfirmed = 5 9 true
PREVENTIVE EXIT COULD BE HERE!
pos1, pos2, mergeConfirmed = 5 10 true
PREVENTIVE EXIT COULD BE HERE!
mergeConfirmed = true

Что скажете, имеет ли такой подход с превентивным выходом из рекурсии право на существование? Оговорюсь, что вышеприведенный лог относится к единственному подвернувшемуся мне тестовому случаю, в котором этот подход мог быть мало-мальски полезен. Вполне возможно, что я чего-то недопонимаю...

Здравствуйте, Lazytech, Вы писали:

L>Вполне возможно, что я чего-то недопонимаю...
А зачем понадобилась рекурсия?

Здравствуйте, Stanislav V. Zudin, Вы писали:

SVZ>На первый взгляд задача очень похожа на сортировку слиянием — два линейных прохода по двум массивам.

Сначала я примерно так и сделал, только вот это решение заваливало некоторые тестовые случаи. Проблема в том, что между part1 и part2 возможны «ложные перекрытия» (см. пример ниже).

Еще один лог модифицированного решения

s = Bananas from Bahamas
part1 = Bahas
part2 = Bananas from am
pos1, pos2, mergeConfirmed = 0 0 false
pos1, pos2, mergeConfirmed = 1 0 false
pos1, pos2, mergeConfirmed = 2 0 false
pos1, pos2, mergeConfirmed = 0 1 false
pos1, pos2, mergeConfirmed = 0 2 false
pos1, pos2, mergeConfirmed = 0 3 false
pos1, pos2, mergeConfirmed = 0 4 false
pos1, pos2, mergeConfirmed = 0 5 false
pos1, pos2, mergeConfirmed = 0 6 false
pos1, pos2, mergeConfirmed = 0 7 false
pos1, pos2, mergeConfirmed = 0 8 false
pos1, pos2, mergeConfirmed = 0 9 false
pos1, pos2, mergeConfirmed = 0 10 false
pos1, pos2, mergeConfirmed = 0 11 false
pos1, pos2, mergeConfirmed = 0 12 false
pos1, pos2, mergeConfirmed = 0 13 false
pos1, pos2, mergeConfirmed = 1 13 false
pos1, pos2, mergeConfirmed = 2 13 false
pos1, pos2, mergeConfirmed = 3 13 false
pos1, pos2, mergeConfirmed = 4 13 false
pos1, pos2, mergeConfirmed = 3 14 false
pos1, pos2, mergeConfirmed = 3 15 false
pos1, pos2, mergeConfirmed = 4 15 false
pos1, pos2, mergeConfirmed = 5 15 false
pos1, pos2, mergeConfirmed = 1 14 true
PREVENTIVE EXIT COULD BE HERE!
mergeConfirmed = true

P.S. Если я правильно понял, имелось в виду нечто вроде этого:

Не вполне рабочее решение

function isMerge(s, part1, part2) {
  if (s.length !== part1.length + part2.length) {
    return false;    
  }

  const len = s.length;
  let pos1 = 0,
      pos2 = 0;
      
  for (let i = 0; i < len; i++) {
    if (part1[pos1] === s[i]) {
      pos1++;
    } else if (part2[pos2] === s[i]) {
      pos2++
    } else {
      return false;
    }
  }
  
  return true;
}

Такое решение заваливает некоторые тесты по вышеуказанной причине. Если я что-то сделал не так, прошу указать на ошибку.

P.P.S. Нашел еще один подход, в котором используется стек:
https://stackoverflow.com/questions/49960458/codewars-merged-string-checker

Здравствуйте, Lazytech, Вы писали:

L>Наверное, любой бывалый программист скажет, что подобные фрагменты в подавляющем большинстве случаев лишь засоряют код (поправьте, если это не так). Однако, как мне кажется, в некоторых (редких?) случаях они могут быть полезны.

Там не нужна рекурсия.

Идешь по выходной строке по символам, по порядку, и смотришь, если очередной символ является началом строки s1, откусываешь его от начала строки s1, если началом строки s2, то откусываешь от начала строки s2, а иначе выходишь из цикла.

Если дошел на выходе из цикла ты дошел до конца выходной строки и полностью сожрал обе входные, то ответ "да", иначе — "нет".

Здравствуйте, Буравчик, Вы писали:

Pzz>>Идешь по выходной строке по символам, по порядку, и смотришь, если очередной символ является началом строки s1, откусываешь его от начала строки s1, если началом строки s2, то откусываешь от начала строки s2, а иначе выходишь из цикла.

Б>А если буквы одинаковые в s1 и s2, то какую из строк откусывать?

Вроде как не важно, но математическое доказательство изобретать лениво

Здравствуйте, Буравчик, Вы писали:

Pzz>>Вроде как не важно, но математическое доказательство изобретать лениво

Б>Важно.

Да, пожалуй. Но все равно должен быть линейный, от суммы длинн, алгоритм. Это ж сводится к регулярному автомату, причем построение такого автомата тоже должно быть несложным.

Здравствуйте, Буравчик, Вы писали:

Б>Если откусишь s2 вместо s1, то ошибешься

ОК, тогда вот так.

Если обе подходят, откусываем от обеих, и считаем, сколько раз мы откусили от обеих. Когда доходим до того места, когда начинает подходить только одна, откусываем от нее, а другую проматываем назад на столько, сколько мы насчитали, пока откусывали от обеих.

Здравствуйте, Pzz, Вы писали:

Pzz>Там не нужна рекурсия.
Pzz>Идешь по выходной строке по символам, по порядку, и смотришь, если очередной символ является началом строки s1, откусываешь его от начала строки s1, если началом строки s2, то откусываешь от начала строки s2, а иначе выходишь из цикла.
Pzz>Если дошел на выходе из цикла ты дошел до конца выходной строки и полностью сожрал обе входные, то ответ "да", иначе — "нет".

Выше я привел примерно такое решение (без откусывания строки, но смысл тот же). Также повторяю тестовый случай, который будет завален из-за «ложного перекрытия»:

s = Bananas from Bahamas
part1 = Bahas
part2 = Bananas from am

Здравствуйте, Lazytech, Вы писали:

L>Что скажете, имеет ли такой подход с превентивным выходом из рекурсии право на существование?

Да может, почему нет.

Но вот я не понял, зачем так сложно? Насколько я понимаю, должно хватить цикла по merged строке, и проверкой каждого символа на нахождение в начале одной из проверяемых строк (если найден, то указатель/индекс по той строке увеличиваем).

Здравствуйте, Stanislav V. Zudin, Вы писали:

_>>>А зачем понадобилась рекурсия?

L>>А как иначе решать такие задачи? Из альтернативных подходов могу назвать только лишь динамическое программирование, но рекурсивное решение в данном случае вроде проще.

SVZ>На первый взгляд задача очень похожа на сортировку слиянием — два линейных прохода по двум массивам.

Почему два и два?

Здравствуйте, Marty, Вы писали:

L>>Что скажете, имеет ли такой подход с превентивным выходом из рекурсии право на существование?
M>Да может, почему нет.

Я подозревал, что в данном случае модификация внешней переменной вместо явного возврата результата — это bad practice. Похоже, так и есть.

M>Но вот я не понял, зачем так сложно? Насколько я понимаю, должно хватить цикла по merged строке, и проверкой каждого символа на нахождение в начале одной из проверяемых строк (если найден, то указатель/индекс по той строке увеличиваем).

Выше объяснили, почему такой подход не работает.

Здравствуйте, Marty, Вы писали:

SVZ>>На первый взгляд задача очень похожа на сортировку слиянием — два линейных прохода по двум массивам.

M>Почему два и два?

Неточно выразился. Ессно, имелось в виду одновременно обойти два массива.
Но коллеги уже предложили контрпримеры, на котором это работать не будет.

Можно попробовать применить жадный алгоритм — при совпадении символов выбирать самую длинную последовательность, а не единственный символ. Этот вариант надо проверять.
Но в любом случае мне кажется рекурсия тут лишняя.

Здравствуйте, Lazytech, Вы писали:

L>>>Что скажете, имеет ли такой подход с превентивным выходом из рекурсии право на существование?
M>>Да может, почему нет.

L>Я подозревал, что в данном случае модификация внешней переменной вместо явного возврата результата — это bad practice. Похоже, так и есть.

Всё равно же переменная локальная, она внешняя только для лямбды. Имхо корявенько как-то, но не ужас-ужас

M>>Но вот я не понял, зачем так сложно? Насколько я понимаю, должно хватить цикла по merged строке, и проверкой каждого символа на нахождение в начале одной из проверяемых строк (если найден, то указатель/индекс по той строке увеличиваем).

L>Выше объяснили, почему такой подход не работает.

Да, согласен, не слишком долго думал. Но, думаю, линейный вариант можно сделать. Хотя, конечно, рекурсию налабать обычно проще

Здравствуйте, Stanislav V. Zudin, Вы писали:

SVZ>>>На первый взгляд задача очень похожа на сортировку слиянием — два линейных прохода по двум массивам.

M>>Почему два и два?

SVZ>Неточно выразился. Ессно, имелось в виду одновременно обойти два массива.

Ну, я бы сказал: а) обойти один массив — полную строку (кандидатов не учитываем), либо б) обойти три массива — полная строка и два кандидата

SVZ>Но коллеги уже предложили контрпримеры, на котором это работать не будет.

SVZ>Можно попробовать применить жадный алгоритм — при совпадении символов выбирать самую длинную последовательность, а не единственный символ. Этот вариант надо проверять.
SVZ>Но в любом случае мне кажется рекурсия тут лишняя.

Да, я тоже лажанул на скорую руку. И да, имхо рекурсия не нужна. Но с ней часто проще что-то налабать — вместо явного стека использовать неявный

Здравствуйте, Marty, Вы писали:

M>Всё равно же переменная локальная, она внешняя только для лямбды. Имхо корявенько как-то, но не ужас-ужас

Помню, в какой-то видеолекции какой-то профессор сказал студентам, что так делать нехорошо, и что такие решения не будут зачтены.

M>Да, согласен, не слишком долго думал. Но, думаю, линейный вариант можно сделать. Хотя, конечно, рекурсию налабать обычно проще

Единственный более-менее линейный вариант, который мне удалось найти, — это стек.

Здравствуйте, Stanislav V. Zudin, Вы писали:

SVZ>Но в любом случае мне кажется рекурсия тут лишняя.

Лишняя из-за слишком высокой time complexity? Или есть другие причины не использовать рекурсию? Я уже видел решения на основе DP и стека. И те, и другие заметно сложнее рекурсивных, не говоря уже о меньшей интуитивности.

Здравствуйте, Буравчик, Вы писали:

L>>Единственный более-менее линейный вариант, который мне удалось найти, — это стек.

Б>Решение со стеком не линейное — оно O(N^2)
Б>Обрабатываются все пары i, j (возможные сочетания индексов двух строк)

Вообще, лень думать, но, вероятно, ты прав.

А ты дотошный

Тебе бы тесты писать

Но если ты так пишешь тесты для своего кода, то снимаю шляпу.

Хотя, имхо, для своего кода писать тесты так же годно, как для чужого — я не знаю как. Ну, то есть, это возможно, но не уверен, что это эффективнее, чем разделение обязанностей по написанию кода и написанию тестов. Хз где как, а я за то, чтобы тесты для кода писали бы специально обученные люди, а не авторы кода

Здравствуйте, Marty, Вы писали:

M>Мало ли, что там профессора разные говорят. Вон, у нас Лаптев тоже частенько заговаривается

ЕМНИП, это была бесплатно выложенная лекция Массачусетского технологического института (MIT).

M>На ЖиСкрипте — хз, может и тяжело

Стек — он и в Африке стек. На JS, если не хочется заморачиваться, можно использовать в качестве стека обычный массив (Array). К сожалению, удаление первого элемента массива — достаточно дорогая операция, если элементов много, зато работает из коробки. (Это я с очередью перепутал. Не-не-не, использование массива в качестве стека вполне себе оптимально, ведь растет или урезается только хвост массива.)

M>Ещё явный стек даёт понятие об автоматах с памятью, что полезно. А рекурсия — хренак-хренак и в продакшн. Тоже гут, но не при обучении. Но ты же учишься?

Вот именно, в основном на своих ошибках.

Здравствуйте, Stanislav V. Zudin, Вы писали:

SVZ>Рекурсия не добавляет Time complexity.

Насколько я понял, у рекурсивного решения обсуждаемой в этой теме задачи временнАя сложность O(2^(m+n)), а у решения на основе динамического программирования — всего лишь O(m*n), где m и n — длины коротких строк, из частей которых, возможно, получается длинная строка.

Вот статья, после ознакомления с которой я сделал такой вывод:
Find if a string is interleaved of two other strings | DP-33 – GeeksforGeeks

Если что, мотороллер не мой.

Здравствуйте, vsb, Вы писали:

vsb>Есть забавный способ принудительного выхода из рекурсии — кинуть исключение с результатом.

Не-не-не, я не экстремал. Я всего лишь имел в виду добавление дополнительного условия.

Здравствуйте, watchmaker, Вы писали:

W>Немного оффтопик, но ты говоришь, что это решение принялось как верное?

Да, решение успешно прошло все тесты.

W>Тогда вот совет: если хочешь научится решать подобные околоалгоритмические задачи, то забей на этот сайт.
W>И в предыдущих темах со ссылками на codewars я видел откровенно слабые проверки, через которые легко проходят плохие решения. Может это, конечно, ты так специфически эти задачи выбираешь, но закономерность всё равно должна настораживать.

Такие задачи делают все, кому не лень, так что...

W>В чём тут проблема в твоём решение: оно имеет экспоненциальное время работы. То есть для входных строк длины N может работать за время Ω(2^N) (aka вечность).

Совершенно верно. Именно поэтому вчера я ознакомился с разъяснением работы алгоритма на основе DP, который выдает результат за время порядка O(m*n), где m и n — длины двух коротких строк.

W>Но поинт не в том, что решение плохое (в конце концов, это можно и нетрудно исправить), а в том, что проверяющая система этого не обнаружила.
W>То есть система говорит что ты молодец, а на самом деле она так говорит потому что даже не потрудилась проверит решение

W>Из-за этого трудно учится: как можно понять куда двигаться, если нет нормальной обратной связи?

Обратную связь я получаю, в частности, на этом форуме. Наверное, надоел уже со своими нескончаемыми задачами.

W>Поэтому для обучения лучше взять задачи, тесты и систему проверки, которые хотя бы как-то проверялись (да, при составлении тестов нужно их тоже проверять, что они обеспечивают адекватное покрытие), например с мероприятий icpc и родственных.
W>Для начала можно выбрать любой сайт из этого списка. Да, везде есть вероятность, что какое-то решение "обманет" систему проверки, которая пропустит какой-то хитрый частный случай, на котором решение на самом деле сбоит. Но прямо такой халтуры на этих системах проверки быть не должно.

Спасибо за совет. Возможно, когда-нибудь попробую ему последовать. Хотя на данном этапе мне надо бы научиться уверенно решать задачи уровня 1 кю или хотя бы 3 кю на Codewars...

Здравствуйте, Буравчик, Вы писали:

Б>Решение со стеком не линейное — оно O(N^2)
Б>Обрабатываются все пары i, j (возможные сочетания индексов двух строк)

Ну, пусть будет псевдолинейный вариант, потому что остальные совсем не линейные.

Здравствуйте, Буравчик, Вы писали:

Б>Если функцию is_merge закэшировать, то получим рекурсию + динамику.

Рекурсивный вариант с мемоизацией мне нравится больше, чем DP и стек, потому он проще и интуитивнее. А вообще, наверное, подходы с использованием DP и стека перспективнее, и их тоже неплохо бы освоить.

Здравствуйте, kaa.python, Вы писали:

KP>Направление верное, но совет скорее вредительский. Во-первых, про сайты по линке, ткнул наугад в 3 из них — все 3 отваливаются по таймауту. Во-вторых, давайте предположим, что какой-то заработает... и человек решающий относительно простые задачи столкнется с на голову более высоким уровнем задач и куда как менее дружелюбным интерфейсом системы студенческой олимпиады.

Не-не-не, я никаким боком не олимпиадник. Мне бы просто научиться решать алгоритмические задачи, пусть не всегда самым оптимальным способом.

KP>Я не знаю что там с системой проверки на Codewars, но и на LeetCode и на HackerRank тесты отлавливают квадратичную и выше сложность решения для случаев где её быть не должно, может тоже не всегда, конечно. Так что да, сайт с задачами может и стоит сменить, но лучше не мудрить, а пойти по проторенной дороге, которую 99% разработчиков устраивающихся в компании с агрессивной сортировкой гномиков используют

Смутно подозреваю, что и на Codewars можно найти кучу задач, в которых тесты не пропускают заведомо неоптимальные решения. Уровень задачи, обсуждаемой в этой теме, всего-то 5 кю (для сравнения, самым простым задачам обычно присваивается уровень 8 кю), так что...

Здравствуйте, Lazytech, Вы писали:

L>Ну, пусть будет псевдолинейный вариант, потому что остальные совсем не линейные.

Тогда уж неэкспоненциальный

Здравствуйте, Буравчик, Вы писали:

Б>Тогда уж неэкспоненциальный

Так DP тоже неэкспоненциальный. А вариант со стеком хотя бы при поверхностном ознакомлении напоминает линейный.

Здравствуйте, Буравчик, Вы писали:

Б>Почему ты их разделяешь? Решение со стеком это и есть DP. И рекурсия с мемоизацией тоже DP.

В моем понимании классическое динамическое программирование — это такой подход, когда в простейшем случае решение можно получить, последовательно заполняя таблицу. По крайней мере, такое мнение мне где-то попадалось.

Здравствуйте, vsb, Вы писали:

vsb>Есть забавный способ принудительного выхода из рекурсии — кинуть исключение с результатом.
А лучше развернуть рекурсию в цикл со стеком

... << RSDN@Home 1.3.110 alpha 5 rev. 62>>

Здравствуйте, CreatorCray, Вы писали:

vsb>>Есть забавный способ принудительного выхода из рекурсии — кинуть исключение с результатом.
CC>А лучше развернуть рекурсию в цикл со стеком

Оно-то всегда лучше, но не проще. По-хорошему все эти проблемы с маленькими стеками от несовершенства технологии и должны решаться на уровне компилятора/процессора, а не вручную программистом. Вроде в Go стек условно бесконечный (пока памяти хватает).

Здравствуйте, vsb, Вы писали:

vsb>Оно-то всегда лучше, но не проще.
Почему?
Вместо локальных переиенных на стеке — поля в структуре. Вместо рекурсивного вызова — push в свой стек а код в цикле работает со структурой что на самой вершине стека. Выход из рекурсивной фукнции — просто pop из стека.

vsb> По-хорошему все эти проблемы с маленькими стеками от несовершенства технологии и должны решаться на уровне компилятора/процессора
Нет.

vsb> а не вручную программистом. Вроде в Go стек условно бесконечный (пока памяти хватает).
Не в го в принципе можно сделать так же. Guard page нужна как раз для того, чтобы ловить вот таких вот зациклившихся рекурсивных.

... << RSDN@Home 1.3.110 alpha 5 rev. 62>>

	От:	watchmaker
	Дата:	21.11.20 19:06
	Оценка:	15 (1) +1 -1

	От:	Буравчик
	Дата:	20.11.20 17:36
	Оценка:	19 (2)

	От:	Буравчик
	Дата:	21.11.20 19:02
	Оценка:	5 (1) +1

	От:	Stanislav V. Zudin
	Дата:	21.11.20 19:19
	Оценка:	5 (1) +1

	От:	Буравчик
	Дата:	20.11.20 20:09
	Оценка:	+2

От:	Nuzhny	https://github.com/Nuzhny007
Дата:	13.02.21 07:47
Оценка:

От:	Marty	https://www.youtube.com/channel/UChp5PpQ6T4-93HbNF-8vSYg
Дата:	21.11.20 22:01
Оценка:	5 (1)

От:	kaa.python	РСДН профессионально мёртв и завален ватой.
Дата:	22.11.20 03:45
Оценка:	5 (1)

От:	Pzz	https://github.com/alexpevzner
Дата:	20.11.20 18:12
Оценка: