文字列内の部分文字列を最適に検索するjava

Question

国番号が含まれていてもいなくてもよい電話番号のリストがあります。私は常に国別コードを含むバックエンドサービスから番号を取得します。だから私は最適にバックエンドサービスから来た数に一致する数を見つけました。

は、今私がやっているものです：接触マップは、このような連絡先のマップがある

for(String number : backendNumbers){ 
    for(Map.Entry<String, String> entry : contactMap.entrySet()){ 
     if(number.endsWith(entry.getKey()) && entry.getKey().length() > MINIMUM_CONTACT_LENGTH){ 
      Log.i(TAG, "Found name for "+entry.getKey()+" : "+entry.getKey()+":"+entry.getValue()); 
      break; 
     } 
    } 
} 

は<は「01710111111」、「いくつかの名前は」> = - >このキーは、または含んでも含まなくてもよいです国コード。ほとんどの場合、そうではありません。

「+8801710111111」のように常に国コードを含むバックエンドから番号を取得したとき。

このアプローチの問題は、そのマップが必要なたびにコンタクトマップを生成するオーバーヘッドがあることです。また、各番号のバックエンドからN個の数字を取得する場合は、名前を見つけるためにコンタクトマップ全体をループする必要があります。

ここで私は何ができますか？どんな提案も感謝します。

Answer 1

指定されたループコードの場合、map.keySet()に移動して文字列キーのみを処理できます。 この方法は間違っていませんが、これは特にハッシュマップの値を比較するときに必要となる最小限のオーバーヘッドです。

Answer 2

このアプローチの問題は、マップが必要なたびに連絡先マップを生成するオーバーヘッドがあることです。

まあ、あなたは検索を容易にする構造を持っているか、リスト全体を検索しているかのどちらかです。

私は数字のMap<String, String>を作成します。マップを作成するときには、数字の最小長を計算してください。minLength

次に、バックエンド番号を指定すると、番号だけでなく、すべての接尾辞もminLengthの長さまで検索されます。

for (int beginIndex = 0; beginIndex <= (backendNumber.length() - minLength); beginIndex++) { 
    String name = nameByNumber.get(backendNumber.substring(beginIndex)); 
    if (name != null) { 
     return name; 
    } 
} 

これは、O（バックエンドの最大長 - 最小の長さ）のようなものになります。両方のコレクションを想定し

Answer 3

が大きいです、次は10倍得ることができ：

for (char c='0'; c<='9'; ++c) { 
    Map<String, String> submap = new Map<>(); 
    for(Map.Entry<String, String> entry : contactMap.entrySet()) { 
     String key = entry.getKey(); 
     if (key.length() > MINIMUM_CONTACT_LENGTH 
       && key.charAt(key.length() - 1) == c) { 
      submap.put(key, entry.getValue()); 
     } 
    } 
    for(String number : backendNumbers){ 
     if (!number.isEmpty() 
       && number.charAt(number.length() - 1) == c) { 
      for(Map.Entry<String, String> entry : submap.entrySet()) { 
       .... do what you did 
      } 
     } 
    } 
} 

をアイデアは簡単です：同じ文字と終了の両方場合は、1つの文字列は、別の1のサブことができます。だから私はそれに応じて両方のコレクションを分割し、xxxxx2とxxxxx2のようなテストを保存しました。

明らかに、最後の2桁を使用できますが、オーバーヘッドが増えます。元の複雑さはO(m*n)です。このトリックはO((m+n)*k + (m/k)*(n/k))です。ここで、kはバケットの数です。私は一様に分布する最後の数字を仮定しています。

それははるかに優れて行うことができる....

Answer 4

あなたはそれは常に3つの文字ではありません（国コードととせずにbackendnumbersの地図を作成することができますか？）

Map<String,String> backendMap = new HashMap<>(); 
for(String number : backendNumbers){ 
    backendMap.put(number,number); 
    backendMap.put(number.substring(3),number); 
} 

）数を想定した数が（同じ形式で常に国コードを持っている）、あなたは見つけることbackendMapに乗るだけで作ることができる（またはしない見つけます。