Всем привет. Сегодня вторая часть решения задачи Maximal Rectangle.
Если не видели первую часть, можете посмотреть:
Первая часть: клик
В первой части мы решали вот такую задачу. Дана таблица, нужно найти самый большой прямоугольник, состоящий из единиц, и вывести количество его единиц.
В первой части я создал алгоритм, чтобы эти прямоугольники искать
Мы сделали код, который решил 70 кейсов из 76, что довольно хорошо. Но наш код остановился на этом тяжёлом случае. Здесь слишком большая таблица, и наш код просто не успевает её посчитать.
Ну, может быть, цикл зациклился. Это всё нужно будет проверить.
Сегодня мы будем заниматься оптимизацией задачи, а возможно и исправлять баги.
Приступаем к оптимизации и исправлению багов
Я заметил, что в начале кода есть переменные, которые мы не используем. Я сначала создал "pointx", "pointy", а потом сделал цикл с "xpoint", "ypoint". Также стоит убрать переменную "max_len", потому что есть "max_width".
Так, теперь переменных стало меньше. Но существенно это ничего не поменяет.
Я попробовал вставить массив у себя на компьютере и попробовать на нём код, не зацикливается ли он?
Наш массив 200 на 200.
Очень странно, когда я открыл у себя на компьютере код, он у меня отработал очень быстро, почти мгновенно.
Ответ 147.
А знаете, что я сделал?
Первый раз я вставил код таким, какой он есть, вместе со всеми "console.log()". Он работал у меня очень долго, он постоянно в консоль выводил значения. А когда я убрал все "console.log()", он у меня выполнился почти мгновенно.
Вот оно в чём дело. Так вот в чём оптимизация!! Убирать все "console.log()" это тоже способ. Если бы я до этого додумался раньше, предыдущие мои задачи на LeetCode работали бы быстрее 😨
Ну ладно, попробуем это на сайте.
Да ладно, да вы что? Ещё + 2 решённых кейса. Невероятно. А виноваты были какие-то "console.log()"... Почему то JavaScript тратит значительно больше времени, если ему постоянно надо выводить данные в консоль. По-моему не только JavaScript так делает, ещё и Python.
А что мы имеем здесь?
Мы можем скопировать массив с сайта и вставить в JavaScript у себя на компьютере.
Это массив, полностью заполненный единичками. Проблема в том, что когда наш цикл для "xpoint", "ypoint" отрабатывает, "xpoint" меняется, и циклу надо отрабатывать заново. А здесь смысла в этом нету, у нас абсолютно везде единички, мы просто будем получать всё более маленькие квадраты.
Если вы не смотрели предыдущую статью, рекомендую посмотреть. Настойчиво рекомендую, вы не поймёте, о каких "xpoint", "ypoint" я говорю.
Нам нужно условие, чтобы проверить, что вся огромная таблица это большой квадрат. Если после итерации получилось единиц столько же, сколько во всей таблице элементов, цикл можно завершать. Пишем условие
Так, мы на последнем кейсе. Надо же, достижение то какое... 😨
Если честно, это моя первая задачка на LeetCode на хардах (hard).
Вот здесь я вообще не знаю, что делать. Нужно как-то представить это в видео таблице, чтобы было понятно, но таблица слишком большая.
Есть идея, можно эту таблицу представить в виде csv.
Я немножко считерю и использую PHP. С помощью него я сделаю из массива csv файл.
Ухх, это что???
Для удобства разукрасим эти ячейки по цветам.
Так, мы имеем гигантскую таблицу, в которой есть только две клеточки с нулями: клеточка в начале наверху и клеточка в конце внизу.
Это жёстко...
Но теперь понятно. Мы имеем гигантскую таблицу, но нам мешают две клеточки с нулями, из за которых нашему циклу приходится очень долго считать.
Мне вот интересно, я реально решаю эту задачу 6 часов, или это таймер просто сбился?
Ну вряд ли только решаю, я же ещё и пишу в блог. 😀
Продолжаем думать.
Сделаю более простую таблицу для примера. Допустим, у нас есть нечто, вроде такого. Таблица очень большая, а тут мешают всего два белых квадратика, из за которых приходится делать все эти вычисления.
Он считает квадраты примерно таким способом:
Возможно, нужно сократить такие вычисления. По сути оранжевый квадрат в ширину на всю таблицу, каждую итерацию он просто уменьшается, но лишние вычисления проводятся. Нужно сделать условие, при котором такие алгоритмы будут останавливаться (и у нас останется только оранжевый блок, из всех нарисованных).
Нет, такой способ нам не подойдёт. А если наш блок с нулём будет на другом месте, например в углу, прямоугольники наши посчитаются неправильно, если мы уберём жёлтый и все последующие. Нам же ещё нужно знать нижнюю границу прямоугольника, а до неё надо досчитаться.
Я в тупике.
Честно, я не знаю, что нужно делать, и как можно оптимизировать этот алгоритм на данном этапе 😨
Попробую ка его я запустить на компе
Он выполнился за 8 секунд, ответ 39600. Похоже для LeetCode 8 секунд это много.
Ладно, всё равно потом будем оптимизировать.
У нас есть два способа, что делать дальше:
1) Делать более эффективным конкретно этот случай (с гигантским прямоугольником и ячейками с нулями по краям)
2) Оптимизировать код в целом
Я понял, что вот это условие в коде стоит не на том месте. В этом цикле уже есть все необходимые проверки на случай, если мы случайно попадём в 0. Эту проверку нужно вынести за цикл.
Вот сюда:
Напоминаю, что делают эти 3 цикла:
Первые два цикла (С xpoint и ypoint) задают точку, с которой начинаются наши проверки на квадраты. Я на схемах её кружком обозначаю, можете посмотреть первую часть статьи и посмотреть.
А третий цикл устраивает эти микро проверки. Я вынес условие перед этим циклом, так как внутри они не нужны. Иначе у нас получается очень много проверок, мне кажется, несколько сотен тысяч.
Да. Это мне помогло оптимизировать наш код, теперь он выполняет задачу не за 6 секунд, а за 2,5 секунды
Задача решена, но очень и очень медленно. Наша задача работает медленно на последнем примере.
Ничего. Самое главное, что мы её вообще решили))
Это не просто какая-то задача, это задача уровня "Hard". На LeetCode задачи уровня "Medium" не всегда бывает просто решить. На задачах уровня "Easy" запнуться можно. А это "Hard".
Эту задачу решило 58,6% программистов. И это не просто абы каких программистов, это люди, которые:
1. Проявляют интерес к развитию и решают задачи на LeetCode
2. Которые не испугались надписи "Hard" и решили попробовать свои силы
3. Которые не испугались условий задачи и попробовали.
58% на медиуме и 58% на хардах это совсем разные вещи. Если смотреть относительно задач медиум, то 58% не так уж и мало, из за этого мне немного неловко, хотелось бы сделать что-нибудь особенное 😎. Но 58% на харде это совсем другие вещи.
Но глядя на этот график, чувствую себя тупорылым.
Ладно, я решил задачу так, как смог. Ничего страшного, всё таки это задача "Hard".
Ну а на этом всё, подписывайтесь на канал, ставьте лайки и пишите комментарии 😀