Встроенные алгоритмы Python (Виктор Кривощеков) 17 ноября

У нас, вроде, достаточно много подключилось.

Можем, в принципе, начинать.

Поставьте, пожалуйста, лайк, если меня слышно.

Много поставило.

Все, хорошо.

Так, давайте тогда начинать.

Сейчас поделюсь демонстрацией.

Так, и так.

Вам должна быть видна сейчас презентация.

Отлично.

Так, хорошо.

Сегодня у нас первая лекция нашего сбора к муниципальному этапу.

Всем спасибо, что вы пришли, что вам интересно готовиться к туру.

Так, давайте обсудим вначале основные моменты.

что мы сегодня хотим обсудить.

Мы хотим обсудить организационную часть.

И дальше у нас будут какие-то алгоритмы в нашем питоне и встроенные структуры.

Ну и давайте начнем с организационной части.

Что у нас будет.

Зачем мы собрались и что мы хотим сегодня узнать.

И в принципе в ближайшие две недели.

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

То есть общая наша цель такая, и давайте мы ее выполним.

Давайте скажу некоторые важные ключевые моменты.

Один из моментов, что у нас есть страница курса.

Вы видели, скорее всего, в канале в Telegram, страница, которая выглядит следующим образом.

Ссылка к муниципальному этапу тоже по информатике.

Здесь у вас будут все ссылки на контесты, записи, материалы.

Вся необходимая информация будет здесь находиться.

И также у нас существует страница аналога Курсис.ру.

В ней будут находиться все контесты.

Она выглядит следующим образом.

У вас будет кнопка в IT, регистрация и пробный тур, который сейчас прямо работает.

Здесь вы будете задавать себе задачи и видеть условия их.

Также обращаю внимание, что здесь есть ссылка на канал с объявлениями.

Если вы не подписаны на него, то, пожалуйста, подпишитесь.

Так, самое важное мне это сказал.

Теперь давайте перейдем к самому важному, к туру муниципальному.

Смотрите, что у нас вообще такое муниципальный этап?

в социальной информатике.

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

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

Каждую задачу можно оценить в нуля до 100 баллов, и в задаче описаны способы их получения.

То есть вы можете суммарно набрать до 100 тур от 0 до 500 баллов.

И при этом у вас при подсчете таблицы результатов никак не учитывается, сколько задач вы сдали на 100 баллов, сколько на 99.

У вас просто считают сумму баллов.

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

И после того, как закончился тур, остается таблица с баллами, которая отсортирована по убыванию, и берут топ сколько-то.

То есть, какая тут главная мораль?

Абсолютно без разницы, какие задачи вы полностью решили, какие нет.

Самое важное, сколько вы набрали баллов.

И давайте рассмотрим какой-то пример.

Давайте посмотрим на задачу с реального муниципа.

Я прикрепил справа правила оценки ее.

Давайте прочитаем, что здесь написано.

Решение, правильно работающее при N-15, получает 20 баллов.

То есть,

Задача вам говорит, что вы не обязаны решить полностью задачу при больших N, но если вы решите при N до 15, вы точно получите 20 баллов.

А 20 баллов могут довольно часто решать.

Это довольно крупный балл.

Это получается 1,25 от всего тура.

И 1,5 от задачи.

Дальше мы говорим, что если работает решение при N до 900, то мы получаем 70 баллов.

что это уже довольно хорошо, потому что в данном случае мы не знаем, какие ограничения полные, но n до 900 нам позволяет написать гораздо более простой код, чем на полный балл, а 70 баллов это уже не хухры-мухры.

Это довольно много.

И также нам дают еще дополнительное условие, что если решение работы при item больше или равно 0, то мы получаем также не менее 20 баллов.

Так, хорошо.

И давайте такой вопрос на засыпку.

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

То есть, какие опции допускает задача для получения баллов?

Пожалуйста, напишите ответ на этот вопрос в чате, потом мы его обсудим и разберем.

То есть, как вы думаете, какие баллы можно получить по данной задаче?

Если решать ее на какие-то только подробные ограничения.

То есть, не на полный балл,

А какие можностичные баллы по ней получить?

Так, трое уже ответили.

Давайте еще вас подожду чуть-чуть.

Ага, видел кучу ответов.

Пока еще пишите, давайте еще минутку и обсудим.

Так, и, кажется, ответы у нас больше не поступают, поэтому можем обсудить.

Ну, смотрите, какая вообще возможна опция первая?

У вас решение, в принципе, не работает, вы получаете 0 баллов.

То есть задача может получить 0 баллов, если у вас решение, в принципе, не работает.

Но, думаю, я вас этим не удивил.

А дальше.

У вас решение может работать при n до 15.

И при этом оно может не работать при отрицательных числах аидах.

Тогда у вас решение получит ровно 20 баллов.

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

А какая другая возможная опция?

Если у вас решение работает при n до 15 и при аидах больше равна 0, то вы получите все еще 20 баллов.

Потому что вам нужно, чтобы третья опция выполнялась при любых n. Вы получаете дополнительные 20 баллов, только если она работает при всех полученных числах.

Поэтому у вас решение должно работать

Чтобы получить 40 баллов, оно должно работать либо когда все числа положительные, либо при n до 15.

У вас эти условия не должны пересекаться.

То есть если у вас решение работает только при n до 15 и аид больше равно 0, то вы ничего не получаете.

А вот если они не работают раздельно, то есть у вас решение работает при любых n и аидах больше равно 0, или n до 15 и при произвольных аидах, то вы получаете 40 баллов.

Дальше.

У нас появляется вторая опция.

Написать решение, которое работает при n меньше равна 900.

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

Поэтому появляется опция решить задачу на 70 баллов.

Дальше.

Что у вас еще может произойти?

У вас может решение снова опять же работать при аидах больше равна 0, или

работать до 9600.

А тогда вы получите 90 баллов.

И последняя опция, что у вас решение работает при всех ограниченных задачах, и вы получаете 100 баллов.

То есть в данном случае вы можете получить от 0 баллов, 20 баллов, 40 баллов, 70 баллов, 90 баллов и 100 баллов.

И заметьте, сколько возможностей.

Хотя, казалось бы, всего 3 условия.

Поэтому, когда решаете задачи,

А задумайтесь, какие баллы вы можете набрать.

То есть, какие опции вам, возможно, под силу.

Допустим, на 100 баллов решить задачу сложновато, но если, допустим, получается на n до 900, либо аид больше, чем 0, но при больших n, то это довольно круто, потому что это целых 90 баллов.

Если, допустим, по задаче набрать 90 баллов, и по остальным тоже набрать не 0 баллов, то это довольно хорошо.

То есть, допустим, вам никто не запретит набрать по каждой задаче 90 баллов.

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

Так что не пренебрегайте частичными баллами, они вносят довольно большой вклад.

Так, есть ли какие-то вопросы, как здесь посчитали, какие баллы можно получить по задаче?

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

Ну, поставить дизлайк и задать вопрос.

Так, увидел.

Ага, все.

Там справились.

Ага.

Отлично, дизлайков не увидел.

Поэтому давайте тогда будем держать себя в голове, и до тура вы не будете себя выкидывать эту информацию.

