Dan Burkert has posted comments on this change. ( http://gerrit.cloudera.org:8080/8041 )
Change subject: KUDU-2055 [part 2]: Add util to construct sorted disjoint interval list ...................................................................... Patch Set 4: (1 comment) http://gerrit.cloudera.org:8080/#/c/8041/4/src/kudu/util/sorted_disjoint_interval_list.h File src/kudu/util/sorted_disjoint_interval_list.h: http://gerrit.cloudera.org:8080/#/c/8041/4/src/kudu/util/sorted_disjoint_interval_list.h@54 PS4, Line 54: Status CoalesceIntervals(std::vector<std::pair<PointType, PointType>>* intervals) { Couple of notes on the algorithm: - Since this is meant to be a general utility, it'd be better if it operated on [closed, open) interval, since it's always possible to convert a closed interval to a [closed, open) interval, but it's not possible to convert a closed intervals of strings to [closed, open). I think this algorithm would be useful in a few places where we have string interval sets (see partition_pruner.cc). - This algorithm can be implemented in-place without allocating a new vector. It's also simpler since you don't need / can't have a separate Point type. It requires scanning over the original vector with two pointers from left to right, coalescing/copying ranges as you go, until you get to the end and remove a suffix of now unused elements (from what I can tell the existing implementation over Points is doing something similar). The algorithmic complexity is n*log(n) where n is the number of input intervals. -- To view, visit http://gerrit.cloudera.org:8080/8041 To unsubscribe, visit http://gerrit.cloudera.org:8080/settings Gerrit-Project: kudu Gerrit-Branch: master Gerrit-MessageType: comment Gerrit-Change-Id: I61a813c047be4882f246eaf404598e7e18fcac87 Gerrit-Change-Number: 8041 Gerrit-PatchSet: 4 Gerrit-Owner: Hao Hao <hao....@cloudera.com> Gerrit-Reviewer: Adar Dembo <a...@cloudera.com> Gerrit-Reviewer: Alexey Serbin <aser...@cloudera.com> Gerrit-Reviewer: Andrew Wong <aw...@cloudera.com> Gerrit-Reviewer: Dan Burkert <danburk...@apache.org> Gerrit-Reviewer: David Ribeiro Alves <davidral...@gmail.com> Gerrit-Reviewer: Hao Hao <hao....@cloudera.com> Gerrit-Reviewer: Kudu Jenkins Gerrit-Reviewer: Tidy Bot Gerrit-Reviewer: Todd Lipcon <t...@apache.org> Gerrit-Comment-Date: Thu, 21 Sep 2017 21:08:44 +0000 Gerrit-HasComments: Yes
