No birds

PageRank и блочная структура web

2009-03-16T15:38:00.011+03:00

Каждая страница в web может однозначно идентифицироваться парой чисел: идентификатором сайта, на котором она находится, и внутрисайтовым идентификатором страницы (уникальным только в пределах сайта). Эту пару можно считать уникальным идентификатором страницы в web.

Нарисуем график. По осям x и y расположим web-страницы, упорядоченные по их идентификатору: порядок определяется идентификатором сайта, а для страниц одного сайта – внутрисайтовым идентификатором. Если страница a ссылается на страницу b, на графике нарисуем точку с координатой (a, b). Вот так выглядит такой график:

Если ограничиться только страницами из домена .com, то график выглядит так:

Приблизимся ещё на один шаг – рассмотрим страницы, принадлежащие сайтам доменов stanford.edu и berkeley.edu:

Картинки взяты из Efficient Parallel Computation of PageRank (Christian Kohlschutter и др.) и Exploiting the Block Structure of theWeb for Computing PageRank (Sepandar D. Kamvar и др.).

Диагонали на графиках состоят из цепочки квадратных блоков. Некоторые из них больше, некоторые меньше, но в основном они имеют примерно одинаковый размер.

Каждый такой блок – это отдельный сайт. Страницы внутри сайта связаны ссылками между собой гораздо плотнее, чем со страницами других сайтов. По статистике 90% ссылок в web – внутрисайтовые.

Это открытие способствовало появлению алгоритмов вычисления PageRank, которые позволяют, как ускорить само вычисление, так и осуществлять его параллельно на нескольких машинах.

Самый известный из них так и называется – метод блочной структуры.

Метод блочной структуры (Block structure method)

Алгоритм состоит из четырёх шагов:

1. Строится граф сайтов. В этом графе сайт a связан с сайтом b, если на сайте a есть страница, ссылающаяся на страницу сайта b. Для этого графа выполняется классический PageRank. В результате для каждого сайта мы имеем некое число, которое можно назвать его рейтингом.

2. Затем каждый сайт обрабатывается в отдельности. Мы анализируем внутреннюю структуру: применяем классический PageRank к графу страниц сайта. Ссылки между сайтами игнорируются. Таким образом, для каждой страницы мы получаем так называемый локальный PageRank. Этот этап можно выполнять параллельно на нескольких машинах.

3. Локальный PageRank каждой страницы умножается на рейтинг сайта, на котором она находится и записывается в вектор Z.

4. Вектор Z используется как начальный вектор для вычисления классического PageRank для полного графа web-страниц. При использовании такого начального вектора, необходимое количество итераций сокращается вплоть до 50%.

Вычисление локального PageRank имеет следующие свойства:

1. Т.к. отдельные сайты значительно меньше всего web, локальный PageRank можно вычислять, храня необходимые данные в памяти, а не на жёстком диске, что существенно ускорит работу

2. Локальный PageRank можно вычислять параллельно на нескольких машинах

3. Алгоритм PageRank для графа страниц большинства сайтов сходится достаточно быстро – иногда бывает достаточно всего нескольких итераций

То есть выигрыш метода блочной структуры достигается за счёт того, что 50% итераций PageRank на полном графе заменяются более эффективными операциями.

Сайт, как правило, считается синонимом хост. Конечно, есть методы определения более точных границ сайта на основе алгоритмов кластеризации. Но, я полагаю, что приближение сайт = хост работает вполне адекватно.

Метод блочной структуры – это только один из алгоритмов, вдохновлённых блочной структурой web. Другие алгоритмы отличаются в основном 3-м и 4-м этапом – т.е. тем как из рейтинга сайтов и локальных PageRank получается окончательный результат.

Многие из этих алгоритмов добиваются существенного ускорения работы за счёт отказа от вычисления точного PageRank и вычисляют его аппроксимацию. Аппроксимации часто бывает вполне достаточно. Это позволяет отказаться от вычислительно самого сложного 4-го этапа – вычисления PageRank для полного графа web-страниц. Подробную информацию можно найти среди статей из подборки.

Siterank

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

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

Недостатком PageRank является то, что он поощряет старые страницы, на которые уже накопилось много ссылок, и недооценивает новые, на которые ссылки ещё не успели появиться в большом количестве.

