labath added a comment. I like this idea a lot, in principle. It is much simpler than a full blown interval tree, and it should give us similar performance characteristics.
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.) The implementation itself needs some work though. My incomplete list of comments is: - replace `int` with `size_t` and closed intervals with half-open ones - let's move the computation of the upper bound into the "Sort" function. sorting is O(n log(n)), this is O(n) -- we can just hide it there. - make private functions private - we should avoid the business of figuring out what is the suitable "minimum" value of B by ensuring we call the recursive function on non-empty intervals - clang-format the patch For testing you should add some c++ unit tests for the relevant interfaces. Repository: rLLDB LLDB 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
