Реализация Java, проблема производительности алгоритма Динича

Я надеюсь реализовать алгоритм Динича с помощью 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

Информация о тесте:

  • ОС: macOS Сонома 14.6.1
    • чип: apple m1 pro
  • Версия JDK: openjdk-21.0.2

У меня аналогичный эффект при использовании x64+Ubuntu 22.04+JDK 1.8, а также в x64+centos7.5 + jdk1.8.

Так в чем именно проблема, может ли она быть вызвана кешем процессора?

Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
Как вычислять биты и понимать побитовые операторы в Java - объяснение с примерами
Как вычислять биты и понимать побитовые операторы в Java - объяснение с примерами
В компьютерном программировании биты играют важнейшую роль в представлении и манипулировании данными на двоичном уровне. Побитовые операции...
Поднятие тревоги для долго выполняющихся методов в Spring Boot
Поднятие тревоги для долго выполняющихся методов в Spring Boot
Приходилось ли вам сталкиваться с требованиями, в которых вас могли попросить поднять тревогу или выдать ошибку, когда метод Java занимает больше...
Полный курс Java для разработчиков веб-сайтов и приложений
Полный курс Java для разработчиков веб-сайтов и приложений
Получите сертификат Java Web и Application Developer, используя наш курс.
2
0
52
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

В вашем методе 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.

hehe 21.08.2024 07:37

Другие вопросы по теме