Если учитывать рейтинг сайта, у новой страницы, появившейся на хорошем сайте, уже сразу может быть некий стартовый бонус, что не позволит ей потеряться в пучине.

Такой алгоритм, учитывающий структуру межсайтовых связей, может быть более устойчивым к поисковому спаму – манипулировать структурой страниц гораздо проще, чем структурой связей между сайтами (хостами).

Подборка статей о PageRank

2009-03-16T15:30:00.004+03:00

Вот выложил небольшую подборку статей о PageRank: скачать [14.3 МБ]. В них можно найти более подробную информацию о всём том, что я рассказывал о PageRank, и не только. Статьи на английском.

Развитие PageRank

2009-03-12T17:50:00.062+03:00

С того момента, когда PageRank был впервые представлен в 1998 году, было потрачено немало усилий, чтобы улучшить его качество и скорость вычисления. В этой обзорной и достаточно популярной статье я опишу основные направления исследований вокруг PageRank и варианты алгоритма.

Я разрабатываю систему оценки важности web-страниц на основе входящих и исходящих ссылок в компании Нигма, поэтому смотрю на PageRank с математической стороны, со стороны разработчика а не seo.

Я не буду пересказывать здесь многократно описанные основы PageRank. Предполагается, что читатель знает, что это вообще такое. Если же нет, то для начала могу порекомендовать статью Растолкованный PageRank.

На следующей картинке схематически представлены основные направления исследований, окруживших PageRank. Каждому овалу на схеме будет соответствовать отдельная глава статьи.

PageRank с математической стороны

PageRank основан на математической модели случайного блуждания «пользователя» в сети интернет. В некоторый момент он находится на одной странице, затем случайным образом выбирает одну из ссылок и переходит по ней на другую. «Пользователь» произвольно выбирает ссылки, не отдавая предпочтение каким-либо из них.

PageRank страницы – это вероятность того, что блуждающий «пользователь» находится на данной странице.

Сделаем небольшой набросок того, как рассчитать эту вероятность.

Пронумеруем web-страницы целыми числами от 1 до N.

Сформируем матрицу переходов P, содержащую вероятность перехода «пользователя» с одной страницы на другую. Пусть deg(i) – количество исходящих ссылок на странице i. В таком случае, вероятность перехода со страницы i на страницу j равна:

P[i, j] = 1 / deg(i), если i ссылается на j
P[i, j] = 0, если i не ссылается на j

Пусть p^(k) – это вектор, содержащий для каждой страницы вероятность того, что в момент k на ней находится «пользователь». Этот вектор – распределение вероятностей местоположения «пользователя».

Предположим, что «пользователь» может начать своё бесцельное блуждание с любой страницы. То есть, начальное распределение вероятностей равномерно.

Зная распределение вероятностей в момент k, мы можем узнать распределение вероятностей в момент k+1 по следующей формуле:

В основе этой формулы не более чем правила сложения и умножения вероятностей.

Математически мы пришли к цепи Маркова с матрицей переходов P, где каждая web-страница представляет собой одно из состояний цепи.

Но нам нужно знать вероятность нахождения «пользователя» на странице независимо от того, сколько шагов k он сделал от точки начала блуждания.

Мы берём начальное распределение вероятностей p⁽⁰⁾. Считаем по представленной выше формуле распределение p⁽¹⁾. Затем по той же формуле считаем p⁽²⁾, затем p⁽³⁾ и т.д. до тех пор, пока некие p^(k-1) и p^(k) не будут отличаться лишь незначительно (полное равенство будет достигнуто при k стремящемся к бесконечности).

Таким образом, последовательность p⁽¹⁾, p⁽²⁾, p⁽³⁾ … сойдётся к некому вектору p = p^(k). Интересно, что вектор p на самом деле не зависит от начального распределения (т.е. от того, с какой страницы начал своё блуждание воображаемый «пользователь»).

Вектор p таков, что в любой момент (начиная с некоторого момента k), вероятность того, что «пользователь» находится на странице i, равна p[i]. Это и есть искомый PageRank.

Этот алгоритм называется методом степеней (power method). Он сойдётся только в том случае, если выполняются два условия: граф страниц должен быть сильно связным и апериодическим. Как достигается выполнение первого условия, будет рассмотрено далее. Второе же без дополнительных усилий справедливо для структуры web.

Примечание

