12

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

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

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

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

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

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

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

6
  • То есть строчки 111;123;222 и 123;222; будут в разных группах, так как в рамках конкретных "колонок" совпадений нет?
    – Regent
    Commented 20 апр. 2018 в 11:12
  • С чтением строк проблем (по времени) нет? Входной lines - это, надеюсь, ArrayList?
    – Regent
    Commented 20 апр. 2018 в 11:15
  • Было бы, кстати, неплохо словами описать какие решения вы пробовали, и насколько они не укладывались по времени.
    – Regent
    Commented 20 апр. 2018 в 11:16
  • @Regent Да, точно. Тут сравнение по колонкам. Не обратил на это внимания. Думал, не важно, в какой колонке. Теперь тогда надо подумать.....
    – Max Lich
    Commented 20 апр. 2018 в 11:30
  • Я не утверждаю что важно, ибо по неточному условию задачи это не понятно наверняка. Потому и спрашиваю. А насчет задачи в целом: в первую очередь, на мой взгляд, нужно убедиться, что в коде (именно в коде, а не в алгоритме, который он реализует) нет плохо написанных мест, из-за которых сильно увеличивается время выполнения. Таким местом, например, может быть обычный for с i, используемый на LinkedList. Во вторую очередь - для определения принадлежности группе можно попробовать использовать ДКА.
    – Regent
    Commented 20 апр. 2018 в 11:36

3 ответа 3

6

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

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

            if (word.equals(""))
                continue;

            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 секунды.

11
  • Время выполнения очень хорошее, радикально его уже вряд ли уменьшишь
    – MBo
    Commented 21 апр. 2018 в 13:29
  • @Regent Хм, спасибо. Попробовал на небольших данных: всё сработало, но некоторые группы он объединил в одну, хотя это абсолютно разные группы (у них нет общих элементов). То есть на таких данных: a;b;c a;d;e x;y;z o;b;s s;y;n b;z;c a;o;w u;h;j ;p; q;;g ;;o t;; ;; выдаёт такой результат: [a;b;c, a;d;e, o;b;s, b;z;c, a;o;w] [x;y;z, s;y;n] [u;h;j] [;p;, q;;g, ;;o] [t;;] [;;]
    – Max Lich
    Commented 22 апр. 2018 в 7:07
  • @Regent То есть ошибка в этой группе: [;p;, q;;g, ;;o]. Но думаю, это несложно поправить.
    – Max Lich
    Commented 22 апр. 2018 в 7:10
  • @MaxLich поправил ошибку с пустыми словами.
    – Regent
    Commented 22 апр. 2018 в 8:02
  • @Regent Кстати, сплит неидеален и не добавляет в массив пустые строки (и из-за этого массив не будет одного размера), поэтому я написал свой метод, который делит строку на отдельные элементы.
    – Max Lich
    Commented 22 апр. 2018 в 8:06
4

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

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

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

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

9
  • Я пример так и думал. И пробовал. Но видимо не те структуры брал, или алгоритм где-то был неверен. Тут есть несколько вопросов: 1. А почему "каждое множество (группа) должно содержать в себе хэш-таблицу (map) элементов"? Что в ней будет ключом и что - значением? 2. Как хранить группы? И как проверять по ним?
    – Max Lich
    Commented 20 апр. 2018 в 13:04
  • 3. Вы писали: "При учёте номера колонки заводится количество map". Почему мэп? Что используется в качестве ключей и значений?
    – Max Lich
    Commented 20 апр. 2018 в 13:10
  • Значения в map не нужны, достаточно ключей. Объединение двух первых строк содержит список таблиц (колонка:hashmap) [0:(111,200),1:(123),2:(222,100)]. Для третьей строки находим, что s[2] содержится в map[2].
    – MBo
    Commented 20 апр. 2018 в 13:15
  • @MBo если значения не нужны, то должен использоваться Set, а не Map. А вам не кажется, что пробегать по массиву групп не очень эффективно? Если весь миллион строк разобьётся на миллион групп, то программа будет работать долго.
    – Regent
    Commented 20 апр. 2018 в 13:19
  • @Regent Да, set правильнее (я быстро глянул про java set, и не уловил, есть ли он в чистом виде). Про пробег по массиву групп хорошей мысли пока не сформировалось
    – MBo
    Commented 20 апр. 2018 в 13:21
