Я надеюсь реализовать алгоритм Динича с помощью Java, и обнаружил странную проблему.
Имя вершины моего графа использует строковый тип, и когда эта строка использует чистые числа, такие как 1, 2, 3,,, 200, на этом этапе скорость ее выполнения очень высока.
Однако если я добавлю префикс к имени узла, скорость выполнения этого кода станет очень низкой из-за длины строки префикса, что трудно понять.
Мой код реализации алгоритма:
package org.apache.misc.alg.dag;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;
public class DinicCalculator<T> implements MaxAntichainCalculator<T> {
private final Map<String, Map<String, Integer>> network;
private List<String> nodes;
private int[] level;
public DinicCalculator() {
network = new HashMap<>();
nodes = new ArrayList<>();
nodes.add("src");
nodes.add("sink");
}
private void bfs(String source) {
level = new int[nodes.size()];
Arrays.fill(level, -1);
level[nodes.indexOf(source)] = 0;
Queue<String> queue = new LinkedList<>();
queue.offer(source);
while (!queue.isEmpty()) {
String u = queue.poll();
for (Map.Entry<String, Integer> entry : network.get(u).entrySet()) {
String v = entry.getKey();
int capacity = entry.getValue();
if (capacity > 0 && level[nodes.indexOf(v)] == -1) {
level[nodes.indexOf(v)] = level[nodes.indexOf(u)] + 1;
queue.offer(v);
}
}
}
}
private int dfs(String u, int flow, String sink) {
if (u.equals(sink)) {
return flow;
}
for (Map.Entry<String, Integer> entry : network.get(u).entrySet()) {
String v = entry.getKey();
int capacity = entry.getValue();
if (capacity > 0 && level[nodes.indexOf(u)] < level[nodes.indexOf(v)]) {
int sent = dfs(v, Math.min(flow, capacity), sink);
if (sent > 0) {
network.get(u).put(v, capacity - sent);
network.get(v).put(u, network.get(v).getOrDefault(u, 0) + sent);
return sent;
}
}
}
return 0;
}
private void addEdge(String from, String to, int capacity) {
network.computeIfAbsent(from, k -> new HashMap<>()).put(to, capacity);
network.computeIfAbsent(to, k -> new HashMap<>()).put(from, 0);
if (!nodes.contains(from)) nodes.add(from);
if (!nodes.contains(to)) nodes.add(to);
}
private Set<String> reach(Map<T, Set<T>> graph, T t, Set<String> visited) {
Queue<T> queue = new LinkedList<>();
queue.add(t);
while (!queue.isEmpty()) {
T current = queue.poll();
String currentKey = "A" + current.toString();
visited.add(currentKey);
for (T neighbor : graph.get(current)) {
String neighborKey = "B" + neighbor.toString();
if (!visited.contains(neighborKey)) {
queue.add(neighbor);
visited.add(neighborKey);
}
}
}
return visited;
}
// entrance
public int calculator(Map<T, Set<T>> graph) {
for (T t : graph.keySet()) {
addEdge("src", "A" + t.toString(), 1);
addEdge("B" + t, "sink", 1);
Set<String> visitedSubset = new HashSet<>();
for (String u : reach(graph, t, visitedSubset)) {
addEdge("A" + t, u, 1);
}
}
int maxFlow = 0;
while (true) {
bfs("src");
if (level[nodes.indexOf("sink")] == -1) {
break;
}
int flow;
while ((flow = dfs("src", Integer.MAX_VALUE, "sink")) > 0) {
maxFlow += flow;
}
}
return graph.size() - maxFlow;
}
}
Мой тестовый код:
package org.apache.misc.alg.dag;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
import org.junit.jupiter.api.Test;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
public class DagTests {
private static final Logger logger = LoggerFactory.getLogger(DagTests.class);
@Test
public void test() {
// Test prefixes of different lengths
// like 1,2,3,4,,,,,200
test1("");
// like A1,A2,A3,A4,,,,,A200
test1("A");
test1("AA");
test1("AAA");
test1("x");
test1("xx");
// like xx_1,xx_2,xx_3,,,,xx_200
test1("xx_");
}
public void test1(String prefix) {
Map<String, Set<String>> graph = genGraph(prefix);
long t1 = System.currentTimeMillis();
int result = new DinicCalculator<String>().calculator(graph);
logger.info("DinicCalculator with prefix: " + prefix + ", result: " + result + ", time: " + (System.currentTimeMillis() - t1));
}
private Map<String, Set<String>> genGraph(String prefix) {
Map<String, Set<String>> graph = new HashMap<>();
String end = null;
for (int i = 0; i < 200; i++) {
String i1 = prefix + i;
String i2 = prefix + (i + 1);
graph.put(i1, new HashSet<>(Arrays.asList(i2)));
end = i2;
}
graph.put(end, new HashSet<>());
return graph;
}
}
Вывод моего тестового кода:
18:21:24.609 [main] INFO org.apache.misc.alg.dag.DagTests -- DinicCalculator with prefix: , result: 1, time: 503
18:21:27.137 [main] INFO org.apache.misc.alg.dag.DagTests -- DinicCalculator with prefix: A, result: 1, time: 2526
18:21:48.843 [main] INFO org.apache.misc.alg.dag.DagTests -- DinicCalculator with prefix: AA, result: 1, time: 21706
18:21:55.826 [main] INFO org.apache.misc.alg.dag.DagTests -- DinicCalculator with prefix: AAA, result: 1, time: 6983
18:21:57.199 [main] INFO org.apache.misc.alg.dag.DagTests -- DinicCalculator with prefix: x, result: 1, time: 1373
19:35:07.166 [main] INFO org.apache.misc.alg.dag.DagTests -- DinicCalculator with prefix: xx, result: 1, time: 4389965
19:45:18.590 [main] INFO org.apache.misc.alg.dag.DagTests -- DinicCalculator with prefix: xx_, result: 1, time: 611424
Информация о тесте:
У меня аналогичный эффект при использовании x64+Ubuntu 22.04+JDK 1.8, а также в x64+centos7.5 + jdk1.8.
Так в чем именно проблема, может ли она быть вызвана кешем процессора?
В вашем методе dfs
отсутствует посещенная проверка. На практике вы выполняете неограниченный поиск, который выполняется очень медленно.
Кроме того, я изменил поле nodes
на Map<String, Integer>
вместо List<String>
, чтобы избежать дорогостоящих звонков nodes.indexOf
.
После этого я вижу вот что:
DinicCalculator with prefix: , result: 1, time: 85
DinicCalculator with prefix: A, result: 1, time: 102
DinicCalculator with prefix: AA, result: 1, time: 104
DinicCalculator with prefix: AAA, result: 1, time: 91
DinicCalculator with prefix: x, result: 1, time: 67
DinicCalculator with prefix: xx, result: 1, time: 66
DinicCalculator with prefix: xx_, result: 1, time: 83
Вот код DinicCalculator:
public class DinicCalculator<T> {
private final Map<String, Map<String, Integer>> network;
private Map<String, Integer> nodes;
private int[] level;
public DinicCalculator() {
network = new HashMap<>();
nodes = new HashMap<>();
nodes.put("src", nodes.size());
nodes.put("sink", nodes.size());
}
private void bfs(String source) {
level = new int[nodes.size()];
Arrays.fill(level, -1);
level[nodes.get(source)] = 0;
Queue<String> queue = new LinkedList<>();
queue.offer(source);
while (!queue.isEmpty()) {
String u = queue.poll();
for (Map.Entry<String, Integer> entry : network.get(u).entrySet()) {
String v = entry.getKey();
int capacity = entry.getValue();
if (capacity > 0 && level[nodes.get(v)] == -1) {
level[nodes.get(v)] = level[nodes.get(u)] + 1;
queue.offer(v);
}
}
}
}
private int dfs(String u, int flow, String sink, HashSet<String> visited) {
if (visited.contains(u)) {
return 0;
}
visited.add(u);
if (u.equals(sink)) {
return flow;
}
for (Map.Entry<String, Integer> entry : network.get(u).entrySet()) {
String v = entry.getKey();
int capacity = entry.getValue();
if (capacity > 0 && level[nodes.get(u)] < level[nodes.get(v)]) {
int sent = dfs(v, Math.min(flow, capacity), sink, visited);
if (sent > 0) {
network.get(u).put(v, capacity - sent);
network.get(v).put(u, network.get(v).getOrDefault(u, 0) + sent);
return sent;
}
}
}
return 0;
}
private void addEdge(String from, String to, int capacity) {
network.computeIfAbsent(from, k -> new HashMap<>()).put(to, capacity);
network.computeIfAbsent(to, k -> new HashMap<>()).put(from, 0);
if (!nodes.containsKey(from)) nodes.put(from, nodes.size());
if (!nodes.containsKey(to)) nodes.put(to, nodes.size());
}
private Set<String> reach(Map<T, Set<T>> graph, T t, Set<String> visited) {
Queue<T> queue = new LinkedList<>();
queue.add(t);
while (!queue.isEmpty()) {
T current = queue.poll();
String currentKey = "A" + current.toString();
visited.add(currentKey);
for (T neighbor : graph.get(current)) {
String neighborKey = "B" + neighbor.toString();
if (!visited.contains(neighborKey)) {
queue.add(neighbor);
visited.add(neighborKey);
}
}
}
return visited;
}
// entrance
public int calculator(Map<T, Set<T>> graph) {
for (T t : graph.keySet()) {
addEdge("src", "A" + t.toString(), 1);
addEdge("B" + t, "sink", 1);
Set<String> visitedSubset = new HashSet<>();
for (String u : reach(graph, t, visitedSubset)) {
addEdge("A" + t, u, 1);
}
}
int maxFlow = 0;
while (true) {
bfs("src");
if (level[nodes.get("sink")] == -1) {
break;
}
int flow;
while ((flow = dfs("src", Integer.MAX_VALUE, "sink", new HashSet<>())) > 0) {
maxFlow += flow;
}
}
return graph.size() - maxFlow;
}
}
Спасибо, это действительно решило мою проблему. Но мне все равно интересно, почему добавление префиксов приводит к всплеску затрат времени. Тип узлов всегда был String.