Уведомления

Группа в Telegram: @pythonsu

#1 Сен. 16, 2010 20:07:22

o7412369815963
От:
Зарегистрирован: 2009-06-17
Сообщения: 1986
Репутация: +  32  -
Профиль   Отправить e-mail  

теги

Lexander
Решение, как обычно, зависит от используемых инструментов. Например, где хранить тэги.
Уточни, плз, объем обрабатываемых данных. А то миллион объектов…
Сколько объектов, сколько тэгов всего, сколько тэгов для каждого объекта, сколько тэгов можно одновременно выбрать из облака (кол-во фильтров)?..
объектов 1М, тегов 5К, кол-во фильтров, которое можно выбрать, не ограничено.

Офлайн

#2 Сен. 16, 2010 20:15:42

o7412369815963
От:
Зарегистрирован: 2009-06-17
Сообщения: 1986
Репутация: +  32  -
Профиль   Отправить e-mail  

теги

на счет solr, желательно решение под питон и встраиваемое. а вообще охота сделать колесо, т.е. нужен алгоритм.

Офлайн

#3 Сен. 17, 2010 10:34:07

ZAN
От:
Зарегистрирован: 2007-06-10
Сообщения: 403
Репутация: +  10  -
Профиль   Отправить e-mail  

теги

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



Офлайн

#4 Сен. 17, 2010 11:58:01

Lexander
От:
Зарегистрирован: 2008-09-19
Сообщения: 1139
Репутация: +  33  -
Профиль   Отправить e-mail  

теги

o7412369815963
тегов 5К, кол-во фильтров, которое можно выбрать, не ограничено.
Это условие похоже на сферического…
Почему?
Ты себе представляешь страницу с 5к тэгов и пользователя, который тыкает на ВСЕ тэги? ;)

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



Офлайн

#5 Сен. 17, 2010 13:56:18

o7412369815963
От:
Зарегистрирован: 2009-06-17
Сообщения: 1986
Репутация: +  32  -
Профиль   Отправить e-mail  

теги

Lexander
Ты себе представляешь страницу с 5к тэгов и пользователя, который тыкает на ВСЕ тэги? ;)
все просто, на верх выходят часто используемые теги, где-нибуть штук 30, после того как 1 тег будет выбран он отсеет облако от которого из 5К останется 30, а если не видно, то можно воспользоваться поиском по тегам - автокомплит.

Офлайн

#6 Сен. 17, 2010 13:58:59

o7412369815963
От:
Зарегистрирован: 2009-06-17
Сообщения: 1986
Репутация: +  32  -
Профиль   Отправить e-mail  

теги

ZAN
o7412369815963 Скажите, а в делали реальные измерение на миллионе записей?
Для базы данных это не так уж и много и обычная выборка здесь будет самое то.
пока не делал, но все равно пока вариантов нет. буду делать так.

Офлайн

#7 Сен. 17, 2010 16:51:05

ZAN
От:
Зарегистрирован: 2007-06-10
Сообщения: 403
Репутация: +  10  -
Профиль   Отправить e-mail  

теги

o7412369815963
пока не делал, но все равно пока вариантов нет. буду делать так.
Попробовал потестить. Создал таблицу, где один столбец - данные, другой - тег:
/*create table*/
CREATE TABLE entry (
id SERIAL,
data varchar(32),
tag varchar(32)
);
Забил таблицу записями. На каждую единицу данных - пять различных тегов. Теги добавлялись в список последовательно, по мере заполнения таблицы, чтобы одни теги встречались чаще других.
import random
import hashlib
import psycopg2


CONN_STRING = "dbname=tags user=pmaster"
RECORDS = 1000000
TAGS = 1000
TAGS_FOR_RECORD = 5


def main():
tags = ['a', 'b', 'c', 'd', 'e']
progress = 0
record_list = []
for i in xrange(RECORDS/TAGS_FOR_RECORD):
#generating data to be saved
use_tags = random.sample(tags, 5)
data = hashlib.md5(str(i)).hexdigest()
record_list.append([data, use_tags])

