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

 
 
 
Сообщения:59
Здравствуйте. Есть такая задача:
Quote:
С помощью Java сделать следующее:
а) Считать файл со строчками вида

A1;B1;C1

A2;B2;C2

...

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

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

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

111;123;222

200;123;100

300;;100

все принадлежат одной группе, так как первые две строчки имеют одинаковое значение 123 во второй колонке,
а две последние одинаковое значение 100 в третьей колонке

в) Вывести полученные группы в файл в следующем формате:

Группа 1

строчка1

строчка2

строчка3

...

Группа 2

строчка1

строчка2

строчка3

В начале вывода указать получившиееся число групп с более чем одним элементом.

Сверху расположить группы с наибольшим числом элементов.

Архив с данными для выполнения задания lng.7z (https://github.com/PeacockTeam/new-job/blob/master/lng.7z)

Приемлимое время работы на обыкновенном ноутбуке до 30 секунд.

После выполнения задания необходимо отправить количество полученных групп.

Пункты "а" и "в" я, естественно, смогу выполнить. Но на пункте "б" у меня затык. Разными способами уже пытался сгруппировать строки, и не получается. Основная проблема - это время выполнения программы (оно намного больше указанных 30 секунд).
Последний мой способ такой:
1) Создаю мапу для пары "элемент строки-номер группы строки", создаю лист (список), хранящие группы строк в виде трисетов с номерами строк)
2) Прохожусь по строкам:
 а) кидаю элементы строки в сет
 б) проверяю пересекается ли этот сет и сет ключей из мапы, если пересекается, по общему элементу нахожу номер группы (и сразу же в эту группу добавляю текущий номер строки)
 в) если множества не пересекаются и номера группы нет, то создаю новую группу, кидаю туда текущий номер строки и сохраняю номер добавленной группы
 г) прохожусь по всему множеству элементов строк и добавляю их всех в мапу (в качестве значения беру номер группы)
3) кидаю полученный список групп в трисет
4) потом прохожусь по этому трисету и для каждого элемента вытягиваю строку и вывожу её. В итоге получается вывод, как в задачи.

Код метода поиска строк:
    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;
    }
 
 
