Еще раз… вопрос выбора: LinkedList & ArrayList

Решение небольшой, но интересной задачи на 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

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