Вся правда о массивах структуры данных
содержание видео
Дата: 2023-03-12
Похожие видео
Комментарии и отзывы: 20
Андрій
Я делал такую базу, не подозревая, что именно о такой будут когда-то рассказывать. Нигде не учился. Пришел логично. Первый прототип базы был статический, но очень быстрый. И в момент, когда я не знал какой именно длинны будут некоторые текстовые поля, пришлось изобретать велосипед. Добавил ссылки. При удалении, информация просто не учитывалась. По факту она не удалялась. Ровно также вижу и работает Microsoft Access. Динамическая база данных при GOTO на нужный нам столбец работает медленней чем статическая, поскольку в статической можно просто умножить наш указатель на длину и мы точно попадем в начало нужной нам информации. А здесь нам уже нужно высчитывать из ссылки к ссылке пока не получим желаемую. Вначале я использовал только указатель вперед. Но позже столкнулся с проблемой вставки информацию в середину и решил не раздвигать ячейки, не перезаписывать жёсткий диск за каждый раз, а это даже очень актуально при использовании SSD накопителя. По этому добавил указатель назад и это позволило мне добавлять значения в конец, но подавать пользователю это как будто данные находятся в середине. Чесно говоря не знаю что лучше прыжки или перезапись. Возможно найдутся люди умнее и заявят мол диск всегда перезаписывается. Не знаю что конкретно на физическом уровне там делается. Исходил из логики. Access будет удобней использовать, но там есть ограничения по объему памяти. Да и по скорости он проигрывает, но удобен в конструкторе, особенно на этапе создания, когда в процессе может понадобиться добавить новое поле в базу данных. А в своем движке приходится допилить функционал, чтоб поле безопасно добавить или удалить, чтоб при необходимости сжать базу (очистить от удаленных записей. Кстате, потом сделал еще один гибрид интересный где использовались два файла: один статический а другой динамический. Динамический только для текста, а в статическом были уже ссылки на точку входа информации в динамическом файле. Через 5 лет посмотрел на весь этот чудо код и офигел сколько времени было потрачено
ответить
Я делал такую базу, не подозревая, что именно о такой будут когда-то рассказывать. Нигде не учился. Пришел логично. Первый прототип базы был статический, но очень быстрый. И в момент, когда я не знал какой именно длинны будут некоторые текстовые поля, пришлось изобретать велосипед. Добавил ссылки. При удалении, информация просто не учитывалась. По факту она не удалялась. Ровно также вижу и работает Microsoft Access. Динамическая база данных при GOTO на нужный нам столбец работает медленней чем статическая, поскольку в статической можно просто умножить наш указатель на длину и мы точно попадем в начало нужной нам информации. А здесь нам уже нужно высчитывать из ссылки к ссылке пока не получим желаемую. Вначале я использовал только указатель вперед. Но позже столкнулся с проблемой вставки информацию в середину и решил не раздвигать ячейки, не перезаписывать жёсткий диск за каждый раз, а это даже очень актуально при использовании SSD накопителя. По этому добавил указатель назад и это позволило мне добавлять значения в конец, но подавать пользователю это как будто данные находятся в середине. Чесно говоря не знаю что лучше прыжки или перезапись. Возможно найдутся люди умнее и заявят мол диск всегда перезаписывается. Не знаю что конкретно на физическом уровне там делается. Исходил из логики. Access будет удобней использовать, но там есть ограничения по объему памяти. Да и по скорости он проигрывает, но удобен в конструкторе, особенно на этапе создания, когда в процессе может понадобиться добавить новое поле в базу данных. А в своем движке приходится допилить функционал, чтоб поле безопасно добавить или удалить, чтоб при необходимости сжать базу (очистить от удаленных записей. Кстате, потом сделал еще один гибрид интересный где использовались два файла: один статический а другой динамический. Динамический только для текста, а в статическом были уже ссылки на точку входа информации в динамическом файле. Через 5 лет посмотрел на весь этот чудо код и офигел сколько времени было потрачено
ответить
Феликс
Здравствуйте Алек. Я так понимаю, что когда то будет продолжение. Дисциплина Алгоритмы и структуры данных интересная и большая.
По структурам: хэш-таблицы (с открытым, закрытым хэшированием, целая роща всяких деревьев с их самобалансировкой. Кстати, есть ещё списки с пропусками. Это когда при движении прыгают через несколько узлов. При приближении к цели - постепенно через меньшее количество узлов. Т. е, там присутствуют узлы с разным количеством next, как бы разной высоты.
По алгоритмам: семейство сортировок. Начиная с трёх базовых O(n2. Потом сортировка Шелла, прочесыванием. Потом O(nln(n) - Хоара, слиянием, пирамидальная. Ну, и мало знакомые - поразрядные (распределением) - для целых чисел. Для 4-хбайтных целых чисел - у поразрядной сортировки O(4n. Сравните: 4 и ln(n. Круче же, согласитесь! А почему то не не знают ) Ее на списках применять надо конечно. На массивах памяти много надо. Для строк есть запатентованная поразрядная: abc-sort.
Поиск подстроки в строке. Другими словами: слова или предложения в тексте. Или какой-либо последовательности (сигнатуры) в бинарном содержимом. Алгоритмы Кнута-Морриса-Пратта, Боуэра-Мура-Хорспула, Рабина-Карпа.
Это основные вещи, которые просто интересно знать!
ответить
Здравствуйте Алек. Я так понимаю, что когда то будет продолжение. Дисциплина Алгоритмы и структуры данных интересная и большая.
По структурам: хэш-таблицы (с открытым, закрытым хэшированием, целая роща всяких деревьев с их самобалансировкой. Кстати, есть ещё списки с пропусками. Это когда при движении прыгают через несколько узлов. При приближении к цели - постепенно через меньшее количество узлов. Т. е, там присутствуют узлы с разным количеством next, как бы разной высоты.
По алгоритмам: семейство сортировок. Начиная с трёх базовых O(n2. Потом сортировка Шелла, прочесыванием. Потом O(nln(n) - Хоара, слиянием, пирамидальная. Ну, и мало знакомые - поразрядные (распределением) - для целых чисел. Для 4-хбайтных целых чисел - у поразрядной сортировки O(4n. Сравните: 4 и ln(n. Круче же, согласитесь! А почему то не не знают ) Ее на списках применять надо конечно. На массивах памяти много надо. Для строк есть запатентованная поразрядная: abc-sort.
Поиск подстроки в строке. Другими словами: слова или предложения в тексте. Или какой-либо последовательности (сигнатуры) в бинарном содержимом. Алгоритмы Кнута-Морриса-Пратта, Боуэра-Мура-Хорспула, Рабина-Карпа.
Это основные вещи, которые просто интересно знать!
ответить
Дима
Спасибо за качественный контент! Подача материала отличная, сразу видно, что Автор знает о чём говорит.
Могу сказать пару слов о Связанных списках:
Преимущество Однонаправленного списка перед Двунаправленным в чуть меньшем потреблении памяти на каждый элемент списка и чуть более быстром выполнении некоторых функций.
На этом его преимущества заканчиваются, и проявляется множество НЕпреимуществ.
К примеру:
Поиск/Удаление/Вставка в Двунаправленном списке можно начать как с начала, так и с конца.
То-есть, если Index < Length / 2 = начинаем идти с Head-a к нужному элементу,
а если Index > Length / 2 с Tail-a назад к нужному элементу.
А в Однонаправленном списке тебе придётся идти всегда сначала.
По-этому, зачастую, Двунаправленные списки выигрывают у Однонаправленных.
Я промолчу о некоторых функциях, типа Реверса данных внутри списка или их Смещения (Не Nod-ов, там Однонаправленные списки сразу проигрывают.
ответить
Спасибо за качественный контент! Подача материала отличная, сразу видно, что Автор знает о чём говорит.
Могу сказать пару слов о Связанных списках:
Преимущество Однонаправленного списка перед Двунаправленным в чуть меньшем потреблении памяти на каждый элемент списка и чуть более быстром выполнении некоторых функций.
На этом его преимущества заканчиваются, и проявляется множество НЕпреимуществ.
К примеру:
Поиск/Удаление/Вставка в Двунаправленном списке можно начать как с начала, так и с конца.
То-есть, если Index < Length / 2 = начинаем идти с Head-a к нужному элементу,
а если Index > Length / 2 с Tail-a назад к нужному элементу.
А в Однонаправленном списке тебе придётся идти всегда сначала.
По-этому, зачастую, Двунаправленные списки выигрывают у Однонаправленных.
Я промолчу о некоторых функциях, типа Реверса данных внутри списка или их Смещения (Не Nod-ов, там Однонаправленные списки сразу проигрывают.
ответить
AlexAnder
У списков есть ещё один весомый минус помимо дополнительного поля с указателем, жрущего память. Это malloc, который к тому же враппер к системному вызову alloc, который работает на VAD таблицах, которые также жрут память. Особенно когда элементы списка 10-50 байт в большинстве своём случаев, а alloc работает со страницами памяти по 4 килобайта. Это лютейший стресс для операционки. А некоторые операционки не умеют в принципе выделять память меньше страницы и получается что на элемент, в смысле на каждый элемент, размером в несколько байт улетает ровно 4 килобайта. Короче списки - величайшее зло и ошибка. Можно без них если чуть повнимательней отнестись к организации алгоритмов и структур данных.
ответить
У списков есть ещё один весомый минус помимо дополнительного поля с указателем, жрущего память. Это malloc, который к тому же враппер к системному вызову alloc, который работает на VAD таблицах, которые также жрут память. Особенно когда элементы списка 10-50 байт в большинстве своём случаев, а alloc работает со страницами памяти по 4 килобайта. Это лютейший стресс для операционки. А некоторые операционки не умеют в принципе выделять память меньше страницы и получается что на элемент, в смысле на каждый элемент, размером в несколько байт улетает ровно 4 килобайта. Короче списки - величайшее зло и ошибка. Можно без них если чуть повнимательней отнестись к организации алгоритмов и структур данных.
ответить
Человек
Не совсем верно говорить, что статический массив размещается только на стеке. short arr = (short )malloc(Нужное колл-во байт); Ты же понимаешь, что это тоже массив и тоже статический, только размещен в куче? О динамическом массиве мы говорим, когда речь идет о каком-то контейнере (классе ) у которого уже описаны все механизмы управления, в том числе и перевыделение памяти, что по сути происходит, что мы просто (уничтожаем) высвобождаем не нужный блок памяти переписав сперва все нужное в новый выделеный блок нужного нам размера, и адрес у указателя меняем на новый непрерывный блок.
ответить
Не совсем верно говорить, что статический массив размещается только на стеке. short arr = (short )malloc(Нужное колл-во байт); Ты же понимаешь, что это тоже массив и тоже статический, только размещен в куче? О динамическом массиве мы говорим, когда речь идет о каком-то контейнере (классе ) у которого уже описаны все механизмы управления, в том числе и перевыделение памяти, что по сути происходит, что мы просто (уничтожаем) высвобождаем не нужный блок памяти переписав сперва все нужное в новый выделеный блок нужного нам размера, и адрес у указателя меняем на новый непрерывный блок.
ответить
Евгений
Очень круто. За 13 минут благодаря крутому визуалу и грамотным объясниям вспомнил все, что в универе проходили чуть ли не целый семестр.
Было бы очень круто так же разобрать более сложные структуры, вроде тех же хеш-таблиц.
А ещё было бы полезно делать референсы на популярные языки, например, массив в С - это чистый массив, а вот в плюсах - это двунаправленный связный список
Ps не надо пожалуйста тригериться, про с/с++ я написал для примера и знаю что это не так
ответить
Очень круто. За 13 минут благодаря крутому визуалу и грамотным объясниям вспомнил все, что в универе проходили чуть ли не целый семестр.
Было бы очень круто так же разобрать более сложные структуры, вроде тех же хеш-таблиц.
А ещё было бы полезно делать референсы на популярные языки, например, массив в С - это чистый массив, а вот в плюсах - это двунаправленный связный список
Ps не надо пожалуйста тригериться, про с/с++ я написал для примера и знаю что это не так
ответить
NanzeRT
Я писал игровой движок, и у меня возникла необходимость хранить кучу объектов в одном массиве с частыми добавлениями в конец, произвольными удалениями и перебором всех элементов. Для этой задачи отлично подошёл двусвязный список, так как в нём можно было сделать произвольное удаление за O(1) за счёт комбинации его с перебором всех элементов - я по ссылкам помечаю объекты как удалённые и при переборе вычищаю их.
ответить
Я писал игровой движок, и у меня возникла необходимость хранить кучу объектов в одном массиве с частыми добавлениями в конец, произвольными удалениями и перебором всех элементов. Для этой задачи отлично подошёл двусвязный список, так как в нём можно было сделать произвольное удаление за O(1) за счёт комбинации его с перебором всех элементов - я по ссылкам помечаю объекты как удалённые и при переборе вычищаю их.
ответить
Bavaria
Тонкость на которой любят валить на собеседованиях по C# и Java: массивы всегда являются ссылочным типом и следовательно память всегда будет выделяться в управляемой куче (за исключением unsafe кода, в стеке будет находиться указатель на выделенную область памяти. В C/C++ по умолчанию массив определяется в стеке, либо с помощью malloc определяется в куче.
ответить
Тонкость на которой любят валить на собеседованиях по C# и Java: массивы всегда являются ссылочным типом и следовательно память всегда будет выделяться в управляемой куче (за исключением unsafe кода, в стеке будет находиться указатель на выделенную область памяти. В C/C++ по умолчанию массив определяется в стеке, либо с помощью malloc определяется в куче.
ответить
Bash
Это конечно всё простенько, просто ужас сколько всего есть сложного в информатике, и поэтому становиться интересно. А самое главное, что математика тут играет ключевую роль, она помогает анализировать алгоритмы, описывать наш окружающий мир и тд. Поэтому самым главным инструментом программиста является именно математика.
ответить
Это конечно всё простенько, просто ужас сколько всего есть сложного в информатике, и поэтому становиться интересно. А самое главное, что математика тут играет ключевую роль, она помогает анализировать алгоритмы, описывать наш окружающий мир и тд. Поэтому самым главным инструментом программиста является именно математика.
ответить
neektt
Вообще, при удалении в обычном массиве можно менять удаляемый элемент с последним местами, и уменьшать размер на 1. Теряем строгий порядок (который, на самом деле, нужен не всегда, зато получаем удаление за О(1. Оптимизаций куча. По опыту, при всех плюсах, связный список нужен только в очень небольшом пуле задач.
ответить
Вообще, при удалении в обычном массиве можно менять удаляемый элемент с последним местами, и уменьшать размер на 1. Теряем строгий порядок (который, на самом деле, нужен не всегда, зато получаем удаление за О(1. Оптимизаций куча. По опыту, при всех плюсах, связный список нужен только в очень небольшом пуле задач.
ответить
PlaytOster
Я бы все таки рекомендую именовать поиск в массиве - доступом к элементу. Это не поиск в чистом виде. К примеру если взять код который на экране когда идет речь про поиск в списке - которое О(n), где сверяется некая мифическая data, то такой код и на массиве будет за O(n) работать. Но это не отменяет крутости видоса!
ответить
Я бы все таки рекомендую именовать поиск в массиве - доступом к элементу. Это не поиск в чистом виде. К примеру если взять код который на экране когда идет речь про поиск в списке - которое О(n), где сверяется некая мифическая data, то такой код и на массиве будет за O(n) работать. Но это не отменяет крутости видоса!
ответить
Михаил
Контент шикарный! Спасибо за труд! И пожелание:
Интересно будет видео о процессах и потоках ОС. Как они создаются, хранятся, исполняются. Их параллельный запуск, приостановка, возобновление, взаимодействие. Что такое процесс? Есть ли предел количества потоков? Как чередуется исполнение потоков в CPU?
ответить
Контент шикарный! Спасибо за труд! И пожелание:
Интересно будет видео о процессах и потоках ОС. Как они создаются, хранятся, исполняются. Их параллельный запуск, приостановка, возобновление, взаимодействие. Что такое процесс? Есть ли предел количества потоков? Как чередуется исполнение потоков в CPU?
ответить
Феликс
2: 38 статический массив. на стеке? И все?
Вынужден добавить, это когда речь идёт о локальных переменных.
Как известно, есть ещё глобальные. Такие переменные находятся в секции данных. Т. е. они изначально уже там, ещё при загрузке модуля в память. И до конца жизни этого модуля.
ответить
2: 38 статический массив. на стеке? И все?
Вынужден добавить, это когда речь идёт о локальных переменных.
Как известно, есть ещё глобальные. Такие переменные находятся в секции данных. Т. е. они изначально уже там, ещё при загрузке модуля в память. И до конца жизни этого модуля.
ответить
Arman
по поводу поиска в массиве хочу сказать что O(1) это доступ на адрес так как в Си например arr == arr[0], получается что первый элемент это так же указатель на массив, и это облегчает найти нужный нам адрес но никак элемент который лежит в адресе, а поиск элемента уже O(n.
ответить
по поводу поиска в массиве хочу сказать что O(1) это доступ на адрес так как в Си например arr == arr[0], получается что первый элемент это так же указатель на массив, и это облегчает найти нужный нам адрес но никак элемент который лежит в адресе, а поиск элемента уже O(n.
ответить
EyeZary
Оптимизация выделения памяти для массивов через рост на коэффициент и без переаллокаций при удалениях? Удаление элемента массива замещением из последнего если порядок не важен? Интрузивные списки с удалением O(1) без необходимости искать элемент?
ответить
Оптимизация выделения памяти для массивов через рост на коэффициент и без переаллокаций при удалениях? Удаление элемента массива замещением из последнего если порядок не важен? Интрузивные списки с удалением O(1) без необходимости искать элемент?
ответить
Vladimir
все распространенные языки при необходимости увеличения размера автоматического массива увеличивают его размер в 2 или 3 раза. Так что чаще всего добавление в конец массива делается за константное время.
ответить
все распространенные языки при необходимости увеличения размера автоматического массива увеличивают его размер в 2 или 3 раза. Так что чаще всего добавление в конец массива делается за константное время.
ответить
#jackpraid
А почему вы ничего не рассказали о бинарном дереве? Поиск в нём равняется O(1, добавление элементов равняется O(1, и поиск элемента по значению тоже равняется O(1, то есть поиск по значению в линейное время.
ответить
А почему вы ничего не рассказали о бинарном дереве? Поиск в нём равняется O(1, добавление элементов равняется O(1, и поиск элемента по значению тоже равняется O(1, то есть поиск по значению в линейное время.
ответить
Maksym
Alek - Спасибо тебе за стольчудесный контент. Ты просто огромнейшый молодец, за столь краткий период времени ты уже сделал огромный вклад в жизни других людей, жаль что я больше не смогу видеть твои видео.
ответить
Alek - Спасибо тебе за стольчудесный контент. Ты просто огромнейшый молодец, за столь краткий период времени ты уже сделал огромный вклад в жизни других людей, жаль что я больше не смогу видеть твои видео.
ответить
pcsekret
У тебя хорошо поставлен голос, хорошо рассказываешь, но иногда убаюкивает. Какой-то интересный тон есть: . Такое ощущение, что сейчас в транс войду. Наверно музыка еще создает трассовое состояние.
ответить
У тебя хорошо поставлен голос, хорошо рассказываешь, но иногда убаюкивает. Какой-то интересный тон есть: . Такое ощущение, что сейчас в транс войду. Наверно музыка еще создает трассовое состояние.
ответить
Alex
Как всегда афигенный контент! Всё раскладываешь по полочкам и показываешь наглядный пример! Если бы ты записал серию уроков по какому-либо ЯП или технологии, я бы в запой просмотрел всё!
ответить
Как всегда афигенный контент! Всё раскладываешь по полочкам и показываешь наглядный пример! Если бы ты записал серию уроков по какому-либо ЯП или технологии, я бы в запой просмотрел всё!
ответить
Добавить отзыв, комментарий
Другие видео канала
1:34
38:14