4

ファイルパスにマップするKey-Valueパラメーターが大量にあります。ほとんどが次の形式です

filepath : /some/path
param_name_1 => 1234
param_name_2 => qwerty

ただし、ワイルドカード文字を含めることができるものもあります

filepath : /other/path
param_name_1 => 123*4
param_name_2 => ab?12

ここで、?は任意の1文字に一致するワイルドカードであり、は0以上*の文字に一致するワイルドカードです。

私のユーザーは、マップされたパスを照合して返す必要がある独自のKVパラメーターのセットを提供できます。

例:ユーザーが提供する

param_name_1 => 1234
param_name_2 => qwerty

Application returns /some/path

ユーザーが提供する

param_name_1 => 123asdqweqweqdqweq1231asdcase4
param_name_2 => abW12

Application returns /other/path

ワイルドカードを含まないすべてのマッピングhashCode()について、保存されているマッピングとユーザー提供のマッピングを計算し、HashMap非常に高速なルックアップを実行できます(一致する3〜4個のパラメーター、100000個のマッピング、0ミリ秒で結局のところハッシュ)。

ただし、ワイルドカードを含むマッピングの場合、ワイルドカードを含むすべてのマッピングのリストを介して線形ルックアップを実行することに固執しています。このようなマッピングは約2000〜5000あり、各ルックアップには200ミリ秒弱かかり、高速化する必要があります。

一般的なルックアップを実行してワイルドカードを照合する方法や、すべてのマッピングを組み合わせるその他の照合手法はありますか?

4

1 に答える 1

4

TreeMapの代わりにを使用する場合HashMapは、プレフィックス検索を実行して、反復処理する必要のあるアイテムの数を減らすことができます。*またはの前に表示される文字を取得し、?それらの文字で始まるすべてのキーを繰り返し処理します。もちろん、検索語がワイルドカードで始まる場合、これは機能しません。

この問題に対する他の一般的なアプローチは、文字ngramsまたはトライベースの構造を使用することですが、それははるかに複雑です。

于 2013-01-16T16:45:15.790 に答える