-
Юбилейный DevConfX пройдет 21-22 июня в Москве. Как всегда — Вы решаете, кто попадет в программу секции Backend — голосуйте за интересные доклады
круги друзей
- Автор темы Sky_Flex
- Дата начала
Sky_Flex
Новичок
HraKK? не умничай, может что такое конкретно "транзитивное замыкание графа" я и не знаю, но суть уловил: если изменений связей в графе значительно меньше происходит чем вызов этих связей для просмотра, то оптимальнее хранить все связи уже "просчитанными" как то отдельно, и менять их при изменении какой либо связи.
Crazy
Developer
Транзитивное замыкание -- это самоочевидное решение. Вот только рекомендую посчитать, сколько места понадобится для хранения.
Кроме того, не забываем, что нам нужен некоторый алгоритм обновления замыкания при изменении связей.
Но можно пойти и с другой стороны: если сеть большая и третий круг составаляет ее достаточно малую часть, то можно применить что-нибудь из арсенала инструментария для работы с разреженными данными.
Кроме того, не забываем, что нам нужен некоторый алгоритм обновления замыкания при изменении связей.
Но можно пойти и с другой стороны: если сеть большая и третий круг составаляет ее достаточно малую часть, то можно применить что-нибудь из арсенала инструментария для работы с разреженными данными.
Румата
Новичок
У меня еще идея родилась - можно напрямую написать [email protected] (или какое там у них мыло) и спросить, как они реализовывали 
Sky_Flex, так что, будем решать проблему? В каком виде у тебя хранится вся информация и какой объем ее? Насколько много связей между участниками Кругов?
Sky_Flex, так что, будем решать проблему? В каком виде у тебя хранится вся информация и какой объем ее? Насколько много связей между участниками Кругов?
bkonst
.. хочется странного?...
Ну, оценка сверху количества связей - n(n-1)/2, где n-количество пользователей. Для 100.000 пользователей при затратах 9 байт на представление одной связи (пусть связь содержит информацию о двух идентификаторах пользователей по 4 байта и 1 байт - длину пути) это составит ~42 ГБайт. Реально будет использоваться меньше, так как граф отношений может (будет) содержать несколько несвязных компонент (да и использовать "настоящее" транзитиное замыкание не нужно, так как оно будет содержать информацию о всех "кругах", а не только о трех первых - вместо этого можно ограничиться тем, что получится после третьей итерации).
Sky_Flex
Новичок
харниться в 2-х таблицах:
в первой все вершины, во второй все связи.
1-ая: 2,4,5,1,6,7,9.... (id-шки короче)
2-ая:
2-1
2-4
2-11
4-1
4-2
4-5
4-8
5-4
5-7
5-11
и т.д.
сейчас пытаюсь тощить рекурсивно... алгоритм придумываю, поиск в глубину рекурсивно работает, но не лучшие решения ищет, сейчас в ширину пишу )
с дейкстером не разобрался.
в первой все вершины, во второй все связи.
1-ая: 2,4,5,1,6,7,9.... (id-шки короче)
2-ая:
2-1
2-4
2-11
4-1
4-2
4-5
4-8
5-4
5-7
5-11
и т.д.
сейчас пытаюсь тощить рекурсивно... алгоритм придумываю, поиск в глубину рекурсивно работает, но не лучшие решения ищет, сейчас в ширину пишу )
с дейкстером не разобрался.
Crazy
Developer
Нам нужна какая-то статистика для оценки размеров кругов. В качестве простейшего примера беру свой аккаунт на linkedin.com:
1. 28
2. 800+
3. 140,300+
(кстати, эти плюсы уже подсказывают, что используется тот или иной алгоритм отложенных пакетных вычислений)
Всего пользователей -- 11,000,000.
Пугает то, что в третьем круге мы УЖЕ имеем более 100,000 пользователей.
Известно, что linkedin.com работает. Следовательно, они используют структуры, радикально отличные от транзитного замыкания.
Вообще, имеет смысл вернуться к началу и подумать, чего мы от этой структуры хотим. Применительно к моему примеру:
1. 28 записей имеет смысл дать для просмотра/листания. Вполне реально найти что-то пролистыванием.
2. 800 записей -- это уже на грани приемлемости для простого просмотра. Причем, я человек асоциальный и весьма вероятно, что активные пользователи будут иметь второй круг в пределе на порядок-полтора крупнее.
3. 140,000 -- за пределами здравого смысла при просмотре.
Соответственно, для второго и третьего круга я вижу одно применение: быть ограничителем при поиске ("искать не далее 3-го круга").
Соответственно, имеет смысл думать над структурой, которая позволяет получить весь список первого круга, а второй и третий использовать для наложения ограничений на поиск без возможности просмотреть весь список.
Мнения?
-~{}~ 16.06.07 23:50:
1. 28
2. 800+
3. 140,300+
(кстати, эти плюсы уже подсказывают, что используется тот или иной алгоритм отложенных пакетных вычислений)
Всего пользователей -- 11,000,000.
Пугает то, что в третьем круге мы УЖЕ имеем более 100,000 пользователей.
Известно, что linkedin.com работает.
Следовательно, они используют структуры, радикально отличные от транзитного замыкания.Вообще, имеет смысл вернуться к началу и подумать, чего мы от этой структуры хотим. Применительно к моему примеру:
1. 28 записей имеет смысл дать для просмотра/листания. Вполне реально найти что-то пролистыванием.
2. 800 записей -- это уже на грани приемлемости для простого просмотра. Причем, я человек асоциальный и весьма вероятно, что активные пользователи будут иметь второй круг в пределе на порядок-полтора крупнее.
3. 140,000 -- за пределами здравого смысла при просмотре.
Соответственно, для второго и третьего круга я вижу одно применение: быть ограничителем при поиске ("искать не далее 3-го круга").
Соответственно, имеет смысл думать над структурой, которая позволяет получить весь список первого круга, а второй и третий использовать для наложения ограничений на поиск без возможности просмотреть весь список.
Мнения?
-~{}~ 16.06.07 23:50:
Удачи тебе.
Crazy
Developer
Sky_Flex, я еще раз повторю свой тезис: структура определяется способом использования.
Хранить так, как ты описал, можно. Не вопрос. Этим ты сможешь построить несложный запрос на получение первог круга.
А где и как ты будешь хранить результаты работы своих алгоритмов? Второй и третий круги как будешь хранить?
Хранить так, как ты описал, можно. Не вопрос. Этим ты сможешь построить несложный запрос на получение первог круга.
А где и как ты будешь хранить результаты работы своих алгоритмов? Второй и третий круги как будешь хранить?
Румата
Новичок
Crazy вопрос в хранении или в алгоритме? В алгоритме используем список смежных вершин и все будет ок.
Меня вот интересуют, где и как будут храниться данные о связях физически, откуда они будут браться.
Реально, сколько может быть друзей первого круга у человека? Не оценка сверху в виде N, а математическое ожидание числа друзей в первом круге?
Меня вот интересуют, где и как будут храниться данные о связях физически, откуда они будут браться.
Реально, сколько может быть друзей первого круга у человека? Не оценка сверху в виде N, а математическое ожидание числа друзей в первом круге?
Crazy
Developer
Вопрос в том, какие структуры будут использованы для хранения данных о втором и третьем круге. Чтобы ответить на него -- нужно знать, как они будет использоваться.
Простейший пример: если мы хотим использовать 2-й и 3-й круг для отсечения при поиске, то можно применить стандартный примем: разделить всех пользователей на кластеры (например -- тупо, по последовательным номерам).
Статистики у меня нет, поэтому я грубо возьму свои данные за средние. Получается, что у меня в контактах по всем трем кругам -- до 2% всех пользователей. Если мы сделаем кластеры по 100 пользователей, то получим для каждого пользователя около 6000 кластеров, в которых он имеет хотя бы один контакт. Для 11,000,000 это все равно потребует слишком много места для зранения, но все же не несколько порядков меньше.
Если учесть, что кластеры можно строить иерархически, то иможно еще более снизить требуемый объем.
Простейший пример: если мы хотим использовать 2-й и 3-й круг для отсечения при поиске, то можно применить стандартный примем: разделить всех пользователей на кластеры (например -- тупо, по последовательным номерам).
Статистики у меня нет, поэтому я грубо возьму свои данные за средние. Получается, что у меня в контактах по всем трем кругам -- до 2% всех пользователей. Если мы сделаем кластеры по 100 пользователей, то получим для каждого пользователя около 6000 кластеров, в которых он имеет хотя бы один контакт. Для 11,000,000 это все равно потребует слишком много места для зранения, но все же не несколько порядков меньше.
Если учесть, что кластеры можно строить иерархически, то иможно еще более снизить требуемый объем.
Sky_Flex
Новичок
а почему нужно хранить обязательноданные о 2-м и 3-м круге?
т.е. просто каждый раз высчитывать их слишком тормазно получиться?
как же тогда все хранить, с тем условием, что связи то меняются/добавляются/удаляются... как определить потом какие куски сохраненые пересчитать, а какеи нет?
т.е. просто каждый раз высчитывать их слишком тормазно получиться?
как же тогда все хранить, с тем условием, что связи то меняются/добавляются/удаляются... как определить потом какие куски сохраненые пересчитать, а какеи нет?
Румата
Новичок
Sky_Flex попробуй сделать это алгоритмически. Алгоритмически все расписать. А потом уже php. А в php начни с простого - как можно представить граф. Попробуй на основе каких-нибудь данных сформировать граф "друзей". Попробуй проделать с ним основные операции - как найти смежные вершины у конкретной. Ну и маленькими шагами придешь к большой цели.
Что в алгоритме тебе конкретно непонятно? Ты знаешь, что такое граф, что такое список смежных вершин?
Обычно наоборот в программировании. Есть алгоритм, а ты по нему пишешь пример.
Что в алгоритме тебе конкретно непонятно? Ты знаешь, что такое граф, что такое список смежных вершин?
Sky_Flex
Новичок
я понимаю алгоритм поиска: file://localhost/D:/Статьи/Алгоритм%20Дейкстры%20—%20Википедия.mht
вот в таком виде.
и в таком тоже: http://rain.ifmo.ru/cat/view.php/vis/graph-shortest-paths/dijkstra-2001
но как это программно реализовать?
и еще я не понимаю как значение минимального растояния до вершины, поможет вывести мнимальный путь до нее.
наеврно туплю страшно... но уже какой день нифига опнять не могу САБЖ.
вот в таком виде.
и в таком тоже: http://rain.ifmo.ru/cat/view.php/vis/graph-shortest-paths/dijkstra-2001
но как это программно реализовать?
и еще я не понимаю как значение минимального растояния до вершины, поможет вывести мнимальный путь до нее.
наеврно туплю страшно... но уже какой день нифига опнять не могу САБЖ.
Румата
Новичок
Такс. Есть структура следующего вида : некий массив, по индексу i там будет располагаться еще один массив со списком всех вершин, которые смежны с вершиной i.
На основе примера, что есть в Википедии, построй такую структуру.
Далее, давай временно забудем про алгоритм Дейкстры и посмотрим на алгоритм поиска в ширину
http://en.wikipedia.org/wiki/Breadth-first_search
Почитай. Сможешь такой сделать?
На основе примера, что есть в Википедии, построй такую структуру.
Далее, давай временно забудем про алгоритм Дейкстры и посмотрим на алгоритм поиска в ширину
http://en.wikipedia.org/wiki/Breadth-first_search
Почитай. Сможешь такой сделать?