0

попробуйте решить сами, а потом возвращайтесь сюда.

  • храним результат в виде списка множеств для уникальности: [номер_группы -> [строки_группы]]
  • используем вспомогательный список хэш-таблиц: [позиция_слова -> { слово -> номер_группы }]
  1. считать строку, разбить на колонки
  2. обойти колонки. для каждой колонки которая указывает на существующий к текущему моменту номер группы, если это не впервые для этой строки, пересасываем все строки найденной теперь группы в первую, переназначаем их колонки на нее и освобождаем найденную теперь группу.
  3. если не нашли ни одной, добавляем строку как новую группу. иначе добавляем ее к той группе которая найдена первая.
  4. когда считали все строки остается вывести список множеств строк - все группы
package org.example;

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        BufferedReader reader;
        try {
            reader = new BufferedReader(new FileReader(args[0]));
            List<Set<String>> groups = new ArrayList<>();
            List<Map<String, Integer>> parts = new ArrayList<>();

            String line = reader.readLine();
            while (line != null) {
                String[] columns = getColumnsOf(line);
                Integer groupNumber = null;
                for (int i = 0; i < Math.min(parts.size(), columns.length); i++) {
                    Integer groupNumber2 = parts.get(i).get(columns[i]);
                    if (groupNumber2 != null) {
                        if (groupNumber == null) {
                            groupNumber = groupNumber2;
                        } else if (!Objects.equals(groupNumber, groupNumber2)) {
                            for (String line2 : groups.get(groupNumber2)) {
                                groups.get(groupNumber).add(line2);
                                apply(getColumnsOf(line2), groupNumber, parts);
                            }
                            groups.set(groupNumber2, new HashSet<>());
                        }
                    }
                }
                if (groupNumber == null) {
                    if (Arrays.stream(columns).anyMatch(s -> !s.isEmpty())) {
                        groups.add(new HashSet<>(List.of(line)));
                        apply(columns, groups.size() - 1, parts);
                    }
                } else {
                    groups.get(groupNumber).add(line);
                    apply(columns, groupNumber, parts);
                }
                line = reader.readLine();
            }
            reader.close();

            System.out.println("Групп размера больше 1: " + groups.stream().filter(s -> s.size() > 1).count());
            groups.sort(Comparator.comparingInt(s -> -s.size()));
            int i = 0;
            for (Set<String> group : groups) {
                i++;
                System.out.println("\nГруппа " + i);
                for (String val : group) {
                    System.out.println(val);
                }
            }
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }

    private static String[] getColumnsOf(String line) {
        for (int i = 1; i < line.length() - 1; i++) {
            if (line.charAt(i) == '"' && line.charAt(i - 1) != ';' && line.charAt(i + 1) != ';') {
                return new String[0];
            }
        }
        return line.replaceAll("\"", "").split(";");
    }

    private static void apply(String[] newValues, int groupNumber, List<Map<String, Integer>> parts) {
        for (int i = 0; i < newValues.length; i++) {
            if (newValues[i].isEmpty()) {
                continue;
            }
            if (i < parts.size()) {
                parts.get(i).put(newValues[i], groupNumber);
            } else {
                HashMap<String, Integer> map = new HashMap<>();
                map.put(newValues[i], groupNumber);
                parts.add(map);
            }
        }
    }
}

программа работает достаточно быстро и требует меньше гигабайта памяти.

следует дописать вывод не в sout а в файл, назвать переменные более соответствующе.

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.