Здравствуйте, dinama, Вы писали:
D>и с запросом придется то-же самое делать. и опять-же для каждого паросочетания атрибутов в запросе — множество, которое затем пересекать.
А не получается ли тут OLAP какого-нибудь?
Здравствуйте, dunamo, Вы писали:
D>Есть множество элементов. Элементы имеют набор атрибутов. Каждый атрибут может иметь одно или несколько значений. D>Выбрать удовлетворяющие запросу.
Самое простое для каждого значения создать массив, в который поместить ID элементов у которых есть это значение. Массивы отсортировать по ID.
Далее получив запрос берём массивы, соответствующие этим значениям и проводим попарное слияние выкидывая уникальные элементы и оставляя только один из дубликатов.
Если на одном из этапов получили пустой результат, то ничего не найдено.
Для оптимизации нужно начинать с самых маленьких по размеру массивов.
Потребление памяти: размер ID * количество атрибутов * количество записей.
... << RSDN@Home 1.0.0 alpha 5 rev. 0>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, dunamo, Вы писали:
D>хотелось оптимизировать задачу математически. D>например, сразу отбросить те элементы, которые не удовлетворяют заданному набору значений атрибутов (запросу).
Можно хранить список битовых массивов длиной "список людей".
* Список битовых масивов для языков: индекс элемента массива — индекс человека, значение элемента "1" если знает язык, "0" если не знает.
** Тоже самое для стран.
Затраты памяти на такую модель = люди * (языки + страны) битов
Операции выбора = побитовые "и" и "или" и др.
*** Хотим найти людей, которые посещаки одну из стран: побитовое "или" по **
Владеют заданым языком: побитове "и" по * и **
Хотим найти людей, которые посещали несколько стран: побитове "и" по **
ну и т.п.
Задача сводится к банальным операциям множествами.
