0: Доброго времени суток. Давайте дальше потихонечку продолжать. И перед тем, как мы перейдём уже непосредственно к различным структурам данных алгоритмам и прочим прочим полезным важным вещам. Разберём некоторый нюанс, который мелькал уже

1: В предыдущих видео касательно массивов и листов. То есть я использовал эти 2

2: Термина, по сути, как синонимы. И фактически это примерно 1 и тоже с некоторыми нюансами. К тому же есть ещё такая отдельная проблема, да, то есть массивы, листы, окей, они встречаются в других языках программирования, они по разному немножко работают. В отличие, например, от

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

4: Двусмысленности не было. Соответственно, прежде всего, давайте начнём с массивов. То есть у нас с точки зрения работы с памятью есть 2 таких самых элементарных

5: Самых элементарных. 11, с которыми мы работаем, это, по сути, переменная, да, то есть кусочек маленький, оперативной памяти, скажем, элемент 1, и massive это после

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

7: Место это так называемый сирей сирей, также известный как просто массив статический массив.

8: Статический массив массив. Почему сирэй, да, то есть, ну, язык программирования си, это буквально как бы, кусок памяти, к которому мы напрямую имеем доступ. Понятное дело, что с точки зрения операционной системы там накладываются, определённы

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

10: Статический у нас массив, он у нас нерасширяемый, то есть это буквально кусок памяти. Почему он нерасширяемый? Ну давайте мы для этого посмотрим собственно на оперативную память, да, то есть возьмём просто какой-то набор

11: Ячеек.

12: Попробуем добавить туда какие-то данные берём, соответственно добавляем икс равный 2, то есть какое-то интовские значение ну предположим, что оно у нас хранится в соответствующей ячейке памяти, да, то есть у нас есть какая-то там локальная переменная

13: Стейке икс, она равняется 2. Естественно, мы понимаем, что в этот момент у нас в стеке раз это локальная переменная, то она хранится у нас в стеке сама переменная хранит внутри себя адрес, да, то есть здесь можно как бы

14: Указать в скобочках 0 икс 0 другими словами, x это псевдоним для адреса 0 икс 0, можно так его рассматривать и в куче, то есть где-то в оперативной памяти у нас вот хранится значение нашего x хоро.

15: Хорошо, добавляем дальше игрек да, то есть добавили его значение равно единице int мы с вами как программисты воспринимаем конечно же эти значения как соответственно некий объект имеющий

16: Значение 2 1 имеющий тип int, хранящийся где-то да понятное дело, что в реальности у вас тут ещё будет какая-то дополнительная информация, то есть это не чисто значение, которое занимает 8 bit, а какие-то дополнительные вещи тут будут естественно храниться особенно.

17: В питоне, где у нас все является объектом, а объекты, помимо прочего, хранят довольно большое количество дополнительной технической информации, то есть размер, какие-то там методы и тд. И тп. Со временем мы узнаем некоторые эти вещи, вот, но мы рассматриваем

18: В общих чертах и концентрируется в данном в данный момент на значении. Окей. Добавляем дальше какой-нибудь лист, да, то есть добавляем лист 3 элемента 0 0 0. Понятное дело, что у нас в целом 0

19: 0 0. Само значение где-то хранится в куче. Давайте я его нарисую где-нибудь. Вот здесь, например, 00:00 00:00. И в внутри листа хранятся ссылки на

20: Наше значение.

21: Вот, то есть, понятное дело, что в данном случае я упоминал это для значений интов от - 5 до двухста 56, да, - 5, 256 вклю.

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

23: Вот таких вот специфичных оптимизаций, которые существуют также, например, и для некоторых строк.

24: Собственно, интернирование строк. В общем случае у нас, конечно, объекты даже одинаковые находятся в разных местах, в оперативной памяти. Если мы их просто где-то независимо друг от друга создаём, имейте ввиду то, что у нас

