java - ブールクエリをサポートするメモリ内データ構造

Question

次のように、1 つ以上のキー文字列をオブジェクトにマップするメモリにデータを格納する必要があります。

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

したがって、Java では、データ構造は以下を実装する可能性があります。

Map<Set<String>, V>

文字列が次のようなブール値の基準に一致するオブジェクトのリストを効率的に受信できるようにする必要があります。

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

私は Java で作業しているので、理想的なソリューションは既製の Java ライブラリです。ただし、必要に応じてゼロから何かを実装したいと考えています。

誰にもアイデアはありますか？可能であれば、メモリ内データベースのオーバーヘッドを避けたいと思います.HashMapに匹敵する速度(または少なくとも同程度)を望んでいます。

score 6 · Accepted Answer

実際、私はこの問題が好きだったので、以前の回答の精神で完全な解決策を実装しました。

http://pastebin.com/6iazSKG9

スレッドセーフでも何でもないシンプルなソリューションですが、楽しくて良い出発点だと思います。

編集：要求に応じて、いくつかの詳細

使用法については単体テストを参照してください。

との 2 つのインターフェイスがありDataStructure<K,V>ますQuery<V>。DataStructure はマップのように動作します (私の実装では、実際には内部マップで動作します) が、次のように組み合わせることができる再利用可能で不変のクエリオブジェクトも提供します。

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

((blue OR red) AND NOT green としてタグ付けされたオブジェクトを検索するクエリ)。このクエリは再利用可能です。つまり、バッキングマップが変更されるたびに結果が変更されます (ITunes スマートプレイリストのようなものです)。

クエリオブジェクトは既にスレッドセーフになっていますが、バッキングマップはそうではないため、ここには改善の余地があります。また、クエリは結果をキャッシュすることもできますが、それはおそらく、パージメソッド (Wicket のモデルの detach メソッドのようなもの) を提供するためにインターフェイスを拡張する必要があることを意味します。

ライセンスに関して: もし誰かがこのコードを欲しがっていたら、喜んで SourceForge などに載せます...

ショーン

score 1 · Accepted Answer

基準はビットマップインデックス作成に適していますか: http://en.wikipedia.org/wiki/Bitmap_index ?

score 0 · Accepted Answer

文字列キーをバイナリ定数にマップし、ビットシフトを使用して適切なマスクを生成できます。

score 0 · Accepted Answer

最も簡単な方法は、単純に再帰的なフィルタリングを行い、クリーバーになることです。たとえば、が空のセットに評価されたX AND Y場所を評価する場合です。X

ただし、マッピングはタグ(「赤」や「青」など) からオブジェクトのセットへのマッピングである必要があります。

再帰の基本ケース (アトミックタグの解決) は、このマップでの単純な検索になります。AND交差点、ORユニオンなどを使用して実装されます。

score 0 · Accepted Answer

満足のいく解決策を見つけることができなかったので、自分で作成してオープンソース (LGPL) プロジェクトとしてリリースすることにしました。

score 0 · Accepted Answer

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("red"), myMap.get("green")), myMap.get("blue"))

score 0 · Accepted Answer

Google コレクションのSetMultimapは、基になる構造を取得し、それをマップの静的フィルターと組み合わせて、必要なクエリ動作を取得する簡単な方法のように見えます。

建設は次のようになります

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()

述語をいくらでも作成できますが、Predicatesには、contains/doesn't contain スタイルクエリを実行するのにおそらく十分なメソッドがいくつかあります。

score 0 · Accepted Answer

ある種のデータベースソリューションが最善の策だと本当に思います。SQL は、データのクエリを簡単にサポートします。

(X and Y) and not Z

score 0 · Accepted Answer

0

これはうまくいくだろう再利用可能な条件/式クラス

于 2010-05-20T16:33:37.487 に答える

java - ブールクエリをサポートするメモリ内データ構造

9 に答える 9

Related

Reference