Нужное решить такую задачу:
Разбить множество уникальных строк на непересекающиеся группы по следующему критерию:
Если две строчки имеют совпадения непустых значений в одной или более колонках, они принадлежат одной группе.
Например, строчки
111;123;222 200;123;100 300;;100
все принадлежат одной группе, так как первые две строчки имеют одинаковое значение
123
во второй колонке, а две последние одинаковое значение100
в третьей колонке
Также есть ограничение на время работы программы (30 секунд). Также могу добавить количество строк - около миллиона. Вот мой код:
private static Set<TreeSet<Integer>> findLineGroups(List<String> lines) {
Set<TreeSet<Integer>> resultSet = new TreeSet<>((Comparator<TreeSet<Integer>>) (trSet1, trSet2) -> {
int diff = trSet2.size() - trSet1.size();
if (diff != 0)
return diff;
Iterator<Integer> iterator1 = trSet1.iterator();
Iterator<Integer> iterator2 = trSet2.iterator();
while (iterator1.hasNext()) {
diff = iterator1.next() - iterator2.next();
if (diff != 0)
return diff;
}
return 0;
});
Map<String, Integer> termLineGroupsPairs = new HashMap<>();
List<TreeSet<Integer>> lineNumGroups = new ArrayList<>();
for (int lineNum = 0; lineNum < lines.size(); lineNum++) {
String line = lines.get(lineNum);
String[] lineElements = line.replaceAll("\"", "").replaceAll(" ", "").split(";");
Set<String> termSet = new HashSet<>(Arrays.asList(lineElements));
termSet.remove("");
Integer groupNum = null;
TreeSet<String> 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<Integer> 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;
}
И все мои решения работают слишком долго (а пробовал по-разному решать эту задачу). Правда, если строк меньше тысячи, то работает быстро (укладываюсь в указанное ограничение), и практически с любым моим алгоритмом.
Прошу подсказать, как можно решить эту задачку (или что изменить в моём решении, чтобы работало быстро).
111;123;222
и123;222;
будут в разных группах, так как в рамках конкретных "колонок" совпадений нет?lines
- это, надеюсь,ArrayList
?for
сi
, используемый наLinkedList
. Во вторую очередь - для определения принадлежности группе можно попробовать использовать ДКА.