Всегда держите, что частичные баллы – это очень важно.

У вас будет скоро тур, на котором вы можете как раз-таки проверить, каково получать эти частичные баллы.

Хорошо, давайте тогда перейдем к основной части занятия, а именно подробно поговорим про Python.

Какая у нас вообще сегодня философия будет, когда будем писать код?

Чем он короче, тем он быстрее.

Как вы знаете, наверное, Python довольно медленный язык.

Наверное, вы с таким сталкивались.

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

И если вы напишите какой-то код на питоне вместо встроенной функции, то, скорее всего, он будет работать медленнее.

Поэтому мы сегодня изучим какие-то встроенные штуки, которые уже есть в питоне.

Если про них помните, то лучше их использовать, чем самописанные.

Потому что они просто будут быстрее.

А как вы знаете, на Python довольно несложно получить таймлимит.

Хорошо.

Давайте начнем с самого важного.

Как, в принципе, ускорить произвольную программу на Python?

Для этого у нас есть три главные оптимизации.

И чтобы их продемонстрировать, давайте я запущу

демонстрацию экрана моего текстового редактора.

Давайте создам какую-нибудь папку.

И буду в ней писать код.

Так, у меня абсолютно пустая папка.

Да, давайте порт мне сделаю крупнее.

Так, видно.

Хорошо.

И давайте напишем какой-нибудь простой код.

Давайте я просто возьму и сделаю следующее.

У меня есть n чисел на входе, и я хочу их просуммировать.

Так, что я начал писать?

Так, давайте мне дается n чисел на вход, и я их просуммирую.

Так, запустим.

Так, оно считало одно число, двойку, и получилось, что сумма 2.

Давайте считаем два числа, 3, 4.

Получим сумму 7.

Казалось бы, самая обычная программа.

А давайте попробуем протестировать в каких-то суровых условиях.

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

Давайте создам вначале текстовый файл какой-то, который вводит просто миллион чисел.

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

Так, давайте сделаем так.

Здесь будет миллион чисел, и каждую от 0 до миллиона выведу.

Так, я создал наш файл.

Вот видите, это все числа от нуля до миллиона.

И давайте запущу нашу программу, которая его суммирует.

Я использую специальную штуку, консоль, которая позволяет отправлять ввод-вывод.

Особо не задумывайтесь, как она работает.

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

Хорошо.

Видите, что работал довольно долго.

Причем заметно долго.

Вот, допустим, раз, два.

Ну, полторы-две секунды.

Я также использую специальную штуку, которая есть только в длинных системах, называется time, которая посчитает время выполнения программы.

Ладно, я насчитал дольше, но выполняет 0,8 секунд.

Что вообще довольно странно.

Всего миллион чисел, а наш компьютер не может это даже быстро посчитать.

И какая есть первая оптимизация?

Оптимизировать можно, вот вывод.

А для этого мы хотим написать следующую штуку.

from sys input stdin и stdout.

Эти штуки нам позволят ускорить ввод-вывод.

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

input равно stdin readline.

И все без скобочек.

Особо не задумывайтесь, что они делают.

Это просто специальная команда, которая позволит ускорить ввод-вывод.

Зачем ускорить только ввод?

И давайте посмотрим, что произойдет

Можно сказать, что да, C++ взяли.

Но там чуть долговато будет.

Но долговато объяснять, как они работают.

Но можно сказать, да, что и взяли C++.

Так, давайте запустим.

И смотрите, обратите внимание, что наша программа стала работать 0,2 секунды, а было 0,8.

Я думаю, это довольно неплохо.

Мы сократили 4 раза выполнение нашей программы.

В довольно неплохой оптимизации.

Вот так вот, да.

Встроенный вот вывод работает долговато.

И также давайте посмотрим, как быстро выводить числа.

Для этого используется команда stdout.write.

Ну какие у нее есть нюансы?

Она принимает в себя только строку.

Для этого мы должны превратить наше число в строку.

И дополнительно еще вывести слешен, если мы этого хотим.

То есть print по умолчанию у нас переводит строку, а stdout.write нет.

Поэтому мы дополнительно хотим еще добавить slash n. Получается, stdout.write у нас будет быстрым вводом.

stdout.write stdout.write это быстрый ввод.

Интересно, кстати, что

А, потому что у меня тут немножко процессор еще заменился.

Давайте я его ускорю.

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

Вот вывел два числа.

И давайте, допустим, померяем что-нибудь в другую сторону.

Давайте я попрошу нашу программу вывести все числа от нуля до ста.

От нуля, допустим, до миллиона.

Та это будет чуть-чуть маловато.

Ну так же делаем.

stdoutwrite str и t плюс slash n.

Так, она мне сейчас будет долго выводить, ну, чуть-чуть подождем.

2 секунды.

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

А давайте попробуем теперь сделать через спринт.

Как видите, разница не сильно заметная, но она есть.

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

Здесь 0,3 секунды, а если использовать честный быстрый вывод, то оно работает чуть быстрее, но не столько критично, как вот.

То есть вот такая вот строка, вот прямо must-have.

Как видите, она там ускорила у нас четыре раза нашу программу.

Это одна из самых крупных оптимизаций, которые можно сделать.

Дальше у нас есть более крутая оптимизация еще.

Наш весь код запихать в одну функцию.

То есть, допустим, мы делаем какой-то код.

Не знаю, у нас есть задача А плюс Б. Допустим, я напишу самую простую версию.

Считываем два числа, вводим.

И чтобы его ускорить, можно сделать следующую вещь.

Весь код запихать в одну функцию.

То есть просто написать, допустим, defmain или любое другое название.

И вызвать ее потом.

Тогда в силу устройства Python он лучше работает со всеми значениями, которые находятся в функции.

И это будет вторая крупная оптимизация.

Продемонстрировать ее скорость не могу, так как придется написать более сложную программу, которая это должна мерить.

Но можешь поверить, что это тоже неплохо ускоряет.

Ну и какая еще третья есть оптимизация?

Это, конечно, отправить на PyPy.

Если вы полностью инвестируете в систему, у вас обычно есть выбор.

Не просто отправить на Python 3, а есть еще такая штука, как PyPy.

В силу своего исходного кода, он работает быстрее, чем Python, но с оговорками.

А именно, он плохо работает со строками,

И если вы хотите отправить задачу на Python, то лучше отправить на Python 3, точнее на PyPy 3.

Лучше отправить на обоих языках и посмотреть, как у вас работает.

Потому что не гарантировано, что PyPy будет работать лучше.

В среднем да, но не всегда.

Здесь на презентации собрал как раз три главных трюка.

Это первое – оптимизировать ввод, оптимизировать вывод, отправить под PyPy.

Но помните, что PyPy еще раз не гарантированно работает лучше.

И, конечно, все запихать в функцию main.

В сегодняшнем контесте вы еще увидите, что это работает, сильно ускоряет нашу программу.

Сами еще потестируйте.

Хорошо, ну мы здесь с помощью каких-то хаков оптимизировали нашу программу.

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

Ну, раз мы затронули тему вообще ввода-вывода, то давайте посмотрим, какие еще важные штуки можно делать с вводом-выводом.

А точнее, давайте просто с выводом.

