|
|
|
Как реализовать сравнение множеств?
|
|||
|---|---|---|---|
|
#18+
Уважаемые профи, подскажите, пожалуйста, новичку, как наиболее эффективно (простота, производительность, расширяемость) реализовать сравнение множеств? В Кратких источниках инфы не нашел, Дейта читать начал, но не хватает ни подготовки, ни времени, чтобы осилить. Интересует прежде всего общий подход, принципы (частных случаев, где это требуется, даже у меня несколько). Дано: - интернет-проект, работа в интерактивном режиме, в реальном времени. Планируемая нагрузка - несколько тысяч хостов в сутки. - язык PHP - СУБД не выбрана, выбор во многом зависит от ответа на указанный выше вопрос. С др. стороны, выбор ограничен бесплатными СУБД, пока рассматриваю MySQL и Postgresql. Есть сущности (порядка 20 тысяч), у которых есть однородные свойства. Общий набор свойств - около 1 тысячи, но каждая сущность обладает только 1-50 из этого набора. Пользователь задает несколько произвольных сущностей, программа получает из базы и производит пересечение множеств их свойств. (На этом этапе особых сложностей не вижу, все варианты сработают.) Далее возникает сложность: нужно найти в базе те сущности, у которых есть то же (пересеченное) множество свойств (в идеале - не только полное, но и частичное). Проблема: Не знаю, как лучше организовать такой поиск. Мои варианты: 1) свойства каждой сущности реализовать массивами. Использовать Постгрес (не работал с этой СУБД). Наиболее понятный для меня путь, тем более, что свойства могут быть в различной степени выражены и иметь др. характеристики, что можно реализовать многомерностью массивов. Не знаю, однако, будет ли такой поиск (сравнение массивов) работать: а) корректно, б) сравнимо по производительности, скорости со вторым. 2) создать отдельную таблицу свойств (поля) и сущностей (записи), в ячейках собственно писать степени выраженности свойства у сущности (например, 0 - 100%). Фактически др. реализация двумерного массива. Насколько я понимаю, больше подходит под концепцию реляционной базы, но становится громоздкой (тысяча полей и 20 тысяч строк), нечитабельной. И запрос на поиск становится достаточно громоздким - типа: SELECT * FROM свойства WHERE поле1>0 AND поле2>0 AND поле23>0 ... AND поле45>0 (или его можно оптимизировать?). Есть ли более эффективные варианты или какой из моих эффективнее? Спасибо! ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.05.2016, 14:41 |
|
||
|
Как реализовать сравнение множеств?
|
|||
|---|---|---|---|
|
#18+
coder234Проблема: Не знаю, как лучше организовать такой поиск. Пересечение множеств делается с помощью оператора JOIN. Частичные пересечения получаются за счёт фильтрации по количеству совпадающих атрибутов. Например, так: Код: sql 1. 2. 3. 4. Posted via ActualForum NNTP Server 1.5 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.05.2016, 15:04 |
|
||
|
Как реализовать сравнение множеств?
|
|||
|---|---|---|---|
|
#18+
coder234, Сформируй в таблице сущностей строковое поле PropertyList, которое содержит упорядоченный список свойств (или id свойств). Например: PropertyList=',поле1,поле2,поле23, ...,поле45,' Поиск будешь делать так: SELECT * FROM сущности WHERE PropertyList like '%,поле1,%,поле2,%,поле23,% ...%,поле45,%'. Сравнить по маске 20 тыс сущностей не так уж долго. Поля в маске тоже должны быть упорядоченны. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.05.2016, 15:22 |
|
||
|
Как реализовать сравнение множеств?
|
|||
|---|---|---|---|
|
#18+
Dimitry Sibiryakov, Спасибо за пример. Но мне бы сначала определиться с ОРГАНИЗАЦИЕЙ данных, для эффективной манипуляции ими (т.е. сравнения множеств). ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.05.2016, 15:39 |
|
||
|
Как реализовать сравнение множеств?
|
|||
|---|---|---|---|
|
#18+
DirksDR, спасибо! Подобная идея мне приходила в голову - загнать списки свойств в строку и искать LIKE или регулярными выражениями. Но будет ли это работать при различном кол-ве и порядке перечисления свойств у сущностей? Можно, конечно, перевести все свойства в числовые коды (четырехзначные) и упорядочить их при вставке по возрастанию. Но и тогда мне кажется, что этот вариант проигрывает тем двум, которые я привел выше. Если таблица 20000х1000 (второй мой вариант) может быстро обрабатываться, то пока выглядит предпочтительней - нет дублирования, возможно просто добавлять и изменять сущности и свойства.... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.05.2016, 15:51 |
|
||
|
Как реализовать сравнение множеств?
|
|||
|---|---|---|---|
|
#18+
coder234Но мне бы сначала определиться с ОРГАНИЗАЦИЕЙ данных, для эффективной манипуляции ими (т.е. сравнения множеств). Тебе бы сначала изучить теорию множеств. А далее просто: любая реляционная таблица это множество, а выборка из неё - подмножество. Posted via ActualForum NNTP Server 1.5 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.05.2016, 16:19 |
|
||
|
Как реализовать сравнение множеств?
|
|||
|---|---|---|---|
|
#18+
Dimitry Sibiryakov, но я правильно понял, что вы лично - за второй вариант? (И ваш пример выборки как раз по этой таблице?) Просто я пытаюсь найти самый эффективный вариант организации данных (быстрый, надежный, производительный) для сравнения множеств (в данном случае - пересечение чаще всего используется) + с учетом, что свойства сущностей могут иметь доп. характеристики (многомерный массив мне ближе по восприятию в практике, так получилось :)) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.05.2016, 16:26 |
|
||
|
Как реализовать сравнение множеств?
|
|||
|---|---|---|---|
|
#18+
coder234Просто я пытаюсь найти самый эффективный вариант организации данных (быстрый, надежный, производительный) для сравнения множеств Эва... Рекомендую ещё поискать святой грааль и чайник Рассела. С ними может получиться проще и быстрее. Posted via ActualForum NNTP Server 1.5 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.05.2016, 16:43 |
|
||
|
Как реализовать сравнение множеств?
|
|||
|---|---|---|---|
|
#18+
coder234, Помимо ваших вариантов есть еще третий - сделать дополнительную таблицу свойств (IDСущности, ИмяСвойства, ЗначениеСвойства). тогда отбирающий запрос будет выглядеть примерно Код: sql 1. 2. 3. 4. 5. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.05.2016, 17:20 |
|
||
|
Как реализовать сравнение множеств?
|
|||
|---|---|---|---|
|
#18+
coder234 Проблема: Не знаю, как лучше организовать такой поиск. Если имеется в виду пересечение множеств, то, к примеру, у Оракла (но наверное не только у него) есть: intersect. первое множество: select * from ( select 1, 2 from dual union all select 1, 3 from dual ) второе select * from ( select 1, 2 from dual union all select 1, 4 from dual ) Их пересечение: select * from ( select 1, 2 from dual union all select 1, 3 from dual ) intersect select * from ( select 1, 2 from dual union all select 1, 4 from dual ) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.05.2016, 20:14 |
|
||
|
Как реализовать сравнение множеств?
|
|||
|---|---|---|---|
|
#18+
Спасибо всем! Насчет доп. таблицы - не совсем понял смысл ее. Насчет Intersect - да, это выглядит лучше, чем Join, понятнее, по кр. мере. Вроде, Постгрес поддерживает? MySQL, кажется, нет. А с массивами в Постгрес никто не работал? (Мой первый вариант). Там тоже есть простые запросы на пересечение и т.д. Все-таки очень интересно было бы узнать, как в реальности работает (надежность, производительность по сравнению со вторым вариантом)? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.05.2016, 14:08 |
|
||
|
Как реализовать сравнение множеств?
|
|||
|---|---|---|---|
|
#18+
Кот Матроскинcoder234, Помимо ваших вариантов есть еще третий - сделать дополнительную таблицу свойств (IDСущности, ИмяСвойства, ЗначениеСвойства). тогда отбирающий запрос будет выглядеть примерно Код: sql 1. 2. 3. 4. 5. Вот, все-таки заинтересовал меня этот вариант. Общая идея. Хотя я и не понял (поясните?), в чем смысл "дополнительности" таблицы, если это альтернатива (строгое ИЛИ) моим двум вариантам, и запрос остался мной непонятым, особо в части авторin (<Здесь Ваш список пересечения, найденный на первом этапе>) Конечно, на первый взгляд выглядит "не совсем эстетично", по таблице - "куча" дублирующихся сущностей с кучей дублирующихся свойств. Но пара сущность-свойство и далее - возможность нарастить характеристики свойства с помощью доп. столбцов + относительная простота выборки подкупают.... Хотя при таком варианте получается таблица ДО 1 млн строк... (Об обновлении - при изменении сущностей-свойств) не упоминаю... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.05.2016, 17:13 |
|
||
|
Как реализовать сравнение множеств?
|
|||
|---|---|---|---|
|
#18+
coder234Кот Матроскинcoder234, Помимо ваших вариантов есть еще третий - сделать дополнительную таблицу свойств (IDСущности, ИмяСвойства, ЗначениеСвойства). тогда отбирающий запрос будет выглядеть примерно Код: sql 1. 2. 3. 4. 5. Вот, все-таки заинтересовал меня этот вариант. Общая идея. Хотя я и не понял (поясните?), в чем смысл "дополнительности" таблицы, если это альтернатива (строгое ИЛИ) моим двум вариантам, Вам не нравится слово "дополнительная"? Я имел в виду две таблицы - "Сущности" и "СвойстваСущностей". Если кроме свойств поиска у Ваших сущностей нет атрибутов, и Вы не видите проблем с получением IDсущности - ну да, таблицу самих сущностей можно не делать, и тогда описанная таблица станет основной. coder234 и запрос остался мной непонятым, особо в части авторin (<Здесь Ваш список пересечения, найденный на первом этапе>) А что тут непонятного? Вот Вы, цитирую, "произвели пересечение множеств их свойств" (запросом или на клиенте) - вот результат этого пересечения подставьте вместо моих угловых скобок. Если запросом - подставьте запрос, если на клиенте - сформируйте строку-перечисление через запятую и подставьте ее. авторНо пара сущность-свойство и далее - возможность нарастить характеристики свойства с помощью доп. столбцов + относительная простота выборки подкупают.... Хотя при таком варианте получается таблица ДО 1 млн строк... Тут надо понимать, что структура хороша именно для описанной Вами задачи - сравнения множеств свойств. Для обычного поиска по значениям свойств, типа "найти все детали из алюминия весом более 500г" - она подходит, ээ, не блестяще. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.05.2016, 19:58 |
|
||
|
Как реализовать сравнение множеств?
|
|||
|---|---|---|---|
|
#18+
coder234СУБД не выбрана, выбор во многом зависит от ответа на указанный выше вопрос. Есть ли более эффективные варианты <..>?Есть. Например, в СУБД Caché можно обойтись одним полем, в котором хранить сразу множество значений и строить индексы по ним. Есть и соответствующее расширение SQL для поиска по таким полям (см. подробности в статье ). Например для Вашей задачи можно сделать подобное: Код: plaintext 1) найти все сущности, множество которых содержит значения 4 и/или 5: select * from сущность where for some %element(множество) (%value in (4,5)) Результат: имямножествоe25,1,9,4e33,0,4e11,5,9e47,8,5 2) найти все сущности, множества которых входят (полностью или частично) в множества из сущностей 'e1' и/или 'e4' (т.е. 1,5,9,7,8,5): select * from сущность where for some %element(множество) (%value %inlist (select $listfromstring(list(множество)) from сущность where имя in ('e1','e4'))) Результат:имямножествоe11,5,9e25,1,9,4e47,8,5Сгенерировал 20000 сущностей, в каждом множестве из которых от 1 до 50 полей со значениями от 1 до 1000. Запрос вида 2) отрабатывает за 0.212 cек., из которых execute=0.003, fetch=0.209; количество вернувшихся записей = 11422. Увеличение количества сущностей и/или полей в множестве не сильно скажется на скорости из-за наличия индексов.coder234Дано: - интернет-проект , работа в интерактивном режиме, в реальном времени . Планируемая нагрузка - несколько тысяч хостов в сутки. <..> С др. стороны, выбор ограничен бесплатными СУБД, пока рассматриваю MySQL и PostgresqlХотя Caché и не бесплатна, но для стартапов есть интересные модели оплаты , например Revenue Share (отчисления от дохода), и хостинг. Уже есть успешные примеры (см. ссылку выше). ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.05.2016, 10:17 |
|
||
|
Как реализовать сравнение множеств?
|
|||
|---|---|---|---|
|
#18+
Кот Матроскин, спасибо, понятно. servit, и вам большое спасибо, особо за выкладки по времени выполнения - буду сравнивать :) Но более распространенная и бесплатная СУБД Postgresql предоставляет похожий функционал (массивы, индекс). Наверное, я постараюсь сделать несколько вариантов на стенде и сравнить. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.05.2016, 12:40 |
|
||
|
Как реализовать сравнение множеств?
|
|||
|---|---|---|---|
|
#18+
coder234Наверное, я постараюсь сделать несколько вариантов на стенде и сравнить.Сравнили? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 31.05.2016, 15:38 |
|
||
|
Как реализовать сравнение множеств?
|
|||
|---|---|---|---|
|
#18+
coder234DirksDR, спасибо! Подобная идея мне приходила в голову - загнать списки свойств в строку и искать LIKE или регулярными выражениями. Но будет ли это работать при различном кол-ве и порядке перечисления свойств у сущностей? Можно, конечно, перевести все свойства в числовые коды (четырехзначные) и упорядочить их при вставке по возрастанию. Но и тогда мне кажется, что этот вариант проигрывает тем двум, которые я привел выше. Если таблица 20000х1000 (второй мой вариант) может быстро обрабатываться, то пока выглядит предпочтительней - нет дублирования, возможно просто добавлять и изменять сущности и свойства.... это была дурацкая идея, зря ты благодаришь. нормальная идея - это EAV. дальше найдешь. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 31.05.2016, 20:09 |
|
||
|
Как реализовать сравнение множеств?
|
|||
|---|---|---|---|
|
#18+
servit, Нет пока не сравнивал. Переключился на другие задачи пока, а эта пусть отлежится немного, дозреет :) Может,еще какие варианты появятся. Или укрепится вера в один -два из уже имеющихся. MasterZiv, Насколько я понимаю, EAV - это именно то, что предложил ранее Кот Матроскин 19180551 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 31.05.2016, 21:14 |
|
||
|
Как реализовать сравнение множеств?
|
|||
|---|---|---|---|
|
#18+
Не устаю удивляться: неужели так никто никогда и не сравнивал производительность в той же Postgresql работы с элементами в массивах в одном поле таблицы и разнесенными по разным полям (т.е. собсно вопрос 1 поста) ? Скоро вернусь к этой задаче и буду первым?? А может, вообще обойтись без СУБД, и самый быстрый вариант - XML? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 08.06.2016, 16:24 |
|
||
|
Как реализовать сравнение множеств?
|
|||
|---|---|---|---|
|
#18+
coder234 , Лучше спросите на форуме PostgreSQL или поищите там про массивы, например: 7897242 , 19140597 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 09.06.2016, 12:57 |
|
||
|
Как реализовать сравнение множеств?
|
|||
|---|---|---|---|
|
#18+
coder234Не устаю удивляться: неужели так никто никогда и не сравнивал производительность в той же Postgresql работы с элементами в массивах в одном поле таблицы и разнесенными по разным полям (т.е. собсно вопрос 1 поста) ? Скоро вернусь к этой задаче и буду первым?? А может, вообще обойтись без СУБД, и самый быстрый вариант - XML?Чудак-человек. До тебя никто-никто никогда велосипедов не делал, ты первый. Вперед, без сомнений, только вперед! О результатах доложишь. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 09.06.2016, 14:00 |
|
||
|
Как реализовать сравнение множеств?
|
|||
|---|---|---|---|
|
#18+
coder234Не устаю удивляться: неужели так никто никогда и не сравнивал производительность в той же Postgresql работы с элементами в массивах в одном поле таблицы и разнесенными по разным полям (т.е. собсно вопрос 1 поста) ? Скоро вернусь к этой задаче и буду первым?? А может, вообще обойтись без СУБД, и самый быстрый вариант - XML? Самый быстрый вариант не XML, а plain text в памяти. Для этого есть куча noSQL БД. Скорости не чета PostgreSQL, но есть "нюансы" - про ACID стоит забыть. :-) А так, если что, в PostgreSQL есть "массивы" и "JSON". По которым можно строить индексы и делать запросы. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.06.2016, 07:13 |
|
||
|
Как реализовать сравнение множеств?
|
|||
|---|---|---|---|
|
#18+
coder234Не устаю удивляться: неужели так никто никогда и не сравнивал производительность в той же Postgresql работы с элементами в массивах в одном поле таблицы и разнесенными по разным полям (т.е. собсно вопрос 1 поста) ? Скоро вернусь к этой задаче и буду первым?? А может, вообще обойтись без СУБД, и самый быстрый вариант - XML? DS ведь ответил уже: Dimitry Sibiryakov любая реляционная таблица это множество, а выборка из неё - подмножество. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.06.2016, 09:00 |
|
||
|
|

start [/forum/topic.php?fid=32&msg=39235341&tid=1540318]: |
0ms |
get settings: |
9ms |
get forum list: |
13ms |
check forum access: |
3ms |
check topic access: |
3ms |
track hit: |
164ms |
get topic data: |
11ms |
get forum data: |
3ms |
get page messages: |
55ms |
get tp. blocked users: |
1ms |
| others: | 12ms |
| total: | 274ms |

| 0 / 0 |

Извините, этот баннер — требование Роскомнадзора для исполнения 152 ФЗ.
«На сайте осуществляется обработка файлов cookie, необходимых для работы сайта, а также для анализа использования сайта и улучшения предоставляемых сервисов с использованием метрической программы Яндекс.Метрика. Продолжая использовать сайт, вы даёте согласие с использованием данных технологий».
... ля, ля, ля ...