При выполнении условий сильной связности и апериодичности, согласно эргодической теореме, цепь Маркова с матрицей перехода P имеет единственное стационарное распределение p:

PageRank и является стационарным распределением цепи Маркова.

Также это выражение представляет собой собственную систему, а вектор p — собственный вектор матрицы A. Поэтому и применяется метод степеней — численный метод для поиска собственных векторов.

Висячие узлы (dangling nodes)

Висячие узлы – это страницы, которые не имеют исходящих ссылок. Страница может не иметь исходящих ссылок просто потому, что у неё их нет, либо потому, что она не была прокраулена (crawled) – т.е. страница попала в базу, т.к. на неё ссылаются другие прокрауленные страницы, но сама прокраулена не была, и о её исходящих ссылках ничего не известно.

Для вычисления PageRank в графе страниц не должно быть висячих узлов. Сумма каждого ряда матрицы переходов должна быть равна единице (row-stochastic), для висячих же узлов она окажется равной 0 – входные данные алгоритма будут некорректными.

По статистике, даже если поисковая система имеет достаточно большой индекс, 60% страниц оказывается висячими. Поэтому то, как с ними поступать, оказывает большое влияние на ранжирование.

Метод удаления

Изначальный подход, предложенный Пэйджем, заключается в том, чтобы удалить висячие узлы перед вычислением PageRank. В качестве обоснования предлагается то, что висячие узлы не оказывают влияния на другие страницы. Но это не совсем так – удаляя их, мы уменьшаем количество исходящих ссылок страниц, которые на них ссылаются. Тем самым мы увеличиваем значение PageRank, которое эти страницы передают через свои ссылки.

Кроме того, удаление висячих узлов, может создать новые висячие узлы. Таким образом, требуется проделать несколько итераций удаления (обычно 5 или что-то около того).

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

Считать связанными со всеми другими страницами

Наиболее популярный трюк заключается в том, чтобы считать висячие узлы связанными со всеми другими страницами. В модели случайного блуждания данный метод находит подходящее объяснение: попав на страницу без исходящих ссылок, «пользователь» перескакивает на любую другую страницу сети случайным образом.

Можно считать вероятность попадания «пользователя» на страницу из висячего узла в результате такого перескока распределённой равномерно среди всех страниц сети. Но можно и не считать её таковой. Например, можно исключить попадание из висячего узла на другой висячий узел. Или распределить вероятность между страницами по аналогии с аристократическим вектором телепортации, о котором будет рассказано ниже в главе Телепортация.

Матрица переходов модифицируется следующим образом:

d[i] = 1, если i – висячий узел, и 0 в противном случае
v[j] – вероятность попадания «пользователя» на страницу j из висячего узла

Шаг назад (step back)

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

Петля (self-link)

Упомяну кратко ещё один способ. Каждому висячему узлу можно добавить ссылку на самого себя – это приведёт в порядок матрицу переходов. Но после вычисления PageRank, результат придётся определённым образом скорректировать. Подробности описаны в G. Jeh and J.Widom “Scaling Personalized Web Search.”

Телепортация

Решение проблемы висячих узлов ещё не даёт сильную связность графа. Поэтому вводится телепортация.

В модели случайного блуждания это выглядит так: «пользователь», находясь на некоторой странице, с вероятностью c переходит по одной из её ссылок и с вероятностью (1 – c) * v[j] перескакивает (телепортируется) на страницу j. Стохастический вектор v описывает вероятность телепортации на ту или иную страницу и называется вектором телепортации.

c как правило выбирается в диапазоне 0.85 – 0.9. Большие значения дают более точные результаты, но более медленную сходимость. Меньшие значения – быструю сходимость, но менее точные результаты.

Плюс ко всему, чем меньше значение с, тем больше возможностей для поискового спама – достаточно создать на сайте огромное количество страниц и они будут, как зонтик, собирать значительный PageRank, получаемый за счёт телепортации.

Существует два способа выбора вектора телепортации: демократический и аристократический. Демократический вектор содержит одинаковые значения вероятности для всех страниц. Это стандартный вариант. Аристократический содержит низкую вероятность для обычных страниц и более высокую для избранных достоверно качественных неспамерских страниц. Последний способ явно поощряет избранные страницы в ущерб остальным, зато более устойчив к поисковому спаму.

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

