1

ip-lookup 構造を実装している間、キーの「フロア」(つまり、指定された値以下の最大のキー) を検索できるトライのような構造でキーのセットを維持しようとしていました。鍵）。私は Apache Collections 4 PatriciaTrieを使用することにしましたが、残念ながらfloorEntryと関連するメソッドは使用できないことがわかりましたpublic。私の現在の「汚い」解決策は、(Scala で) リフレクションを強制することです:

val pt = new PatriciaTrie[String]()
val method = pt.getClass.getSuperclass.getDeclaredMethod("floorEntry", classOf[Object])
method.setAccessible(true)
// and then for retrieving the entry for floor(key) 
val entry = method.invoke(pt, key).asInstanceOf[Entry[String, String]]

同じ機能を持つクリーンな方法はありますか? このメソッドが公開されていないのはなぜですか?

4

1 に答える 1

1

これらのメソッドが公開されていない理由はわかりません。Map(共通APIでやりたいことを実現できるからかもしれません)。

要件を満たす方法は次のとおりです。

PatriciaTrie<String> trie = new PatriciaTrie<>();
trie.put("a", "a");
trie.put("b", "b");
trie.put("d", "d");

String floorKey = trie.headMap("d").lastKey(); // d

ドキュメントによると、トライの最大キーのビット数に依存するため、これは非常に効率的です。

編集:以下のコメントによると、上記のコードには境界の問題があります:指定されたキーより厳密に低いheadMap()キーを持つマップのビューを返します。つまり、上記の例では、(必要に応じて)の代わりに,が返されます。trie.headMap("b").lastKey()"a""b"

この境界の問題を修正するには、次のトリックを使用できます。

String cFloorKey = trie.headMap("c" + "\uefff").lastKey(); // b

String dFloorKey = trie.headMap("d" + "\uefff").lastKey(); // d

\uefffが最高の Unicode 文字であるため、すべてが期待どおりに機能するようになりました。実際、 を検索するとkey + "\uefff"、それがトライに属している場合keyは常に返され、 がトライに存在しない場合はkeyの直前の要素が返されます。keykey

現在、このトリックはStringキーに対して機能しますが、他のタイプにも拡張可能です。つまり、Integer検索できるキーの場合key + 1、Date1 ミリ秒を追加できるキーの場合などです。

于 2015-09-12T14:21:02.433 に答える