25: 2 ивана в разных группах находятся. Это не означает, что это один и тот же человек, да? Ну так получилось, соответственно, здесь у нас давайте 0 x 48. То есть лист у нас ссылается на нолик в 48 ячейке, и это

26: У нас, по идее, должно быть как-то так.

27: А, ну ещё 1, ещё 1 единичку забыл. 1, 1, 1, 1, да, то есть, вот у нас лис, последовательно выделенная область памяти. Каждый элемент у нас здесь занимает 8 bit. Предположим, да, такой у нас размер адреса, мы для на.

28: Наглядности взяли и 1 элемент у нас вот он хранится и ссылается как бы сюда. То есть мы можем рассмотреть это значение как адрес. Ну и наш нолик я здесь для простоты нарисую в, в принципе, единственном варианте. Окей.

29: Что если мы хотим добавить элемент, то есть представим себе такую ситуацию мы берём наш лист, вызываем у него метод аппенд аппенд, допустим, 8. И вот что в этот момент мы должны сделать, то есть

30: Лист это последовательно выделенная область памяти и как бы

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

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

33: Это в данном случае нолик 16 плюс прибавить, соответственно, размер каждого элемента в данном случае 8, умноженное на количество элементов, которые я хочу скипнуть, то есть пропустить, умножить на 2 2 на 8 будет 16 16 + 16 0 x 32. Получаем д.

34: 0 x это указание того, что это просто адрес, а не какое-то рандомное значение для удобства окей. То есть действительно, вот у нас значение во 2 индексе, в ячейке памяти 0 x 32, и оно как бы указывает сюда хорошо прекра.

35: То есть, если я хочу добавить новое значение, то мне, по идее, его надо добавить сюда, но тут то уже занята память, как бы, что мне делать? То есть я бы мог, конечно, сделать следующую вещь. Окей, давайте.

36: Мы создадим, во первых, восьмёрку где-то в памяти, да, в куче. Ну ладно, давайте создадим.

37: Это у нас получится что-то типа 0 0, 0, 0 1:00 0. Да, восьмёрку создали. Теперь нам надо её добавить, ну, ссылку на неё добавить в лист, но мы не можем сюда ссылку положить, потому что там уже значение какое, т.

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

39: Вот набор ячеек оперативной памяти, он не пустой в том плане, что там типа ничего не хранится. Оперативная память всегда хранит либо нолики, либо единички. Просто для того, чтобы не писать здесь кучу Ноликов или какой-то рандомный мусор, я

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

41: Но 4 элемент, да, у нас будет храниться вот где-то здесь как-то, наверное, не очень хорошо, собственно, почему? Ну потому что 0, 0, 0, 0.

42: 0 0. И у нас как бы лист теперь выглядит следующим образом. Да, тут ещё 1 значение. Давайте я это попробую удалить сейчас. Да, хорошо. У нас ещё 1 значение. Восьмёрка, но восьмёрка имеет индекс 0.

43: 1, 2, 3. То есть она должна находиться по адресу.

44: 3 8 да 24 0 x 40 0 x 40 а тут вообще не адрес нашей восьмёрки, тут какое-то другое значение, и это на самом деле проблема, если мы работаем напрямую с оперативной.

45: Памятью, да, с такими чистыми массивами, без проверок границ, так называемое переполнение буфера, если так очень вкратце, очень забегая вперёд, но не сильно, это нам сейчас принципиально. То есть мы попали на неправильное значение, получа

46: Что нам надо где-то хранить информацию вот в этих вот пробелах, об этих пропусках, да, надо добавлять исключения. То есть какие-то индексы будут работать корректно с такой формулой, да, а какие-то нет, ну на самом деле это конечно бред. Почему? Потому что мы

47: Мы себе, таким образом, жизнь усложним, потому по той простой причине, что massive это последовательно, область, последовательно выделенная область памяти, да, если мы хотим как-то сделать по другому, то нам надо про

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

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

