Спасибо за труд, но всё же как-то недостаточно. Я уже настроился и ожидал увидеть информацию о других стурктурах, как вдруг видео закончилось. Жду продолжения.
Алекс, спасибо огромное, для меня твой канал просто как глоток свежего воздуха и огромное вдохновение. Моя жизнь и профессия давно устоялись, и работа моя не связана с программирование и IT. Сейчас изучаю Си просто для души, в школе увлекался бэйсиком и паскалем, благодаря этому поступил в институт без экзаменов после олимпиады, потом забросил, некогда было. Отсутствие необходимости изучать то что модно и в тренде, дает возможность изучать программирование так, как мне интересно а не требуется для обретения или смены профессии. Твой канал для меня просто находка, именно та информация которую я ищу. И пусть в современном мире низкоуровневое программирование не особо нужно, а все алгоритмы разложены по полочкам и изучены, пусть. Мне нравится именно корни и основы, и я буду программировать так, как раньше, экономя байты памяти, оптимизируя какие то задачи, что бы это могло запускаться на любом примитивном железе. Это самый кайф! Спасибо!
Было бы круто от тебя видеть цикл видео про ООП, принципы правильного проектирования кода и подобное. Нравится как ты все визуализируешь, сразу все понятно становится
(...принципы правильного проектирования кода...) видео на 3 секунды. Их не существует... правильных. Они есть рзные, каждые служат своей цели. Проектирование кода... структурирование кода ещё туда-сюда. Проектируют, обычно, системы, компоненты, модули методом декомпозиции функциональной, структурной, логической, физической, организационной. 2023 год, забудьте уже про ООП, в век поведенческих моделей -- дитя рожённое сумрачным гением Гарди Буча и Ива Якобса под конец 80-х. Имеет очень ограниченое применение, для прикладных систем. ООП - как парадигма моделирования и описания реальных систем ещё более менее, но с оговорками. Но как принцип структурирования кода уже давно не выдерживает критики.
Как же круто подаётся материал! Прямо интересно смотреть и прямо сразу хочется ещё больше видео! Низкий поклон автору за такие шедевры! Всегда с нетерпением жду новые видео!
У списков есть ещё один весомый минус помимо дополнительного поля с указателем, жрущего память. Это malloc, который к тому же враппер к системному вызову alloc, который работает на VAD таблицах, которые также жрут память. Особенно когда элементы списка 10-50 байт в большинстве своём случаев, а alloc работает со страницами памяти по 4 килобайта. Это лютейший стресс для операционки. А некоторые операционки не умеют в принципе выделять память меньше страницы и получается что на элемент, в смысле на каждый элемент, размером в несколько байт улетает ровно 4 килобайта. Короче списки - величайшее зло и ошибка. Можно без них если чуть повнимательней отнестись к организации алгоритмов и структур данных.
@@MrRastler Зачем писать велосипеды? Есть уже готовый список называется ArrayList. Если нужна скорость добавления данных то установите capacity правильное значение и arrayResize ни когда не произойдет. Если что элементы списка это 32 битные ссылки, поэтому смело можно задавать капасити в 8 мегабайтов, если точно знаете что у вас в списках может быть миллион элементов
Разве malloc может выделить 4кб памяти на КАЖДЫЙ элемент? Да, минимальный размер памяти, который можно "попросить" у операционной системы - это размер страницы виртуальной памяти. Далее уже задача libc при вызове malloc постараться задействовать куски этой страницы, и только если не получилось - запрашивать у операционной системы. Это уже не говоря о всяких jemalloc с кучей эвристик - thead-local буферы для обьектов фиксированной маленькой величины и тд В крайней случае, можно выделять единым куском память память под 100, 200, 400 узлов списка и потом использовать их - реализовать pool allocator Большим недостатком при этом будет частые промахи по кэшу - но это неизбежно И все таки списки бывают довольно полезны - как без них реализовывать персистентные(ну даже персистентный стек) или lock-free (например Michael-Scott Queue) структуры?
Я делал такую базу, не подозревая, что именно о такой будут когда-то рассказывать. Нигде не учился. Пришел логично. Первый прототип базы был статический, но очень быстрый. И в момент, когда я не знал какой именно длинны будут некоторые текстовые поля, пришлось изобретать велосипед. Добавил ссылки. При удалении, информация просто не учитывалась. По факту она не удалялась. Ровно также вижу и работает Microsoft Access. Динамическая база данных при GOTO на нужный нам столбец работает медленней чем статическая, поскольку в статической можно просто умножить наш указатель на длину и мы точно попадем в начало нужной нам информации. А здесь нам уже нужно высчитывать из ссылки к ссылке пока не получим желаемую. Вначале я использовал только указатель "вперед". Но позже столкнулся с проблемой вставки информацию в середину и решил не раздвигать ячейки, не перезаписывать жёсткий диск за каждый раз, а это даже очень актуально при использовании SSD накопителя. По этому добавил указатель "назад" и это позволило мне добавлять значения в конец, но подавать пользователю это как будто данные находятся в середине. Чесно говоря не знаю что лучше прыжки или перезапись. Возможно найдутся люди умнее и заявят мол диск всегда перезаписывается. Не знаю что конкретно на физическом уровне там делается. Исходил из логики. Access будет удобней использовать, но там есть ограничения по объему памяти. Да и по скорости он проигрывает, но удобен в конструкторе, особенно на этапе создания, когда в процессе может понадобиться добавить новое поле в базу данных. А в своем движке приходится допилить функционал, чтоб поле безопасно добавить или удалить, чтоб при необходимости сжать базу (очистить от удаленных записей). Кстате, потом сделал еще один гибрид интересный где использовались два файла: один статический а другой динамический. Динамический только для текста, а в статическом были уже ссылки на точку входа информации в динамическом файле. Через 5 лет посмотрел на весь этот чудо код и офигел сколько времени было потрачено
Как всегда афигенный контент! Всё раскладываешь по полочкам и показываешь наглядный пример! Если бы ты записал серию уроков по какому-либо ЯП или технологии, я бы в запой просмотрел всё!
Тонкость на которой любят валить на собеседованиях по C# и Java: массивы всегда являются ссылочным типом и следовательно память всегда будет выделяться в управляемой куче (за исключением unsafe кода), в стеке будет находиться указатель на выделенную область памяти. В C/C++ по умолчанию массив определяется в стеке, либо с помощью malloc определяется в куче.
Спасибо за качественный контент! Подача материала отличная, сразу видно, что Автор знает о чём говорит. Могу сказать пару слов о Связанных списках: Преимущество Однонаправленного списка перед Двунаправленным в чуть меньшем потреблении памяти на каждый элемент списка и чуть более быстром выполнении некоторых функций. На этом его преимущества заканчиваются, и проявляется множество НЕпреимуществ. К примеру: Поиск/Удаление/Вставка в Двунаправленном списке можно начать как с начала, так и с конца. То-есть, если Index < Length / 2 = начинаем идти с Head-a к нужному элементу, а если Index > Length / 2 с Tail-a назад к нужному элементу. А в Однонаправленном списке тебе придётся идти всегда сначала. По-этому, зачастую, Двунаправленные списки выигрывают у Однонаправленных. Я промолчу о некоторых функциях, типа Реверса данных внутри списка или их Смещения (Не Nod-ов), там Однонаправленные списки сразу проигрывают...
Очень круто. За 13 минут благодаря крутому визуалу и грамотным объясниям вспомнил все, что в универе проходили чуть ли не целый семестр. Было бы очень круто так же разобрать более сложные структуры, вроде тех же хеш-таблиц. А ещё было бы полезно делать референсы на популярные языки, например, "массив в С - это чистый массив, а вот в плюсах - это двунаправленный связный список" Ps не надо пожалуйста тригериться, про с/с++ я написал для примера и знаю что это не так
Шок. Вся правда о массивах. Материал, запрещённый в официальной литературе по компьютерным технологиям. По существу, материал качественный, по-моему, подход автора серьёзен и строг :-)
Кстати, если тебе понравится такая тема, то предлагаю записать видео о двойной буферизации (когда используется два буфера для байтов данных). Это очень связано с тематикой канала, потому что такие алгоритмы помогают избежать например мерцания экрана. Но вообщем ты показываешь правильные вещи, респект и удачи в дальнейшем желаю.
Видео класс. Есть код для более глубокого ознакомления, тут же есть принципиальная картинка что происходит. Очень удобно. А звуковое оформление вообще топ.
Можно довольно несложным путём сделать, чтобы операция добавления и удаления в массив работала за O(1). Для этого нужно при добавлении нового элемента в массив в ситуации, когда свободных "ячеек" нет - создавать новый массив не с размером N+1, а с размером N*2. А при удалении - если количество оставшихся после удаления элементов в массиве меньше, чем половина длины - то нужно создать новый массив, размером в 2 раза меньше, и перенести туда все оставшиеся элементы. Допустим, что у нас изначально массив размера 10, и мы добавляем туда 10 элементов. Тогда при добавлении первого элемента - у нас произойдёт создание нового массива, размером 20 + копирование 10 исходных элементов + добавление 1 элемента - т.е. 11 операций. При этом добавление остальных 9 элементов - займёт 9 операций. В сумме получится, что добавление 10 элементов заняло 20 операций. А значит, добавление 1 элемента заняло, в среднем, 2 операции. Если добавляем 100 элементов при изначальном количество 10 - то количество операций будет такое: 11 + 9 = 20 - чтобы добавить 10 элементов 21 + 19 = 40 - чтобы добавить ещё 20 элементов 41 + 39 = 80 - чтобы добавить ещё 40 элементов 81 + 29 = 110 - чтобы добавить оставшиеся 30 элементов. Получается, суммарное количество операций - 250, что в среднем представляет из себя 2.5 операции на добавление 1 элемента. При 1000 элементов - это будет так: 20 + 40 + 80 + 160 + 320 + 641 + 379 = 1640. Получится, в среднем, 1.64 операции для добавления 1 элемента. При 10000 элементов - это будет: 20 + 40 + 80 + 160 + 320 + 640 + 1280 + 2560 + 5121 + 4899 = 15120 - уже 1.512 операций для добавления одного элемента. Если так продолжать - то в пределе количество операций для добавления одного элемента будет 1 - что и является асимптотикой O(1). Чтобы было в среднем ровно 1 операция на добавление - нужно, чтобы на добавление M элементов нужно было M операций. Худший вариант, который может быть - это когда у нас изначально 1 элемент в массиве. В такой ситуации - добавление M элементов потребует 2+4+8+16+... операций - из которых половина уйдёт на дублирование массив, а половина - на добавление M элементов. Количество шагов (n) можно рассчитать как логарифм по основание 2 от M, округлённый в нижнюю сторону + разница между M и этой суммой оставшихся элементов - но это значение не больше M - поэтому общее количество шагов можно считать как логарифм от M, округлённый в верхнюю сторону. Сумма такой геометрической прогрессии - это 2*(2^n-1) =2^(n+1)-2. Учитывая, что n - количество шагов - это ⌈log_2_M⌉, получится, что сложность добавления M элементов - это O(2^(⌈log_2_M⌉+1)-2) = O(2*(M+1)-2) = O(2*M) = O(M) (я предполагаю, что, в худшем случае, округление вверх даст M+1). Ну и отсюда вывод, что добавление одного элемента - O(1). Немного кривоватое доказательство - но какое есть. Примерно аналогичные рассуждения и для удаления.
Название видео ввело в заблуждение. Ожидал увидеть допустим хоть и краткий, но разбор/сравнение всех основных структур данных. По факту в видео лишь примитивная база, и то из двух элементов. Хоть речь и шла про списки, однако самый главный и важный список так и не был разобран: обёртка над статическим массивом, в разных языках называемая List(C#, Java), vector(C++), Array(Typescript). В название стоило бы дописать, что речь идёт об односвязном и д двусвязном списках
5:36 Поиск в массиве имеет сложность О(1) ?? Не Поиск, а Доступ! Поиск как раз в неотсортированном массиве O(n), а в отсортированном зависит от метода, но все равно НЕ О(1)
6:20 в java приходиться вручную создавать новый массив перезаписывать в него данные, а потом добавлять что хотел, по этому я массивы уже давно забыл...
Это конечно всё простенько, просто ужас сколько всего есть сложного в информатике, и поэтому становиться интересно. А самое главное, что математика тут играет ключевую роль, она помогает анализировать алгоритмы, описывать наш окружающий мир и тд. Поэтому самым главным инструментом программиста является именно математика.
"Для работы с данными у нас есть три основных операции - это запись данных в память, чтение данных из памяти и их удаление ..." Это не операции, а скорее манипуляции с данными - перестановки данных местами. Операция - это то нечто, которое из одних данных делает другие данные. К примеру, есть операция сложения данных (чисел) - из пары данных чисел мы делаем третье - сумму чисел. Но основные операции которые выполняет компьютер - это всё же не сложение и умножение (и уж тем более не "чтение" и 'запись") - а _сравнение_ данных. Равно - не равно, больше - меньше, а также привязанные к этим сравнениям _логические_ операции "и", "или", "не". Сиречь логическое сложение, умножение и отрицание с дальнейшим ветвлением алгоритма (который в свою очередь тоже является _данными_ ) Но честно говоря, после такой "вводной" про "операции", с которой начинается ролик, комментировать его дальше уже смысла нет. Некорректность (мягкое слово) изначальных посылок ведёт к бредовости последующих рассуждений про массивы, очереди и хэш-таблицы. Автор ролика явно не понимает (и не даёт ответ на вопрос): "а нахрена всё это нужно???"
строго говоря же ведь динамический массив не может тоже свой размер менять. Можно его удалить и аллоцировать новый, а вот resize насколько я помню невозможен на низком уровне. При этом мы присваиваем старому указателю адрес на новый динамический массив. При этом указатель сам по себе можно не связывать в своём мышлении с динамическим массивом. Так как он может быть перезаписан другим адресом. Мы можем вообще создать ссылку на динамический массив, а старый указатель удалить, удалить ссылку, сделать новый указатель или ссылку и присвоить в него адрес массива. В общем не так важно каким способом мы помним по какому адресу хранится динамический массив, как много указателей для этого используем. Динамический массив ничего не почувствует, потому что это отдельная сущность. resize же на верхнем уровне работает на основе высвобождения памяти и аллокации нового участка памяти и копирования указателя на участок этой памяти в объект-обёртку, который обслуживает динамический массив.
У тебя хорошо поставлен голос, хорошо рассказываешь, но иногда убаюкивает. Какой-то интересный тон есть :). Такое ощущение, что сейчас в транс войду. Наверно музыка еще создает трассовое состояние.
по поводу поиска в массиве хочу сказать что O(1) это доступ на адрес так как в Си например *arr == arr[0] , получается что первый элемент это так же указатель на массив, и это облегчает найти нужный нам адрес но никак элемент который лежит в адресе, а поиск элемента уже O(n).
все распространенные языки при необходимости увеличения размера автоматического массива увеличивают его размер в 2 или 3 раза. Так что чаще всего добавление в конец массива делается за константное время.
Это неправда, просто по причине того, что чем больше был исходный массив, тем больше нужно процессорного времени для того, чтобы скопировать элементы из старого массива в новый
@@Dmytro-Tsymbaliuk Амортизационно за константное время - чем больше массив, тем реже приходится делать это копирование. Если массив размера 1000, его расшили в 2 раза, у него 1000 свободных ячеек, значит следующее копирование произойдет через 1000 вставок. Потом через 2000 и тд - если массив стал размера N, то суммарно копирований было 1 + 2 + 4 + 8 + ... + N = 2 * N - 1, на каждую вставку два копирования это константа. Но можно любую вставку делать за константу, если копировать элементы из старого массива в новый - когда память в старом массиве кончается, выделяем новый и вставляем туда (по нужному индексу), далее при каждой вставке вставляем элемент в новый массив и копируем 2 элемента из старого массива в новый. Когда новый массив будет заполнен, старый уже будет пустой - его можно удалить. Правда, выделение памяти не совсем константная операция, но это уже другая история
Алекс, я нашел чела что вырвал из внутри все мои мысли... Это ты. Но к сожелению мне сложно найти то чего я хочу достичь, приходиться идти по заданным тропам... Мне кажется только ты поймешь из моего окружения! Я начал учебу на платформе (не буду говорить какую) она разделена на 2 курса изучения питона и Фреймворк Джанго... Как я закончил изучение языка стало на столько не интересно что учу через силу... Чую что учу не то что хотел... Но приходиться учить что б хоть как то окунуться в ит. Есть друг что прыгает но его уровень такой же :"просто собирать пазл и обрабатывать кучу инфы" помоги плиз я с детства мечтал быть программистом но последние лет 10 с цифрами даже не общался( пошел по юриспруденции) спасай бро
Я писал игровой движок, и у меня возникла необходимость хранить кучу объектов в одном массиве с частыми добавлениями в конец, произвольными удалениями и перебором всех элементов. Для этой задачи отлично подошёл двусвязный список, так как в нём можно было сделать произвольное удаление за O(1) за счёт комбинации его с перебором всех элементов - я по ссылкам помечаю объекты как удалённые и при переборе вычищаю их.
Не верно. Для таких вещей лучше всего использовать стандартный ArrayList из java. По моему в плюсах это std:vector но я не уверен. В ArrayList всегда можно обращаться к элементам по индексу. Если нужно не по индексу а по ключю то тогда HashMap. Главное что бы элементы списка были ссылки. В java все классы это ссылки. Там не возможно создать обьект который будет хранится по значению как структуры в шарпе. По этому каждый элемент твоего ArrayList - это 32битное ссылка. Создаешь список с параметром capacity который равен макс размеру твоего ArrayList. Если будет нештатная ситуация а оббем списка превысит capacity то ни чего страшного, этот класс сделает resize автоматом, просто эта функция работает долго поэтому лучше сразу задать правильный capacity
@@serhiis_ я делаю случайные удаления, в обычном массиве они делаются за O(n), в то время как в двусвязном списке они делаются за O(1), и конкретно в моём решении абсолютно все операции над двусвязным списком производятся за O(1), так как я не делаю обращения по индексу, так что лучше использовать именно его
@@NullzeRT дык я писал не за обычный массив а за ArrayList. Обычный массив лет 20 как ни кто не использует. в плюсах это std:vector как минимум. Ну если у тебя операций удаления ОЧЕНЬ много в минуту то тогда есть LinkedList. Это тоже массив, только он разбитый на двусвязный список по 10-20 элементов на каждый подмассив. Число элементов настраивается. Аналогичная структура есть и в с++, уже не помню какая лет 15 на плюсах ни чего не писал
возможно я не совсем понял, но связанный список где хранится? в массиве? в чем смысл тогда что то выдумывать если по факту это массив пользовательских типов данных? ИЛИ ЭТО И ЕСТЬ СУТЬ ВИДЕО что есть массивы и есть массивы с пользовательскими типами данных, только одни так и называются массивами данных а другие - связанные списки (ну что б сложней было разобраться)
Не совсем верно говорить, что статический массив размещается только на стеке. short * arr = (short *)malloc(Нужное колл-во байт); Ты же понимаешь, что это тоже массив и тоже статический, только размещен в куче? О динамическом массиве мы говорим, когда речь идет о каком-то контейнере (классе ) у которого уже описаны все механизмы управления, в том числе и перевыделение памяти, что по сути происходит , что мы просто ("уничтожаем") высвобождаем не нужный блок памяти переписав сперва все нужное в новый выделеный блок нужного нам размера, и адрес у указателя меняем на новый непрерывный блок.
Брат, ты хочешь сказать что push_back() к вектору в c++ работает за О(n), если нет, то что ты пытался сказать? Брат, это было бы полезное видео если бы ты объяснил как увеличивать массив так, чтобы амортизированное время работы каждого шага было О(1), а так твоё видео скорее запутывает новичков, чем рассказывает про массивы
Вектор в С++ это не простой массив. Это надстройка над обычным массивом, которая при вставке и удалении может автоматически менять размер того массива, где все и хранится. Причем, изменение размера массива происходит не каждый раз при вставке/удалении. Вектор при вставке новых значений, если массив заполнился, выделяет больше места для массива, но с запасом, чтобы при еще нескольких вставках не надо было по новой выделять место. В видео рассказывается про обычный, "сырой" массив, которым надо вручную манипулировать. А про "как увеличивать массив так, чтобы амортизированное время работы каждого шага было О(1)", я не думаю, что такое возможно. Выделение новой памяти большего размера для вставки значений происходит не просто так. За пределами массива тоже есть какие-то данные, и нельзя допустить, чтобы они стерлись или перезаписались, ведь из-за этого может пострадать работа вообще другой программы или ОС вылетит
@@YuraSamusenko если при заполнении массива каждый раз создавать массив в два раза большего размера, то легко посчитать, что в среднем каждая операция добавления будет работать за О(1)(n+n/2+n/4+n/8+…=2n, 2n/n = 2, 2 это O(1) на добавление), это и реализовано в c++ или в python или в любом другом современном языке программирования и мне кажется, что без этого рассказ о массиве является не полным
@@Ilya-kondakov у вас с математикой проблемы, чем больше массив, тем больше нужно времени на то, чтобы скопировать данные из старого в новый, так что нифига не O(1)
@@Dmytro-Tsymbaliuk в winAPI есть функция reallocate которая добавляет памяти, если есть такая возможность. Вроде в boost с++ эта функция есть. Уже не помню. В общем память в ОЗУ фрагментирована и если оЗУ не загружена под завязку то есть большой шанс что realloc пройдет успешно и не нужно ни чего копировать
Тут есть видео об отличиях кодера от программиста, в котором довольно много токсичных высказываний на тему тех, кто идёт в разработку только из-за высоких зарплат Реклама курсов после этого - апогей продажности
Поиск в массиве имеет сложность O(n), это доступ к конкретному элементу по известному индексу O(1).
оговорочка
Спасибо за труд, но всё же как-то недостаточно. Я уже настроился и ожидал увидеть информацию о других стурктурах, как вдруг видео закончилось. Жду продолжения.
видео называется "вся правда о массивах"
Очень хорошая подача, сам до конца не знаю как устроены все структуры, поэтому жду продолжения!
Алекс, спасибо огромное, для меня твой канал просто как глоток свежего воздуха и огромное вдохновение. Моя жизнь и профессия давно устоялись, и работа моя не связана с программирование и IT. Сейчас изучаю Си просто для души, в школе увлекался бэйсиком и паскалем, благодаря этому поступил в институт без экзаменов после олимпиады, потом забросил, некогда было. Отсутствие необходимости изучать то что модно и в тренде, дает возможность изучать программирование так, как мне интересно а не требуется для обретения или смены профессии. Твой канал для меня просто находка, именно та информация которую я ищу. И пусть в современном мире низкоуровневое программирование не особо нужно, а все алгоритмы разложены по полочкам и изучены, пусть. Мне нравится именно корни и основы, и я буду программировать так, как раньше, экономя байты памяти, оптимизируя какие то задачи, что бы это могло запускаться на любом примитивном железе. Это самый кайф! Спасибо!
Красавчик, Алекс. Контент пушка, пили дальше. Будь уверен, благое дело делаешь, сил тебе, хорошей работы и здоровья, брат!
Самый великолепный канал по програмированию
Было бы круто от тебя видеть цикл видео про ООП, принципы правильного проектирования кода и подобное. Нравится как ты все визуализируешь, сразу все понятно становится
Рано или поздно все сводится к процедурному программированию.
@Пиво и приколы Перегорание
@@DocNight процессор сгорает?
@@DocNight оаоаоаоао. Как круто.
(...принципы правильного проектирования кода...) видео на 3 секунды. Их не существует... правильных. Они есть рзные, каждые служат своей цели. Проектирование кода... структурирование кода ещё туда-сюда.
Проектируют, обычно, системы, компоненты, модули методом декомпозиции функциональной, структурной, логической, физической, организационной.
2023 год, забудьте уже про ООП, в век поведенческих моделей -- дитя рожённое сумрачным гением Гарди Буча и Ива Якобса под конец 80-х. Имеет очень ограниченое применение, для прикладных систем.
ООП - как парадигма моделирования и описания реальных систем ещё более менее, но с оговорками. Но как принцип структурирования кода уже давно не выдерживает критики.
Жду объяснение следующих структур СПС за видео.
Как же круто подаётся материал! Прямо интересно смотреть и прямо сразу хочется ещё больше видео!
Низкий поклон автору за такие шедевры! Всегда с нетерпением жду новые видео!
Великолепно изложено! Огромная благодарность за титанический труд!
Непревзойденно! Браво! Супер важное и сложное простым языком, понятной картинкой, стильно даже! Ты лучший!
У списков есть ещё один весомый минус помимо дополнительного поля с указателем, жрущего память. Это malloc, который к тому же враппер к системному вызову alloc, который работает на VAD таблицах, которые также жрут память. Особенно когда элементы списка 10-50 байт в большинстве своём случаев, а alloc работает со страницами памяти по 4 килобайта. Это лютейший стресс для операционки. А некоторые операционки не умеют в принципе выделять память меньше страницы и получается что на элемент, в смысле на каждый элемент, размером в несколько байт улетает ровно 4 килобайта. Короче списки - величайшее зло и ошибка. Можно без них если чуть повнимательней отнестись к организации алгоритмов и структур данных.
Отличное замечание. И вообще, было бы неплохо автору указать как выделяться память ОС, из этого можно пересмотреть вообще подход к данным.
@@MrRastler Зачем писать велосипеды? Есть уже готовый список называется ArrayList. Если нужна скорость добавления данных то установите capacity правильное значение и arrayResize ни когда не произойдет. Если что элементы списка это 32 битные ссылки, поэтому смело можно задавать капасити в 8 мегабайтов, если точно знаете что у вас в списках может быть миллион элементов
Разве malloc может выделить 4кб памяти на КАЖДЫЙ элемент? Да, минимальный размер памяти, который можно "попросить" у операционной системы - это размер страницы виртуальной памяти. Далее уже задача libc при вызове malloc постараться задействовать куски этой страницы, и только если не получилось - запрашивать у операционной системы. Это уже не говоря о всяких jemalloc с кучей эвристик - thead-local буферы для обьектов фиксированной маленькой величины и тд
В крайней случае, можно выделять единым куском память память под 100, 200, 400 узлов списка и потом использовать их - реализовать pool allocator
Большим недостатком при этом будет частые промахи по кэшу - но это неизбежно
И все таки списки бывают довольно полезны - как без них реализовывать персистентные(ну даже персистентный стек) или lock-free (например Michael-Scott Queue) структуры?
Я делал такую базу, не подозревая, что именно о такой будут когда-то рассказывать. Нигде не учился. Пришел логично. Первый прототип базы был статический, но очень быстрый. И в момент, когда я не знал какой именно длинны будут некоторые текстовые поля, пришлось изобретать велосипед. Добавил ссылки. При удалении, информация просто не учитывалась. По факту она не удалялась. Ровно также вижу и работает Microsoft Access. Динамическая база данных при GOTO на нужный нам столбец работает медленней чем статическая, поскольку в статической можно просто умножить наш указатель на длину и мы точно попадем в начало нужной нам информации. А здесь нам уже нужно высчитывать из ссылки к ссылке пока не получим желаемую. Вначале я использовал только указатель "вперед". Но позже столкнулся с проблемой вставки информацию в середину и решил не раздвигать ячейки, не перезаписывать жёсткий диск за каждый раз, а это даже очень актуально при использовании SSD накопителя. По этому добавил указатель "назад" и это позволило мне добавлять значения в конец, но подавать пользователю это как будто данные находятся в середине. Чесно говоря не знаю что лучше прыжки или перезапись. Возможно найдутся люди умнее и заявят мол диск всегда перезаписывается. Не знаю что конкретно на физическом уровне там делается. Исходил из логики. Access будет удобней использовать, но там есть ограничения по объему памяти. Да и по скорости он проигрывает, но удобен в конструкторе, особенно на этапе создания, когда в процессе может понадобиться добавить новое поле в базу данных. А в своем движке приходится допилить функционал, чтоб поле безопасно добавить или удалить, чтоб при необходимости сжать базу (очистить от удаленных записей). Кстате, потом сделал еще один гибрид интересный где использовались два файла: один статический а другой динамический. Динамический только для текста, а в статическом были уже ссылки на точку входа информации в динамическом файле. Через 5 лет посмотрел на весь этот чудо код и офигел сколько времени было потрачено
Как всегда афигенный контент! Всё раскладываешь по полочкам и показываешь наглядный пример! Если бы ты записал серию уроков по какому-либо ЯП или технологии, я бы в запой просмотрел всё!
Благодарю Вас за ваш труд! Очень интересная подача материала. Не жалею, что нашёл этот канал.
Братан, хорошо, давай-давай вперёд! Контент вообще в кайф, красавчик! Можно вот этого и того почаще?
Спасибо за выпуск!👍
Реально так контент из которого, начинающим и даже программистам с опытом, нужно впитывать каждое слово.
Я сейчас как раз изучаю массивы в ассемблере. Так как ассемблер самый низкоуровневый, то это видео для меня стает очень актуальным. Спасибо
Подача и полезность в одном видео - это редкость! красава
Возвращаюсь к каждому видео по 3 раза, и как в хорошей книге нахожу что-то новое. Благодарю!
Случайно попал на видос! Подписываюсь) Автор крут!
Массивы: чёрт нас раскрыли, сваливаем
Тонкость на которой любят валить на собеседованиях по C# и Java: массивы всегда являются ссылочным типом и следовательно память всегда будет выделяться в управляемой куче (за исключением unsafe кода), в стеке будет находиться указатель на выделенную область памяти. В C/C++ по умолчанию массив определяется в стеке, либо с помощью malloc определяется в куче.
Круто.
Я наконец-то стал что-то понимать!
Спасибо, друг!
Спасибо, продолжай в том же духе!
Массивы и связанные списки это так сказать база, в книге «Грокаем алгоритмы» очень доходчиво объяснены.
Спасибо за качественный контент! Подача материала отличная, сразу видно, что Автор знает о чём говорит.
Могу сказать пару слов о Связанных списках:
Преимущество Однонаправленного списка перед Двунаправленным в чуть меньшем потреблении памяти на каждый элемент списка и чуть более быстром выполнении некоторых функций.
На этом его преимущества заканчиваются, и проявляется множество НЕпреимуществ.
К примеру:
Поиск/Удаление/Вставка в Двунаправленном списке можно начать как с начала, так и с конца.
То-есть, если Index < Length / 2 = начинаем идти с Head-a к нужному элементу,
а если Index > Length / 2 с Tail-a назад к нужному элементу.
А в Однонаправленном списке тебе придётся идти всегда сначала.
По-этому, зачастую, Двунаправленные списки выигрывают у Однонаправленных.
Я промолчу о некоторых функциях, типа Реверса данных внутри списка или их Смещения (Не Nod-ов), там Однонаправленные списки сразу проигрывают...
Респект, брачо! всего тебе хорошего и побольше!
Я кнш это всё знаю, но я не могу пропустить ни один твой видос. Они прекрасны😍
Большое спасибо!
Братан, хорош, давай-давай вперёд! Контент вообще в кайф, красавчик! Можно вот этого и того и почаще?
Очень круто. За 13 минут благодаря крутому визуалу и грамотным объясниям вспомнил все, что в универе проходили чуть ли не целый семестр.
Было бы очень круто так же разобрать более сложные структуры, вроде тех же хеш-таблиц.
А ещё было бы полезно делать референсы на популярные языки, например, "массив в С - это чистый массив, а вот в плюсах - это двунаправленный связный список"
Ps не надо пожалуйста тригериться, про с/с++ я написал для примера и знаю что это не так
Кольцевой однонаправленный список -> план эвакуации при пожаре.
Это просто щииииииииикарноооооооо! Топовый котент! Все очень наглядно) огромное спасибо за Ваш труд
Единственный канал где не проматываю рекламу, чтоб поддержать автора.
Интеграцию?😂
@@Долой_Уныние да
Шок. Вся правда о массивах. Материал, запрещённый в официальной литературе по компьютерным технологиям. По существу, материал качественный, по-моему, подход автора серьёзен и строг :-)
Кстати, если тебе понравится такая тема, то предлагаю записать видео о двойной буферизации (когда используется два буфера для байтов данных). Это очень связано с тематикой канала, потому что такие алгоритмы помогают избежать например мерцания экрана. Но вообщем ты показываешь правильные вещи, респект и удачи в дальнейшем желаю.
gold in front of my eyes, very well done content. Thank you
Супер объяснение, кратко и четко
Видео класс. Есть код для более глубокого ознакомления, тут же есть принципиальная картинка что происходит. Очень удобно.
А звуковое оформление вообще топ.
Отлично!
Отличная подача... Спасибо.
Можно довольно несложным путём сделать, чтобы операция добавления и удаления в массив работала за O(1).
Для этого нужно при добавлении нового элемента в массив в ситуации, когда свободных "ячеек" нет - создавать новый массив не с размером N+1, а с размером N*2.
А при удалении - если количество оставшихся после удаления элементов в массиве меньше, чем половина длины - то нужно создать новый массив, размером в 2 раза меньше, и перенести туда все оставшиеся элементы.
Допустим, что у нас изначально массив размера 10, и мы добавляем туда 10 элементов. Тогда при добавлении первого элемента - у нас произойдёт создание нового массива, размером 20 + копирование 10 исходных элементов + добавление 1 элемента - т.е. 11 операций. При этом добавление остальных 9 элементов - займёт 9 операций.
В сумме получится, что добавление 10 элементов заняло 20 операций. А значит, добавление 1 элемента заняло, в среднем, 2 операции.
Если добавляем 100 элементов при изначальном количество 10 - то количество операций будет такое:
11 + 9 = 20 - чтобы добавить 10 элементов
21 + 19 = 40 - чтобы добавить ещё 20 элементов
41 + 39 = 80 - чтобы добавить ещё 40 элементов
81 + 29 = 110 - чтобы добавить оставшиеся 30 элементов.
Получается, суммарное количество операций - 250, что в среднем представляет из себя 2.5 операции на добавление 1 элемента.
При 1000 элементов - это будет так:
20 + 40 + 80 + 160 + 320 + 641 + 379 = 1640.
Получится, в среднем, 1.64 операции для добавления 1 элемента.
При 10000 элементов - это будет:
20 + 40 + 80 + 160 + 320 + 640 + 1280 + 2560 + 5121 + 4899 = 15120 - уже 1.512 операций для добавления одного элемента.
Если так продолжать - то в пределе количество операций для добавления одного элемента будет 1 - что и является асимптотикой O(1).
Чтобы было в среднем ровно 1 операция на добавление - нужно, чтобы на добавление M элементов нужно было M операций.
Худший вариант, который может быть - это когда у нас изначально 1 элемент в массиве.
В такой ситуации - добавление M элементов потребует 2+4+8+16+... операций - из которых половина уйдёт на дублирование массив, а половина - на добавление M элементов.
Количество шагов (n) можно рассчитать как логарифм по основание 2 от M, округлённый в нижнюю сторону + разница между M и этой суммой оставшихся элементов - но это значение не больше M - поэтому общее количество шагов можно считать как логарифм от M, округлённый в верхнюю сторону.
Сумма такой геометрической прогрессии - это 2*(2^n-1) =2^(n+1)-2. Учитывая, что n - количество шагов - это ⌈log_2_M⌉, получится, что сложность добавления M элементов - это O(2^(⌈log_2_M⌉+1)-2) = O(2*(M+1)-2) = O(2*M) = O(M) (я предполагаю, что, в худшем случае, округление вверх даст M+1).
Ну и отсюда вывод, что добавление одного элемента - O(1).
Немного кривоватое доказательство - но какое есть.
Примерно аналогичные рассуждения и для удаления.
Сделай видео, как монтируешь видео.
Сделай видео по алгоритмам! Понятно, что по хорошему оно займет не один час, но мне бы очень хотелось увидеть такое видео на твоём канале
Огромное спасибо автору! Очень полезная информация
Афигенный ролик только бы вот были бы примеры с питоном, с++
Не смотрел, но уже понял, что топ
Спасибо, очень крутые видео!
полезное дело делаешь, спасибо, продолжай!
Вот это реально, больше чем просто лайк
Название видео ввело в заблуждение. Ожидал увидеть допустим хоть и краткий, но разбор/сравнение всех основных структур данных. По факту в видео лишь примитивная база, и то из двух элементов. Хоть речь и шла про списки, однако самый главный и важный список так и не был разобран: обёртка над статическим массивом, в разных языках называемая List(C#, Java), vector(C++), Array(Typescript). В название стоило бы дописать, что речь идёт об односвязном и д двусвязном списках
Крутой видос, не душни.
Контент просто огонь !!!
5:36 Поиск в массиве имеет сложность О(1) ?? Не Поиск, а Доступ! Поиск как раз в неотсортированном массиве O(n), а в отсортированном зависит от метода, но все равно НЕ О(1)
6:20 в java приходиться вручную создавать новый массив перезаписывать в него данные, а потом добавлять что хотел, по этому я массивы уже давно забыл...
6:50 сдвигать в java тоже самому надо все...
Круто, спасибо за контент.
Спасибо за видео!
Спасиба бальшой ты очен памог
Это конечно всё простенько, просто ужас сколько всего есть сложного в информатике, и поэтому становиться интересно. А самое главное, что математика тут играет ключевую роль, она помогает анализировать алгоритмы, описывать наш окружающий мир и тд. Поэтому самым главным инструментом программиста является именно математика.
Новый водосток подъехал, так ждал, так ждал
"Для работы с данными у нас есть три основных операции - это запись данных в память, чтение данных из памяти и их удаление ..."
Это не операции, а скорее манипуляции с данными - перестановки данных местами. Операция - это то нечто, которое из одних данных делает другие данные. К примеру, есть операция сложения данных (чисел) - из пары данных чисел мы делаем третье - сумму чисел.
Но основные операции которые выполняет компьютер - это всё же не сложение и умножение (и уж тем более не "чтение" и 'запись") - а _сравнение_ данных. Равно - не равно, больше - меньше, а также привязанные к этим сравнениям _логические_ операции "и", "или", "не". Сиречь логическое сложение, умножение и отрицание с дальнейшим ветвлением алгоритма (который в свою очередь тоже является _данными_ )
Но честно говоря, после такой "вводной" про "операции", с которой начинается ролик, комментировать его дальше уже смысла нет. Некорректность (мягкое слово) изначальных посылок ведёт к бредовости последующих рассуждений про массивы, очереди и хэш-таблицы. Автор ролика явно не понимает (и не даёт ответ на вопрос): "а нахрена всё это нужно???"
Ничего не понял, но очень интересно. Жаль что мой уровень программирования пока еще слишком маленький что бы понимать такие вещи.
строго говоря же ведь динамический массив не может тоже свой размер менять. Можно его удалить и аллоцировать новый, а вот resize насколько я помню невозможен на низком уровне. При этом мы присваиваем старому указателю адрес на новый динамический массив. При этом указатель сам по себе можно не связывать в своём мышлении с динамическим массивом. Так как он может быть перезаписан другим адресом. Мы можем вообще создать ссылку на динамический массив, а старый указатель удалить, удалить ссылку, сделать новый указатель или ссылку и присвоить в него адрес массива. В общем не так важно каким способом мы помним по какому адресу хранится динамический массив, как много указателей для этого используем. Динамический массив ничего не почувствует, потому что это отдельная сущность. resize же на верхнем уровне работает на основе высвобождения памяти и аллокации нового участка памяти и копирования указателя на участок этой памяти в объект-обёртку, который обслуживает динамический массив.
Ура🎉 новое видео
Была бы троичная система, мы бы меньше упоминали о несовершенстве компьютера. Однако эту развилку уже проехали, назад пути нет.
Помню в древних проектах создавали классы Array.
Я думал это из-за отсутствия std::vector.
Сейчас понимаю, что так работать с массивами проще.
круто, спасибо!
поиск в массиве по индексу имеет сложность О(1)
а по значению - перебором O(n)
У тебя хорошо поставлен голос, хорошо рассказываешь, но иногда убаюкивает. Какой-то интересный тон есть :). Такое ощущение, что сейчас в транс войду. Наверно музыка еще создает трассовое состояние.
Я изучал это на 1 курсе универа и реализовывал на C++
Только начал писать курсовую,на тему алгоритмов сортировки
Приятель, наверно только СВЯЗНЫЕ списки, а не связанные. Или они в узлы связаны?
интересно,всегда забываю про удаление, потому что это по сути обычная запись
Спасибо за инфу! Стал не много умнее)
Реклама skyeng - не знаю как зашквариться сильнее. :)
не задонатить автору - вот как
по поводу поиска в массиве хочу сказать что O(1) это доступ на адрес так как в Си например *arr == arr[0] , получается что первый элемент это так же указатель на массив, и это облегчает найти нужный нам адрес но никак элемент который лежит в адресе, а поиск элемента уже O(n).
Я бы хотел попросить о видео по расчёту сложности алгоритмов 🙏
Спасибо!
Молю, сделай видео про процессы и потоки
11:57 в схеме опечатка?4 узел должен с 3 свяываться
все распространенные языки при необходимости увеличения размера автоматического массива увеличивают его размер в 2 или 3 раза. Так что чаще всего добавление в конец массива делается за константное время.
Это неправда, просто по причине того, что чем больше был исходный массив, тем больше нужно процессорного времени для того, чтобы скопировать элементы из старого массива в новый
@@Dmytro-Tsymbaliuk Амортизационно за константное время - чем больше массив, тем реже приходится делать это копирование. Если массив размера 1000, его расшили в 2 раза, у него 1000 свободных ячеек, значит следующее копирование произойдет через 1000 вставок. Потом через 2000 и тд - если массив стал размера N, то суммарно копирований было 1 + 2 + 4 + 8 + ... + N = 2 * N - 1, на каждую вставку два копирования это константа. Но можно любую вставку делать за константу, если копировать элементы из старого массива в новый - когда память в старом массиве кончается, выделяем новый и вставляем туда (по нужному индексу), далее при каждой вставке вставляем элемент в новый массив и копируем 2 элемента из старого массива в новый. Когда новый массив будет заполнен, старый уже будет пустой - его можно удалить. Правда, выделение памяти не совсем константная операция, но это уже другая история
@@АлексейКутасов-п7и копирование не константа, а O(n)
Автору огромное спасибо за работу! А можешь подсказать что за фоновая музыка играет? Мне кажется она идеально подошла бы во время работы
Алекс, я нашел чела что вырвал из внутри все мои мысли... Это ты. Но к сожелению мне сложно найти то чего я хочу достичь, приходиться идти по заданным тропам... Мне кажется только ты поймешь из моего окружения! Я начал учебу на платформе (не буду говорить какую) она разделена на 2 курса изучения питона и Фреймворк Джанго... Как я закончил изучение языка стало на столько не интересно что учу через силу... Чую что учу не то что хотел... Но приходиться учить что б хоть как то окунуться в ит. Есть друг что прыгает но его уровень такой же :"просто собирать пазл и обрабатывать кучу инфы" помоги плиз я с детства мечтал быть программистом но последние лет 10 с цифрами даже не общался( пошел по юриспруденции) спасай бро
Я писал игровой движок, и у меня возникла необходимость хранить кучу объектов в одном массиве с частыми добавлениями в конец, произвольными удалениями и перебором всех элементов. Для этой задачи отлично подошёл двусвязный список, так как в нём можно было сделать произвольное удаление за O(1) за счёт комбинации его с перебором всех элементов - я по ссылкам помечаю объекты как удалённые и при переборе вычищаю их.
Не верно. Для таких вещей лучше всего использовать стандартный ArrayList из java. По моему в плюсах это std:vector но я не уверен. В ArrayList всегда можно обращаться к элементам по индексу. Если нужно не по индексу а по ключю то тогда HashMap. Главное что бы элементы списка были ссылки. В java все классы это ссылки. Там не возможно создать обьект который будет хранится по значению как структуры в шарпе. По этому каждый элемент твоего ArrayList - это 32битное ссылка. Создаешь список с параметром capacity который равен макс размеру твоего ArrayList. Если будет нештатная ситуация а оббем списка превысит capacity то ни чего страшного, этот класс сделает resize автоматом, просто эта функция работает долго поэтому лучше сразу задать правильный capacity
@@serhiis_ я делаю случайные удаления, в обычном массиве они делаются за O(n), в то время как в двусвязном списке они делаются за O(1), и конкретно в моём решении абсолютно все операции над двусвязным списком производятся за O(1), так как я не делаю обращения по индексу, так что лучше использовать именно его
а перебор всех элементов не даёт дополнительной сложности, так как мне в любом случае надо перебирать всё
@@NullzeRT дык я писал не за обычный массив а за ArrayList. Обычный массив лет 20 как ни кто не использует. в плюсах это std:vector как минимум. Ну если у тебя операций удаления ОЧЕНЬ много в минуту то тогда есть LinkedList. Это тоже массив, только он разбитый на двусвязный список по 10-20 элементов на каждый подмассив. Число элементов настраивается. Аналогичная структура есть и в с++, уже не помню какая лет 15 на плюсах ни чего не писал
@@serhiis_ ну я под обычным массивом их и имел ввиду) Ну LinkedList - это всё ещё двусвязный список, так что сути особо не меняет
Поиск значения в массиве ничем не отличается от поиска в связанном списке - тот же перебор и сравнение всех значений пока не найдено нужное.
возможно я не совсем понял, но связанный список где хранится? в массиве? в чем смысл тогда что то выдумывать если по факту это массив пользовательских типов данных? ИЛИ ЭТО И ЕСТЬ СУТЬ ВИДЕО что есть массивы и есть массивы с пользовательскими типами данных, только одни так и называются массивами данных а другие - связанные списки (ну что б сложней было разобраться)
Скажите пожалуйста что за язык программирование в видео? Ради интереса.
Только начинаю изучать программирование массивы знаю, циклы тоже, а списки нет, как они вылядят в коде
Не совсем верно говорить, что статический массив размещается только на стеке. short * arr = (short *)malloc(Нужное колл-во байт); Ты же понимаешь, что это тоже массив и тоже статический, только размещен в куче? О динамическом массиве мы говорим, когда речь идет о каком-то контейнере (классе ) у которого уже описаны все механизмы управления, в том числе и перевыделение памяти, что по сути происходит , что мы просто ("уничтожаем") высвобождаем не нужный блок памяти переписав сперва все нужное в новый выделеный блок нужного нам размера, и адрес у указателя меняем на новый непрерывный блок.
5:42, а точно речь про поиск элемента в массиве, а не доступ к нему?
👍
Ура
огонь
Брат, ты хочешь сказать что push_back() к вектору в c++ работает за О(n), если нет, то что ты пытался сказать? Брат, это было бы полезное видео если бы ты объяснил как увеличивать массив так, чтобы амортизированное время работы каждого шага было О(1), а так твоё видео скорее запутывает новичков, чем рассказывает про массивы
Вектор в С++ это не простой массив. Это надстройка над обычным массивом, которая при вставке и удалении может автоматически менять размер того массива, где все и хранится. Причем, изменение размера массива происходит не каждый раз при вставке/удалении. Вектор при вставке новых значений, если массив заполнился, выделяет больше места для массива, но с запасом, чтобы при еще нескольких вставках не надо было по новой выделять место. В видео рассказывается про обычный, "сырой" массив, которым надо вручную манипулировать. А про "как увеличивать массив так, чтобы амортизированное время работы каждого шага было О(1)", я не думаю, что такое возможно. Выделение новой памяти большего размера для вставки значений происходит не просто так. За пределами массива тоже есть какие-то данные, и нельзя допустить, чтобы они стерлись или перезаписались, ведь из-за этого может пострадать работа вообще другой программы или ОС вылетит
@@YuraSamusenko если при заполнении массива каждый раз создавать массив в два раза большего размера, то легко посчитать, что в среднем каждая операция добавления будет работать за О(1)(n+n/2+n/4+n/8+…=2n, 2n/n = 2, 2 это O(1) на добавление), это и реализовано в c++ или в python или в любом другом современном языке программирования и мне кажется, что без этого рассказ о массиве является не полным
@@Ilya-kondakov у вас с математикой проблемы, чем больше массив, тем больше нужно времени на то, чтобы скопировать данные из старого в новый, так что нифига не O(1)
@@Dmytro-Tsymbaliuk в winAPI есть функция reallocate которая добавляет памяти, если есть такая возможность. Вроде в boost с++ эта функция есть. Уже не помню. В общем память в ОЗУ фрагментирована и если оЗУ не загружена под завязку то есть большой шанс что realloc пройдет успешно и не нужно ни чего копировать
@@Dmytro-Tsymbaliuk Для тех кто будет читать в будущем и думает также как и вы: ru.wikipedia.org/wiki/Амортизационный_анализ
Не ссылки, а указатели (pointer)!
это все и для JS закономерно?
Тут есть видео об отличиях кодера от программиста, в котором довольно много токсичных высказываний на тему тех, кто идёт в разработку только из-за высоких зарплат
Реклама курсов после этого - апогей продажности
Блин, как же сложно. Пересматриваю и все равно ничего в голове не вяжется. Может это не моё...
Бро, как ты такие анимации чёткие делаешь?
Навык
Какие языки программирования, вы знаете?