Значение v[j] не должно быть равно 0. Иначе может оказаться, что j недосягаема из некой другой страницы, что означает нарушение сильной связности.

Телепортация модифицирует матрицу переходов следующим образом:

v – вектор телепортации

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

Ускорение метода степеней

Многие исследователи пытались ускорить сходимость метода степеней. Посмотрим на самые удачные способы.

Для удобства повторю формулу, которую мы используем на каждой итерации. Назовём её формулой А:

Метод Гаусса-Зейделя (Gauss-Seidel method)

На каждой итерации в методе степеней мы используем значения элементов вектора p^(k) чтобы рассчитать вектор p^(k+1). Отличие метода Гаусса-Зейделя в том, что мы сразу используем значения вычисленных элементов вектора p^(k+1) для вычисления его остальных элементов.

В методе Гаусса-Зейделя мы последовательно элемент за элементом вычисляем вектор p^(k+1). При это там где, согласно формуле А, нам нужно использовать значение p^(k)[i] мы используем p^(k+1)[i], если этот элемент вектора уже был вычислен.

Согласно экспериментам этот метод способен сократить необходимое количество итераций на 40%. Его недостаток в том, что его достаточно сложно вычислять параллельно.

Методы экстраполяции (Extrapolation methods)

В этой группе методов мы проделываем некоторое количество d обычных итераций метода степеней. Затем на основе результатов этих итераций строим аппроксимацию решения и используем её вместо p^(k) для следующей итерации. Через следующие d итераций повторяем трюк. И так далее пока алгоритм не сойдётся.

Исследователям удавалось достичь сокращения необходимого количества итераций на 30%.

Адаптивный метод (Adaptive method)

Этот метод основан на наблюдении, что значительная часть элементов вектора p сходится гораздо быстрее остальных и затем почти не меняется. Ускорение в этом методе достигается за счёт того, что мы не пересчитываем значения таких элементов.

Если в какой-то момент k для некоторого элемента i обнаруживается что p^(k+1)[i] - p^(k)[i] меньше определённого порога, мы считаем, что значение PageRank для страницы i найдено и более не пересчитываем i-тый элемент вектора p.

Исследователям удавалось достичь сокращения времени работы метода степеней на 20% при помощи этого трюка.

Однако данный метод требует периодически переупорядочивать данные, чтобы избежать вычисления тех элементов, значения которых считаются уже найденными. Поэтому адаптивный метод плохо подходит для больших графов – переупорядочить огромный объём данных становится слишком дорогой задачей.

Метод блочной структуры (Block Structure Method)

Web имеет блочную структуру. Это открытие столь интересно, что я намерен посвятить ему отдельный пост. Там же и обсудим этот метод.

UPD: пост о блочной структуре web.

Численные методы

Вычисляя значение PageRank, мы ищем такой вектор p, что

Это выражение является так называемой собственной системой, а p – собственный вектор матрицы A. Задача поиска собственного вектора может быть представлена системой линейных уравнений. В нашем случае это будет огромная, но всё же обычная система, которая может быть решена при помощи численных методов линейной алгебры.

Тем не менее, вычисление PageRank численными методами ещё находится в экспериментальной области. Каковы будут характеристики и свойства этих методов на реальных графах web пока не понятно.

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

Параллелизация

Вычисление PageRank параллельно на нескольких машинах позволяет существенно ускорить работу.

По сути методы параллелизации можно разделит на два типа.

Первые разделяют граф страниц на плотно связные компоненты – группы страниц плотно связанных ссылками между собой и имеющие относительно немного ссылок на страницы вне группы. PageRank для каждой такой группы вычисляется параллельно. Процессы/потоки периодически обмениваются информацией, когда дело доходит до ссылок между страницами разных групп.

Ко второму типу относятся методы, использующие блочную структуру web. О них мы поговорим в уже обещанном выше посте о блочной структуре.

UPD: пост о блочной структуре web.

Оптимизация ввода-вывода

Это довольно интересная тема, которую я приберегу для одного из следующих постов. Я представлю три алгоритма, которые будут интересны не только с точки зрения вычисления PageRank, но и вообще с точки зрения обработки больших объёмов информации.

Эволюция графа

Довольно естественной кажется идея не пересчитывать PageRank для всех страниц целиком, а найти способ обновлять его по мере эволюции графа страниц (по мере эволюции web).