50: Копасити, то есть вместимость копасити, у меня будет, допустим, тут 5 элементов и count, это количество элементов в данный момент, в данный момент у меня 3 элемента, и тут у меня будет, как бы, ну, какие-то нолики, которые я не буду воспринимать, да?

51: Это просто будет резервированное место для дополнительных элементов. О, теперь, если я захочу в лист добавить новое значение, я значение создаю в нашем, как его.

52: В нашей куче, да. Так, у меня почему-то здесь нолики. Ну ладно, давайте это удалю.

53: Соответственно, я восьмёрку создаю где-то в куче, да? Так, стоп. Вот так вот. Давайте я, собственно, 0 че то удалил, да, немножечко не то, что хотел.

54: Сделал. Ну ладно. Так вот, мы создаём восьмёрку 0 00:00. Так, нет, стоп 1:00 0 ok адрес. Ссылку на неё в упрощённом варианте кладём сюда.

55: Ну, потому что мы хотим восьмёрку добавить. У нас всего лишь 3 элемента. То есть мы хотим положить восьмёрку, н, на 4 индекс, ой, в смысле, на 3 индекс, на 4 позицию. А куда это надо? Ну, 0 x, 16.

56: + 8 * 3 в 3 индекс кладём опять-таки здесь 24 0 x 16 + 0 24 0 x 40 ну, в принципе, тоже самое, что и выше, да, то есть вот сюда нам надо положить адрес восьмёрки.

57: Окей, ну, значит, берём сюда, кладём адрес 0 x 72, да, как бы вот сюда указываем, и у нас все хорошо. То есть теперь, если мы захотим обратиться к восьмёрке, мы, используя логичную формулу.

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

59: Да, то есть у нас как бы это все сюда ссылается, и что, если я теперь захочу добавить новый элемент, ну, то есть добавить, допустим, 10, у меня опять закончилось место в листе, что мне делать? И вот

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

61: Следовательно, выделенной памяти, в чем заключается идея динамического массива? Динамический массив, также известный как лист в си плюс плюсе си. Это у нас вектор, что немножко некорректно, но тем не менее, вот его идея заключается в том, что он

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

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

64: В телефонах, да, в слабых компьютерах, но памяти. Так, то несколько гигабайт, да, переведите гигабайты в байты и посмотрите, сколько там условных ячеек памяти будет. То есть нам пришлось бы двигать очень большое количество 0.

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

66: Буквально из 1 ячейки в другую копируем нолики единички. Соответственно, чем больше Ноликов, единичек, тем больше действий нам придётся выполнить, мягко говоря, печально. Более того, обратите внимание. Да, я вот так вот, все хорошо. Да, все вроде.

67: Красиво. У меня вот здесь значение в листе указывает вот сюда, да, на восьмёрку.

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

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

70: Ну, не особо хитрую, но вполне логичную вещь. У нас нет места, нам надо найти место. То есть мы берём и находим новый кусок памяти для нашего листа, но выделяем здесь в самом простом варианте.

71: В 2 раза больше места. То есть теперь мы как бы создадим новый лист, который будет хранить в себе в 2 раза больше элементов, чем предыдущий наш, то есть 10 штук. 1, 2, 3, 4, 5, 6, 7, 8, 9. Ну да.

72: Давайте ещё 10 элемент добавлю. Угу. И 10 элемент. Все, понятное дело, что здесь у нас какой-то, какие-то там нолики, какие-то рандомные значения будут не сильно, это принципиально. И дальше мы копируем все старые значения, то есть

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

74: В нём на данный момент 5 у нас здесь было, да, потому что я добавил ещё там нолик и восьмёрку каунт 5, а копасити 10.

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

76: Вполне себе нормально. То есть захотели мы добавить 10, да? Окей, расширили, так сказать, наш лист и теперь можем добавлять сюда десятку.

