Решение небольшой, но интересной задачи на java, с которой я столкнулся, сподвигло в очередной раз возвратиться к теме выбора реализации List-та.

Известно, что реализация Linked- или ArrayList-а в разных ситуациях (вставка, удаление.. добавление элемента в середину/начало/конец списка) ведет себя по разному. Что делает выбор текущей реализации не всегда очевидным. Proof?..

Например, существует задача выделения сообществ (подграфов). Необходимо сделать следующее:

а) считать файл со строками вида

A1;C2;F4
C2;Z4;N2
N2;H1;L8
T7;O7
...

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

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

они принадлежат одной группе. Например, строчки:

111;123;222
200;123;100
300;;100

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

На вход консольного приложения подаем файл (csv) c более чем млн. строк. Рассмотрим решение задачи с помощью библиотеки JGraphT:

@Component
public class Processing {

    @Autowired
    FiosUtil fiosUtil;

    public Graph<String, DefaultEdge> graph = new SimpleGraph<>(DefaultEdge.class);     DefaultDirectedWeightedGraph
    public Map<String, List<List<String>>> groupMap = new HashMap<>();
    public List<List<List<String>>> groupList = new LinkedList<>();
    private Integer groupCounter = 1;

    public void process() throws IOException {
        BufferedReader csvReader = new BufferedReader(new InputStreamReader(fiosUtil.getResourceFileStream()));
        String row;
        while ((row = csvReader.readLine()) != null) {
            List<String> rowSet = fiosUtil.getRowSet(row);
            createGraph(rowSet);
        }
        csvReader.close();
        System.out.println(">> Created graph. Graph vertexes are: " + graph.vertexSet().size() + "\t\t(unique digits in all row's)");
        boolean isEndOfGroups = graphIterate(graph);
        while (!isEndOfGroups) {
            isEndOfGroups = graphIterate(graph);
        }
        outOfGroups();
    }

    public void createGraph(List<String> row) {
        List<List<String>> list = new ArrayList<>();
        list.add(row);
        String initItem = "";
        if (!row.isEmpty()) initItem = row.get(0);
        for (String item : row) {
            if (!item.isEmpty()) {
                graph.addVertex(item);
                groupMap.merge(item, list, (x, y) -> {
                    x.addAll(y);
                    return x.stream().distinct().collect(Collectors.toList());
                });
                if (!initItem.isEmpty() && !initItem.equals(item)) {
                    graph.addEdge(initItem, item);
                    initItem = item;
                }
            }
        }
        if(row.size() == 3) graph.addEdge(row.get(0), row.get(row.size()-1));
    }

    public boolean graphIterate(Graph<String, DefaultEdge> graph) {
        List<List<String>> groupRows = new LinkedList<>();
        List<String> groupVertex = new ArrayList<>();
        Iterator<String> graphIterator = graph.vertexSet().iterator();
        if (graphIterator.hasNext()) {
            DepthFirstIterator<String, DefaultEdge> depthFirstIterator = new DepthFirstIterator<>(graph, graphIterator.next());
            while (depthFirstIterator.hasNext()) {
                String vertex = depthFirstIterator.next();
                groupVertex.add(vertex);
            }
            for (String vertex : groupVertex) {
                groupRows.addAll(new ArrayList<>(groupMap.get(vertex)));
            }
        }
        removeGraphEntrySaveRows(groupRows);
        return graph.vertexSet().size() == 0;
    }

    private void removeGraphEntrySaveRows(List<List<String>> group){
        List<List<String>> rowsGroup = group.stream()
                .peek(row -> row.forEach(vertex -> graph.removeVertex(vertex)))
                .distinct()
                .sorted(Comparator.comparingInt(List::size))
                .collect(Collectors.toList());
        groupList.add(rowsGroup);
    }

    public void outOfGroups(){
        Iterator<List<List<String>>> groupsIterator = groupList.iterator();
        while (groupsIterator.hasNext()){
            List<List<String>> currentGroup = groupsIterator.next();
            groupList.stream()
                    .filter(iterateGroup -> iterateGroup.equals(currentGroup))
                    .peek(iterateGroup -> {
                        iterateGroup.addAll(currentGroup);
                        groupList.remove(currentGroup);
                    });
        }

        for (List<List<String>> rowsGroup : groupList){
            System.out.println("\nGroup<" + groupCounter++ + ">:" +
                    "\n----------------------------------------------------");
            rowsGroup.forEach(System.out::println);
        }
    }
}

Для этого, в каждой входящей строке создаем vertex для каждого значения, создаем между ними edges. Затем просто обходим созданный граф DepthFirstIterator-итератором, исключая пройденные вершины и находим т.о., очередной подграф (или подгруппу, согласно условию задачи).

При правильной реализации на среднем ноутбуке мы вполне укладываемся в 30 sec. Как думаете, на сколько увеличится время решения, если поменять реализацию groupList на  ArrayList<>()?

Ссылка на GitHub

Вариант решения через алгоритм