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

199

21 апреля 2018, 20:10

Нужное решить такую задачу:

Разбить множество уникальных строк на непересекающиеся группы по следующему критерию:

Если две строчки имеют совпадения непустых значений в одной или более колонках, они принадлежат одной группе.

Например, строчки

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;
}

И все мои решения работают слишком долго (а пробовал по-разному решать эту задачу). Правда, если строк меньше тысячи, то работает быстро (укладываюсь в указанное ограничение), и практически с любым моим алгоритмом.

Прошу подсказать, как можно решить эту задачку (или что изменить в моём решении, чтобы работало быстро).

Answer 1

Есть такая структура данных - лес непересекающихся множеств (disjoint sets union). Устроен он очень просто, и позволяет быстро объединять связанные элементы.

В данном случае, если игнорировать утверждение про необходимость совпадения номера колонки, каждое множество (группа) должно содержать в себе хэш-таблицу (map) элементов типа 123 и т.д.

Каждая новая строка делится на элементы и проверяется наличие этих элементов в существующих группах.
- Если ни один элемент не имеет совпадений, заводится новая группа.
- Если совпадение одно, строка добавляется в эту группу.
- Если два и более - строка служит линком, связывающим группы - они объединяются, и строка добавляется к объединенной группе.

При учёте номера колонки заводится количество map, соответствующее максимальному количеству колонок, и поиск проводится в каждом из map.

Answer 2

К какому решению "почти в лоб" я пришел:

храним результат в виде списка списков: [номер_группы -> [строки_группы]]
используем вспомогательный список хэш-таблиц: [позиция_слова -> { слово -> номер_группы }]
и вспомогательную хэш-таблицу для хранения какая группа в какую была влита
каждую строку разбиваем на слова
каждое слово строки ищем в соответствующей (позиции слова в строке) хэш-таблице
- если слово есть, запоминаем номер группы (значение из хэш-таблицы), в которой оно найдено
- если слова нет, то добавляем его в список новых слов
если строка (а точнее её слова) найдена в группах, то берём первую из "живых" (объяснение этого позже) групп, иначе создаём новую группу
добавляем новые слова в соответствующие хэш-таблицы с номером найденной/созданной группы
объединяем найденные группы в одну, выбранную ранее. Так как группы хранятся в виде списка строк, то просто объединяем списки строк в один у выбранной группы, а более ненужные группы отмечаем как "мёртвые" (присваиваем 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<List<String>> findGroups(List<String> lines)
{
    List<Map<String, Integer>> wordsToGroupsNumbers = new ArrayList<>(); //[позиция_слова:{слово:номер_группы}]
    List<List<String>> linesGroups = new ArrayList<>(); //[номер_группы:[строки_группы]]
    Map<Integer, Integer> mergedGroupNumberToFinalGroupNumber = new HashMap<>(); //{номер_слитой_группы:номер_группы_в_которую_слили}
    for (String line : lines)
    {
        String[] words = line.split(";");
        TreeSet<Integer> foundInGroups = new TreeSet<>();
        List<NewWord> newWords = new ArrayList<>();
        for (int i = 0; i < words.length; i++)
        {
            String word = words[i];
            if (wordsToGroupsNumbers.size() == i)
            {
                wordsToGroupsNumbers.add(new HashMap<>());
            }
            Map<String, Integer> 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 секунды.