[
https://issues.apache.org/jira/browse/CALCITE-4049?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17134529#comment-17134529
]
Xiening Dai edited comment on CALCITE-4049 at 6/12/20, 8:44 PM:
----------------------------------------------------------------
I agree with [~julianhyde]. You cannot say there's no tradeoffs just because we
have more memory. There are OOM issues we have seen, such as CALCITE-3784.
In terms of the change itself, I wonder why we would need ConList in the first
place. If we just use a LinkedList, we can concact the head node and also have
O(1) complexity for size().
was (Author: xndai):
I agree with [~julianhyde]. You cannot say there's no tradeoffs just because we
have more memory. There are OOM issues we have seen, such as CALCITE-3784.
In terms of the change itself, I wonder why we would need ConList in the first
place. If we just use a LinkedList, we can contact the head node and also have
O(1) complexity for size().
> 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)