Давайте вот, допустим, предположим, что мы хотим решить следующую задачу.

Даны два числа.

И мы хотим вывести пример следующего вида.

Если дают там числа 3 и 4,

то мы хотим сделать пример 3 плюс 4 равно 7.

Вывести на экран.

И в Python есть такая крутая штука, как f-строки.

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

str a плюс пробел.

Ну, давайте сразу большую строку сделаем.

Плюс пробел плюс.

Плюс str b. Плюс равно пробел.

Плюс строка, плюс a, b, c. Плюс a, плюс b. Так, давайте уберу вот файл.

Просто запишу нашу программу.

3, 4.

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

Но согласитесь, что это не очень элегантно.

Довольно странно, что мы должны вначале произвести наше число в строку, потом сложить его с каким-то плюсом.

потом еще раз сложить, что довольно сложно.

И в Python, начиная с версии 3.6, это довольно древняя версия, которая уже давно поддерживается, есть такой крутой механизм f-строка.

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

То есть давайте посмотрим пример.

Вначале просто увидим.

Так, забыл сохранить.

Ну и действительно оно вывело переменную 3.

И давайте тогда напишем полное решение нашей задачи.

Мы хотим вначале вывести значение переменной a, потом плюсик, потом значение переменной b, затем равно и значение a плюс b. Заметьте, что мы не обязаны писать название переменной, можем написать тут произвольное выражение.

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

Он приятнее выглядит и более читаемый.

Да, ошибиться тут, наверное, будет сложнее.

И с помощью таких же f-строк можно аккуратно выводить число с произвольной точностью.

А давайте я, допустим, возьму число 1, 2, 3, 4, 5.

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

Тогда, опять же, можно написать f-строку, и тут нужно использовать специальный механизм.

Мы хотим вывести наше число x, а затем двоеточие, точка 6.

Ну, давайте, допустим, двоеточие, точка 3.

И что тогда у нас произойдет?

4.

И оно у нас вывело до трех знаков после запятой.

Точнее, вывело ровно три знака.

Оно вывело.

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

Ну, двоеточие, точка 3F, да, согласен, что это не очень приятно выглядит.

Но, к сожалению, в Python это единственный способ аккуратно вывести нужное количество знаков после точки.

И, поверьте, это самый приятный способ это сделать.

И заметьте, что наше число еще округлилось при этом.

То есть держите в виду, что раз у нас стояло после этого число больше чем 5, больше равное чем 5, то у нас число округлилось из трех знаков.

То есть здесь у нас стоит не четверка, а пятерка.

Краски из-за математического округления.

И в принципе довольно часто вот эта концепция f-строк нам может помочь.

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

С большой точностью число.

Или наоборот, с очень маленькой.

И если вы не справитесь это сделать, то будет немножко неприятно.

Нет, не все занятия будут на питоне.

Просто сегодня лекция заключается в возможностях питона, которые могут помочь на Олимпиаде.

Так, есть ли какие-то вопросы, как работают F-строки, как можно использовать?

А если нужно N знаков после запятой, то вместо 3 написать N?

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

Как видишь, оно не сработало.

Потому что оно поняло, что N – это не наше число, а просто какая-то встроенная команда NF.

К сожалению, N знаков вывести ровно не получится.

Ну и в среднем это, кажется, не нужно.

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

Но произвольных знаков обычно у нас не требуется.

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

Ну и не забывайте также, конечно, обязательно писать букву F.

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

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

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

можно просто закинуть фигурные скобки в еще одни фигурные скобки.

Тогда ровно они выведутся.

Скорее всего, вряд ли вам нужно выводить фигурные скобки, но если вдруг такое случилось, что вам нужна одновременно F-строка и фигурная скобка где-то внутри, то можете просто засунуть фигурные скобки в фигурные скобки.

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

Хорошо.

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

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

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

Хорошо, давайте перейдем дальше тогда.

Сегодня мы говорим вообще, в принципе, про встроенные штуки в Python, которые ускоряют нашу программу.

И давайте на всякий случай уточню, все же знают, что такое списки в Python.

Так, а если не знакомы в Python, то знакомы ли в каком-то языке программирования?

Если не знакомы, то тоже ставьте лайк.

Точнее, если не знакомы, поставьте дизлайк, пожалуйста.

Ага, понял.

Краткое напоминание, что у нас такое массивы.

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

К нему можно обращаться по индексу,

записывать туда значения и получать их.

Массивы нумеруются от 0 до размера массива минус 1.

Такое краткое сведение про массивы.

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

И, наверное, вы знаете, что ждут два способа их построения.

Допустим, я хочу создать массив длиной 10 в пятой.

Так, здесь опечатка, я хотел здесь написать им нужно и. Допустим, я хочу создать какой-то массив длиной 10 в пятой, где хранятся числа равные квадрату.

То есть 0, 1, 4, 9 и так далее.

И первый способ это построить, я использую команду append.

Добавляю каждый раз в наш массив текущий новое число.

Но что плохого в такой программе?

Давайте мы ее запустим.

То есть мы хотели, допустим, просто построить массив, который содержит квадраты чисел от 0 до 10 в пятой.

Казалось бы, ну, почему бы и нет?

Что может произойти плохого?

Давайте я опять же использую специальную штуку, которая заменяет время в плане программы.

Интересно.

Я ждал, что она будет дольше.

Давайте попрошу вывести еще какое-то значение.

Тогда поднимем ограничения.

Длиной 10 в седьмой.

Ага, я смог его замедлить.

Представим, я хочу создать массив длиной 10 в седьмой.

Как видите, он выполнился за 0,7 секунд.

Что, в принципе, довольно нормально, учитывая его размер.

Но все же не очень.

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

Давайте попробуем заранее создать его нужного размера и будем писать в эту ячейку значение i умножить на i. То есть давайте не добавлять в конец число, а просто в нужную ячейку писать нужное значение.

То есть в данном случае нам нужно писать в ячейку номер i

значение i умноженное на i. То есть ровно то же самое, только я заранее создал массив нужного размера и потом буду в него писать.

И давайте в таком случае проверим время выполнения нашей программы.

О, как же так?

Оно выполняется дольше, чем предыдущий способ.

Но бывает, что сказать.

Но вообще мораль была такая, что добавлять конец это довольно долго.

А возможно здесь нам не повезло то, что у нас не все ячейки из массива использовались.

Давайте я его заставлю использовать все ячейки из массива и увидим сумму.

Вот, 1,3 секунды.

А давайте теперь с другим способом построения массива попробуем.

Так, что-то мне не везет.

Так, было 1.3, стало 1.4.

Ну, очень жаль, нам не повезло в данном случае.

То есть такой способ оказался быстрее, чем append, что довольно неожиданно.

И при этом вы заметили, что разные способы построения массива занимают разное количество времени.

А давайте попробуем еще другой способ сделать.

Это был номер один способ, задать с помощью append все элементы.

Тот раз с помощью просто пройти по циклу.

И есть третий способ.

Так, а если в строку данные записываются через ListMapInputSplit, будет ли быстрее, чем ваш способ?

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

То есть это самый оптимальный и лучший способ.

А остальное будет занимать больше кода и, скорее всего, будет дольше работать.