В «Incremental Page Rank Computation on Evolving Graphs» Prasanna Desikan и др. предлагают следующий способ.

Сперва выделить часть графа, состоящую из страниц, до которых не существует путей от новых страниц, исчезнувших страниц, либо страниц, ссылки которых были изменены. Удалить эту часть графа, оставив только граничные узлы (т.к. они влияют на PageRank оставшихся страниц). Посчитать PageRank для оставшегося графа. Затем отмасштабировать значения PageRank с учётом общего количества страниц – т.к. количество страниц влияет на часть PageRank, получаемую за счёт телепортации.

Замечу, что полученный в результате PageRank не является точным, а всё же некой аппроксимацией.

По различным данным от 25% до 40% ссылок между web-страницами меняются в интернет в течение недели. Такая скорость изменения, на мой взгляд, оправдывает полный пересчёт PageRank всех страниц.

Персонализация

Представление о важности той или ной страницы во многом субъективно. То, что покажется одному отбросом, другой сочтёт изумрудом. Пусть есть очень качественная страница об игре керлинг, но я совершенно не хочу, чтобы она вылезала лично мне в топ. Чтобы учитывать в ранжировании интересы конкретного человека был придуман персонализированный PageRank.

Выбирается какое-то количество категорий, по которым можно классифицировать тематику тех или иных страниц (или сайтов). Например: культура, спорт, политика и т.п.

Пусть T[j] – множество страниц, принадлежащих к категории j (или расположенных на сайте, принадлежащем к данной категории).

Для каждой категории формируется особый вектор телепортации v (см. главу Телепортация).

v[i] очень мало, если страница i не принадлежит T[j], и значительно больше если принадлежит.

Для каждого тематического вектора телепортации вычисляется тематический PageRank p_j. Вычислить сто тематических PageRank для ста категорий вполне реально.

Допустим, у нас есть вектор k, сумма элементов которого равна единице. Значение k[j] отражает степень заинтересованности пользователя (реального, а не того из модели блуждания) в категории j.

Степень заинтересованности пользователя может быть указана явно, или она может быть сохранена в его профиле. Или она может быть выведена исходя из того, какие слова входят в запрос. Например, если запрос содержит слово fairtrade то можно вывести, что пользователь заинтересован на 0.4 в теме общество, на 0.4 в теме экономика и на 0.2 в теме политика.

Во время ранжирования результатов запроса пользователя для страниц используется следующее итоговое значение PageRank:

k[0] * p₀ + k[1] * p₁ + … + k[n] * p_n , где n – количество категорий

Таким образом, рейтинг страницы будет зависеть от того, что реально интересно пользователю.

Темы, которые будут рассмотрены в следующих постах

Оптимизация ввода-вывода

Siterank

UPD: Эта тема освещена в посте о блочной структуре web.

Насколько похожи лица людей?

2009-02-18T11:26:00.002+03:00

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

Рассматриваются цифровые полутоновые изображения. Такие изображения представимы матрицей целых чисел. Операциями сложения и умножения на число для изображений являются соответствующие матричные операции.

Можно найти ортонормированное базисное множество изображений B.

B = {F1, F2, ... , Fm}

Такое, что для любого изображения Ij из множества n изображений (n >> m):

Ij со штрихом — это аппроксимация исходного изображения Ij в виде линейной комбинации m базисных изображений.

Т.е. при помощи линейной комбинации m базисных изображений мы можем с некоторой точностью получить любое из n изображений некоторого множества.

Так причём же здесь человеческие лица...

В нескольких исследовательских проектах было продемонстрировано, что от 15 до 20 базисных изображений достаточно, для представления базы данных с изображениями человеческих лиц. То есть любое человеческое лицо можно представить набором всего 15-20 чисел (!). В любой момент по этим числам можно получить фотографическое изображение человеческого лица.

Как нужно использовать Hibernate?

2009-02-17T21:13:00.006+03:00

Когда я стал внедрять Hibernate, понял, что существует определённый стандартный способ его использования. У меня есть подозрение, что его специально не выставляют на показ начинающим пользователям, дабы не отпугнуть их тем, что на архитектуру их приложения накладываются новые требования со стороны тех средств, использование которых хотелось бы видеть прозрачным.