77: И вот этот вот кусок памяти, он, по сути, выделен под наш лист, то есть под все 10 его элементов. Соответственно, если я хочу добавить здесь десятку, то мне надо её создать где-то в куче, да, и это

78: Будет вот так вот. Че у нас там так, так, так, так, так, так. И ссылку на неё. То есть адрес этого значения положить вот сюда.

79: Ага.

80: Все это как бы указывает вот сюда. Теперь мы добавили в наш лист очередное значение, очередное значение 10 и все хорошо, да, то есть count увеличился на единичку. С точки зрения оперативной памяти у нас никаких проблем не

81: Возникло, да, мы сделали как бы лишние лишние действия, да, мы выделили побольше памяти с запасом, но что поделать? То есть так работает оперативная память и такие действия, в какой-то мере даже

82: Неэффективный, нам приходится выполнять, зато нам становится удобно. Мы как бы не задумываемся о том, как именно лист работает. То есть это как раз-таки пример абстракции, пример инкапсуляции с точки зрения объектно ориентированного программирования, да, которого как раз-таки в асинхронной части тоже курс.

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

84: Расширяется. У него есть возможность изменить свой размер, но изменяет он размер в принципе, в других ках программирования аналогично.

85: Таким образом, который я описал, ну, единственное, что там существуют разные стратегии по расширению. То есть мы не обязательно в 2 раза постоянно увеличиваем его значение. То есть вот в 5, 10, да, потом, если мы ещё раз расширим, в 20 есть

86: Альтернативный вариант, там различные функции, которые могут вам в этом помочь. Подходы в питоне это что-то типа 1 и 3. Насколько помню, коэффициент расширения вот, ну, в сишарпе у нас в 2 раза меняется, но тем не менее,

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

88: Данных это динамический массив лист вектор, который у нас как раз-таки в питоне и называется листом. Но что ж такое-то в питоне эррей?

89: А в питоне рей упс это, в общем то тоже самое, что и лист.

90: Так вот это тоже самое что лист, но с некоторым нюансом, то есть в случае эррея мы чётко указываем какой тип объектов у нас используется, то есть если в лист мы можем запихнуть например int строку.

91: Любой другой кастомный объект и что угодно, то в ray питоновский мы можем запихнуть только элементы 1 типа, то есть например Инты да, мы можем туда запихнуть только там строки какие-нибудь там и так далее и тому подобное.

92: В остальных случаях в принципе работает все точно также, то есть ray в питоне это тоже лист, но с более эффективной работой, с памятью.

93: Давайте посмотрим это более наглядно. То есть вообще то, что я вот сейчас описываю, это действительно так. То есть действительно ли мы увеличиваем и занимаем больше памяти при расширении листа, да, не особо пропорционально количеству имеющихся

94: Элементов, то есть, по идее, добавление 1 элемента может сильно увеличить занимаемую память нашим листом, да, действительно ли более эффективный рей питоновский по памяти. Ну давайте это глянем нас

95: На самом деле задача оценки того, сколько памяти занимает тот или иной объект, тем более в питоне, где все является объектом, все, все на все ссылается она не особо тривиальная, вот и стандартный сайсс оф питон.

96: Он на самом деле работает только для встроенных типов, более менее хорошо. Для коллекции он будет уже не так хорошо работать. Ну, в общем, как я уже сказал, это довольно тривиальная задача, по разному её можно решать. Но вот 1 из вариантов это у нас

97: Соответствующий метод size of из пимплера такой маленькой библиотечки, которую мы будем использовать. То есть давайте посмотрим в дебаге, запускаем и, собственно, смотрим, создаём наш массив. Что это за б.

98: Ну, если посмотреть рей, он у нас при создании рановато запустил. Он у нас при создании, при инициализации может принять в себя тайп код type код это какой-то из следующих значений, то есть

99: Б малое б большое, то есть saint интеджер, то есть знаковый целочисленный тип, и для него будет минимум выделено 1 byte 1 байт это 8 бит как раз-таки, да, если мы возьмём, например, значение побольше, то есть вы

