Структура данных в памяти, которая поддерживает логические запросы

Question

Мне нужно хранить данные в памяти, где я сопоставляю одну или несколько строк ключей с объектом, следующим образом:

"green", "blue" -> object1
"red", "yellow" -> object2

Итак, в Java структура данных может реализовывать:

Map<Set<String>, V>

Мне нужно иметь возможность эффективно получать список объектов, где строки соответствуют некоторым логическим критериям, таким как:

("red" OR "green") AND NOT "blue"

Я работаю на Java, поэтому идеальным решением была бы готовая библиотека Java. Я, однако, готов реализовать что-то с нуля, если это необходимо.

У кого-нибудь есть идеи? Я бы предпочел избежать накладных расходов в базе данных в памяти, если это возможно, я надеюсь на что-то сопоставимое по скорости с HashMap (или, по крайней мере, того же порядка).

Answer 1

На самом деле мне понравилась проблема, поэтому я реализовал полное решение в духе моего предыдущего ответа:

http://pastebin.com/6iazSKG9

Простое решение, не поточнобезопасное или что-то в этом роде, но, я думаю, веселое и хорошее начало.

Редактировать: некоторые уточнения, как требуется

---

См. Модульный тест для использования.

Существует два интерфейса: DataStructure<K,V> и Query<V>. DataStructure ведет себя в некоторой степени как карта (и в моей реализации она фактически работает с внутренней картой), но она также предоставляет повторно используемые и неизменяемые объекты запроса, которые можно комбинировать следующим образом:

    Query<String> combinedQuery = 
    structure.and(
                    structure.or(
                            structure.search("blue"), 
                            structure.search("red")
                    ),
                    structure.not(
                            structure.search("green")
                    )
    );

(Запрос, который ищет объекты, помеченные как (синий ИЛИ красный), а НЕ зеленый). Этот запрос можно использовать повторно, что означает, что его результаты будут меняться всякий раз, когда меняется фоновая карта (вроде интеллектуального плейлиста ITunes).

Объекты запросов уже поточнобезопасны, но карта поддержки - нет, поэтому здесь есть место для улучшения. Кроме того, запросы могут кэшировать свои результаты, но это, вероятно, будет означать, что интерфейс должен быть расширен для обеспечения метода очистки (вроде метода отсоединения в моделях Wicket), который не будет красивым.

Что касается лицензирования: если кто-нибудь захочет этот код, я буду рад поместить его в SourceForge и т. Д ...

Sean

Answer 2

Подходят ли критерии для индексации растрового изображения: http://en.wikipedia.org/wiki/Bitmap_index?

Answer 3

Мне не удалось найти удовлетворительное решение, поэтому я решил приготовить свой собственный и выпустить его как проект с открытым исходным кодом (LGPL), найти его здесь .

Answer 4

Коллекции Google SetMultimap выглядит как простой способ получить базовую структуру, а затем объединить ее со статическими фильтрами Maps , чтобы получить требуемое поведение при запросах.

Строительство будет идти примерно как

smmInstance.put(from1,to1);
smmInstance.put(from1,to2);
smmInstance.put(from2,to3);
smmInstance.put(from3,to1);
smmInstance.put(from1,to3);
//...

запросов будут выглядеть как

valueFilter = //...build predicate
Set<FromType> result = Maps.filterValues(smmInstance.asMap(),valueFilter).keySet()

Вы можете сделать любое изворотливое построение предиката, но Предикаты имеет несколько методов, которых, вероятно, будет достаточно, чтобы содержать / не содержать запросы стилей.

Answer 5

это тоже сработало бы повторно используемые классы условий / выражений

Answer 6

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

(X and Y) and not Z

Answer 7

Вы можете отобразить строковые ключи в двоичную константу, а затем использовать битовое смещение для создания соответствующей маски.

Answer 8

Ознакомьтесь с проектом Apache Commons - Collections . У них есть множество замечательных вещей, которые вы сможете использовать, в частности класс CollectionUtils для выполнения строгой логики на основе коллекции.

Например, если ваши значения были сохранены в HashMap (как предложено в другом ответе) следующим образом:

myMap["green"] -> obj1
myMap["blue"] -> obj1
myMap["red"] -> obj2
myMap["yellow"] -> obj2

Затем, чтобы получить результаты, которые соответствуют: ("red" or "green") and not "blue, вы можете сделать это:

CollectionUtils.disjunction (CollectionUtils.union (myMap.get («красный»), myMap.get («зеленый»)), myMap.get («синий»))

Answer 9

Я бы сказал, что самый простой способ - просто выполнить рекурсивную фильтрацию и очистку, когда, например, вычисляется X AND Y, где X вычисляется для пустого набора.

Однако отображение должно быть от тегов (например, "красный" или "синий") до наборов объектов .

Базовый случай (разрешение атомарных тегов) рекурсии будет тогда простым поиском на этой карте. AND будет реализован с использованием пересечения, OR с использованием объединения и т. Д.