Хабр Курсы для бэкендеров
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Поток Бэкенд доступен 24/7 благодаря поддержке друзей Хабра
Комментарии 27
Пишите, что статья объясняет проще, но я считаю, что написана она не очень хорошо. Как обычно, тем, кто задачи решать умеет, ваша статья не нужна, тем кто не умеет - она не очень поможет.
Начнем с того, что надо дать определение окна. Почему оно sliding. Аналогию с хотя бы с двумя картонками. которыми закрывают часть массива слева и справа (ибо логарифмические линейки уже никто и не представляет себе).
Главный косяк - вы объясняете что, а не почему и как к этому прийти.
Вы начинаете объяснять решение с указателей, и говорите про дубликаты в окне, но к этому моменту еще не сказали, что вообще за окно такое.
Потом вы объясняете действия "без кода", но там ссылаетесь на какой-то map.
Как обычно в подобных статьях, вы в тексте описываете код, а не объясняете почему код именно такой.
Ну и никакого обобщения принципа вы не даете. Решение конкретно этой задачи по вашей статье еще можно выучить, но уже соседнюю задачу на такое же скользящее окно прочитавший вашу статью не решит.
Почему вообще в задаче на длиннейшую подстроку с каким-то свойством возникает окно? Потому что свойство "наследуемое" - если оно выполняется для какой-то строки, то и для всех в нее вложенных - тоже. Поэтому можно вообще все подстроки сгруппировать по, допустим, концу. Для каждого фиксированного конца в ответ идут строки с последовательными длинами с одного символа и до какой-то самой длинной строки. Эту самую длинную строку мы и ищем, потом среди всех различных концов остается взять максимум. Скользящее окно как раз и будет представлять собой эту самую наидлиннейшую подстроку с фиксированным концом.
Еще эту задачу можно решать с другого конца. Мне кажется, такое объяснение было бы понятнее. Начните с наивного решения с двумя вложенными циклами, где перебираете начало и потом конец, а внутри считаете циклом - есть ли дубликаты в подстроке с мапой. Это кубическое решение. Потом заметьте, что при удлинении строки можно пересчитать проверку дубликата просто обработав один новый символ, поэтому не надо для каждого конца гнать вложенный третий цикл, можно двумя циклами все обработать. Вот уже квадратичное решение. Потом заметьте, что при сдвиге начала в право на 1 позицию у вас ответ будет не короче ответа для предыдущей строки -1. Так что можно не двигать указатель конца циклом с самого начала, а сразу оставить там, где он и был. Вот и возникло окно и решение за линию. Вот и нарисовалось скользящее окно.
Часть замечаний действительно справедлива — например, про то, что можно было подробнее ввести само понятие окна и дать более явную аналогию. Это можно улучшить, и, возможно, я добавлю такой раздел в статью.
Однако цель материала была немного другой. Я не ставил задачу выводить технику sliding window через цепочку оптимизаций O(n³) → O(n²) → O(n). Такой подход действительно хорошо работает в учебных разборах алгоритмов, но он значительно увеличивает объем статьи и смещает фокус с самой техники на историю ее вывода.
В статье я сознательно пошел от практического применения: показать, как работает окно, как двигаются указатели и как поддерживается состояние структуры данных (map) внутри окна. Для читателей, которые уже встречали задачи на строки и два указателя, такой формат обычно оказывается более прямолинейным.
При этом идея «наследуемого свойства» подстрок, о которой вы пишете, действительно является одной из причин, почему sliding window вообще применим в подобных задачах. Это хорошее дополнение к теме, но оно выходит немного за рамки конкретного разбора задачи, который был основной целью статьи.
В любом случае спасибо за подробную обратную связь
Такой подход действительно хорошо работает в учебных разборах алгоритмов, но он значительно увеличивает объем статьи и смещает фокус с самой техники на историю ее вывода.
Я считаю что это и должно быть фокусом в статьях для начинающих. Иначе это как пытаться зубрить формулу решения системы линейных уравнений вместо объяснения что можно строки друг из друга вычитать и таким образом получить нули выше диагонали.
Ну вот в этой задаче читатель поймет как применять map. А в задаче, где надо найти наибольший подмассив с суммой не больше заданной, уже не факт что поймет, что вместо мапа нужна сумма. Не объясняя принципы на которых решение строится вы не даете читателю никакой возможности решение обобщать. Это можно было бы обойти разобрав сразу 3-5 задач, обратив внимание что там меняется от задачи к задаче.
Почему вообще в задаче на длиннейшую подстроку с каким-то свойством возникает окно? Потому что свойство "наследуемое" - если оно выполняется для какой-то строки, то и для всех в нее вложенных - тоже
Наследуемое оно в данной конкретной ситуации, но не в общем случае (например, "найти самую длинную подстроку, в которой К различных символов" - тоже окно), потому, имхо, лучше не упоминать.
Эта задача тождественна задаче найти "самую длинную подстроку, где не более K различных символов" (если в строке вообще есть хотя бы K различных символов). Ведь, если подстрока содержит меньше K символов, то ее можно расширить, прибавится максимум 1 новый символ и условие все еще выполнится.
А это свойство уже наследуемо.
То есть каждая задача с наибольшей подстрокой и окном сводится к "наследуемой"?
Я думаю да. В некоторых задачах, где свойство меняется не "непрерывно", а скачакми, и может перескочить искомое значение придется обработать частный случай - наидлиннейшее окно <= K штук может иметь <K штук и в ответ его брать не надо. Но суть остается такой же: за счет наследуемости можно сократить решение с O(n^2) до O(n).
А есть какой-то стандартный шаблон для sliding window, который позволяет для разных задач подставлять реализацию (как, например, с бинпоиском), или там слишком много разных вариаций? Ну, типа
left = 0
for right in range(n):
add(right)
while left <= right and not good(): remove(left++)
И, кстати, почему-то везде все итерируют по правому концу, и подбирают левый, хотя, кажется, итерировать по левому концу немного более естесственно?
Есть. Именно как у вас. Только в общем случае add и remove принимают еще и индекс элемента. Мало ли что там за метрика. Но, покуда метрика наследуема - если какое-то окно good(), то любой его подмассив тоже - это работает.
Можно итерировать и по другому концу. Но тут 2 варианта: если вы цикл с задом наперед гоните, то это фактически абсолютно тоже самое и будет, только на развернутом массиве. Если же вы двигаете в цикле left с 0 до n, и right подстраиваете, то там надо будет "заглядывать вперед". Вы увеличиваете right, если следующее окно будет хорошее. Или поддерживать инвариант, что right - это первый плохой элемент. Ну и появляется отдельный вариант, когда left обгоняет right.
right = 0
for left in range(n):
while right < n and (right <= left or good()): add(right)
// left..right-1 - answer?
remove(left)
Не велика разница, и то и другое выводится: фиксируем или конец или начало и двигаем другой максимально дальше. Потом переходим к следующему фиксированному концу и отодвигаем второй конец в ту же сторону, пока надо.
Кому-то один кажется интуитивнее, кому-то другой. Мне кажется исходный вариант чуть проще. Там на одну проверку меньше и код обработки окна и проверки ответа разделяется. Во втором варианте окно надо обрабатывать до проверки ответа и после.
А разве доступ к хэш-таблице занимает время О(1) ?
Именно так
?
В среднем, действительно, у хеш-таблицы доступ за O(1).
То есть, не зависит от размера таблицы?
Что-то я пропустил. Думал, лучший вариант - что-то типа O(log N)
Да, в среднем добавление, удаление и поиск в хеш таблице - O(1). В худшем случае O(N) вообще, но его считается практически невозможно подобрать в хороших реализациях.
То есть, не зависит от размера таблицы?
Как бы да. Вон в массиве доступ по индексу O(1). Тоже не зависит от размера. Именно на этом и строится хеш таблица.
Точно, я как раз про сравнение хеш-таблиц с массивами. Специально почитал, как это реализовано (я не фанат Go, только учусь))) под капотом, и гарантированной скорости доступа не нашёл.
Вообще, в этой задаче не нужны даже никакие хеш-мапы. Нужен лишь массив на 26 элементов - по одному для каждого символа.
Я про то же. В массиве же всё быстрее и гарантировано. Фишка алгоритма ведь в том, что изначальная скорость О(N²) разменивается на O(N) за счёт использования таблицы. Бесплатно ничего не бывает (c). Автор про это не заикнулся. Поэтому не-плюс автору.
Ну, про 26 многие национальные языки с вами не согласятся))) Ya by dazhe komment ne smog tut ostavit)) blya, probela tozhe net, i tolko kaps est. OXPEHETb!
Не совсем. Таблица нужна чтобы за константу пересчитывать метрику окна при добавлении/удалении одного элемента. Но если этот пересчет будет за O(n), то вы все-равно техникой скользящего окна соптимизируете уже с O(n^3) до O(n^2).
Даже в какой-то какой-то извращенной не аддитивной метрике где одинаково сложно изменить один элемент и пересчитать метрику всей подстроки с нуля, скользящее окно работает. Оно позволяет считать метрику максимум в 2n окнах. когда как перебор должен будет подсчитать n(n+1)/2 подстрок.
Ну, про 26 многие национальные языки с вами не согласятся
В конкретной задаче написано:
sconsists of English letters, digits, symbols and spaces.
Так что я был не совсем прав. Достаточно 256 элементов.
Не совсем понял про извращённую метрику. Про то, что окно принципиально меняет сложность - это да, естественно.
Я про то, что внутри цикла ( это О(n) сразу же ) я могу вызвать не symbols[value] , а, например, сортировку. И сказать: "Ну, я ж её вызвал один раз, значит она О(0), а что?"
Вообще, документация по go никаких гарантий не дает, но то, что map там unordered, как бы намекает, что для него используются хеш таблицы. И как я понял туда можно использовать ключи, для которых даже сравнение не реализовано. Так что деревья поиска тут отпадают вообще. Остается только хеш таблица.
Думал, лучший вариант - что-то типа O(log N)
Это если словарь сделан не как хэш-мап, а на основе дерева. Например, std::map.
Это какой-то jumping window
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Решение задачи с собеседования используя технику Sliding Window на Go