100: Не 8 бит для 1 интеджер, а это какие интеджеры возможны? Ну это, например, беззнаковые интеджеры от нуля до двухста 55. То есть 256 значений это 2 в 8 степени 8 Ноликов, единичек, всевозможных комбинаций.

101: Бинарной системе исчисления у нас соответственно да, в 8 вот a floating point, то есть дробные какие-то значения, 4 байта может быть выделено 8 байт и так далее и тому подобное да, в данном случае мы создаём

102: Беззнаковый, то есть мы нигде не указываем знак числа, они у нас все положительные. Интежер, целочисленное значение. То есть у нас все возможные значения идут от нуля до двухста 55. Ну, я здесь взял 255, добавляем 3 элемента в наш

103: Ray тест и создаём обычный лист тест 2 ну и дальше уже давайте смотреть что же произойдёт.

104: Запускаем. Так, так, так, все как бы хорошо. Действительно, у нас вот тут вот айтем сайс, 1 1 байт, ну, e type, код б. Тут 3 элемента у нас имеются, можно посмотреть, какие-то там внутренние элементы нашего Рея.

105: То есть действительно, там, что он содержит, какой у него класс, какое-то описание, да, тут вот буквально то, что я вам только что показывал, тут буквально документация в самом объекте хранится, да, в питоне это так и

106: На самом деле очень, очень много, много, много каких-то вещей, специальных методов, о которых мы позже будем говорить. В общем, теперь довольно наглядно. Я думаю, видно, почему у нас сейчас объект будет занимать довольно много памяти в операти.

107: Смотрим, наш рей занимает 88 байт, ну это примерно, а наш лист занимает 120 byte в полтора раза больше, плюс минус, хотя и там, и там 3 элемента, там, и там 250.

108: Хранится 250 250. Ну окей, давайте добавим по 1 элементу. Добавляем наш массив обычная. Рей питоновский не увеличил своё свой размер. А вот лист

109: Увеличил до 152, да, если я добавлю ещё, опять-таки, ре, не увеличил свой размер, а лист увеличил опять на 20, там на 32 байта, да?

110: Окей. То есть в целом даже вот такой вот пример.

111: Пусть даже и примерный, да, но позволяет наглядно заметить, что в целом эррей, да, поскольку чётко знает, что все элементы будут 1 типа, что они будут занимать максимально, там, например, 1 байт, он для отдельных элементов

112: Выделяет прям 1 байт, не выделяет место под ссылку, которая должна быть, ну, под место, под адрес, который довольно большой должен быть, а он более эффективно обрабатывает хранение элементов. Давайте посмотрим, что будет, если я добавлю кучу элементов опять

113: Дебак запускаем, это нам не особо нужно. Прокручиваем сюда и смотрим 104. То есть вот эти все добавления в наш эррей привели к тому, что с 88 мы увеличили размер до 100.

114: 4 байт.

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

116: Наглядно думаю, ещё 1 нюанс, который стоит здесь проговорить. Давайте это я уберу, это я уберу, это уберу в принципе. А, нет, это я оставлю, да, мы тут добавим кучу элементов и

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

118: Мы сейчас посмотрим и адрес то у нас у массива и у листа один и тот же, да, что после добавления кучи элементов, что до этого, почему так? Ну потому что на самом деле сам объект, да, объект.

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

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

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

122: Как угодно называйте. У нас пересоздавался какой-то внутренний массив, да и, соответственно, когда мы пересоздаём его, у нас внутри ссылочка меняется 0 x. Тут, допустим, 4, а сам объект листа никуда не пропал.

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

124: Это тоже последовательно выделенная область памяти, где под каждый элемент выделяется чётко определённый

125: Объём информации, да, то есть каждый элемент занимает одинаковое количество памяти, но

126: Динамические массивы, они расширяются тем, что копируются в новое свободное место с запасом.

127: Вот пока что как-то так.