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

[igorpom]

51:28 - почему писать гораздо медленнее, чем читать.

Это связано с тем, что при чтении мы обращаемся к адресу в памяти и считываем. Возможно, даже не из оператиной памяти, а из кеша процессора, что еще быстрее.
А при записи мы сначала проверяем есть ли достаточно места в зарезервированном участке памяти, если нет, то, возможно, пройдет удаление неиспользуемых объектов, если и это не помогло, то пойдет запрос к ядру системы на выделение еще одногоучастка памяти для этого потока, если в озу нет свободного места, ядро операционки будет определять, что можно выгрузить из оперативки в файл подкачки на диск, сама запись на диск тоже долгая. В любом случае, даже без выгрузки на диск, запись дольше чтения будет)

[maxpanteleev]

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

[FedorShmidt]

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

[esergey]

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 Ответы на вопросы

[esergey]

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

[ИванКозловский-шн]

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

[gespsy]

23:12 по идеи нужно же удалить элемент под номером len(xlist) - 1, а не i - ый

[TheRunnerSVO]

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

[dimkafn]

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

[inbtcwetrust]

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

[malwarewoman]

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

[АнастасияКириллова-зт]

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

[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

[floumaster]

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

[leonidk]

Лекция хорошая, но в первой задаче есть логическая и алгоритмическая ошибка:
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

[sashavpope]

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

[ИванТимошенков-ыг]

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

[RomanTokarenko]

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

[TopUser]

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

[codemystery]

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