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

#java #коллекции #big_data

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


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

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


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

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

Ответы

Ответ 1

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


храним результат в виде списка списков: [номер_группы -> [строки_группы]]
используем вспомогательный список хэш-таблиц: [позиция_слова -> { слово -> номер_группы }]
и вспомогательную хэш-таблицу для хранения какая группа в какую была влита
каждую строку разбиваем на слова
каждое слово строки ищем в соответствующей (позиции слова в строке) хэш-таблице


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

если строка (а точнее её слова) найдена в группах, то берём первую из "живых" (объяснение
этого позже) групп, иначе создаём новую группу
добавляем новые слова в соответствующие хэш-таблицы с номером найденной/созданной группы
объединяем найденные группы в одну, выбранную ранее. Так как группы хранятся в виде
списка строк, то просто объединяем списки строк в один у выбранной группы, а более
ненужные группы отмечаем как "мёртвые" (присваиваем 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 секунды.


Ответ 2

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

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

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

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