Построение графика в JGraphT версии 0.8.2 быстрее, чем в версии 1.3.0 - PullRequest
Новая
       21

Построение графика в JGraphT версии 0.8.2 быстрее, чем в версии 1.3.0

2 голосов
/ 03 февраля 2020

Я строю график с более чем 90000 ребрами: 

DefaultDirectedGraph graph = ...
graph.addVertex(keyFrom);
graph.addVertex(keyTo);
graph.addEdge(keyFrom, keyTo);

В новой версии у меня следующие результаты:

  • BUILD_GRAPH заняло 13596 мс Число ребер: 90469
  • BUILD_GRAPH заняло 14354 мс. Число ребер: 94309
  • BUILD_GRAPH заняло 6647 мс. Число ребер: 90465

Со старой версией у меня следующие результаты: *

  • BUILD_GRAPH заняло 5081 мс Число ребер: 90469
  • BUILD_GRAPH заняло 3949 мс Число ребер: 94309
  • BUILD_GRAPH заняло 4351 мс Число ребер: 90466

Профилировщик сказал мне, что этот код медленен в lib: 

UniformIntrusiveEdgesSpecifics:
 return edgeMap.putIfAbsent(e, intrusiveEdge) == null;

Я пытался улучшить хэш-код вершины. Но это не помогает. Я хотел бы перейти на новую версию библиотеки. Но производительность это проблема. Есть идеи, почему новая версия библиотеки работает медленнее?

1 Ответ

0 голосов
/ 04 февраля 2020

После того, как я узнал:

  • График имеет не 90 000 больших ребер, но имеет 3 Mio ребра! Только с большими графиками вы можете наблюдать разницу в производительности!

  • Если переопределить метод График containsEdge, производительность будет в три раза выше, чем в новой версии

    new DefaultDirectedGraph<GraphNode,StandardFieldConnKeyEdge>(StandardFieldConnKeyEdge.class) { 

        @Override
    public StandardFieldConnKeyEdge addEdge(final GraphNode sourceVertex, final GraphNode targetVertex) {
        return super.addEdge(sourceVertex, targetVertex);

    }

    @Override
    public boolean containsEdge(final GraphNode sourceVertex, final GraphNode targetVertex) {
        return false;
    }

};

У меня есть проект затмения, который показывает эту проблему!

...