#splitting data into portions
if i % (RECORDS/(TAGS_FOR_RECORD*TAGS)) == 0:
#printing progress
progress += 1
print progress

save_records(record_list)
record_list = []

#adding new tags
tags.append('tag%s' %i)
save_records(record_list)

print '---'
print 'records:', (i+1)*TAGS_FOR_RECORD, 'tags:', len(tags)

def save_records(record_list):
conn = psycopg2.connect(CONN_STRING)
cur = conn.cursor()
for data, tags in record_list:
for tag in tags:
cur.execute('insert into entry (data, tag) values (%s, %s)', (data, tag))
conn.commit()
cur.close()
conn.close()
Получаем начальное облако:
/* get tag cloud of most popular tags*/
select
count(tag), tag
from
entry
group by
tag
order by
count(tag) desc fetch first 100 rows only
/* 0.39 s */
Сужаю теги:
select
count(tag), tag
from
entry
where (data in (
select
data
from
entry
where
tag='d'))
and (tag!= 'd')
group by
tag
order by
count(tag) desc
fetch first 100 rows only
/* 0.79 s */
А вот получение самих данных уже по-быстрее:
select distinct
data
from
entry
where
(tag = 'b') and data in (
select
data
from
entry
where
tag = 'c')
fetch first 100 rows only
/* 0.25 s */
Если убрать distinct, то еще вдвое быстрее.
В общем, не фонтан, конечно, тестил на ноутбуке core 2 duo 2.1 GHz, 2Gb mem. Вопрос в том какое будет железо, ну и запросы влоб, какие я для тестов использовал, нужно заменить скорее всего на что-то более адекватное.



Офлайн

#8 Сен. 17, 2010 17:31:41

o7412369815963
От:
Зарегистрирован: 2009-06-17
Сообщения: 1986
Репутация: +  32  -
Профиль   Отправить e-mail  

теги

в данном примере кол-во объектов 200К а не миллион (RECORDS/TAGS_FOR_RECORD).

запрос сужения мне кажется не оптимальным - на каждый фильтрующий тег - вложенный запрос, т.е. от 5-и тегов база здохнет.

у меня все это крутиться на mongoDB, попробую сделать выборку одним проходом (без вложенных запросов)

Отредактировано (Сен. 17, 2010 17:33:35)

Офлайн

#9 Сен. 17, 2010 18:27:42

ZAN
От:
Зарегистрирован: 2007-06-10
Сообщения: 403
Репутация: +  10  -
Профиль   Отправить e-mail  

теги

o7412369815963
запрос сужения мне кажется не оптимальным - на каждый фильтрующий тег - вложенный запрос, т.е. от 5-и тегов база здохнет.
Ну да, это только для примерной оценки сложности запроса. Просто задача сужения позволяет делать последующую выборку по уже полученным результатам (хранить курсор или временные таблицы), которая будет проходить наобарот быстрее предыдущей, и удалять кеш после завершения сессии пользователя или по какому-нибудь явному вызову invalidate.



Офлайн

#10 Сен. 17, 2010 19:20:33

Lexander
От:
Зарегистрирован: 2008-09-19
Сообщения: 1139
Репутация: +  33  -
Профиль   Отправить e-mail  

теги

o7412369815963
запрос сужения мне кажется не оптимальным - на каждый фильтрующий тег - вложенный запрос, т.е. от 5-и тегов база здохнет.
у меня все это крутиться на mongoDB, попробую сделать выборку одним проходом (без вложенных запросов)
Ты бы сразу уточнил об используемых инструментах.
Конечно, на Монго полуить данные по тэгам:
db.entry.find({tag: {$all: ['c', 'd']}})
При наличии индекса вида Multikeys работать будет на вполне приличной скорости.



Офлайн

Board footer

Модераторировать

Powered by DjangoBB

Lo-Fi Version