То есть встроенное чтение будет работать лучше всего.

А не можете заметить немного из-за пометок?

В данном случае оно замедлилось, ну, в смысле из-за комментариев.

Про это вопрос.

из-за символов решетка?

Нет, комментарии у нас никак не влияют на скорость исполнения кода, это просто производим текст.

Просто получилось, что мы здесь дважды обходим наш массив, как можете заметить.

Мы вначале создаем его размер 97, а потом задаем значение.

Мы его дважды обошли.

А здесь мы обходим один раз, но довольно долго.

Поэтому первый способ оказался у нас чуть-чуть быстрее.

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

Штука называется у нас генераторы.

И как мы их пишем?

Мы внутри массива пишем, какое выражение мы хотим задать относительно элемента i. И внутри перебираем циклом.

числа от 0 до 10 в 7.

То есть, ровно столько, сколько мы хотели.

То есть, как работает данный способ?

Мы говорим, что у нас будет какой-то массив, в нем будут храниться элементы равные i умножить на i, и i будем перебирать от 0 до 10 в 7.

И давайте снова померим время хранения нашей программы.

Давайте попробуем.

1.067.

То есть у нас этот способ работает одну секунду, предыдущий способ работал 1.4, а до этого первый способ работал 1.3.

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

То есть если наш массив можно как-то задать заранее

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

Данная штука у нас называется генератор, но можете его особо не запоминать.

Вот как называется генератор.

Про какие скобки идет речь?

Можешь, пожалуйста, подсказать, в какой строке я забыл скобки?

А, хорошо.

Так, тем меньше код, тем быстрее.

Кстати, да, краски ровно применение нашей мудрости.

Заметьте, что здесь массив создается довольно длинной строкой, здесь тоже довольно длинной командой, а здесь довольно короткой.

И он оказался краски быстрее.

А почему он работает быстрее такого же цикла?

Допустим, почему... А, почему он работает быстрее, чем второй способ, да?

Ага, смотри.

Потому что изначально мы в данном коде создаем массив размера 10 в седьмой, и потом записываем в него значение.

То есть мы вначале, получается, создаем память для нашего массива размера 10 в седьмой, а потом в нее пишем.

А здесь мы одновременно создаем память и сразу в нее пишем.

То есть встроенные питоновские штуки позволили сразу создать массив с нужными значениями.

Мы в них не записывали, а сразу создали память с нужными числами.

То есть имейте в виду, что если можно создать подобным образом наш массив, то лучше его использовать.

Потому что просто будет быстрее.

А в одном случае то нужно подумать.

Первый или второй способ.

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

Даже меньше.

Так что способ 3 у нас точно лучше, чем все остальные.

Про сравнение первого и второго нужно подумать уже.

У первого способа есть проблема, что мы делаем append.

Казалось бы, наш Append работает от единицы по времени, добавив число в конец массива бесплатно, но это не совсем правда.

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

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

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

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

Он не совсем прост, как вы думаете.

Вот такие вот дела.

Поэтому массивы создаем быстро.

Хорошо.

Мы научились создавать наши массивы.

Теперь давайте научимся в них что-то искать.

Давайте введу какой-то массив с клавиатуры.

Давайте я напомню краски команды для этого.

А то команда длинная, сложная, можно ее и забыть.

List.map.input.split.

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

Самое быстрое, что можно написать...

именно написать, а не с точки зрения работы.

Просто использовать метод in, который возвращает true, если у нас есть число в массиве, и false, если его нет.

Давайте создадим массив из 1, 2, 3, допустим, 10, и хочу проверить число 5.

Да, запись лекции, конечно, будет.

Ну, допустим, вы можете заметить, что числа 5 у нас нет в массиве, и вывела false.

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

Как вы знаете, вы можете догадаться, что он работает за от n, за от размера массива, потому что он просто пробегает все числа встроенным способом и проверяет, равно ли текущее число x или нет.

Способ, в принципе, надежный, пишется просто, но, к сожалению, долгий.

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

Называется она bisect.

Для этого импортируем из модуля bisect, bisect-left и bisect-right.

Смотрите, вот вам может показаться, что модуль bisect это какая-то внешняя библиотека, но нет, она встроена в язык,

Она на любом питоне будет работать.

Я где-то ее дополнительно не устанавливал, она именно встроена в питон.

И давайте посмотрим, что делает у нас метод besectLeft.

Но перед этим давайте отсортируем наш массив.

Для этого лучше использовать команду r.sort.

Она берет и отсортирует массив.

И как тогда быстро научиться проверять, что есть ли у нас число в массиве или нет.

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

Для этого напишем следующую команду.

Давайте найдем какой-то индекс, который я сейчас объясню ему, что значит.

bseq left запустим от массива до нашего числа x. И что будет происходить, когда мы заполняем такую команду?

У нас команда bseq left ищет такую позицию,

что он ищет минимальную позицию, минимальная позиция, что r от tdx больше и равен, чем x. То есть он в отсортированном массиве ищет такую самую раннюю позицию, что r от tdx больше и равен, чем x.

Как оно работает внутри, я сейчас уточнять не буду, буду знать и в скором времени.

И тогда смотрите.

Как тогда проверить, что наше число есть в массиве?

Если у нас r от tdx равно x, это значит, что у нас есть число в массиве.

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

А если r от tdx минерален x,

Но это значит, что проиграли.

Поэтому напишем следующую штуку.

Проверим, во-первых, что наш idx точно существует.

Потому что если наше число x больше, чем все числа в массиве, то у нас вернется длина массива.

То есть мы хотим проверить, что наш idx не равен длине массива, и при этом он равен нашему числу x. То можно вывести смело true.

Иначе говорим, что наше число нет в массиве.

Что мы сделали?

Мы, во-первых, отсортировали наш массив, потому что метод desecrateLeft так работает.

Дальше мы передали в него массив и число x. Тогда он находит минимальную позицию.

Или можно другими словами сказать, что минимальное число, так как массив у нас отсортирован.

И чем меньше позиция, тем меньше число.

Ищет такое число, что r от dx больше равен, чем x. Ну, если вы, допустим, найдете плюс-плюс, то данная штука называется еще lower bound.

Но про это говорить не буду.

И тогда мы хотим проверить, что, во-первых, если dx точно существует, что у нас есть число, которое больше равно, чем мы, и при этом, если оно равно, чем x, то мы нашли наше число.

Иначе нет.

И за сколько работает данный способ?

Он работает у нас за О от логарифма от N. Так, давайте для понимания, кто знает, что такое функция логарифм.

Оставьте лайк, если знаете, и дизлайк, если нет.

Так, дизлайки есть.

Ага, вижу.

Тогда давайте сейчас определим как-то функцию логарифма.

Смотрите.

Это такая минимальная степень двойки, что она больше равна, чем n. То есть логарифм от n равен k, если у нас k минимальная, то есть такая минимальная k целая, что 2 в степени k больше равна, чем n. Или удобно его так скажем.

Большая ли разница по скорости в Python по сравнению с C++?

В зависимости от того, как написать код на Python.

Потому что его можно так замедлить, что будет очень большая.

будет гораздо медленнее.

Но если использовать оптимизацию, то Python может не сильно проигрывать.

