[
https://issues.apache.org/jira/browse/CALCITE-4049?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17132852#comment-17132852
]
Liya Fan commented on CALCITE-4049:
-----------------------------------
[~julianhyde] Thanks a lot for your comments.
The down-side of adding the size field is that it makes the object size 4 bytes
larger (I am not sure if it is 50% larger, as an object has other meta-data to
store). The up-side is reducing the time complexity of getting size from O(n)
to O(1).
IMO, a general trend for performance optimization is to reduce time complexity
by taking more spaces, as memory/disk spaces are becoming less expensive today
and modern computers tend to have larger memory/disk spaces.
For example, we build indices for relation databases to reduce the query time,
at the expense of extra memory/disk spaces. We can also find examples from
Calcite code base. For example, in class
[RexCall|https://github.com/apache/calcite/blob/master/core/src/main/java/org/apache/calcite/rex/RexCall.java],
we have the {{nodeCount}} field, which introduces an extra 4 byte. However,
since it reduces the time complexity of getting node count, it should be
considered a good optimization.
> 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)
