Возможно-ли свести к какой-либо математической модели оптимизацию решения след. задачи —
Есть множество элементов. Элементы имеют набор атрибутов. Каждый атрибут может иметь одно или несколько значений.
Выбрать удовлетворяющие запросу.
Данные редко-изменяемые. Есть возможность выполнить какие-то предварительные расчеты, свести к системе уравнений, матрице и ТД.
Например:
Есть страны и языки. Есть список людей, для которых задано какие страны он посещал и какими языками владеет.
Запрос:
Выбрать людей которые посещали одну из заданных стран и владеют одним из заданных языков.
понятно, что есть прямой перебор, выбор по индексу с обработкой уже выбранных и ТД.
хотелось оптимизировать задачу математически.
например, сразу отбросить те элементы, которые не удовлетворяют заданному набору значений атрибутов (запросу).
Здравствуйте, dunamo, Вы писали:
D>Возможно-ли свести к какой-либо математической модели оптимизацию решения след. задачи —
D>Есть множество элементов. Элементы имеют набор атрибутов. Каждый атрибут может иметь одно или несколько значений. D>Выбрать удовлетворяющие запросу.
Есть такая мат. модель. Называется "реляционная алгебра". Очень рекомендую.
CD>Есть такая мат. модель. Называется "реляционная алгебра". Очень рекомендую.
можно было просто написать "я умный".
у меня есть структура данных в памяти и язык программирования нереляционный. построить индексы атрибутов и организовать перебор не проблема. хочется красивого.
Здравствуйте, dunamo, Вы писали:
D>Возможно-ли свести к какой-либо математической модели оптимизацию решения след. задачи —
D>Есть множество элементов. Элементы имеют набор атрибутов. Каждый атрибут может иметь одно или несколько значений. D>Выбрать удовлетворяющие запросу.
Здравствуйте, dinama, Вы писали:
Б>>Примеры запросов "в студию"
D>в первом сообщении-же пример. D>это не база данных и не sql.
Можно представить в виде множеств: множество тех кто бы в этой стране, множество тех кто знает такой-то язык и т.д. Ну операции с этими множествами. Это всё равно не далеко от реляционной алгебры.
Q>Можно представить в виде множеств: множество тех кто бы в этой стране, множество тех кто знает такой-то язык и т.д. Ну операции с этими множествами. Это всё равно не далеко от реляционной алгебры.
ну это и есть последовательный перебор. только много множеств не нужно — выбираем А, из тех выбираем Б и тд.
это если не ошибаюсь — M*N*log(K) (M- число элеметнов, N число арибутов, К число значений атрибута)
а хочется какой-нибудь многомерной матрицы пространства и вычисление подпространства, или отбрасывание подпространства. в одно математическое действие )
Q>>Можно представить в виде множеств: множество тех кто бы в этой стране, множество тех кто знает такой-то язык и т.д. Ну операции с этими множествами. Это всё равно не далеко от реляционной алгебры.
D>ну это и есть последовательный перебор. только много множеств не нужно — выбираем А, из тех выбираем Б и тд. D>это если не ошибаюсь — M*N*log(K) (M- число элеметнов, N число арибутов, К число значений атрибута)
D>а хочется какой-нибудь многомерной матрицы пространства и вычисление подпространства, или отбрасывание подпространства. в одно математическое действие )
Это типа данные представляются в виде точки в n-мерном пространстве, где координаты это значение одного из атрибутов? Тогда выборка это просто взятие n-мерного куба из этого пространства. Дело в том, что на бумаге это может выглядеть как одна простая операция, типа квадратного корня, а на деле требует много операций для своего вычисления.
Q>Это типа данные представляются в виде точки в n-мерном пространстве, где координаты это значение одного из атрибутов? Тогда выборка это просто взятие n-мерного куба из этого пространства. Дело в том, что на бумаге это может выглядеть как одна простая операция, типа квадратного корня, а на деле требует много операций для своего вычисления.
да, что-нибудь эдакое. мозг совсем уже атрофировался от ширпотребных задач.
Здравствуйте, dinama, Вы писали:
D>да, что-нибудь эдакое. мозг совсем уже атрофировался от ширпотребных задач.
Я думаю, что тут многое зависит от того, какого вида будут запросы. Например, только операции равенства / вхождение в множество или могут быть больше / меншье. Дальше, как запросы могут комбинироваться друг с другом — например, могут ли быть запросы вида "или ... или ...".
Фильтр Блума (англ. Bloom filter) — это вероятностная структура данных, позволяющая компактно хранить множество элементов и проверять принадлежность заданного элемента к множеству:
...
Объединение и пересечение двух фильтров Блума одинакового размера и c одинаковым множеством хеш-функций может быть реализовано побитовыми операциями OR и AND над их битовыми массивами.
Здравствуйте, dunamo, Вы писали:
D>Возможно-ли свести к какой-либо математической модели оптимизацию решения след. задачи —
D>Есть множество элементов. Элементы имеют набор атрибутов. Каждый атрибут может иметь одно или несколько значений. D>Выбрать удовлетворяющие запросу.
D>Данные редко-изменяемые. Есть возможность выполнить какие-то предварительные расчеты, свести к системе уравнений, матрице и ТД.
D>
D>Например:
D>Есть страны и языки. Есть список людей, для которых задано какие страны он посещал и какими языками владеет.
D>Запрос:
D>Выбрать людей которые посещали одну из заданных стран и владеют одним из заданных языков.
D>понятно, что есть прямой перебор, выбор по индексу с обработкой уже выбранных и ТД.
D>хотелось оптимизировать задачу математически. D>например, сразу отбросить те элементы, которые не удовлетворяют заданному набору значений атрибутов (запросу).
Обычная хэш таблица. В качестве ключа должна быть комбинация из страны и языка (ну или нужных атрибутов), в качестве значения человек. Сразу при создании кидаем человека в хэш таблицу, а потом по ключу быстро и легко вытаскиваем нужных людей из таблицы.
Тут только надо правильно скомбинировать атрибуты и придумать, что лучше использовать в качестве хэша. Но, думаю это детали реализации.
Q>>Это типа данные представляются в виде точки в n-мерном пространстве, где координаты это значение одного из атрибутов? Тогда выборка это просто взятие n-мерного куба из этого пространства. Дело в том, что на бумаге это может выглядеть как одна простая операция, типа квадратного корня, а на деле требует много операций для своего вычисления.
Поздравляю, вы изобрели хэш-функцию!!!! Надо еще немного напрячь мозги и подумать над структурой данных, как это все хранить и, может быть, изобретете хэш таблицу
D>да, что-нибудь эдакое. мозг совсем уже атрофировался от ширпотребных задач.
Народ, помоему вы все как-то сильно переусложнили, это одна из самых ширпотребных задач.
интересная идейка. надо только свести наборы атрибутов/запрос к данным которые будут хешироваться.
но эта тема для фильтрации запросов, которые точно ничего не найдут.
не совсем обычная.
для каждого сочетания атрибутов элемента — одно значение. и для запроса аналогично.
E элементов
A атрибутов
N значений каждого атрибута
посчитайте сколько получится паросочетаний.
и с запросом придется то-же самое делать. и опять-же для каждого паросочетания атрибутов в запросе — множество, которое затем пересекать.
Здравствуйте, dinama, Вы писали:
K>>Обычная хэш таблица.
D>не совсем обычная. D>для каждого сочетания атрибутов элемента — одно значение. и для запроса аналогично. D>E элементов D>A атрибутов D>N значений каждого атрибута D>посчитайте сколько получится паросочетаний. D>и с запросом придется то-же самое делать. и опять-же для каждого паросочетания атрибутов в запросе — множество, которое затем пересекать.
Может я не совсем задачу понял задачу...
Атрибуты по которым делается запрос известны заранее. Из комбинации атрибутов создаем ключ.Все это засовывается в стандартный контейнер (unordered_map в с++, HashMap в java).
Ключ и такую коллекцию создаете для каждой комбинации атрибутов по которой может делаться запрос.
Или у вас комбинации атрибутов по котором будут делаться запросы неизвестна заранее и пользователь каждый раз задает набор из множества атрибутов для нового запроса?
K>Может я не совсем задачу понял задачу... K>Атрибуты по которым делается запрос известны заранее. Из комбинации атрибутов создаем ключ.Все это засовывается в стандартный контейнер (unordered_map в с++, HashMap в java). K>Ключ и такую коллекцию создаете для каждой комбинации атрибутов по которой может делаться запрос. K>Или у вас комбинации атрибутов по котором будут делаться запросы неизвестна заранее и пользователь каждый раз задает набор из множества атрибутов для нового запроса?
коллекция к которой делается запрос — неизменяема.
а запросы могут быть разные.
так-что если делать "ключ" из комбинаций атрибутов, то это могут быть десятки миллионов ключей.
если например, в коллекции 1000 элементов. по 10 атрибутов, которые имеют по 30 значений, то это
300000 тысяч ключей.
если пришел запрос, в котором для каждого атрибута задано по 10 допустимых значений, то это
100 запросов к хештаблице, с последующей вставкой в упорядоченый список.
сомнительная оптмизация.
лучше уж как выше написали отбросить фильтром Блума невалидные запросы, а дальше по старинке.
Здравствуйте, dinama, Вы писали:
D>коллекция к которой делается запрос — неизменяема. D>а запросы могут быть разные. D>так-что если делать "ключ" из комбинаций атрибутов, то это могут быть десятки миллионов ключей. D>если например, в коллекции 1000 элементов. по 10 атрибутов, которые имеют по 30 значений, то это D>300000 тысяч ключей.
Мы оптимизируем память или время работы?
Похоже я все таки не понял задачу. Будет ли каждый запрос включать все 10 атрибутов, или в одном запросе может быть 1 атрибут, в другом например первый и третий атрибуты и тд.
Хэш таблица будет хранить не все 300000 ключей а их хеши, которых будет меньше. Но если коллекция порядка 1000 элементов то на практике все оптимизации только ухудшат скорость работы. Линейный поиск будет давать лучший результат. В изначальном примере было только 2 атрибута.
D>если пришел запрос, в котором для каждого атрибута задано по 10 допустимых значений, то это D>100 запросов к хештаблице, с последующей вставкой в упорядоченый список.
Ну да, 10 атрибутов по 10 значений, в результате вы должны достать из таблицы 100 элементов, и да для этого надо 100 запросов. Если у вас хорошие хэш функции то можно считать что сложность запроса O(1)
Про последующую вставку в упорядоченный список ничего не говорилось. Можно поподробнее про это?
K>И вообще если коллекция порядка 1000 элементов то на практике все оптимизации только ухудшат скорость работы. Линейный поиск будет давать лучший результат.
на самом дели три разные ситуации:
1. большинство запросов не имеют результат
2. каждый результативный запрос извлекает большинство элементов
3. каждый запрос извлекает минимальное количество элементов
в первом случае оптимизацией будет отбросить "заведомо нерезультативные запросы" (например, упомянутый тут фильтр Блума)
во-втором случае — оптимизации не требуются
в третьем случае — здорово было-бы извлекать быстро удовлетворяющие запросу элементы
K>Про последующую вставку в упорядоченный список ничего не говорилось. Можно поподробнее про это?
если элемент Е имеет значения атрибута A (a1, a2) и атрибута B (b1, b2)
то в хеш этот элемент должен быть вставлен 4 раза: a1b1 a2b1 a1b2 a2b2
для получения результирующей выборки нам нужно исключить дубликаты, т.е. это будет упорядоченое множество, вставка в которое — дополнительное логарифмическое время.
Здравствуйте, dinama, Вы писали:
D>если элемент Е имеет значения атрибута A (a1, a2) и атрибута B (b1, b2) D>то в хеш этот элемент должен быть вставлен 4 раза: a1b1 a2b1 a1b2 a2b2
D>для получения результирующей выборки нам нужно исключить дубликаты, т.е. это будет упорядоченое множество, вставка в которое — дополнительное логарифмическое время.
Ну, тут можно придумать что-нибудь хитрое, например держать в хеш таблице указатели на элемент E и помечать его как уже выбранный после первой выборки, но это так, просто мысли.... я это не предлагаю.
Соглашусь что при больом количестве атрибутов и значеий атрибутов для каждого элемента, простая хэш таблица не лучший вариант.
K>например держать в хеш таблице указатели на элемент E и помечать его как уже выбранный после первой выборки, но это так, просто мысли.... я это не предлагаю.
структура данных "неизменяемая", что позволяет разделять ее между процессами без синхронизаций. так что добавление
чего-либо изменяемого невозможно, а в контексте запроса это строить — опять аллокации, структуры и т.д. не комильфо.
тем-более на больших объемах.
у меня на самом деле "первый" случай — доля результативных запросов очень мала, так-что поиграюсь с фильтром блума.
Здравствуйте, dinama, Вы писали:
D>и с запросом придется то-же самое делать. и опять-же для каждого паросочетания атрибутов в запросе — множество, которое затем пересекать.
А не получается ли тут OLAP какого-нибудь?
Здравствуйте, dunamo, Вы писали:
D>Есть множество элементов. Элементы имеют набор атрибутов. Каждый атрибут может иметь одно или несколько значений. D>Выбрать удовлетворяющие запросу.
Самое простое для каждого значения создать массив, в который поместить ID элементов у которых есть это значение. Массивы отсортировать по ID.
Далее получив запрос берём массивы, соответствующие этим значениям и проводим попарное слияние выкидывая уникальные элементы и оставляя только один из дубликатов.
Если на одном из этапов получили пустой результат, то ничего не найдено.
Для оптимизации нужно начинать с самых маленьких по размеру массивов.
Потребление памяти: размер ID * количество атрибутов * количество записей.
... << RSDN@Home 1.0.0 alpha 5 rev. 0>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, dunamo, Вы писали:
D>хотелось оптимизировать задачу математически. D>например, сразу отбросить те элементы, которые не удовлетворяют заданному набору значений атрибутов (запросу).
Можно хранить список битовых массивов длиной "список людей".
* Список битовых масивов для языков: индекс элемента массива — индекс человека, значение элемента "1" если знает язык, "0" если не знает.
** Тоже самое для стран.
Затраты памяти на такую модель = люди * (языки + страны) битов
Операции выбора = побитовые "и" и "или" и др.
*** Хотим найти людей, которые посещаки одну из стран: побитовое "или" по **
Владеют заданым языком: побитове "и" по * и **
Хотим найти людей, которые посещали несколько стран: побитове "и" по **
ну и т.п.
Задача сводится к банальным операциям множествами.
