Понедельник начинается в субботу.
А. Стругацкий, Б. Стругацкий.

Прошедшее забыто, грядущее сокрыто, настоящее даровано. Поэтому его и зовут настоящим!
Мудрая Черепаха из «Кунг-фу Панда»

Сегодня пойдет речь о методе, который я применяю, когда уматывают планы и лениво что-то делать вообще. Я знаю, есть люди, не любящие планирование. Есть люди, которые не любят загадывать. Есть те, кому просто непонятно, как работает его организм. Во всех этих состояниях я бывал, делюсь опытом.

Метод заключается в том, что основан на одной мысли: есть всего один день, сегодняшний, в котором и нужно делать все по максимуму для результата.

Под катом простая схема, как этого достичь.

Решая упражнения к книге «Программируем коллективный разум», я решил поделиться реализацией одного из алгоритмов упомянутого в этой книге (Глава 2 — Упражнение 1).

Исходные условия следующие: пусть мы имеем словарь с оценками критиков:

critics={'Lisa Rose': {'Superman Returns': 3.5, 'You, Me and Dupree': 2.5, 'The Night Listener': 3.0}, 
           'Gene Seymour': {'Superman Returns': 5.0, 'The Night Listener': 3.5, 'You, Me and Dupree': 3.5}}

Чем выше оценка, тем больше нравится фильм.
Надо вычислить: насколько схожи интересы критиков для того, например, чтобы можно было на основе оценок одного рекомендовать фильмы другому?

Добрый день, Хабрахабр. Это еще один пост в рамках моей программы по обогащению базы данных крупнейшего IT-ресурса информацией по алгоритмам и структурам данных. Как показывает практика, этой информации многим не хватает, а необходимость встречается в самых разнообразных сферах программистской жизни.
Я продолжаю преимущественно выбирать те алгоритмы/структуры, которые легко понимаются и для которых не требуется много кода — а вот практическое значение сложно недооценить. В прошлый раз это было декартово дерево. В этот раз — система непересекающихся множеств. Она же известна под названиями disjoint set union (DSU) или Union-Find.

Условие

Поставим перед собой следующую задачу. Пускай мы оперируем элементами N видов (для простоты, здесь и далее — числами от 0 до N-1). Некоторые группы чисел объединены в множества. Также мы можем добавить в структуру новый элемент, он тем самым образует множество размера 1 из самого себя. И наконец, периодически некоторые два множества нам потребуется сливать в одно.

Формализируем задачу: создать быструю структуру, которая поддерживает следующие операции:

MakeSet(X) — внести в структуру новый элемент X, создать для него множество размера 1 из самого себя.
Find(X) — возвратить идентификатор множества, которому принадлежит элемент X. В качестве идентификатора мы будем выбирать один элемент из этого множества — представителя множества. Гарантируется, что для одного и того же множества представитель будет возвращаться один и тот же, иначе невозможно будет работать со структурой: не будет корректной даже проверка принадлежности двух элементов одному множеству if (Find(X) == Find(Y)).
Unite(X, Y) — объединить два множества, в которых лежат элементы X и Y, в одно новое.

На рисунке я продемонстрирую работу такой гипотетической структуры.