[
https://issues.apache.org/jira/browse/CALCITE-4049?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17136119#comment-17136119
]
Julian Hyde commented on CALCITE-4049:
--------------------------------------
[~fan_li_ya], Can you describe the use case where you were getting performance
problems?
If would be surprised if one call to find the length of a path was problematic.
In a many typical graphs with N nodes I'd expect the length of the shortest
path is much smaller than N - say O(sqrt(N)). So in a graph of 10,000 nodes,
finding the length of a path might require 100 or so operations. For such
graphs, even fairly large, asking for the length of one path would not be
expensive.
Now if you are getting lots of paths and asking each for its length, then you
now have a more complex algorithm. There are several ways that algorithm could
be optimized - say by computing the path lengths once and storing them; or
having a way of asking for all paths of length k - but it depends on the
algorithm.
Or are you finding that the graph freezing process is slow? (I would not be
surprised, given that it calls {{List.size()}} many times, but again, there are
other ways of optimizing the freezing algorithm.)
> Reduce the time complexity of getting shortest distances
> --------------------------------------------------------
>
> Key: CALCITE-4049
> URL: https://issues.apache.org/jira/browse/CALCITE-4049
> Project: Calcite
> Issue Type: Improvement
> Components: core
> Reporter: Liya Fan
> Assignee: Liya Fan
> Priority: Major
> Fix For: 1.24.0
>
> Time Spent: 1h 20m
> Remaining Estimate: 0h
>
> Currently, we have {{Graphs#makeImmutable}} to compute the shortest paths
> between all pairs of nodes. For many scenarios, however, we do not need the
> exact paths between nodes. Instead, we are only interested in the lengths of
> the shortest paths.
> To get the path length, we need to get the shortest path first, which is
> returned as a {{List}}, then we call the {{List#size()}} method. According to
> the current implementation, the returned list is of type {{ConsList}}. The
> time complexity of {{ConsList#size}} is O(p) (p is the number of vertices on
> the path), which is inefficient.
> In this issue, we revise the implementation of {{ConsList#size}} so that it
> takes O(1) time. In addition, we also give a utiltiy to get the shortest
> distances between nodes.
--
This message was sent by Atlassian Jira
(v8.3.4#803005)
