unnar added a comment. In D74759#1893450 <https://reviews.llvm.org/D74759#1893450>, @labath wrote:
> 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 ? That should work...although I'm not sure how that is any different to the range or data being public. If a user modifies anything then it has essentially invalidated the whole structure anyway. 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
