Lexander
Сен. 18, 2010 20:16:31
Небольшой пример на основании приведенной таблицы элементов для того, чтобы убедиться - мы имеем в виду одно и то же.
1. Выводим первые Х тегов.
2. Выбираем тэг В — в выборке остаются элементы 1, 2, 4, 10. В облаке остаются тэги А, В, С, D, F. Что еще нужно вывести, количество каждого тэга в полученном списке элементов: А = 1, B = 4, C = 2, D = 1, F = 1, так? Еще что-то?
3. Выбираем второй тэг C — в выборке 2 элемента: 1 и 2. В облаке остаются тэги: A, B, C, D. Аналогично п.2 А = 1, B = 2, C = 2, D = 1. Дополнительно выводим то, что было задумано в п.2.
4. Выбираем третий тэг А — в выборке элемент 1. В облаке: A, B, C. Все тэги имеют значение 1.
Так?
Если еще что-то нужно выводить, покажи на этом примере что выводится и какое значение должно иметь, исходя из приведенных данных.
Ed
Сен. 18, 2010 21:33:02
o7412369815963
это и есть простой граф который я выложил выше в посте 35, из него не получить фильтр по 2-м тегам
Да, согласен. Без списка id объектов, оттеженых каждым тэгом не получить.
Но с ним вроде как не должно быть проблем. посмотрим на примере:
{tag1: ,
tag2: ,
tag3: ,
tag4: }
Итого на первом уровне показываем просто все тэги и длины их списков id:
tag1(5), tag2(4), tag3(5), tag4(2)
На втором уровне для скажем tag1 легко получим: tag2(3) tag3(3) и tag4(1)
На третьем для tag2 получим tag3(2) и tag4(1)
Ну и так далее. Все находится простым пересечением множеств. Того же redis-а тут должно хватить за глаза. Или проблема в том, что хранить оба соответствия объект - тэг и тэг - объект не хочется?
o7412369815963
Сен. 18, 2010 21:51:50
мдя, map_reduce можно же на find накладывать… тогда должно быстрее гораздо работать, ща проверю :)
Lexander
Так?
Если еще что-то нужно выводить, покажи на этом примере что выводится и какое значение должно иметь, исходя из приведенных данных.
да, так… надо будет проверить производительность :)
o7412369815963
Сен. 18, 2010 21:59:35
Ed
Ну и так далее. Все находится простым пересечением множеств. Того же redis-а тут должно хватить за глаза. Или проблема в том, что хранить оба соответствия объект - тэг и тэг - объект не хочется?
идея не плохая, но тегов 5К.
o7412369815963
Сен. 18, 2010 22:11:20
o7412369815963
мдя, map_reduce можно же на find накладывать… тогда должно быстрее гораздо работать, ща проверю :)
сделал так:
tags = db.events.map_reduce(map, reduce, query={ 'tags': { '$all': [ 'a', 'b' ] } })
tags = list(tags.find().sort('value',DESCENDING).limit(100))200К обрабатывает за 3сек, элементов попавших под условие (2 тега) = 65000
ща сделаю разнообразие тегов поболее, т.е. приближу к реальности, должно ещё шустрее обрабатываться
Ed
Сен. 18, 2010 22:11:35
То, что тэгов 5K еще полбеды. Оттеженых одним тэгом объектов может быть потенциально 1M, а это хуже.
Но redis такое вроде как умеет. Вот из его FAQ:
Q: What is the maximum number of keys a single Redis instance can hold? and what the max number of elements in a List, Set, Ordered Set?¶
A: In theory Redis can handle up to 2^32 keys, and was tested in practice to handle at least 150 million of keys per instance. We are working in order to experiment with larger values.
Every list, set, and ordered set, can hold 2^32 elements.
Actually Redis internals are ready to allow up to 2^64 elements but the current disk dump format don't support this, and there is a lot time to fix this issues in the future as currently even with 128 GB of RAM it's impossible to reach 2^32 elements.
o7412369815963
Сен. 18, 2010 22:32:12
получен более менее неплохой результат, редис пока отложу.
o7412369815963
ща сделаю разнообразие тегов поболее, т.е. приближу к реальности, должно ещё шустрее обрабатываться
итого: объектов 200К, тегов 500, на каждый объект по 5 тегов
1) выборка 100 отсортированных элементов: 0.031 s
2) выборка 100 отсортированных тегов: 0.076 s
увеличение числа фильтров (кол-ва тегов) не увеличивает затрачиваемое время!!!
в дальнейшем для увеличения производительности, теги заменю индексами (теги в отдельную коллекцию)
сейчас протестирую на 1М объектов, 5К тегов, 10 тегов на элемент
o7412369815963
Сен. 18, 2010 23:11:12
o7412369815963
сейчас протестирую на 1М объектов, 5К тегов, 10 тегов на элемент
результат:
1) выборка 100 отсортированных элементов: 0.049 s
2) выборка 100 отсортированных тегов: 0.122 s
монга рулит :)
всем спасибо!
ZAN
Сен. 20, 2010 13:18:37
Выложи плиз решение, интересно очень )
o7412369815963
Сен. 21, 2010 05:29:32
это добавление тегов в граф (старый список тегов и новый для одного объекта)
def EventTags_set(t_old1,t_new1):
#r = []
#for t in t_old:
# if t in t_new: r.append(t)
#for t in r:
# del t_old[t]
# del t_new[t]
#raise Exception(str( t_new ))
t_old = []
for t in t_old1:
if t not in t_new1: t_old.append(t)
t_new = []
for t in t_new1:
if t not in t_old1: t_new.append(t)
# remove
db = getDBn()
for name in t_old:
tag = db.events_tags.find_one({ 'name':name })
if not tag: continue
tag['count'] -= 1
tags = tag['tags']
for n in t_old:
if name != n:
if n in tags:
if tags[n] < 2: del tags[n]
else: tags[n] -= 1
db.events_tags.save(tag)
# append
for name in t_new:
tag = db.events_tags.find_one({ 'name':name })
if not tag: tag = { 'name':name, 'tags':{}, 'count':0 }
tag['count'] += 1
tags = tag['tags']
for n in t_new:
if name != n:
if n in tags: tags[n] += 1
else: tags[n] = 1
db.events_tags.save(tag)
Получение тегов
def EvenetTags_list(tags):
db = getDBn()
if not len(tags): return db.events_tags.find({},{ 'name':1, 'count':1 }).sort('count',DESCENDING)
elif len(tags) == 1:
tt = db.events_tags.find_one({ 'name':tags[0] })
if not tt: return []
tt = tt['tags']
return sorted( [ { 'name':t, 'count':tt[t]} for t in tt ] , key=lambda x:x['count'], reverse=True )
map = Code(""" function() {
this.tags.forEach(
function(x) {
emit(x, 1);
}
);
}""")
reduce = Code("""function (key, values) {
var total = 0;
for(var i in values) total += values[i];
return total;
}""")
result = db.events.map_reduce(map, reduce, query={ 'tags': { '$all': tags } })
result = list(result.find().sort('value',DESCENDING).limit(100))
return [ { 'name':x['_id'], 'count':x['value'] } for x in result if x['_id'] not in tags ]
без фильтра или с 1 фильтром - берет из графа, если 2 и более - мап_редьюс