0

テキスト処理用のコードを書いていますが、最初に文字列を整数に変換すると、処理がずっと速くなります。これを行うために、Dictionary クラスを作成しました。新しい文字列が表示されるたびにインデックスを付け、文字列から int へのマップと int から文字列へのマップの 2 つのマップを保持するので、両方の方法で簡単に検索できます。 . コードは次のとおりです。

class Dictionary {
    private Map<String, Integer> map;
    private Map<Integer, String> reverse_map;
    private int nextIndex;

    public Dictionary() {
        map = new HashMap<String, Integer>();
        reverse_map = new HashMap<Integer, String>();
        nextIndex = 1;
    }

    public int getIndex(String string) {
        if (!map.containsKey(string)) {
            map.put(string, nextIndex);
            reverse_map.put(nextIndex, string);
            nextIndex++;
        }
        return map.get(string);
    }

    public String getString(int index) {
        // getIndex is always called first, so we don't need to check anything
        return reverse_map.get(index);
    }
}

これは、私のシングルスレッドコードでうまく機能しています。しかし、今はこの複数のスレッドを使用して速度を上げたいと思っていますが、その方法がわかりません。ConcurrentHashMap を使用することを考えputIfAbsentましたが、インデックスを 2 回使用しないことが保証されるかどうかはわかりません。Collections.synchronizedMap を使用したくありませんでした。このディクショナリはスレッド間で非常に頻繁にアクセスされるため、読み取りと書き込みのたびにブロックされるため、単一のスレッドよりもはるかに優れているとは思われません。これを機能させる方法はありますか？

4

2 に答える 2

1

並行ソリューションの問題は原子性です。これらは私の考えです：

private final ConcurrentMap<String, Integer> map = new ConcurrentHashMap<String, Integer>();
private final ConcurrentMap<Integer, String> reverse_map = new ConcurrentHashMap<Integer, String>();
private final AtomicInteger nextIndex = new AtomicInteger(1);

public int getIndex(String string) {
  Integer i = map.get(string);
  if (i == null) {
    final Integer newI = nextIndex.getAndIncrement();
    i = map.putIfAbsent(string, newI);
    if (i == null) {
      reverse_map.put(newI, string);
      return newI;
    }
  }
  return i;
}

これには非常に良性の失敗モードがあります。一部のインデックスは未使用のままになります。

この時点で、手元の文字列を担当していることがわかったので、無条件に 2 番目のマップに移動したことに注意してください。

于 2012-07-13T19:30:45.297 に答える
1

getIndex最も簡単な方法は、2 つのメソッド (およびgetString)にラベルを付けることですsynchronized。どのようなスピードアップが得られるかを確認してください。多分それで十分でしょう。

を使用するにはConcurrentHashMap、次のようにします。

private AtomicInteger nextIndex;
public int getIndex(String string) {
    Integer n = map.get(string);
    if (n == null) {
        int idx = nextIndex.getAndIncrement();
        n = map.putIfAbsent(string, idx);
        if (n != null) return n;
        reverse_map.put(idx, string);
        return idx;
    }
    return n;
}

2 つのスレッドが同じ文字列を同時に挿入すると、インデックスがスキップされることがありますが、それほど頻繁ではありません。

于 2012-07-13T19:32:52.597 に答える