То есть если аккуратно использовать встроенные методы, использовать оптимизацию, то он может не сильно проигрывать.

Может пару раз, но, допустим, не в сотню.

А если без оптимизации, то можно и в 100 раз проиграть спокойно.

Так, вот, логарифм у нас такой, минимальное число k, что 2 в степени k больше 0, чем n. Это значок степени.

И, допустим, пару ключевых значений.

Логарифм от 10 в 5 это у нас 17, а логарифм от 10 в 9 это у нас 30.

А, допустим, логарифм от 10 в 3 это у нас 10.

И, то есть,

То есть, когда, допустим, мы выполняем поиск по массиву длиной 10 в пятый, то мы потратим всего 17 операций на проверку, есть ли число x в массиве или нет.

За нас это все реализовали, это встроенный, быстрый метод, который записан на t++.

Он работает очень быстро, его очень желательно использовать, если мы хотим проверить, есть ли число в массиве или нет.

Если у нас есть какой-то метод bisectLeft, то, наверное, у вас может появиться вопрос, а что делать тогда bisectRight?

Скажите, пожалуйста, какие в целом могут попасть алгоритмы на сош?

Довольно различные.

И в среднем то, что будет проходить на сборах, то может, в принципе, попасть на муниципальном этапе.

Мы узнали, как использовать bisectLeft.

что он очень быстрый и что работает обязательно для ассортированных массивов.

То есть это важно, не забудьте его ассортировать заранее.

Так, ну и давай тогда узнаем, что такое bisectRate.

Это, в свою очередь, такая позиция, что это такая минимальная позиция, что наше число строго больше, чем число x.

То есть, заметьте, что у нас bisect.left возвращал такое число, что оно больше или равно, при этом минимальное, а bisect.right такое минимальное число, что оно строго больше.

Иногда это нам может пригодиться, зависит от того, что мы хотим сделать.

Но это довольно две полезные такие функции встроенные.

Ну, опять же, не забывайте запускать их на сортированном массиве.

Потому что, если вы забудете...

то вам никто не скажет об этом, что вы забыли.

В данном случае нам повезло, конечно, что программа заработала, потому что просто повезло.

Но если не повезет, то можем очень сильно проиграть.

Поэтому не забывайте, вам про это никто не напомнит.

Так, хорошо.

Мы научились быстро искать число в массиве.

С помощью встроенных методов.

Особо самим не думая, как это делается.

И при этом потрачу всего 10 символов.

Считаю, что довольно неплохо.

Так.

Смотрите.

Представьте, мы отсортировали теперь наш массив в порядке убывания.

Точнее, в порядке возрастания.

Теперь мы хотим отсортировать в порядке убывания.

В питоне есть такая встроенная штука, называется ключ сортировки.

А код, который есть в презентации, будет у вас.

То есть презентация у вас будет, у вас все будет.

Так, хорошо, давайте теперь научимся сортировать массив, допустим, в порядке убывания.

Конечно, массив можно развернуть, но давайте научимся без разворота сортировать массив в нужном порядке.

Для этого в Python есть такая ключевая штука, как ключ сортировки.

Он объясняет правила, по которым будет сортироваться наш массив.

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

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

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

Допустим, когда мы хотим отсортировать массив r, мы говорим, что вот давай, когда мы берем it-элемент из массива, будем брать его ровное значение для сортировки.

Так, допустим, 3, 4, 5, допустим, число 5.

Как видите, он сортировался в порядке

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

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

Тогда есть такой следующий трюк.

Давайте наше каждое число умножим на минус один.

Да, есть специальная штука reverse true метод в сорте.

Но мы сейчас изучим более прикольную штуку.

Можем написать здесь перед выражением минус x. Тогда что произойдет с нашим массивом?

Каждый раз, когда мы будем брать элемент, мы будем сравнивать не с самими числами, а их отрицание.

Ну и как вы знаете, что число a больше, чем b, если минус a меньше, чем минус b.

Таким образом, когда мы говорим, что просим нашу программу отсортировать число по минус x, то оно самовозьмет, и когда мы будем получать элемент, оно умножит его на минус 1, будет их сравнить таким образом.

И если отрицательное число меньше от другого отрицательного, то положительный, наоборот, возраст убывает.

Ну и давайте посмотрим, как это работает.

Знаете, что наш массив отсортировался в порядке убывания.

И, допустим, здесь вы можете писать производные правила, как вы хотите сортировать элемент.

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

И при этом заметьте, что наш массив никогда не поменялся.

Оно использовало правило "-x", только когда сортировало.

Сам массив оно никак не меняло.

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

Команда sort не возвращает массив, она именно меняет оригинальный.

То есть, как можно заметить, r.sort, мы ничего с ним не сделали, оно ничего не возвращает, мы просто поменяли исходный массив.

И давайте сделаем следующее.

Давайте попробуем найти, допустим, число 2 по правилу λx-x.

То есть давайте в него передадим правило, по которому мы сортировали наш массив.

То есть мы отсортировали в порядке убывания по нашему правилу.

Теперь давайте попробуем его подставить.

Посмотрим, что получится.

Так, ну да, я забыл ввести dx.

Смотрите, что произошло?

Почему она вывела 4?

Почему она говорит, что ближайший и больший элемент это у нас за границей массива?

Она посмотрела, что у нас

Когда мы сравниваем элементы, оно берет правило минус х. И оно взяло вначале наш массив, представило, как будто он минус 5, минус 4, минус 3, минус 1, и искало первое значение, которое больше, чем 2.

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

Ну а если, допустим, мы хотели найти первое число, которое меньше, чем мы, такое максимальное число, то мы должны еще применить наше правило для элемента.

То есть, если мы хотели найти первое число больше, чем 2, точнее, меньше, чем 2, то мы должны сюда были подставить минус 2.

И, как вы можете заметить, оно вывело индекс 3.

То есть, оно говорит, что единица – это самое большое число, которое меньше, чем 2.

То есть, в наш поиск можно подставлять правило, по которому мы сортировали.

Так, поступил вопрос в чате.

А что если массив будет двумерный?

То для сортировки по неубыванию по первому элементу нужно подставить lambda x, x нулевое.

Да, в точности правильно.

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

Да, Роман, правильно.

То есть хорошо, что мы научились делать?

Мы научились сортировать массив по произвольному правилу, которое мы хотим сделать.

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

Получается, что мы научились делать?

Мы научились искать минимальное значение, которое больше равно, чем мы, минимальное значение, которое больше, минимальное значение, которое меньше, вообще максимальное значение, которое меньше.

и максимальное значение, которое меньше равно, чем мы.

Так, хорошо, поступил интересный вопрос в чате.

А как отсортировать, допустим, двумерный массив, вначале по первому элементу, а потом по второму, если они равны?

Так, давайте еще какой-нибудь там элемент.

Для этого мы хотим придумать правило, по которому мы хотим сортировать наш массив.

Вообще, можно вспомнить следующую штуку.

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

Тогда что сортировать?

Два элемента из двух.

Я вот спил вопрос в чате.

Как нам отсортировать наш массив?

Прошу прощения.

Как отсортировать наш массив?

Вначале к первому элементу, а потом, если равны, то вторые.

