Тренировки по алгоритмам от Яндекса. Лекция 3: «Множества»

Расписание тренировок доступно по ссылке: yandex.ru/yaintern/algorithm-...
Чат в Телеграме для общения и вопросов о тренировках: t.me/joinchat/Ve7wRegrZtI0NjIy

[@maxpanteleev9448]

Черт возьми, как же приятно после лекций Бабенко слушать АДЕКВАТНОЕ человеческое объяснение и нормальную русскую речь вместо кучи странных неуместных математических терминов)))

[@MikhalevS]

Так уровень этих курсов значительно различается

[@bunnyrin]

@@MikhalevS А что лучше смотреть? Открытые лекции ШАДа по алгоритмам или это?

[@MikhalevS]

@@bunnyrin лекции ШАДа предполагают, что у вас уже был курс по алгоритмам. Так что начинать лучше с этого, как мне кажется)

[@tertiumorganum5665]

да, это потому что уровень 8 класса

[@FedorShmidt]

это самый ламповый преподаватель которого я видел

[@esergey12]

0:23 План лекции. 0:34 Что должно уметь множество. 1:45 Как устроено множество. 19:10 Наше собственное мультимножество. 25:13 Термины 26:26 Что можно хранить эффективно в множестве 29:41 Амортизированная сложность. 31:48 Решение проблемы с хеш-таблицей. 40:47 Задача 1. Найти, числа A+B=X 45:01 Задача 2. Пропущенная буква, словарь. 50:26 Ответы на вопросы

[@desygameschannel8390]

37:10 непонятный звук xD

[@amigo4884]

Хорошие лекции, спасибо вам

[@esergey12]

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

[@user-ol9es1ch9x]

Очень высокий уровень подачи, спасибо !

[@algosavage7057]

очень крутая лекция! Спасибо!

[@Velichkina_a]

Очень здорово, спасибо!

[@mak_whisk]

Спасибо большое!

[@mt_compl1cated]

29.11.22 Крутая лекция)

[@dimkafn]

Неужели во втором задании это является самым эффективным решением??

[@malwarewoman]

Как знания о множествах пригодится в программировании и какой области?

[@sashavpope]

На 1.75х освоил! Думаю 2х будет предел)

[@TheRunnerSVO]

конструкция со словами ans.append(word in goodwords) наполнит список булевыми значениями. Надо if вынести и просто добавлять слово, если оно прошло проверку

[@totgor3777]

В этом и состояла задача - ответить для каждого слова из текста на вопрос, состоит ли оно в словаре

[@user-ec1hy1rv1r]

не очень понятно, почему поиск элемента происходит за O(N+k), и почему в удалении говорится про сложность O(k/N)?

[@olegbokerov7152]

Поиск элемента тоже происходит за O(k/N) И это = О(1), т.е. константе, в случае равномерного распределения K элементов по N столбикам значений хэш функции

[@inbtcwetrust6747]

44:43 подождите но разве при поиске числа в массива(find (C++)) мы не перебираем этот же массив тем самым получив сложность O(N^2) ? или в Python if x - nownum in prevnums это что то менее затратное чем find() в C++ ?

[@user-lu3zp4gf4b]

а где там массив? там множество. до этого обсуждали за сколько в множестве ищутся элементы

[@floumaster7346]

Здравствуйте, блин почему вы не ведёте на информатике. регионах от Сириуса?

[@JoffreyB]

Сириуса Блека?

[@user-xs8lx7xq9t]

Я немного не понимаю, почему в реализации set, нельзя просто удалить x при xlist[i] == x; ведь мы создали список внутри списка, а списки и так поддерживают функцию удаления из любого места, возможно реализация в видео быстрее, но я все же думаю, что можно было и воспользоваться функцией удаления

[@tonykabin5326]

Она работает за N, если не конец списка

[@user-lu3zp4gf4b]

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

[@mas0n_]

@@user-lu3zp4gf4b Что ты подразумевал под "список в питоне это не список как в плюсах"? Ты имел в виду под списком в плюсах односвязный/двусвязный список?