Стандартный способ использования Hibernate — паттерн Session per View. Согласно этому паттерну использование Hibernate должно выглядеть следующим образом: открывается сессия, получаются все необходимые данные, производятся вычисления, строится представление, сессия закрывается. После закрытия сессии никакие данные, полученные с момента её открытия, более не используются.

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

До тех пор пока вы используете объекты, полученные из Hibernate, вы должны иметь открытой сессию, в которой были получены эти объекты (или к которой были привязаны), и иметь активную транзакцию! Использовать эти объекты можно только в однопоточной среде! Иначе со стороны Hibernate возможны ошибки.

Обычно, создаётся некоторый перехватчик, срабатывающий при получении запроса. Он открывает сессию и делает её доступной для всех классов, методы которых выполняются в данном потоке обработки (что-то типа ThreadLocal).

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

Т.е. объекты, полученные из Hibernate — не совсем обычные POJO. Хоть об этом и уверяют на официальном сайте проекта. В чём же их отличие мы узнаем далее.

Начиная с Hibernate 3, везде, где только можно, выполняется ленивая загрузка, если явно не указано обратное. При помощи ASM'а Hibernate на лету генерирует байт код прокси-объектов и экранирует ими связи запрашиваемых объектов. За счёт этих прокси части объекта подгружаются по мере необходимости.

Если же сессия была закрыта, а использование объекта продолжается, то, в случае обращения к такому прокси возникает рантаймовое LazyInitializationException. Если же два потока в один момент обратятся к одному прокси, то поведение вовсе не предсказуемо, т.к. прокси используют сессию, а сессия предназначена только для однопоточного использования.

От ограничений Session per View можно избавиться, если в определённый момент иметь гарантию того, что объект загружен полностью со всеми своими связями. Тогда он станет обычным POJO. Его можно будет использовать после закрытия сессии и использовать многопоточно, если сам объект на это рассчитан.

Получить такую гарантию можно, если отключить для всех связей этого объекта ленивую загрузку. Это довольно утомительно, т.к. нет способа отключить ленивую загрузку сразу для всего — придётся отключать её для каждого класса отдельно.

Второй способ — написать метод, который бы в необходимый момент мог вызвать полную инициализацию всего графа объекта. В Hibernate нет собственного такого метода, но он позволяет его реализовать:


public class LoadDragoon {

    private SessionFactory sessionFactory;

    private static Logger logger = Logger.getLogger(LoadDragoon.class.getName());

    public LoadDragoon(SessionFactory sessionFactory) {
        this.sessionFactory = sessionFactory;
    }

    public void forceLoad(Object obj) throws HibernateException {
        if (obj == null) {
            return;
        }

        Class entityClass = Hibernate.getClass(obj);

        if (!Hibernate.isInitialized(obj)) {
            logger.finest("Force initialization of " + entityClass.getName());
        }

        Hibernate.initialize(obj);
        ClassMetadata md = sessionFactory.getClassMetadata(entityClass);

        if (md == null) {
            return;
        }

        String[] propertyNames = md.getPropertyNames();

        for (String propertyName : propertyNames) {
            Type propertyType = md.getPropertyType(propertyName);

            if (propertyType.isEntityType()) {
                Object assoc = md.getPropertyValue(obj, propertyName, 
                    EntityMode.POJO);
                forceLoad(assoc);
            } else if (propertyType.isCollectionType()) {
                Object container = md.getPropertyValue(obj, propertyName, 
                    EntityMode.POJO);
                Hibernate.initialize(container);

                if (container instanceof Map) {
                    Map map = (Map) container;

                    for (Map.Entry entry : map.entrySet()) {
                        forceLoad(entry.getKey());
                        forceLoad(entry.getValue());
                    }
                } else {
                    Collection collection = (Collection) container;

                    for (Object element : collection) {
                        forceLoad(element);
                    }
                }  
            }
        }
    }

}

Злые модули

2009-02-17T21:00:00.008+03:00

Есть такая засада в C++, Java и, вероятно, в некоторых других языках. Функции, вычисляющие модуль целого числа (std::abs в С++ или Math.abs в Java), способны возвращать отрицательные значения!

Например, число типа long имеет максимальное значение 2147483647, а минимальное — -2147483648. Соответственно, модуль минимального числа типа long не может быть представлен типом long — функция просто молча вернёт переданное в неё отрицательное значение.