Так, Илья, я, к сожалению, не могу прямо сейчас ответить на этот вопрос, потому что не знаю, но это можно проверить.

Но вообще, если у тебя есть какая-то функция, то можно написать λx равно f от x. Это точно сработает.

Так, как теперь нам отсортировать вначале по первому элементу, а потом по второму?

Для этого можно написать следующее правило сортировки.

x нулевое, затем x первое.

Тогда у нас вместо массива будут сравниваться только первые два элемента.

И наш код вначале будет сравнивать первый элемент, потому что у нас так сравниваются массивы, и при равенстве второй.

Давайте посмотрим, что это действительно так.

Да, замечу, что он сортировался вначале по первому элементу, потому что у нас правило такое, что вначале берем первый элемент, а затем по второму.

Так, ответил на вопрос.

Роман, как это работает?

Как это сделать?

Почему работает?

То есть любое правило сортировки просто должно указывать, какой объект мы хотим сравнивать.

И в данном случае мы будем сравнивать массив из двух чисел.

Ну а массивы из двух чисел сравниваются следующим образом.

Сначала сравниваются первые элементы, а потом вторые.

Да, контест будет где-то через час после конца занятия.

Так, давайте рассмотрим, какие маленькие победы мы достигли.

Мы научились быстро искать число в массиве отсортированном.

В том же встроенной функции.

Так, а если у нас будет 1, 2, 3, 4, 1, 2, 5, 7?

то сортировка нам не гарантирует, в каком порядке они будут.

Потому что, с точки зрения сортировки, эти элементы два одинаковых.

Потому что мы сказали, что мы сравниваем только по первому и второму элементу.

А то, что будет позже, мы не знаем.

То есть здесь может произойти все, что угодно.

Я, допустим, не могу сказать, какой будет порядок.

Но в данном случае он сохранился.

Если я их переставлю, то я не знаю, сохранится он или нет.

то, что мне ничего не известно, как работает сортировка внутри.

Она просто говорит, что сравнится первые два элемента.

Но, на случай, порядок сохранился.

Бывает.

Мук не сохранится.

В чём вопрос?

В каком смысле, как её сортировать?

Если мы хотим сортировать по первому и второму элементу, то наша программа сделала всё правильно.

Она вначале отсортировала по первому, затем по второму.

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

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

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

Так, мы научились быстро искать, быстро сортировать по произвольному правилу, не реализуя свою сортировку.

Так, теперь давайте познакомимся с еще более быстрым способом поиска.

Есть такая структура данных в Python, называется Set.

Задается она с помощью следующей штуки.

Set, круглые скобки.

И что она умеет делать?

Давайте здесь чуть-чуть поленюсь и скопирую сразу готовый пример.

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

Но есть у нее один нюанс.

Я бы сказал даже пару.

Так, я что-то забыл закомментировать.

Что такое set?

Это будет наша специальная структура, которая умеет делать быстрый поиск.

Нет, она добавляет завод единицы ровно.

И заметьте, что случилось.

Она, во-первых, нашу двойку

сохранила ровно один раз.

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

Он будет храниться ровно один раз.

Это первый нюанс у сета.

Затем, заметьте, в каком порядке мы добавляем элементы?

2, 4, 3, минус 1.

И посмотрите, в каком порядке они здесь хранились.

2, 3, 4, минус 1.

Заметьте, что у нас 4 и 3 поменялись местами.

И сет – это такая структура, во-первых, она не хранит

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

То есть порядок мы заранее не знаем, какой получится.

То есть от запуска к запуску он не меняется, но заранее предсказать мы его не можем.

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

а мульчисет нет в питоне.

Тогда что дальше можем сделать?

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

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

Но set можно все равно вывести, например, с помощью звездочки setR, если вы видели при массиве.

То есть при сохранении он навсегда или при запуске трансферится.

Не очень понял вопрос.

Можешь, пожалуйста, переформулировать?

Но при этом вывести мотив мы можем.

С помощью звездочки.

И перебрать элементы сета с помощью цикла тоже можем.

Смотрите, я смог перебрать элементы сета.

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

Такой нюанс у сета.

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

Но это все компенсируется его главной фишкой.

Нет, у нас структуры все.

все, что мы пишем, весь код, он не сохраняется в какой-то другой памяти.

У нас вся память хранится только, когда программа работает.

После того, как программа закроется, все, у нас ничего больше не хранится.

То есть уникальное значение, то есть у нас после запуска программы сет всегда пустой.

А если что-то удалить из сета, то можно порядок поменять.

Да, порядок вообще у нас еще раз произвольный.

И все, главная фишка сета –

что я могу написать следующую команду.

Проверьте, есть ли число в сете, ну или вообще другой произвольный элемент, за от единицы.

То есть в прошлый раз у нас в массиве поиск работал за проход по всем элементам.

А в данном случае проверить, что элемент в нашем сете можно за от единицы.

То есть мы добавляем за от единицы и проверяем, что в сете за от единицы.

Это очень круто, это очень быстро.

К сожалению, здесь от единицы не такая же, как, допустим, посчитать 2 плюс 2.

Это чуть сложнее, чем, допустим, посчитать 2 плюс 2, но тоже довольно быстро.

То есть мы не будем пробегать все элементы.

Если кто-то знаком с словами хешмапа, то да, это хешмапа.

И, допустим, если мы хотим удалить элементы сета, то есть специальный метод discard.

И, допустим, если я удалю двойку, то ее больше не будет.

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

Ну и когда мы запустим еще раз поиск числа в сете, то его не будет.

Ну и удаление, конечно, тоже работает за от единицы.

То есть все вот такие методы сетом, добавление, удаление, поиск, работают за от единицы.

Долго от единицы, но хоть какую-то.

Роман, ответ на этот вопрос – да, но подробнее узнаете завтра на лекции.

А можно ли все добавить в список?

Хороший вопрос, к сожалению, нельзя.

Почему нельзя?

Потому что некоторые штуки в Python запрещают тебе добавлять специальный тип объектов.

Это свойство называется изменяемость.

Я не особо буду сейчас о нем говорить, но могу просто показать пример, что такое изменяемость.

Если я напишу, допустим, a равно 1, 2, 3 и b равно a, то при изменении значения b у меня поменяется массив a.

То есть, допустим, здесь поменялось значение а, хотя я этого не просил.

Это свойство называется изменяемость.

И из-за этого, собственно, нельзя добавлять списки.

В него можно добавлять строки, числа, но, к сожалению, не списки.

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

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

Но числа и строки почему нет?

И делать поиск за от единицы.

Тогда связи просто не будет.

В данном случае связь между B и A разорвалась.

Они друг от друга отдельно живут.

То есть, что вы, получается, можете с помощью стадии делать?

Вы можете, допустим, положить n объектов в set, и потом q раз проверять, есть ли число, допустим, в сети или нет.

И будет это работать суммарно за количество запросов и количество чисел.

Что довольно полезно.

То есть, допустим, если вы хотите 10 в пятый раз проверить, что есть ли число в наборе из 10-ти пятых элементов,

в наборе из десятипятых элементов, то это будет быстро.

А если это делать с помощью массива, то это будет гораздо дольше.

