Hao Hao has posted comments on this change. Change subject: KUDU-2055 [part 2]: Add util to construct sorted disjoint interval list ......................................................................
Patch Set 2: (21 comments) http://gerrit.cloudera.org:8080/#/c/8041/1//COMMIT_MSG Commit Message: PS1, Line 9: This patch adds an utility to construct a sorted disjoint interval list : given a list of intervals. The operation to construct such one is : O(klg k + k) where 'k' is the number of points in > maybe mention a bit what this is for? easier to review for perf if we know Done http://gerrit.cloudera.org:8080/#/c/8041/1/src/kudu/util/sorted_disjoint_interval-test.cc File src/kudu/util/sorted_disjoint_interval-test.cc: Line 29 > warning: using decl 'Substitute' is unused [misc-unused-using-decls] Done PS1, Line 36: > Should this be a class/structure template as well (with type for the left Done PS1, Line 37: > If not using a class template for this ClosedInterval, consider making the Done Line 46 > nit: const? Done Line 47 > int: const? Done PS1, Line 50: : : : : : > nit: why does this need to be its own struct? why not a lambda within sort( Done, but I do not see much difference between these two? PS1, Line 58: > nit: consider IntIntervalTraits or something? Or just IntInterval? Done PS1, Line 85: : : > nit: here and below consider replacing with something like Done Line 132 > I don't see any coverage for single element intervals, like Done http://gerrit.cloudera.org:8080/#/c/8041/1/src/kudu/util/sorted_disjoint_interval.h File src/kudu/util/sorted_disjoint_interval.h: PS1, Line 17: : > Use #pragma once for C++11 ! Done PS1, Line 27: : > nit: How about, "A set of sorted disjoint intervals holds a list of non-ove Done PS1, Line 33: > nit: to emphasize the sortedness of the sorted disjoint interval set, maybe Done PS1, Line 40: > immutable? Done PS1, Line 46: : : : : : : : : : : : : : : : : : > Is there a way to encapsulate this into some sort of templatized abstract b I have rewrite the logic of constructing a sorted disjoint interval list to avoid too many template functions. PS1, Line 66: > nit: it's more of a SortedDisjointIntervalList Done PS1, Line 65: : > Why does SortedDisjointInterval need its own class; could it just be a temp If we have other implementations of interval list may be we can do that. But I feel that is too abstract at least for the use case I encounter at LBM, which is specific for sorted and disjoint intervals. PS1, Line 89: > Maybe, just move it inside the class definition above? Done Line 94 > just looking at this quickly... curious why we need a specific Traits::sort Thanks a lot for the proposal! Yeah this would work and simplify the template definition. Only the operation complexity would change from, O(nlg n + n) where 'n' is the number of intervals, to O(klg k + k) where 'k' is the number of 'point'. But I guess it is ok. PS1, Line 98: > Two questions here: 1) right, we need to check that. 2) removed the following logic. PS1, Line 106: > ++cur might be better since it doesn't need to store the prev iterator valu Rewritten the logic here. -- To view, visit http://gerrit.cloudera.org:8080/8041 To unsubscribe, visit http://gerrit.cloudera.org:8080/settings Gerrit-MessageType: comment Gerrit-Change-Id: I61a813c047be4882f246eaf404598e7e18fcac87 Gerrit-PatchSet: 2 Gerrit-Project: kudu Gerrit-Branch: master Gerrit-Owner: Hao Hao <hao....@cloudera.com> Gerrit-Reviewer: Alexey Serbin <aser...@cloudera.com> Gerrit-Reviewer: Andrew Wong <aw...@cloudera.com> 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-HasComments: Yes
