Как эффективно группировать строки?

Нужное решить такую задачу:
Разбить множество уникальных строк на непересекающиеся группы по следующему критерию: Если две строчки имеют совпадения непустых значений в одной или более колонках, они принадлежат одной группе. Например, строчки
111;123;222 200;123;100 300;;100 все принадлежат одной группе, так как первые две строчки имеют одинаковое значение 123 во второй колонке, а две последние одинаковое значение 100 в третьей колонке
Также есть ограничение на время работы программы (30 секунд). Также могу добавить количество строк - около миллиона. Вот мой код:
private static Set> findLineGroups(List lines) { Set> resultSet = new TreeSet<>((Comparator>) (trSet1, trSet2) -> { int diff = trSet2.size() - trSet1.size(); if (diff != 0) return diff;
Iterator iterator1 = trSet1.iterator(); Iterator iterator2 = trSet2.iterator(); while (iterator1.hasNext()) { diff = iterator1.next() - iterator2.next(); if (diff != 0) return diff; }
return 0; });
Map termLineGroupsPairs = new HashMap<>(); List> lineNumGroups = new ArrayList<>();
for (int lineNum = 0; lineNum < lines.size(); lineNum++) { String line = lines.get(lineNum); String[] lineElements = line.replaceAll("\"", "").replaceAll(" ", "").split(";"); Set termSet = new HashSet<>(Arrays.asList(lineElements)); termSet.remove("");
Integer groupNum = null; TreeSet tempSet = new TreeSet<>(termLineGroupsPairs.keySet()); tempSet.retainAll(termSet); //оставляем только общие элементы if (!tempSet.isEmpty()) { String term = tempSet.first(); groupNum = termLineGroupsPairs.get(term); lineNumGroups.get(groupNum).add(lineNum); }
if (groupNum == null) { TreeSet group = new TreeSet<>(); group.add(lineNum); lineNumGroups.add(group); groupNum = lineNumGroups.size() - 1; } for (String term : termSet) { termLineGroupsPairs.put(term, groupNum); } if (lineNumGroups.size() % 1000 == 0) System.out.println(lineNumGroups.size()); }
resultSet.addAll(lineNumGroups); return resultSet; }
И все мои решения работают слишком долго (а пробовал по-разному решать эту задачу). Правда, если строк меньше тысячи, то работает быстро (укладываюсь в указанное ограничение), и практически с любым моим алгоритмом.
Прошу подсказать, как можно решить эту задачку (или что изменить в моём решении, чтобы работало быстро).

Ответ

К какому решению "почти в лоб" я пришел:
храним результат в виде списка списков: [номер_группы -> [строки_группы]] используем вспомогательный список хэш-таблиц: [позиция_слова -> { слово -> номер_группы }] и вспомогательную хэш-таблицу для хранения какая группа в какую была влита каждую строку разбиваем на слова каждое слово строки ищем в соответствующей (позиции слова в строке) хэш-таблице
если слово есть, запоминаем номер группы (значение из хэш-таблицы), в которой оно найдено если слова нет, то добавляем его в список новых слов если строка (а точнее её слова) найдена в группах, то берём первую из "живых" (объяснение этого позже) групп, иначе создаём новую группу добавляем новые слова в соответствующие хэш-таблицы с номером найденной/созданной группы объединяем найденные группы в одну, выбранную ранее. Так как группы хранятся в виде списка строк, то просто объединяем списки строк в один у выбранной группы, а более ненужные группы отмечаем как "мёртвые" (присваиваем null, дабы не перемещать элементы внутри списка) добавляем строку в список строк группы
Кода выходит ещё больше, чем слов:
//вспомогательный класс для добавления новых слов private static class NewWord { public String value; public int position;
public NewWord(String value, int position) { this.value = value; this.position = position; } }
private static List> findGroups(List lines) { List> wordsToGroupsNumbers = new ArrayList<>(); //[позиция_слова:{слово:номер_группы}] List> linesGroups = new ArrayList<>(); //[номер_группы:[строки_группы]] Map mergedGroupNumberToFinalGroupNumber = new HashMap<>(); //{номер_слитой_группы:номер_группы_в_которую_слили} for (String line : lines) { String[] words = line.split(";"); TreeSet foundInGroups = new TreeSet<>(); List newWords = new ArrayList<>(); for (int i = 0; i < words.length; i++) { String word = words[i];
if (wordsToGroupsNumbers.size() == i) wordsToGroupsNumbers.add(new HashMap<>());
if (word.equals("")) continue;
Map wordToGroupNumber = wordsToGroupsNumbers.get(i); Integer wordGroupNumber = wordToGroupNumber.get(word); if (wordGroupNumber != null) { while (mergedGroupNumberToFinalGroupNumber.containsKey(wordGroupNumber)) wordGroupNumber = mergedGroupNumberToFinalGroupNumber.get(wordGroupNumber); foundInGroups.add(wordGroupNumber); } else { newWords.add(new NewWord(word, i)); } } int groupNumber; if (foundInGroups.isEmpty()) { groupNumber = linesGroups.size(); linesGroups.add(new ArrayList<>()); } else { groupNumber = foundInGroups.first(); } for (NewWord newWord : newWords) { wordsToGroupsNumbers.get(newWord.position).put(newWord.value, groupNumber); } for (int mergeGroupNumber : foundInGroups) { if (mergeGroupNumber != groupNumber) { mergedGroupNumberToFinalGroupNumber.put(mergeGroupNumber, groupNumber); linesGroups.get(groupNumber).addAll(linesGroups.get(mergeGroupNumber)); linesGroups.set(mergeGroupNumber, null); } } linesGroups.get(groupNumber).add(line); } linesGroups.removeAll(Collections.singleton(null)); return linesGroups; }

Возможно, у меня слишком быстрый для тестирования скорости работы "как им надо" компьютер, но для миллиона строк, каждая из которых состоит из 5 слов, каждое из которых, в свою очередь, состоит из 5 строчных букв английского алфавита, время выполнения составляет примерно 4 секунды.