cout << "min = " << numeric_limits::min() << " ; max = " <<
    numeric_limits::max() << endl; 
cout << "abs(min) = " << abs(numeric_limits::min());

Вывод:


min = -2147483648 ; max = 2147483647
abs(min) = -2147483648

На это можно однажды крепко налететь...

В SmallTalk, к слову, такой проблемы нет. Т.к. ему вообще не свойственна проблема переполнения целых чисел. LargePositiveInteger, имеет неограниченый размер. А операции над ограниченным по размеру SmallInteger, при необходимости автоматически приведут к созданию LargePositiveInteger и использованию его в качестве результата.

synchronized

2009-02-17T20:48:00.001+03:00

Мужик подходит к кассе, чтобы сделать покупку. Говорит: "Девушка, дайте мне килограммчик картошки, полкило помидоров и ещё вот этот..." В этот момент встревает другой мужчина: "Девушка, а почём у вас перец?!" Девушка достаёт нож и режет горло обоим. Объекты, хорошо работающие в однопоточной среде, могут совершенно непредсказуемо повести себя в многопоточной.

Джайнистская логика

2009-02-17T20:44:00.000+03:00

Программисты обычно работают с бинарной логикой, рассматривающей два типа суждений: утвердительные и отрицательные. Иногда приходится работать с тернарной логикой, добавляющей третье суждение: "неизвестно".

В джайнизме же, введена семеричная логика! Джайнисты справедливо считают, что истиность любого суждения относительна. Каждое суждение порождено определёнными условиями и, следовательно, ограничено. Различные суждения об одном и том же предмете могут быть справедливыми каждое со своей точки зрения. Это воззрение во многом сформировало логику джайнистов.

Таким образом, признаётся семь типов условного суждения. Помимо утверждения (A обладает свойством B), отрицания (A не обладает свойством B), вводятся ещё пять:

1) А обладает свойством B, а также не обладает свойством B;
2) A есть неописуемое;
3) А обладает свойством B, и является неописуемым;
4) А не обладает свойством B, и является неописуемым;
5) А обладает свойством B, а также не обладает свойством B и является неописуемым;

К первому суждению прибегают, когда объект в некоторых условиях обладает определённым свойством, а в некоторых не обладает. В том случае, когда мы вынуждены одновременно приписать объекту такие характерные признаки, которые не совместимы, будучи противоположными или противоречивыми, объект есть неописуемое. Последние три типа суждений образуются посредством комбинаций. 3-е по списку утверждение означает, что объект может обладать некоторым свойством, но безотносительно к контексту (например, времени или пространству) ему не может быть приписан данный признак. 4-е и 5-е вводятся аналогично.

Это краткая характеристика. Тему можно было бы развить.

Думается, что логика джайнистов может быть выражена средствами классической логики. Мыслить же непосредственно их суждениями я бы не смог...

Собака

2009-02-17T20:33:00.003+03:00

Забавная картинка из книги Your brain on java издательства Oreilly.

Картинка расположена в контексте разговора о коллекциях, генериках и преобразовании типов:

Попугаи-киллеры, охотящиеся на овец

2009-02-17T20:24:00.001+03:00

Цитата из книги "Программист-прагматик" [Эндрю Хант, Дэид Томас]:

"Когда вы начинаете некий проект, придумайте имя для проектной команды, в идеале -- нечто из ряда вон выходящее. В прошлом мы называли проекты в честь попугаев-киллеров, охотящихся на овец, оптических обманов и мифических городов. Потратьте полчаса на придумывание самого идиотского брэнда и используйте его в ваших служебных записках и отчётах. В разговорах с людьми свободно упоминайте название вашей команды"

Безусловно стоит взять эту рекомендацию на вооружение!

Дихотомия

2009-02-17T20:14:00.003+03:00

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

В "The Art of Computer Programming" Дональда Кнута сообщается, что двоичный поиск впервые вызвал дискуссию в 1946 году, и вплоть до 1962 г. (!) никому не удавалось опубликовать алгоритм, корректно работающий с массивами длины, отличной от 2^n - 1.

О глазах

2009-02-17T19:57:00.002+03:00

Известно, что личность человека можно идентифицировать по радужной оболочке глаза. Однако, прежде чем стали внедряться системы, использующие этот факт, требовалось выяснить, насколько различаются радужные оболочки глаз разных людей. Требовалось найти надёжный способ вычисления по снимку человеческого глаза такого идентификатора, который был бы уникален.