Ну и с помощью bin-поиска там будет, кажется, тоже дольше, но, опять же, это нужно смотреть на практике.

Да, связь можно... Нет, если мы написали a равно b с массивами, то у нас связь сохранится уже до конца.

Это надо будет создавать новый массив сразу тогда.

А если сделать перед добавлением в сет константный массив?

Есть такая штука, которая делает константный массив.

Ее можно использовать.

В таком случае будет работать.

Но чтобы не усложнять, я не буду о нем говорить.

Предположим, что его не существует.

То есть мы можем, получается, быстро проверять, отвечать на кучу вопросов, есть ли элемент в массиве, кого-то на баре или нет.

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

Очень жалко, зато быстрый поиск.

Я думаю, это довольно тоже неплохо.

Это довольно часто применимая вещь.

Кажется, допустим, set – вторая по применимости структура, которая вообще встречается в мире.

Вначале, допустим, это будет массив, а вторая – это будет set.

А третья, наверное, будет мапа.

Или, ну, мы с вами дикт, про который я там сейчас расскажу.

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

Смотрите.

Представьте, я хочу делать следующее.

Я не хочу, допустим, создавать какой-то большой массив, а хочу уметь обращаться в точки 10 в 9, не создавая 10 в 9 элементов.

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

Опять же, я немножко поднимусь и скопирую пример.

Что умеет делать словарь?

Он умеет записывать по произвольному ключу значение, то есть, допустим, в строку ABC записал FGH, обратиться по ключу,

и удалить ключ.

Это, опять же, все работает за от единицы.

Пожалуйста, не спамьте в чате с маленькими.

Спасибо.

То есть что у нас умеет делать словарь?

Он умеет по произвольному значению записывать какой-то новый элемент.

То есть, допустим, что для b целых хотим возвращать fgh.

По строке 100, допустим, хотим возвращать значение 100.

По значению 10 девятых мы хотим возвращать минус 1.

И все эти методы работают в завод единицы.

То есть мы можем записывать завод единицы, удалять завод единицы и проверять, что есть ли в словаре завод единицы.

Смотрите, мапа – это такое ключевое слово из Python, ой, из C++.

В Python это называется dict.

То, что, допустим, было выше слова map, это другая мапа, это другая штука.

То есть когда вы пишете list map.input.split, это другой мап.

Не путайте его с мапами свист плюс.

Ну то есть словарь что у нас может делать?

Он может по произвольному значению записывать какой-то объект и по нему потом же получать обратно.

Можно удалять этот ключ.

И можно проверять, есть ли у нас ключ или нет.

И если мы, допустим, хотим перебрать все объекты в нашем словаре,

то мы перебираем просто в D наш элемент, и потом обращаемся по D-итему.

Так, хорошо, сейчас поступила куча вопросов.

Так, словарь это имейн, есть мапа?

Ну, мапа это в C++ принято называть.

В нашем случае это словарь, это называется дикт.

Встроена функция map, выполняет другое в питоне.

Можно ли использовать словарь как ключ значения?

Я не особо понял, что это значит.

Переформулируй, пожалуйста, вопрос.

А насколько C++ быстрее Python по времени?

В зависимости от того, насколько его хорошо оптимизировать.

Можно и в 4 раз проиграть, а можно, допустим, раз всего в 5-2.

Есть ли смысл писать на Python?

Если вам это удобно и проще, почему нет?

У вас же никто не запрещает весь тур писать на одном языке.

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

Если хотите, задайте задачу на питоне.

Если захотели, на плюсах.

Как вам удобнее?

Что вам кажется проще написать?

Дом пишите.

Если вы понимаете, что задача точно зайдет на питоне, почему бы не написать на питоне, если вам нравится?

Словарь не создается фигурными скобками?

Да, можно создать словарь здесь с помощью фигурных скобок.

Ну, или можно писать слово dict.

То есть это то же самое, что dr равно фигурные скобки.

А, в словаре можно ли использовать словарь как ключ, то есть можно ли, допустим, написать, что какой-то другой словарь, и, допустим, b от d написать равно 1.

К сожалению, нельзя.

Свойство того, что d – это такой же изменяемый тип, как и... Короче, такое же свойство изменяемости есть, как у списка.

Поэтому нельзя.

Но можно записывать его как значение.

То есть как значение здесь можно, допустим, написать 100, 100, 100.

Но в левой части нельзя.

Так, давайте я выведу здесь d от 100.

И вывелся краский массив с трех элементов.

100, 100, 100.

То есть здесь можно в правой части писать массив, но здесь вот категорически запрещено.

Нам потом не даст это разрешить.

Все материалы будут опубликованы на странице ЕДУ, которая выше прислала, которая есть в чате, точнее, в канале сборов.

Ну и ссылка на канал сборов была выше в чате.

То есть что у нас такое, по сути, еще раз, наш дикт.

Это штука, которая позволяет по произвольному ключу записывать произвольное значение и получать по нему, и искать.

То есть это такой сет, можно сказать, но который поддерживает чуть больше функционала.

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

И все это работает, конечно, за от единицы, но давайте еще раз напомню, что это от единицы не такая же быстрая, как, допустим, в списке.

От единицы бывают разные.

Они могут работать разное количество времени.

Поэтому, когда пишете код, будьте чуть аккуратнее.

Допустим, не стоит использовать дикт вместо массива, если это можно.

Потому что можно получить TL, и будет не очень приятно.

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

Сейчас сядет у меня демонстрация, и будет не очень приятно.

Пару секунд.

Так, все.

У нас теперь проблем нет.

Можем продолжать.

А вот если мап, то у него автоматически происходит сортировка по ключам.

А в Python так же будет?

Вот хороший, кстати, вопрос.

К сожалению, нет.

Можно заметить, что здесь, допустим, после этого фора вывелся abc, fgh, million, потом abd.

Но я думаю, это произвольный довольно порядок.

Я бы его никаким не назвал.

То есть, опять же, как в статье, у нас порядок случайный.

Зато за это мы получаем от единицы время работы.

То есть помните, что все эти текстуры по-твердому встречают порядок.

Зато от единицы.

Лекция по C++ будет завтра, да.

И давайте рассмотрим другую последнюю штуку, прикольную.

То есть что мы получили?

Мы получили структуру, которая позволяет делать сверхбыстрые поиски и сверхбыстрые обращения по элементу.

Обращения еще не скинули.

Так, у меня случайно пропал один слайд, который я потом докину.

И напоследок давайте вернемся к структуре, к самому массиву.

Сегодня на лекции у нас только питон.

Не посетить какую-то лекцию не возбраняется.

То есть вы можете пройти сборы, но не посетить какие-то лекции.

Это не запрещается.

Главное потом в конце оставить обратную связь и потом получить сертификат.

Контесты, опять же, тоже необязательны, но вам же лучше, если, наверное, вы порешаете задачи.

И давайте вернемся к структуре, которая позволяет хранить... Не знаю, зачем у вас сертификат, просто на стенку повесить.

Распечатать, повесить.

Не знаю.

Хорошо, давайте чуть-чуть вернемся к лекции.

Нам буквально чуть-чуть осталось.

Помните, что массив может добавлять значение в конец и удалять из конца.

Как в фонде, удалять из конца – это от единицы.

