labath added a comment. In D74759#1893186 <https://reviews.llvm.org/D74759#1893186>, @unnar wrote:
> In D74759#1880499 <https://reviews.llvm.org/D74759#1880499>, @labath wrote: > > > Have you done a proper complexity analysis here? I doubt the `O(log n)` > > claim is true in general. It would have to be at least `O(m + log n)` (m - > > number of elements found), but it's not clear to me whether even this is > > true in general. (However, I believe this can achieve ~~log(n) for > > non-degenerate cases.) > > > I should have been more specific, searching for any interval that contains a > point can be done in `O(log n)` but in our case where we are searching for > all intervals that contain the point and as Jarin said we believe it takes > `O(m log n)` (I admit I have not done a thorough analysis of the time > complexity myself). The theoretical best you can do is indeed `O(m + log n)`. Yep, I can easily convince myself is m*log(n). I can believe it can be O(m+log(n)) too, but proving that would require some pretty careful accounting. In either case, I am sure this is better than what we have now. >> For testing you should add some c++ unit tests for the relevant interfaces. > > Done. Do you think we should also unit test ComputeUpperBounds or just the > interface? Testing the interface should be enough. In fact, the main thing that is bothering me about this patch at this stage is that the new "upper_bound" member is public and accessible to the user. I haven't decided yet what to do about it. Have you looked at what it would take to make that private somehow? Maybe by storing std::pair<Entry, bound> in the private vector, and only handing out pointers to the `Entry` component ? CHANGES SINCE LAST ACTION https://reviews.llvm.org/D74759/new/ https://reviews.llvm.org/D74759 _______________________________________________ lldb-commits mailing list lldb-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/lldb-commits