В системе Sensar Secure System, предназначенной для идентификации пользователей банкоматов, по радужной оболочке вычисляется 2048-ми битный код. Значение каждого бита определяется путём вычисления корреляции двумерного вейвлета Габора с изображением радужной оболочки в 1024-х точках изображения. Комплексозначное корреляционное значение преобразуется в два бита кода.

Чтобы убедиться в пригодности такого способа, для кодов достаточно большого количества пар глаз были вычислены расстояния Хэмминга. Расстояние Хэмминга между двумя кодами это количество несовпадающих бит при их сравнении. То есть, это значение показывает насколько различаются радужные оболочки.

Было получено, что коды для двух глаз одного человека столь же независимы и столь же отличаются друг от друга как коды глаз совершенно разных людей. Иными словами, текстуры радужных оболочек своих собственных глаз различны и некоррелируют между собой!

Также любопытно следующее. Зрачок и радужная оболочка имеют круговую форму, но центры этих окружностей не совпадают.

+=

2008-08-02T09:37:00.009+04:00

Обычно считают, что в Java x += y (и аналогично -=, *= и т.п.) является лишь сокращённой записью x = x + y. Но это не вся правда. Посмотрим на следующий пример:

short s = 1;
s = s + 1;

Этот код не компилируется, несмотря на то, что 1 + 1 = 2 представимо типом short! Причина не только в том, что литерал 1 имеет тип int. Не будет компилироваться и такой вариант:

short s1 = 1;
short s2 = 1;
s2 = s2 + s1;

То же самое можно было бы написать с типами byte и char. Причина в том, что результат арифметических операций с использованием типов short, byte, char имеет тип int. Мотивация этого такова: к примеру, сумма двух byte может легко быть больше того, что влезет в byte. Но код можно исправить следующим образом без явного преобразования типов:

short s = 1;
s += 1;

short s1 = 1;
short s2 = 1;
s2 += s1;

На самом деле x += y, вопреки распространённому мнению, эквивалентно

x = (тип x) (x + y);

Т.е. включает в себя преобразование результата к типу x. То же самое верно и для операторов -=, *= и т.п.

Литералы

2008-08-02T08:14:00.006+04:00

Известно, что в java литералы целых чисел имеют по умолчанию тип int, а литералы чисел с плавающей точкой – double. Но, помимо различий в типе, есть ещё некоторое различие в поведении.

Не удивительно, что эта строчка при компиляции вызывает ошибку из-за несовместимости типов float и double:

float f = 25.2; // слева float, справа double

И, казалось бы, следующий пример тоже не должен был бы компилироваться, ведь int не преобразуется в byte неявно:

byte b = 127; // слева byte, справа int

Однако последний пример компилируется! В этом случае, если значение справа представимо типом byte (от -128 до 127), компилятор сам выполнит преобразование. Аналогично, без явного преобразования, целочисленные литералы можно присваивать типам short и char.

Проблема 2038

2007-01-29T15:50:00.005+03:00

Стандартная библиотека C++ не предоставляет подходящего типа данных для дат. C++ наследует структуры и функции для работы с датами и временем от C.

В C для представления даты/времени используется тип time_t. Это зависимый от реализации арифметический тип (в разных реализациях C/C++ может представлять различный диапазон значений), представляющий временной период (интервал времени) с точностью до одной секунды.

В большинстве реализаций time_t позволяет представить наибольший интервал времени в 2147483648 секунд. Это примерно 68 лет. Также в большинстве реализаций для представления текущего времени в качестве начала отсчёта используют 0:00:00 1 января 1970 года.

Т.е. в большинстве популярных реализаций невозможно представить даты и времена после 2038 года, и большая часть программного обеспечения перестанет работать, если заранее не принять меры!

В Visual C++ 2005 time_t является синонимом __time64_t, т.е. способен представить больший интервал и не подвержен ошибке 2038. Однако, это препятствует переносимости кода. Чтобы использовать обычный 32-битный time_t следует определить _USE_32BIT_TIME_T.

В Boost есть хорошая библиотека date_time, не подверженая проблеме 2038. Ожидается, что будущие средства стандартной библиотеки для работы с датой/временем будут основаны на date_time.