[@fdfasdfsdfasf]

В исходной версии кода ошибка в delete, после pop необходимо выйти из цикла. size = 10 myset = [[] for _ in range(size)] def add(x): if not find(x): myset[x % size].append(x) def find(x): h = x % size for now in myset[x % size]: if now == x: return True return False def delete(x): xlist = myset[x % size] for i in range(len(xlist)): if xlist[i] == x: xlist[i] = xlist[len(xlist) - 1] xlist.pop(-1) break

[@ilsaffff]

return тоже обеспечивает выход из цикла, т.к. выходит из функции, соответсвенно из цикла тоже

[@leonidk2064]

Лекция хорошая, но в первой задаче есть логическая и алгоритмическая ошибка: 1. Пример: если Х=8 и последовательность 4,4,5,3, то приведенный в лекции алгоритм даст ответ 4,4 Хотя по условию задачи мы должны вернуть 2 разных числа, а они в данном случае 5 и 3. Это логическая ошибка. 2. алгоритмическая ошибка в том, что в худшем случай мы будем приближаться к перебору второй степени. Пример: дана убывающая последовательность: nums = [*range(1_000_000,0,-1)], а Х=3. Поскольку ответ 2,1 мы должны перебрать весь 1 млн элементов, но в приведенном алгоритме мы вынуждены хранить в множестве все элементы до 2-х включительно и делать бесполезные операции поиска по множеству, которые будут отнимать ненужное время. Правильный вариант: def anymame(nums, x): prevnums = set() for nownum in nums: if 0 < x - nownum != nownum: if x - nownum in prevnums: return nownum, x - nownum prevnum.add(nownum) return 0, 0

[@tvoya.katunya]

Можно добавить проверку дополнительную: !(x - current === current) const twoTermsWithSumX = (nums, x) => { const previous = new Set(); for (let current of nums) { previous.add(current) if (previous.has(x - current) && !(x - current === current)) { return `${current}, ${x - current}` } } }

[@fdfasdfsdfasf]

На самом деле ошибки нет. Под различными числами понимались различные объекты. В вашем примере две четверки - это 2 разных объекта. Ошибка заключалась в том, что если ваш массив состоит из следующих чисел. [4, 2, 12] и Х=8 Когда мы решаем за квадрат, получится, что четвёрка будет использоваться 2 раза, а это один и тот же объект. Ответ будет (4, 4), хотя, четверка то одна. Как такое может быть? Дальше лектор исправил эту ошибку, добавив ограничение на пароход по цифрам.

[@TopUser2022]

хах, в первой задаче второе решение тоже имеет квадратичную сложность оператор in - это тот же цикл for

[@homie2694]

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

[@TopUser2022]

@@homie2694 интересно, где же вы там словарь увидали?)

[@homie2694]

@@TopUser2022 имелся в виду set)

[@RomanTokarenko]

9:14 рассказываете про сет, а фактически рассказываете про хеш-таблицу. Как-то странно. Не совсем понял, зачем так рассказ построен

[@user-pl9ec3ns6f]

Отличий HashSet в реализации от HashMap совсем не много. В питоне так вообще set это практически dict без значений и методами множеств.

[@RomanTokarenko]

@@user-pl9ec3ns6f вы правы, все так, просто классически рассказ строят иначе, сначала про внутрянку хеш-таблицы говорят, а потом говорят, что хеш-сет использует ее внутри себя, а тут наоборот. Это и смутило

[@codemystery]

а почему в первом задании нельзя пройтись один раз циклом по множеству складывая if nums[i] + nums [i+1] == x ? плюс еще проверку сделать в конце на наличие элемента nums[i+1]. Это тоже O(N)

[@user-dv7yl6kg8y]

Потому что у вас проверяется только сумма соседних чисел.

[@funkindy]

19:40 [[]]*setsize же

[@megacybercat]

Это создаст setsize одинаковых списков. Если изменить один, так же изменятся и остальные. Поэтому используют цикл

[@funkindy]

@@megacybercat резонно