Это, в принципе, довольно хорошо, чтобы удалять из конца и добавлять в конец.

Ну а представьте, допустим, в какой-то причине хотим добавлять сначала и удалять изначально еще.

Ну вот так, допустим, захотелось.

Если мы это будем делать с помощью списка, то это будет тратить ОТН времени.

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

Удаление середины тоже нет быстрого, к сожалению.

Есть медленное, но оно работает за размер массива.

Я думаю, это довольно неприятно.

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

Но это слишком сложные структуры, и они не поддаются до уровня региона задачи C минимум.

Не раньше региона C. Но добавлять и удалять изначально нам может быть полезно.

И для этого есть такая штука встроенная, называется DEC.

Так.

Для этого нужно подключить следующую штуку.

И создается она следующим образом.

Пишем актер одной скобки deck.

То есть from collections import deck.

Опять же, эта штука есть в питоне по умолчанию.

Никакую библиотеку скачивать не нужно, она всегда гарантированно будет.

И как работает с деком?

Да, точно так же, как с массивом.

Я могу даже вот отсюда из такого же массива его создать, из 1, 2, 3, 5, 6, передав его в круглые скобки.

Добавить семерку, допустим, в конце.

Допустим, добавить еще девятку, вывести его.

Перебрать все элементы, вывести его.

Обратиться к второму значению.

Все это можно.

Как видите, здесь...

А, я не то вывел просто.

Да, я сейчас про разницу расскажу.

То есть, смотрите, был, допустим, массив 1, 2, 3, 5, 6.

Я его 7, 9 вывел.

Перебрал все элементы, вывел.

И, допустим, обратился по второму значению.

Получил тройку.

То есть, он выполнил все функции.

Если я хочу изменить значение, то ровно точно так же, как в массиве.

Допустим, я запишу втрое значение, а 2 равно 10.

Получу в конце значение 10, потому что я ввожу здесь а втрое.

Я его поменял и сразу вывел.

Получил 10.

То есть может работать так же, как с обычным списком.

Казалось бы, зачем он тогда надо, но у него есть еще важное преимущество.

Я сейчас про время работы расскажу.

Но мы можем добавлять еще начало списка.

Для этого я просто напишу команду append left.

Добавлю в начале четверку.

И давайте посмотрим, как он изменился.

Давайте я выведу его до добавления и после.

Заметьте, что здесь вывелось еще четверка в начале.

И добавление произошло за от единицы.

И если я хочу удалить с конца,

то для удаления справа у меня есть команда pop, а слева pop left.

То есть говорит, что удалить слева.

И она тоже работает за от единицы.

То есть список у нас не умеет такое делать, а дек умеет.

То есть все вернулось обратно.

И мы тратили всего от единицы времени.

Казалось бы, почему тогда не использовать всегда дек вместо списка дефолтного?

Ну, опять же, это от единицы чуть дольше работает,

чем обычный питоновский список.

Да, он по памяти может больше занимать, чуть медленнее работать, не так плохо, как set и dict, но чуть медленнее.

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

Это не сильно будет тормозить и не сильно будет много памяти тратить.

Не сильно больше.

Но вместо списка его использовать не стоит.

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

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

Но, опять же, вместо списка использовать дек не стоит.

Это просто тормозит вашу программу, и это будет довольно странно.

Да, можно, но я пока не ловил.

Используйте только с умом.

Не стоит его куда угодно пихать.

То есть мы сейчас... Что научились делать?

Мы научились быстренько добавлять массив в начало.

Ну да, и вот последние краски у нас.

Три структуры позволяют делать какие-то операции в золотые единицы.

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

Вопрос к АКБ.

В Python нет такого понятия как АКБ.

Это называется undefined behavior.

Но есть Cypress Plus, который говорит, что поведение не определено, мы не знаем, что произойдет дальше.

В Python гарантированно поведение, с ним не встретишься.

Очередь есть же в такой же библиотеке?

Да, она есть, но очередь нет смысла использовать, если у нас есть дек.

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

Скорее всего, даже не отличаются, я почти уверен.

Но дек просто мощнее.

Поэтому можно использовать либо список, либо дек.

Хорошо, мы познакомились с всякими структурами, научились быстро искать в массиве.

сортировать по произвольной очереди, в произвольном порядке, и ускорять программу.

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

Нет, хип-ку сегодня не будет.

Хорошо.

Есть ли какие-то вопросы по сегодняшнему занятию?

То есть мы учились просто делать какие-то быстрые операции.

Ускорять Python и делать все быстро.

Если вопросы есть, то, пожалуйста, задавайте.

Если нет, то... Хорошо, сейчас посмотрю парадлайн.

Если вопросов нет, то где-то через час появится контест.

Вы можете поступать, будете к его решению.

Всем спасибо, что пришли.

Расписание лекции есть в канале сборов.

Повторите, пожалуйста, как парадлайн через сеть сработает.

Смотри, давай еще раз напишу.

Мы пишем from sysimport stdin.

Презентация тоже появится скоро вместе с контестом.

А для этого мы пишем input равно stdin.readline.

То есть здесь без скобок все пишем.

input равно stdin.readline.

Вот презентация также написана вроде.

Да.

И когда хотим использовать вот, то... И контест появится где-то через час.

то просто пишем input, допустим, если я хочу считать число, то просто пишу int input.

А, да, там дальше какой-то код есть.

То есть если мы хотим быстрого использования, то std in redline.

Нет, контест закрываться не будет до 12.00.

Ссылка на контест будет опубликована на странице курса, на странице еду.

Ссылка есть в канале.

И презентация также есть, которая скоро будет отправлена.

А вывод stdout.write?

Да.

У контестов дедлайна не будет.

Так, а кто был автором вопроса, пожалуйста?

Можете показаться автором вопроса, кто писал про stdin?

Ответил на него или нет?

А, да, вижу.

Чтобы использовать еще раз stdout.write, мы обязаны перевести все в строке и не забыть добавить в конце слешен, если мы хотим перевести строку, потому что без этого ничего не произойдет.

Так, давай я все ниже закомментирую.

Вот, мне считался один, вывелся один.

Я обязательно использую строку, потому что иначе работать не будет.

И, допустим, если я выведу число еще раз 1, то у меня произойдет, конечно, вывод 1,1.

Так, я забыл сохранить.

Произойдет вывод двух единиц.

А если я забуду слошен, то они выведутся подряд.

Про слошение не забываем.

Хорошо, если есть какие-то еще вопросы, то можете сейчас задать.

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

У вас еще в расписании стоит тур, который будет именно идти по кафремам муниципа.

Так, вопросов, кажется, больше нет.

Так что спасибо всем, что пришли.

Вопрос, тогда как мы сначала вызываем?

Кого вызываем?

Не очень понял.

Смотри, мы когда написали input, мы по сути сказали, что вместо input давай будем вызывать stdin-readline.

Мы его здесь не вызываем, мы просто говорим, что...

input будет работать как sdn-readline, то есть он будет сам дальше подставляться.

Он будет работать как обычный ввод, только вместо input долгого будет использовать sdn-readline.

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

Да, все так.

Так, все вроде обсудили, вопросы отвечены, так что всем пока.