А где комментарии? Ладно, тогда распишу че хочу. Вариант ответа на вопрос в конце: когда известен ключ и не надо перебирать все возможные варианты, что бы найти один единственный. Видос полезный, но надо будет еще утром посмотреть, а то всё забуду. И хотелось бы попросить рассказать про деревья. Бинарные, черно-белые и т.д. Смотрел в интернете - нудно, много воды и надо прям вчитываться в каждую букву что бы понять. Вроде всё. За видосы +реп ❤
Ответ на вопрос в конце 1)Хэш-таблицы, работают быстрее при поиске элементов, в массивах нужно перебрать все элементы, чтобы найти тот самый, в то время как в хэш-таблице вы переходите непосредственно к элементу. 2)Вставка элемента выполняется быстрее в хэш-таблицах, так как вы просто хешируете ключ и вставляете его; в массивах важно сначала переместить элементы, прежде чем вставлять еще один.
Про первое, если у нас есть индекс, то мы сразу перейдем к элементу в массиве и будет O(1) как и в хэш-таблице. Индекс это же альтернатива ключу в хэш-таблице
@@Xname00 поэтому нихуя и не понятно - нахуя хэш-таблицы, если можно юзать обычные массивы -- доступ по ключу равен доступу по индексу. Жопой чую, что тут извечная дилемма по выбору "память-vs-процессор", но автор в видосе это не затронул.
@@Xname00 В том же и суть, что при поиске вы не знаете наличествует ли элемент в массиве/хэше, так о каком индексе речь? При поиске подразумевается не доступ (access), а конструкция типа "if something in array", в этом случае в массиве нужно будет перебирать каждый элемент до тех пор, пока "something" не будет найден, что в худшем случае и будет O(n). В хэшиках элемент вытаскивается сразу без этой беготни.
@@TheUnderLike почти все правда, но если трогать биг О то можно понять, что поиск в HshTable это 0(N) так же как и в массиве из за колизий. А мы программисты как наверное знаешь выбираем надеямся на самый наихудший вариант.
невсегда при заполнение HashTable обычно это на 70%, то HashTable пересоздается с увеличиной длиной в 2 раза как правило.Поэтому по Big O это будет 0(N)-вставка. Да конечно можно сказать что HashTable не заполнен и тд. Но в Big O всегда выбирают самый хужший вариант.Так же как с поиском и удаление все это 0(N) но в среднем да 0(1).
Невероятный кладезь знаний за 10 минут. Если бы меня спросили как понять такие сложные штуки, то я бы, не думая, ткнул пальцем в канал Winderton. Спасибо, мужчина)
В Python dict был неупорядоченным до версии 3.6, для упорядоченного существовал OrderedDict(). Затем dict стал упорядоченным, при этом он остался хеш-таблицей, в итоге теперь в Python две реализации упорядоченного словаря)
Да только упорядоченность дерева подразумевает упорядоченность по значению, а OrderedDict это упорядоченность по времени вставки. Иногда бывает полезно и то и другое, но все же упорядоченность по значению более полезная штука. Например если у тебя ордеред сет в виде дерева то ты можешь искать upper/lower bound за логарифмическое время что покрывает очень большой класс задач. Ордеред дикт по факту совмещает две структуры и в этом плане не совсем уже чистая хэшмапа
Массив быстрее хеш таблицы в случае поиска/замены так как арифметика указателей быстрее хеш функции Но если нужно удалить/добавить элемент то в случае с массивом нужно найти !неприрывную! область в памяти размером {старый массив+новый/новые элементы}, скопировать всё старое и добавить новое и только потом удалить из памяти старый массив весь этот процесс на словах долгих, а не только на деле Хеш таблица же таким не страдает и память выделяется только на новый объект который будет добавлен, а всё старое остаётся на месте Например тот же вектор в с++ частично решает проблему со вставкой, но только в конец и до того момента пока не понадобится амортизация
Ответ на вопрос в конце ролика. Хэш-таблицы могут быть быстрее массивов в двух случаях: 1. Когда известно только значение которое необходимо найти. В случае массива придется перебирать весь массив в случае с мапой ключом будет являться само значение пропущенное через хэш-функцию. 2. Массив хранит в себе сам объект а мапа указатель на память где лежит объект. Соответственно при условии что объекты могут динамически изменять свой размер массив будет требовать переаллокации памяти и переноса себя в эту память что довольно медленно а мапа нет. Возможно есть еще какие то кейсы но сходу в голову пришли эти.
У классического массива, доступ к памяти, осуществляется как: + * size_of(), Если значение функции size_of() не является константой для данного типа, то создать классический массив, из этих элементов невозможно. Переменные(объекты/структуры) чей размер нельзя определить на этапе компиляции - всегда хранятся в куче. Массив из таких элементов всегда будет массивом из указателей. (Даже если сам массив тоже хранится в куче и доступен по указателю). Поэтому второй ваш пример, мне кажется не состоятельным.
Привет чумваки, через два месяца упорного бодания рогами в землю, я пробил этот кокон и понял что дойду до конца и все уже стало понятным и логичным. Если вдруг у вас начался кризис обучения и вы хотите бросить, может быть вы прочтете и это придаст вам сил. Не опускай руки, бро!
о кто то поставил лайк, а после нг праздников так и не сел обратно, но всё ещё знаю что могу, новое видео Виндерпуфена смотрю и оно придаёт мотивации. Всем йоу!
@@kamenyFX все ещё нет, но тут случились обстоятельства после которых приходится работать по 10-12 часов в день. Это серьезно замедляет. Но так будет только до конца месяца. Но я после того как раскидаю долг уже пойду по собесам, такие вот дела.
Очень полезная инфа. От души. Единственное замечание. Почему вставка и удаление из сбалансированных деревьев - это O(log(n)). Может больше? А как же дополнительные операции на перебалансировку дерева? Так называемые вращения (rotations)
скорее всего на русскоязычном сегменте, ты первый кто будет объяснять это для "чайников". Я только начал учиться, но благо тебе есть "неусталость" обучению. TY❣
Потому что вычисление хэша это константа, а она в нотации большого О не учитывается. Большое О говорит о том, как увеличивается сложность в зависимости от количества данных, поэтому там константа не важна. Действительно, реальная производительность у массива может быть выше на всех операциях при малом размере данных, когда эффект константы больше, чем вклад увеличения сложности.
В питоне до 3.7 dict был беспорядочный. В 3.7 его упорядочили (ради оптимизации памяти немного переработали dict, упорядочивание вышло просто полезным плюсом).
Блин я прошёл эту тему на курсе Пайтон, то что ты рассказываешь, вообще нифига не понятно, для других программистов со стажем 5 лет может всё ясно. Для новичков всё быстро сумбурно как то. На других канал даже более сложные темы умудряются рассказать, что всё понятно, тут даже такую простую тему с выносом мозга.
Понимание линейних массивов тоже очень важно. Везде где можно скешировать и проитерироваться, очевидно лучше соблюдать линейность, нежели таблицу или слинкованные структуры данних. А вообще, лучше изучать и практиковать разные структуры и самому тоже делать (без использования стандарта std или boost)
А потом возникают вопросы: *"Какого хрена такой низкий ФПС?!"* или *"Откуда такие сумасшедшие мин требования?!"* или *"Почему такая УЙНЯ занимает NN гигабайт?!"
6:36 С какого это лысого O(1), если нужно пролистать по структуре до попадания на нужный хэш? Мы не адрес всё-таки там храним. Сразу нужно понимать, что структура с абстрактным множеством эл-тов не будет выдавать такие низкие сложности.
Контент годный, объяснение самобытное, чёткое, понятное. Вообще канал классный. А вот запомоиться об остопи3девшую всему интернету Скулль-FUСК-тори - это позор. Лучше бы казино какое рекламировал, чем этих вонючих лохотронщиков (они сами признались, что львиная доля бюджета у них идёт на рекламу - скупили почти всех блогеров-проституток - даже Гоблин не устоял, продал свою жопку и честное имя за пачку баксов).
Вот вы говорите что в Хеш таблицах переход происходит по индексу? Если массив с Int индексами, то теоретически переход происходит к элементу методом умножения к адресу, где непрерывно находятся данные. Но если Хеш это некая сумма элементов (символов) то как происходит "мгновенный" переход? :) Ведь всё в итоге компилится в ассемблер и код. И как бы не очень понятно как без "тупого" перебора таких хеш индексов происходит поиск нужных данных? Или я что-то пропустил? ;)
Задача в том, чтобы найти индекс по значению. Поиск перебором это простой проход по массиву/списку и сравнение каждого элемента О(N). Очевидно, это не касается деревьев и сортированных массивов (где есть бинарный поиск), O(log n). В хэш-таблице индекс получается из значения вызовом хэш-функции. Соответственно проверяется малое количество элементов (те, у которых совпало значение хэш-функции), O(1).
Если грубо переложить на русский unorder set= aн' оодэд cэт или эн' оодэд сет. Видишь, Р отсутствует. Не надо благодарности, это в качестве бл. за твой контент :) Я вижу старание есть, но мисс прононс всетаки есть. По береги наши уши плз :)
@@Ilya-kondakov подумал, что возможно в данном случае и не в чем, а мысль в голове просто засела с курса "математические методы защиты информации", где в криптографии связано со сложностью обнаружения
Это просто оптимизация. Чтобы не вычислять каждый раз остаток от деления (а это довольно тяжёлая операция), делают размер массива равный степени двойки. Тогда остаток от деления будет такой же как в вашей формуле, а битовые операции значительно быстрее вычисления остатка. Но для понимания работы хеш таблицы эта формула не нужна.
Никогда не любил хеш функции, чёрт его знает сколько там будет коллизий. Для меня указатели всегда были надёжне- error: memory access violation: core dumped. (хоть и за указателями надо следить)
А как тогда представить строку, которая будет ключем в виде индекса в вашем примере? Ее ведь нужно пропустить через хэш-функцию. Ну если указтаели используете, то придется все равно сделать что-то типа *(arr + index)
@@torburgmax вопрос был вообще не про ассемблер, а про структуры данных. Просто у Си эта ошибка хотябы видна, а если использовать массив с индексами вместо указателей, то этой ошибки не будет, у тебя просто программа будет медленно но верно сыпаться без ошибок.
@@Z_Z.t какой вопрос?) я имею в виду, что нужно просто выбирать подходящий метод решения проблемы, и мне странно видеть фразы вроде "я не люблю хеш-функции". поэтому и предложил бантики перекладывать напрямую, чтобы все максимально контролировать)
А чё пример hashа, в perlе не показал? Тем более, что в нём это было изначально и раньше других языков стало использоваться им пользоваться использоваться!
С какого перепуга строки в плюсах неизменяемые? Всегда во всех стандартах они были mutable. string_view immutable но это только 17 стандарт и не строка это вовсе а view.
достаточно важный момент для понимания упущен, который объясняет, почему поиск элемента константен по времени. речь про сведение хэша к индексу итогового массива
А можешь объяснить, почему поиск в хэшмапе происходит за константное время ? Надо же найти в ней запись с нужным ключом, а для этого нужно пробежаться по всем элементам. Если они отсортированы, то можно использовпть бинарный поиск, но это все равно логарифмическое время, а не константное. В любом случае оно зависит от количества элементов в мапе и константным быть не может.
Одна из реализаций хеш таблицы - это массив бакетов. В каждом бакете хранится список пар (ключ, значение). Чтобы в этом массиве найти ключ, нужно от ключа посчитать хеш (какое-то число, посчитаное каким-нибудь алгоритмом). Если взять остаток от деления хеша на количество бакетов, то получится индекс бакета в массиве. Дальше по этому бакету можно пробежаться и найти нужный ключ. По факту, каждая отдельная операция работает не совсем за константное время, а за количество объектов в бакете, но количество бакетов и хеш функции подбирают так, чтобы в каждом бакете было очень мало элементов. Всякими математическими методами можно доказать, что среднее количество элементов в бакете не растёт с увеличением количества элементов. Когда элементов в таблице становится больше чем какой-то порог, то количество бакетов увеличивается и все элементы раскидываются заново.
@@руслангасак-н6сЕсли искать не по ключу, а по какому-то другому предикату, то поиск будет O(n), и даже хуже чем в линейном массиве. Потому-что тебе нужно итерироваться по указателях, потом считать память указателя, а потом только использовать предикат.
гений на челе смог мне объяснить мне принцип работы этой структуры... прошел универ, но так и не понимал, как работают словари и причем тут хеш)) спасибо
а зачем тебе анордеред? ордеред хэшмапа дает гарантию порядка при перечислении значений, а анордеред не дает. Поэтому ордеред всегда может заменить анордеред но не наоборот.
НАЧАЛ УЧИТЬ ХЭШТЭЙБЛ, В ИТОГЕ ВЫУЧИЛ СВЯЗНЫЙ СПИСОК, МАССИВ, СЕТ, МАП, И ДЕРЕВЬЯ....
Топчик
ГОУ видосик про декомпозицию предметной области😊
Спасибо за годный контент, а в чем если не секрет, ты монтируешь и делаешь графику?
Такой же путь прошел)
я вот не понял что происходит, слова знакомые что для чего не понятно
можно еще быстрее говорить? ну и мужиков не надо, а так лойс поставлен)
А где комментарии? Ладно, тогда распишу че хочу. Вариант ответа на вопрос в конце: когда известен ключ и не надо перебирать все возможные варианты, что бы найти один единственный. Видос полезный, но надо будет еще утром посмотреть, а то всё забуду. И хотелось бы попросить рассказать про деревья. Бинарные, черно-белые и т.д. Смотрел в интернете - нудно, много воды и надо прям вчитываться в каждую букву что бы понять. Вроде всё. За видосы +реп ❤
Ответ на вопрос в конце
1)Хэш-таблицы, работают быстрее при поиске элементов, в массивах нужно перебрать все элементы, чтобы найти тот самый, в то время как в хэш-таблице вы переходите непосредственно к элементу.
2)Вставка элемента выполняется быстрее в хэш-таблицах, так как вы просто хешируете ключ и вставляете его; в массивах важно сначала переместить элементы, прежде чем вставлять еще один.
Про первое, если у нас есть индекс, то мы сразу перейдем к элементу в массиве и будет O(1) как и в хэш-таблице. Индекс это же альтернатива ключу в хэш-таблице
@@Xname00 поэтому нихуя и не понятно - нахуя хэш-таблицы, если можно юзать обычные массивы -- доступ по ключу равен доступу по индексу. Жопой чую, что тут извечная дилемма по выбору "память-vs-процессор", но автор в видосе это не затронул.
@@Xname00 В том же и суть, что при поиске вы не знаете наличествует ли элемент в массиве/хэше, так о каком индексе речь? При поиске подразумевается не доступ (access), а конструкция типа "if something in array", в этом случае в массиве нужно будет перебирать каждый элемент до тех пор, пока "something" не будет найден, что в худшем случае и будет O(n). В хэшиках элемент вытаскивается сразу без этой беготни.
@@TheUnderLike почти все правда, но если трогать биг О то можно понять, что поиск в HshTable это 0(N) так же как и в массиве из за колизий. А мы программисты как наверное знаешь выбираем надеямся на самый наихудший вариант.
невсегда при заполнение HashTable обычно это на 70%, то HashTable пересоздается с увеличиной длиной в 2 раза как правило.Поэтому по Big O это будет 0(N)-вставка. Да конечно можно сказать что HashTable не заполнен и тд. Но в Big O всегда выбирают самый хужший вариант.Так же как с поиском и удаление все это 0(N) но в среднем да 0(1).
Больше видосов по алгоритмам и структурам данных и ещё сними видос где ты решаешь задачи на литкоде с объяснениеми для чайников
Донат скинь
И в сообщении попроси
dict в python это хештаблица с двойным хешированием, сохранение порядка вставки поддерживается особенностями реализации, а не мапой
Питон лоховской язык
@@имяфамилия-т3ж1ц адепты js подъехали
@@имяфамилия-т3ж1ц😂😂😂 absolution верно
@@имяфамилия-т3ж1цчто ещё расскажешь?
@@имяфамилия-т3ж1ц уроки сделал?)
"А вот С++ .... сделал строки неизменяемыми" - это ошибка.`std::string` имеет изменяемый контент, как и область памяти, на которую указывает `char *`
Думаю он имел ввиду const char*
Невероятный кладезь знаний за 10 минут. Если бы меня спросили как понять такие сложные штуки, то я бы, не думая, ткнул пальцем в канал Winderton. Спасибо, мужчина)
В Python dict был неупорядоченным до версии 3.6, для упорядоченного существовал OrderedDict().
Затем dict стал упорядоченным, при этом он остался хеш-таблицей, в итоге теперь в Python две реализации упорядоченного словаря)
Да только упорядоченность дерева подразумевает упорядоченность по значению, а OrderedDict это упорядоченность по времени вставки. Иногда бывает полезно и то и другое, но все же упорядоченность по значению более полезная штука. Например если у тебя ордеред сет в виде дерева то ты можешь искать upper/lower bound за логарифмическое время что покрывает очень большой класс задач. Ордеред дикт по факту совмещает две структуры и в этом плане не совсем уже чистая хэшмапа
нет, dict в Python это тоже хеш-мапа, не RB-tree
Полезно всё, что ты делаешь! Из этого складывается собственная логика и понимание ,как в это влиться🎓🧠👁
Массив быстрее хеш таблицы в случае поиска/замены так как арифметика указателей быстрее хеш функции
Но если нужно удалить/добавить элемент то в случае с массивом нужно найти !неприрывную! область в памяти размером {старый массив+новый/новые элементы}, скопировать всё старое и добавить новое и только потом удалить из памяти старый массив весь этот процесс на словах долгих, а не только на деле
Хеш таблица же таким не страдает и память выделяется только на новый объект который будет добавлен, а всё старое остаётся на месте
Например тот же вектор в с++ частично решает проблему со вставкой, но только в конец и до того момента пока не понадобится амортизация
Спасибо. Отличный ликбез. Хотелось бы послушать про красночерное дерево
Ответ на вопрос в конце ролика. Хэш-таблицы могут быть быстрее массивов в двух случаях: 1. Когда известно только значение которое необходимо найти. В случае массива придется перебирать весь массив в случае с мапой ключом будет являться само значение пропущенное через хэш-функцию. 2. Массив хранит в себе сам объект а мапа указатель на память где лежит объект. Соответственно при условии что объекты могут динамически изменять свой размер массив будет требовать переаллокации памяти и переноса себя в эту память что довольно медленно а мапа нет. Возможно есть еще какие то кейсы но сходу в голову пришли эти.
У классического массива, доступ к памяти, осуществляется как: + * size_of(),
Если значение функции size_of() не является константой для данного типа, то создать классический массив, из этих элементов невозможно. Переменные(объекты/структуры) чей размер нельзя определить на этапе компиляции - всегда хранятся в куче. Массив из таких элементов всегда будет массивом из указателей. (Даже если сам массив тоже хранится в куче и доступен по указателю).
Поэтому второй ваш пример, мне кажется не состоятельным.
Привет чумваки, через два месяца упорного бодания рогами в землю, я пробил этот кокон и понял что дойду до конца и все уже стало понятным и логичным. Если вдруг у вас начался кризис обучения и вы хотите бросить, может быть вы прочтете и это придаст вам сил. Не опускай руки, бро!
о кто то поставил лайк, а после нг праздников так и не сел обратно, но всё ещё знаю что могу, новое видео Виндерпуфена смотрю и оно придаёт мотивации. Всем йоу!
Ну что там? пол года прошло, добился успеха?
@@kamenyFX все ещё нет, но тут случились обстоятельства после которых приходится работать по 10-12 часов в день. Это серьезно замедляет. Но так будет только до конца месяца. Но я после того как раскидаю долг уже пойду по собесам, такие вот дела.
@@staffa_kar_terma Харош, удачи
Очень полезная инфа. От души. Единственное замечание. Почему вставка и удаление из сбалансированных деревьев - это O(log(n)). Может больше? А как же дополнительные операции на перебалансировку дерева? Так называемые вращения (rotations)
В с++ можно так:
using namespace std;
unordered_map data {
{"Ivan",1},
{"John",2}
}
в С++ строки изменяемые
Как говорят мудрецы, если завис с задачей, то брось на нее хеш таблицу и все будет шикарно.
А лучше положи на нее хрен😂
5:35 в питоне это тоже хеш таблица. Для упорядоченной таблицы есть ordereddict.
Мне понравилось, интересно смотреть. Но это первое видео в моей жизни которое я замедлял, до 0.75. Речь изначально ускорена?
Требуем адское мессиво на 10 часов по плюсам
скорее всего на русскоязычном сегменте, ты первый кто будет объяснять это для "чайников". Я только начал учиться, но благо тебе есть "неусталость" обучению. TY❣
А смысл? Ведь этого будет недостаточно, однако ты рано или поздно дойдешь до них и изучишь уже на более глубоком уровне сам.
Как раз думал, где видосы, как раз дропнул. Тупо сказка перед сном)
Может чуть помедленней стоит, обдумывать не успеваю что ты рассказываешь) А так спасибо, интересный материал, однозначно лайк
зависит от матриала и твоих знаний - я некоторые наборот побыстрее включаю
Хорош хорош братан, давай ещё! Можно такого побольше?
нужно чуть больше комментариев про O(1), почему не учитывается время вычисления хэш-функции?
Потому что вычисление хэша это константа, а она в нотации большого О не учитывается. Большое О говорит о том, как увеличивается сложность в зависимости от количества данных, поэтому там константа не важна. Действительно, реальная производительность у массива может быть выше на всех операциях при малом размере данных, когда эффект константы больше, чем вклад увеличения сложности.
@@KoMedVed только хэш от строки например не константа 🤔в питоне удобно там все хэши заранее вычислены)
@@tonybard Не знаю как в питоне, но в java строки неизменяемые и хэш считается 1 раз - при создании
@@KoMedVed также, но в плюсах не так)
Боже как долго я тебя искал, ты шикарен 😍😍😍 хз кто еще так может информативно рассказывать
Восхищаюсь этим человеком. И его смотрят такие же свехнутые люди, кто любит компы и хочет понимать их лучше.😂 А уже потом кодеры.
Вот это контеент!😂🎉
Я присоединяюсь к требованию десятичасового курса по плюсам !❤
Ты лучший, продолжай свои уроки!!!❤❤❤
В питоне до 3.7 dict был беспорядочный. В 3.7 его упорядочили (ради оптимизации памяти немного переработали dict, упорядочивание вышло просто полезным плюсом).
C++ string изменяемый.
Блин я прошёл эту тему на курсе Пайтон, то что ты рассказываешь, вообще нифига не понятно, для других программистов со стажем 5 лет может всё ясно. Для новичков всё быстро сумбурно как то. На других канал даже более сложные темы умудряются рассказать, что всё понятно, тут даже такую простую тему с выносом мозга.
Вы как то говорили про обучение? Где можно посмотреть информацию об этом??
Я думаю автору видео очень понравится Кложура.
Неизменяемые строки в C++? Расскажите, будьте добры, если я чего-то не знаю...
Спасибо за видос. Непонятно, конечно, но очень интересно =)
Реально годные видосы, очень быстро и по делу,продолжай так же
Понимание линейних массивов тоже очень важно. Везде где можно скешировать и проитерироваться, очевидно лучше соблюдать линейность, нежели таблицу или слинкованные структуры данних.
А вообще, лучше изучать и практиковать разные структуры и самому тоже делать (без использования стандарта std или boost)
при поиске и вставки элементов, это лучше всего сочетается в большом объёме данных или когда тебе по ключу что либо найти надо, вооот...
ответ на вопрос: при поиске {"one":1,"two":2} искать по ключу "two" будет быстрее чем искать 2 в массиве [1,2]. если я правильно пончл вопрос..
Найс. Как всегда база на языке народа. Красавчик 🎉
А потом возникают вопросы:
*"Какого хрена такой низкий ФПС?!"*
или
*"Откуда такие сумасшедшие мин требования?!"*
или
*"Почему такая УЙНЯ занимает NN гигабайт?!"
6:36 С какого это лысого O(1), если нужно пролистать по структуре до попадания на нужный хэш? Мы не адрес всё-таки там храним. Сразу нужно понимать, что структура с абстрактным множеством эл-тов не будет выдавать такие низкие сложности.
хэшмапа это просто массив, где посчитанный хеш является индексом, по которому хранится значение.
Поиск в массиве по индексу происходит за О(1).
Отлично рассказываешь, думаю нужно больше такого контента)
Спасибо. Нравится, что без воды.
1:33 1:35 1:35 1:36 1:36 1:37 1:37 1:38 1:39 1:39 1:40 1:40 1:40
Но ведь часто нужно хранить сортированные данные, для поиска по больше, меньше, ренжам, префиксам.
Так что далеко не всё хэшмапа покрывает.
Интересно, но пока непонятно. Язык на котором пишу (Autoit) знает только про массивы. Ничего лишнего)
dict в python реализован с помощью хэш-таблицы, а не дерева
Во всех случаях, где больше 1 элемента, хэш таблица быстрее массива
Лучший канал по айти
2:22 в плюсах строки изменяемые
В стандарте да. Если использовать std::string.
Возможно он имел ввиду const char*
@@cheerwizard21 Согласен, но, например, char* - тоже строка, и она вполне изменяемая)
Медленно говоришь, можно еще быстрее?
Dude you ain't talking about quantum physics, it feels like this guy wants to sell you that it's a hard concept. Lol, it's not.
Уточнение. В c++ строки изменяемые 2:23 .
Э, в смысле Удзумаки 10, там все 100 должно быть!
А видео четкое:)
офигенский материал, супер
В python dict реализован с использованием структуры данных hash table
4:15 В первый момент подумал, что это Гарольд из мема :)
бомба бро, супер базированная база, мб попробую использовать вместо векторов
чел просто подогрел аудиторию и дал ссылки на рефы 🤡🤡🤡🤡🤡💩💩💩💩.
А если серьезно, то ничего плохого в этом нет. Но инфа по-любому полезная. Спасибо
Контент годный, объяснение самобытное, чёткое, понятное. Вообще канал классный. А вот запомоиться об остопи3девшую всему интернету Скулль-FUСК-тори - это позор. Лучше бы казино какое рекламировал, чем этих вонючих лохотронщиков (они сами признались, что львиная доля бюджета у них идёт на рекламу - скупили почти всех блогеров-проституток - даже Гоблин не устоял, продал свою жопку и честное имя за пачку баксов).
Саурон был бы в восторге от массивов в PHP.
Шикарный материал 👍👍👍
ребят, подскажите, стоит ли учить Php или Python для Бэк-Энда?
питухон
Можешь дать какие-то статьи или видео, а не книжки, пожалуйста
Вот вы говорите что в Хеш таблицах переход происходит по индексу?
Если массив с Int индексами, то теоретически переход происходит к элементу методом умножения к адресу, где непрерывно находятся данные.
Но если Хеш это некая сумма элементов (символов) то как происходит "мгновенный" переход? :)
Ведь всё в итоге компилится в ассемблер и код.
И как бы не очень понятно как без "тупого" перебора таких хеш индексов происходит поиск нужных данных?
Или я что-то пропустил? ;)
Задача в том, чтобы найти индекс по значению. Поиск перебором это простой проход по массиву/списку и сравнение каждого элемента О(N). Очевидно, это не касается деревьев и сортированных массивов (где есть бинарный поиск), O(log n). В хэш-таблице индекс получается из значения вызовом хэш-функции. Соответственно проверяется малое количество элементов (те, у которых совпало значение хэш-функции), O(1).
JS бы еще в примеры добавить...
Если грубо переложить на русский unorder set= aн' оодэд cэт или эн' оодэд сет. Видишь, Р отсутствует. Не надо благодарности, это в качестве бл. за твой контент :)
Я вижу старание есть, но мисс прононс всетаки есть. По береги наши уши плз :)
Гениально
Lua: смотрите, как они извращаются, чтобы достичь 1% моей силы!
Бро, где обещаенные уроки по С++ ?
В питоне хэш мама, по крайней мере взятие элемента и проверка делаются за константу точно
А у Вас есть видео про GUI ??
0:42 ну кто ж берет остаток от деления на 10? Вся эта история гораздо лучше работает в кольцах вычетов, где основание - простое число
а в чем разница...
@@Ilya-kondakov подумал, что возможно в данном случае и не в чем, а мысль в голове просто засела с курса "математические методы защиты информации", где в криптографии связано со сложностью обнаружения
Я думал, что функция вычисления индекса будет посложнее: hash & (bucket_amount - 1). Или так для упрощения видоса просто слелали?
Это просто оптимизация. Чтобы не вычислять каждый раз остаток от деления (а это довольно тяжёлая операция), делают размер массива равный степени двойки. Тогда остаток от деления будет такой же как в вашей формуле, а битовые операции значительно быстрее вычисления остатка. Но для понимания работы хеш таблицы эта формула не нужна.
Все круто, но Juniorу работу хрен найдёшь. А так да, объявления есть 🙂
а что скажешь про разоблачения от black sun?
Написал недавно мапу, сет и мультисет шаблонные) почему я не посмотрел это видео до?)
Никогда не любил хеш функции, чёрт его знает сколько там будет коллизий. Для меня указатели всегда были надёжне- error: memory access violation: core dumped. (хоть и за указателями надо следить)
А как тогда представить строку, которая будет ключем в виде индекса в вашем примере? Ее ведь нужно пропустить через хэш-функцию. Ну если указтаели используете, то придется все равно сделать что-то типа *(arr + index)
@@Kalin_cheetah для этого есть ещё одно дерево, но я забыл как оно называется (чото там то ли постфиксное, то ли префиксное, то ли суффиксное дерево)
да можно и на ассемблере все писать)
@@torburgmax вопрос был вообще не про ассемблер, а про структуры данных. Просто у Си эта ошибка хотябы видна, а если использовать массив с индексами вместо указателей, то этой ошибки не будет, у тебя просто программа будет медленно но верно сыпаться без ошибок.
@@Z_Z.t какой вопрос?) я имею в виду, что нужно просто выбирать подходящий метод решения проблемы, и мне странно видеть фразы вроде "я не люблю хеш-функции". поэтому и предложил бантики перекладывать напрямую, чтобы все максимально контролировать)
йо, очень крутой видос! хотелось бы послушать про деревья и алгоритмы к ним
Годный контент 🎉
Спасибо!
Клёвая подача, очень клёвая! Респект!
Летс гоооу. Новое видео. Виндертон сделай видео о нейронках
с недавнего питона словарь у него стал упорядоченным
А чё пример hashа, в perlе не показал? Тем более, что в нём это было изначально и раньше других языков стало использоваться им пользоваться использоваться!
Как это строки в плюсах неизменяемые
С какого перепуга строки в плюсах неизменяемые? Всегда во всех стандартах они были mutable. string_view immutable но это только 17 стандарт и не строка это вовсе а view.
а нет желания написать какой нибудь фреймворк свой для общего образования работяг?
Он и написать фреймворк ,не смеши
вот уж что-что, а таблицы стоило бы на Lua объяснять
достаточно важный момент для понимания упущен, который объясняет, почему поиск элемента константен по времени. речь про сведение хэша к индексу итогового массива
Мужик, это всё хорошо, но когда будет стрим по С++, ну или по написанию Компилятора, очень ждём
А есть видео, где вы рассказываете о том как перешли от джава к с++?
А можешь объяснить, почему поиск в хэшмапе происходит за константное время ? Надо же найти в ней запись с нужным ключом, а для этого нужно пробежаться по всем элементам. Если они отсортированы, то можно использовпть бинарный поиск, но это все равно логарифмическое время, а не константное. В любом случае оно зависит от количества элементов в мапе и константным быть не может.
Потому что, в мапе ключи уникальны и не повторяются, поэтому за O(1), а не за О(n)
Вроде как-то так ))
Одна из реализаций хеш таблицы - это массив бакетов. В каждом бакете хранится список пар (ключ, значение). Чтобы в этом массиве найти ключ, нужно от ключа посчитать хеш (какое-то число, посчитаное каким-нибудь алгоритмом). Если взять остаток от деления хеша на количество бакетов, то получится индекс бакета в массиве. Дальше по этому бакету можно пробежаться и найти нужный ключ. По факту, каждая отдельная операция работает не совсем за константное время, а за количество объектов в бакете, но количество бакетов и хеш функции подбирают так, чтобы в каждом бакете было очень мало элементов. Всякими математическими методами можно доказать, что среднее количество элементов в бакете не растёт с увеличением количества элементов.
Когда элементов в таблице становится больше чем какой-то порог, то количество бакетов увеличивается и все элементы раскидываются заново.
@@руслангасак-н6сЕсли искать не по ключу, а по какому-то другому предикату, то поиск будет O(n), и даже хуже чем в линейном массиве. Потому-что тебе нужно итерироваться по указателях, потом считать память указателя, а потом только использовать предикат.
А почему комментариев нет? Давайте поддержите молодого программиста
Жду ролик на 10 часов по плюсам
разве в пайтоне хэшпамом не является словарь?
гений на челе смог мне объяснить мне принцип работы этой структуры... прошел универ, но так и не понимал, как работают словари и причем тут хеш)) спасибо
В стандартной библиотеке питона нету unordered hashmap, нужно создать кастомный класс для своих нужд
👍💯🗣️🗣️💅
питон иногда такой питон...
там всегда unordered, там проблемы дийкстру писать с несортированным сетом, это да
а зачем тебе анордеред? ордеред хэшмапа дает гарантию порядка при перечислении значений, а анордеред не дает. Поэтому ордеред всегда может заменить анордеред но не наоборот.