Сообщения:856
Приветствую!
У вас ошибка в данных:
["83950289", ""]
["8383"200000741652251"]
["79855053897"83100000580443402", "200000133000191"]
["83000854422549"]
["837"]
["79321586161", "10000034237264683"200000067130972"]
["83", "200000644359490"]
["830318", "200000814056013"]
["831811290", "200000358586593"]

Как это развидеть? :)
 
 
Сообщения:59
Вы про что??? Какие ошибки?
 
 
Сообщения:856
Данные не соответствуют представленному вами формату
A1;B1;C1
A2;B2;C2

upd. Предыдущее сообщение - это вывод в консоль данных, которые не соответствуют формату, через Arrays.deepToString(line.spilt(";"))
Изменен:20 апр 2018 16:22
 
 
Сообщения:59
gidravlic:
Данные не соответствуют представленному вами формату
A1;B1;C1
A2;B2;C2

upd. Предыдущее сообщение - это вывод в консоль данных, которые не соответствуют формату, через Arrays.deepToString(line.spilt(";"))

Да, тоже заметил, что данные битые. Но это не меняет суть задания.
(В крайнем случае, их можно подогнать под нужный формат.)
 
 
Сообщения:856
Приветствую, maxLich!

Вчера вечером появилось полчаса для рассмотрения этой интересной задачки :) Не нашёл больших проблем её решить за исключением...
Идея такая. В качестве "хранителя" информации создаём класс:
private static class Triplet {
        private final String first;
        private final String second;
        private final String T;

        Triplet(String first, String second, String third) {
            this.first = first;
            this.second = second;
            this.third = third;
        }

        @Override
        public String toString() {
            return first + ";" + second + ";" + third;
        }

{

Далее почти однострочник с Java 8 что-то типа такого:
        Map<Triplet, List<Triplet>> result = Files.readAllLines(Paths.get("Путь к файлу"))
                .parallelStream() 
                .map(l -> l.split(";"))
                .map(a -> {
                    if (a.length == 3) {
                        return new Triplet(a[0], a[1], a[2]);
                    }
                    return null;
                })
                .filter(t -> t != null) 
                .distinct()
                .collect(Collectors.groupingBy(r -> r, Collectors.mapping(r -> r, Collectors.toList())));

        AtomicInteger i = new AtomicInteger(0);

        long count = result.entrySet()
                .stream()
                .filter(r -> r.getValue().size() > 1)
                .count();

        Files.write(Paths.get("result.txt"),
                new StringBuilder("Records grouping count that greater 1 is ")
                        .append(count)
                        .append("\n")
                        .toString()
                        .getBytes());

        Files.write(Paths.get("result.txt"),
                () -> result
                        .entrySet()
                        .stream()
                        .sorted((o1, o2) -> {
                            return (o2.getValue().size() > o1.getValue().size()) ? 1 : ((o2.getValue().size() < o1.getValue().size())) ? -1 : 0;
                        })
                        .<CharSequence>map(e -> "Group " + i.incrementAndGet() + '\n'
                        + e.getValue()
                                .stream()
                                .map(Object::toString)
                                .collect(Collectors.joining("\n"))).iterator(), StandardOpenOption.APPEND);

С таким подходом скорость довольна высокая. Единственное чего не успел правильно реализовать hashCode и equals для Triplet.
Надо помнить, что по контракту hashCode:
“If two objects are equal, then calling hashCode() on both objects must return the same value”.
Это надо для результирующей HashMap

P.S.
Да и для выполнения этого потребовалось -Xmx2048m :D
 
 
Сообщения:59
Такое решение нашёл. Алгоритм:

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


Код метода, который делает всю эту байду=) :
private static List<List<String>> findLineGroups(List<String> lines) {
        class NewLineElement {
            private String lineElement;
            private int columnNum;

            private NewLineElement(String lineElement, int columnNum) {
                this.lineElement = lineElement;
                this.columnNum = columnNum;
            }
        }

        if (lines == null)
            return Collections.emptyList();

        List<List<String>> linesGroups = new ArrayList<>(); //список групп, каждый элемент вида "номер группы - список строк группы"
        if (lines.size() < 2) {
            linesGroups.add(lines);
            return linesGroups;
        }

        List<Map<String, Integer>> columns = new ArrayList<>(); // список стобцов, каждый столбец - мапа с парами "элемент строки/столбца-номер группы"
        Map<Integer, Integer> unitedGroups = new HashMap<>(); //мэп с парами "номер некоторой группы - номер группы, с которой надо объединить данную"
        for (String line : lines) {
            String[] lineElements = line.split(";");
            TreeSet<Integer> groupsWithSameElems = new TreeSet<>(); //список групп, имеющих совпадающие элементы
            List<NewLineElement> newElements = new ArrayList<>(); //список элементов, которых нет в мапах столбцов

            for (int elmIndex = 0; elmIndex < lineElements.length; elmIndex++) {
                String currLnElem = lineElements[elmIndex];
                if (columns.size() == elmIndex)
                    columns.add(new HashMap<>());
                if ("".equals(currLnElem.replaceAll("\"","").trim()))
                    continue;

                Map<String, Integer> currCol = columns.get(elmIndex);
                Integer elemGrNum = currCol.get(currLnElem);
                if (elemGrNum != null) {
                    while (unitedGroups.containsKey(elemGrNum)) // если группа с таким номером объединена с другой,
                        elemGrNum = unitedGroups.get(elemGrNum); //то сохраняем номер группы, с которой была объединена данная
                    groupsWithSameElems.add(elemGrNum);
                } else {
                    newElements.add(new NewLineElement(currLnElem, elmIndex));
                }
            }
            int groupNumber;
            if (groupsWithSameElems.isEmpty()) {
                linesGroups.add(new ArrayList<>());
                groupNumber = linesGroups.size() - 1;
            } else {
                groupNumber = groupsWithSameElems.first();
            }
            for (NewLineElement newLineElement : newElements) {
                columns.get(newLineElement.columnNum).put(newLineElement.lineElement, groupNumber);
            }
            for (int matchedGrNum : groupsWithSameElems) { //перебираем все группы с таким же элементом
                if (matchedGrNum != groupNumber) {
                    unitedGroups.put(matchedGrNum, groupNumber); //сохраняем инф-цию об объединённых группах
                    linesGroups.get(groupNumber).addAll(linesGroups.get(matchedGrNum)); //объединяем группы
                    linesGroups.set(matchedGrNum, null); //помечаем группу с текущим номер, как несуществующую
                }
            }
            linesGroups.get(groupNumber).add(line);
        }
        linesGroups.removeAll(Collections.singleton(null)); //удаляем несуществующие группы
        return linesGroups;
    }
 
 
Сообщения:9725
Похоже на задачу из теории графов - найти компоненты связности. Нода графа - это триплет, ноды связаны если у них есть одинаковые строки.
Изменен:25 апр 2018 20:52
 
 
Сообщения:59
Староверъ:
Похоже на задачу из теории графов - найти компоненты связности. Нода графа - это триплет, ноды связаны если у них есть одинаковые строки.
Не строки, а элементы строк
 
 
Сообщения:59
gidravlic:
Приветствую, maxLich!

Вчера вечером появилось полчаса для рассмотрения этой интересной задачки :) Не нашёл больших проблем её решить за исключением...
Идея такая. В качестве "хранителя" информации создаём класс:
private static class Triplet {
        private final String first;
        private final String second;
        private final String T;

        Triplet(String first, String second, String third) {
            this.first = first;
            this.second = second;
            this.third = third;
        }

        @Override
        public String toString() {
            return first + ";" + second + ";" + third;
        }

{

Далее почти однострочник с Java 8 что-то типа такого:
        Map<Triplet, List<Triplet>> result = Files.readAllLines(Paths.get("Путь к файлу"))
                .parallelStream() 
                .map(l -> l.split(";"))
                .map(a -> {
                    if (a.length == 3) {
                        return new Triplet(a[0], a[1], a[2]);
                    }
                    return null;
                })
                .filter(t -> t != null) 
                .distinct()
                .collect(Collectors.groupingBy(r -> r, Collectors.mapping(r -> r, Collectors.toList())));

        AtomicInteger i = new AtomicInteger(0);

        long count = result.entrySet()
                .stream()
                .filter(r -> r.getValue().size() > 1)
                .count();

        Files.write(Paths.get("result.txt"),
                new StringBuilder("Records grouping count that greater 1 is ")
                        .append(count)
                        .append("\n")
                        .toString()
                        .getBytes());

        Files.write(Paths.get("result.txt"),
                () -> result
                        .entrySet()
                        .stream()
                        .sorted((o1, o2) -> {
                            return (o2.getValue().size() > o1.getValue().size()) ? 1 : ((o2.getValue().size() < o1.getValue().size())) ? -1 : 0;
                        })
                        .<CharSequence>map(e -> "Group " + i.incrementAndGet() + '\n'
                        + e.getValue()
                                .stream()
                                .map(Object::toString)
                                .collect(Collectors.joining("\n"))).iterator(), StandardOpenOption.APPEND);

С таким подходом скорость довольна высокая. Единственное чего не успел правильно реализовать hashCode и equals для Triplet.
Надо помнить, что по контракту hashCode:
“If two objects are equal, then calling hashCode() on both objects must return the same value”.
Это надо для результирующей HashMap

P.S.
Да и для выполнения этого потребовалось -Xmx2048m :D

А не подскажите, как увеличить размера хипа? Я эту опцию писал и в идеи, в настройках запуска приложения, и в настройках джавы писал, и всё равно у меня, с моим решением, валится с ООМ. Хотя может быть на Вашем ООМ и не будет вылетать при таких настройках.
Изменен:26 апр 2018 12:18
 
 
Сообщения:856
Ну как обычно, в качастве аргумента для java: java -Xmx2048m -jar MyApp.jar
 
 
Сообщения:59
gidravlic:
Ну как обычно, в качастве аргумента для java: java -Xmx2048m -jar MyApp.jar

Поставил это в ИДЕИ, в консоли вышло:
Quote:
Could not reserve enough space for 2097152KB object heap

Изменил число на 1536, и все сработало, не вылетело.
 
Модераторы:Нет
Сейчас эту тему просматривают:Нет