Алгоритм поиска элементов не в наборе - PullRequest
Новая
       11

Алгоритм поиска элементов не в наборе

0 голосов
/ 06 октября 2010

У меня есть список продуктов {P1, P2, ...}, каждый из которых может иметь список атрибутов {a1, a2, ...}.Какой самый быстрый алгоритм, чтобы найти все элементы, НЕ имеющие некоторые атрибуты, скажем, {a2, a6, a10}?

Если P1 = {a1, a2, a3} P2 = {a3} P3 = {a1, a4}, алгоритм должен вернуть {P2, P3}

Проблема в том, что я неНе знаю, входной список атрибутов, как это передается пользователем.Список продуктов и связанные с ними атрибуты хранятся в базе данных:

Таблица продуктов (более 10000 строк) 

ProductID int,
ProductName varchar

Таблица атрибутов (около 400 строк, может увеличиться вбудущее) 

AttributeID int,
AttributeName  varchar

Таблица Product_Attribute_Association 

ProductID int,
AttributeID int

У меня есть следующий запрос: 

SELECT p.ProductID, p.ProductName
FROM Product p
WHERE p.ProductID NOT IN 
(SELECT pa.ProductID FROM Product_Attribute_Association pa
 WHERE pa.AttributeID NOT IN (1, 4, 5) -- What ever being passed in
) t

Этот сервис получит довольно сильный удар, и я думаю о кешированииданные из 3 таблиц в памяти в некоторой структуре данных и написать эффективный алгоритм для поиска.Можете ли вы предложить что-то, что я должен изучить?Спасибо

РЕДАКТИРОВАТЬ: Обновление базы данных не является проблемой.Кэш будет восстанавливаться из базы данных каждый час, поэтому время, в течение которого создается кеш, не имеет значения.

Память также не имеет значения.

Ответы [ 3 ]

0 голосов
/ 06 октября 2010

Вот наивное решение:

  • Для каждого атрибута поместите каждый из продуктов, которому принадлежит этот атрибут, в хеш-таблицу с атрибутом, используемым в качестве ключа;
  • Когда поступит пользовательский ввод, инициализируйте результатсо всеми существующими продуктами, затем выполните итерацию по атрибутам и проверьте, существует ли атрибут в хеш-таблице, если это так, удалите все продукты, связанные с этим атрибутом, из результата;
  • То, что у вас есть после завершения итерации, является вашим результатом.
0 голосов
/ 07 октября 2010

Вы можете реализовать «кэш» непосредственно в таблице продуктов:

  • Создать двоичное поле «AttributeCache», где каждый бит представляет атрибут

  • Выполнитьзапрос, который поразрядно оценивает поле кэша

    , выбирает ProductID из Product, где AttributeCache &: attributeMask = 0

Для поиска {a2, a6, a10} attributeMask, очевидно, будет(заполнено до 16 атрибутов): 0100010001000000

Если ваша база данных позволяет это сделать, вы также можете создать индекс для поля AttributeCache, чтобы избежать полных проверок таблиц.

0 голосов
/ 06 октября 2010

Вероятно, это зависит от того, как часто вы будете обновлять базу данных, если это не слишком часто, вы можете:

Для каждого attributeId иметь отсортированный список (или массив) productIds, которые его имеют.Когда приходит запрос, возьмите списки продуктов, соответствующие этим атрибутам, объедините их, а затем объедините с отсортированным списком productIds.

В вашем примере это выглядит следующим образом:

  • a1 -> {p1, p3}
  • a2 -> {p1}
  • a3-> {p1, p2}
  • a4 -> {p3}
  • ...
...