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