Каков наилучший способ получения дубликатов из большого Set‹String›?

У меня есть большой Set<String>, содержащий много слов, скажем:

"aaa, cCc, dDD, AAA, bbB, BBB, AaA, CCc, ..."

Я хочу сгруппировать все повторяющиеся слова из набора, игнорируя чувствительность к регистру слов, а затем сохранить их в Vector<Vector<String>> или что-то еще, поэтому каждый элемент Vector<String> будет содержать группу похожих слов, например:

Vector<String>: ааа, ААА, АаА, ...

Vector<String>: cCc, CCc, ...

Vector<String>: bbB, BBB, ...

Я забочусь о производительности, так как в этом наборе много слов.


java set duplicates
person Brad    schedule 14.07.2011    source источник
comment
1/Знаете ли вы заранее полный список целевых строк?   -  person Matthew Gilliard    schedule 14.07.2011
comment
2/Почему вы используете Vector вместо ArrayList или LinkedList?   -  person Matthew Gilliard    schedule 14.07.2011
comment
Можете ли вы заменить реализацию набора для сортировки значений во внутреннюю структуру, когда они «добавляются» в набор в первую очередь. Я понимаю, что это не то, о чем вы спрашивали, но, похоже, переключение реализации вашей коллекции может упростить это.   -  person Trever Shick    schedule 14.07.2011
comment
Меня волнует производительность, так как этот набор содержит много слов. Вы достаточно заботитесь о том, чтобы запустить на нем профилировщик, или вы просто догадываетесь?   -  person Andrew Thompson    schedule 14.07.2011
comment
Если вы заботитесь о производительности, не используйте потокобезопасный вектор; Вместо этого используйте ArrayList или HashSet.   -  person Peter Lawrey    schedule 14.07.2011
comment
@Брэд, у тебя около 20 вопросов без принятого ответа. Возможно, вы могли бы задавать вопросы таким образом, чтобы на них можно было разумно ответить, или уточнять ответы, чтобы их можно было принять.   -  person Peter Lawrey    schedule 14.07.2011
comment
@Matthew: список слов является переменным. Время от времени оно может меняться. Спасибо за совет, вектором пользоваться не буду.   -  person Brad    schedule 15.07.2011

Ответы (4)


arrow_upward
0
arrow_downward

Я бы создал HashMap<String, Vector<String>> hashMap. Далее, для каждой «строки» в вашем наборе

if (!hashMap.containsKey(string.toLowerCase()){
     Vector v = new Vector();
     v.add(string);
      hashMap.put(string.toLowerCase(), v);
} else { 
     hashMap.get(string.toLowerCase()).add(string);
}

В конце создайте вектор векторов, если необходимо, или работайте с hashmap.valueSet()

person Fortega    schedule 14.07.2011
comment
Большое спасибо ... Я внес некоторые изменения, например, на случай, если некоторые слова в наборе не имеют дубликатов, поэтому их не нужно добавлять в HashMap. - person Brad; 15.07.2011

arrow_upward
2
arrow_downward

Если вы действительно заботитесь о производительности, вы бы не использовали Vector. Что касается проблемы сортировки, одним из решений будет использование объекта TreeMap или TreeSet и создание объекта Comparator, который выполняет требуемое равенство (сортировку).

Реализация может быть:

new TreeMap<String,LinkedList<String>>(new Comparator<String>() {

   // comparator here

});

Применение:

LinkedList<String> entry = map.get(nextKey);
if (entry == null) {
  entry = new LinkedList<String>()
  map.put(nextKey, entry);
}
entry.add(nextKey);
person Martin Algesten    schedule 14.07.2011

arrow_upward
0
arrow_downward

Если вы можете выбрать Set реализацию, вы можете использовать TreeSet с Comparator, которая сравнивает строки без учета регистра. Затем вы сможете перебирать отсортированный список и легко группировать дубликаты.

person Sergey Aslanov    schedule 14.07.2011

arrow_upward
0
arrow_downward

Это повторяет входной набор один раз, и я сомневаюсь, что вы сможете работать намного быстрее. Замена ArrayLists на LinkedLists может обменять локальность на меньшее копирование, что может повысить производительность, но я в этом сомневаюсь. Вот код:

Set<String> input = new HashSet<String>(Arrays.asList(
    "aaa", "cCc", "dDD", "AAA", "bbB", "BBB", "AaA", "CCc"));

Map<String, List<String>> tmp = new HashMap<String, List<String>>();

for (String s : input) {
    String low = s.toLowerCase();
    List<String> l = tmp.get(low);

    if (l == null) {
        l = new ArrayList<String>();
        tmp.put(low, l);
    }

    l.add(s);
}

final List<List<String>> result = new ArrayList<List<String>>(tmp.values());
person Waldheinz    schedule 14.07.2011