- Boost - lists.boost.org

Re: [boost] Median in Boost.Accumulators
by Lakshay Garg 23 Sep '18

23 Sep '18

On Sun, 23 Sep 2018 at 12:53, Zach Laine <whatwasthataddress(a)gmail.com> wrote: > > On Sun, Sep 23, 2018 at 2:45 PM Lakshay Garg <lakshayg373(a)gmail.com> wrote: >> >> On Sun, 23 Sep 2018 at 11:59, Zach Laine <whatwasthataddress(a)gmail.com> wrote: >> > Also, what if I don't actually call get() very often? >> >> If get() is not called very often, then I guess just using a plain vector and >> calling nth_element on it would be the best approach. >> >> > Is there any way to take advantage of make_heap()'s O(n) characteristics, >> > and avoid doing an O(n) push_heap() n times? I can't think of one offhand, >> > just curious. >> >> The complexity of push_heap is actually O(log(n)) and not O(n) > > [make.heap] says: > > Complexity: At most 3 * (last - first) comparisons. > Correct! complexity for make_heap is O(n) and complexity for push_heap is O(logn). https://en.cppreference.com/w/cpp/algorithm/make_heap https://en.cppreference.com/w/cpp/algorithm/push_heap

1 0

Re: [boost] Median in Boost.Accumulators
by Lakshay Garg 23 Sep '18

23 Sep '18

On Sun, 23 Sep 2018 at 11:59, Zach Laine <whatwasthataddress(a)gmail.com> wrote: > > On Sun, Sep 23, 2018 at 10:59 AM Lakshay Garg <lakshayg373(a)gmail.com> wrote: >> >> On Sun, 23 Sep 2018 at 08:39, Zach Laine via Boost >> <boost(a)lists.boost.org> wrote: >> > >> > Could you compare and contrast this with the standard library's way of >> > computing a median, std::nth_element()? Yout just give it N/2 for 'n', and >> > it computes the median. >> >> The reason for not using std::nth_element was because I wanted >> to be able to query the median at any point of the sequence very >> efficiently. Had I used std::nth_element, I would have needed O(n) >> time for obtaining the median. For a case where I need to compute >> median after every single element, this would have required O(n^2) >> time for a sequence of length n. Here is my implementation in case >> you would like to have a look: >> >> https://gist.github.com/lakshayg/d27f29b4634cbfea3fc48c21b7b608ef > > I missed that the first time, thanks. > > Your implementation does not seem to support a windowed working set > (one element at a time is added and the oldest one removed). Is that right? Yes, that is correct. This approach does not support a window. > Also, what if I don't actually call get() very often? If get() is not called very often, then I guess just using a plain vector and calling nth_element on it would be the best approach. > Is there any way to take advantage of make_heap()'s O(n) characteristics, > and avoid doing an O(n) push_heap() n times? I can't think of one offhand, > just curious. The complexity of push_heap is actually O(log(n)) and not O(n)

1 0

Re: [boost] Median in Boost.Accumulators
by Bjorn Reese 23 Sep '18

23 Sep '18

On 09/23/18 04:21, Lakshay Garg via Boost wrote: > I rolled up my custom implementation of the algorithm and > used it for my project. I wanted to check if people on > this list might be interested in such an implementation > for Boost.Accumulators in which case I can try to adapt my > implementation and send a PR. Boost.Accumulators does not seem to be actively maintained. > Performance characteristics: For a stream of n numbers, the > memory required is O(n). Median can be queried at any point > of time in O(1) and adding all the elements costs O(nlog(n)) Sounds like you keep two ordered lists (e.g. std::set) of equal size. Then the median is the first element in the second list.

2 1

Formal Review of Proposed Boost.Histogram Library is HALFWAY through
by Mateusz Loskot 22 Sep '18

22 Sep '18

Dear Boost Community, We've reach half-way through the formal review of Hans Dembinski's Histogram library. The review lasts until the end of September 26th. If you are interested in applications for mathematics, statistics graphics, image analysis, and such, or in the Histogram library itself, please consider reviewing the Histogram library by the end of September 26th. Best regards, -- Mateusz Loskot, http://mateusz.loskot.net

1 0

[filesystem] Library maintainers needed
by Beman Dawes 22 Sep '18

22 Sep '18

I'm retiring, so Boost.Filesystem needs one or more maintainers. This is a high complexity library, further complicated by (1) requiring both Windows and non-Windows implementation code and (2) needing a major upgrade for compatibility with the new standard library version shipped in C++17. Furthermore, there are constant Pull Requests and Issues that arise, and these almost invariably take a lot of time for the maintainer to process. My personal opinion is that Boost should deprecate the Boost library in favor of the standard library implementations, and do only minimal maintenance for several years until most users have migrated to C++17 or later. But that's up to the new maintainers to decide. Thanks, --Beman

3 2

[endian] Library maintainer needed
by Beman Dawes 22 Sep '18

22 Sep '18

I'm retiring, so Boost.Endian needs a maintainer. This is a low/medium complexity library that requires only minor effort to maintain. --Beman

2 1

[timer] Library maintainer needed
by Beman Dawes 22 Sep '18

22 Sep '18

I'm retiring, so Boost.Timer needs a maintainer. This is a simple low complexity library, and requires little effort to effort to maintain. --Beman

1 0

[build][testing] Tests naming in Jamfile
by Mateusz Loskot 21 Sep '18

21 Sep '18

Hi, I'm updating Jamfile-s of Boost.GIL and it made me wondering: For example: test-suite "boost-gil-test" : [ run promote_integral.cpp ] ; Apart from replacing the deprecated test-suite with alias, I wonder what is the recommended policy of naming the test suites, are there any rules? For example, should it be more or less hierarchical boost-{lib}-{testname} {lib}-{testname} {testname} or the name is completely local to/internal in a library and library maintainers are free to name as they desire? I could not find anything in the development guidelines and the testing policy docs. Best regards, -- Mateusz Loskot, http://mateusz.loskot.net p.s. Originally posted to boost-testing incorrectly https://lists.boost.org/boost-testing/2018/09/8446.php

2 2

[system] A non-allocating message() overload
by Peter Dimov 20 Sep '18

20 Sep '18

One of the objections against <system_error> is that message() needs to allocate memory, because it returns an std::string. This is true even for user-defined categories that can implement it without allocating, with a static message table. To address this, I'm thinking of adding the following overload to boost::system::error_category (with the intent of proposing it for std::error_category): virtual char const* message( int ev, char* buffer, size_t len ) noexcept; This is modeled after the glibc-specific version of strerror_r (and in fact has the exact same signature and behavior). If the implementation has a static character literal corresponding to `ev`, it returns it directly. If not, it composes an error message into the provided buffer, then returns `buffer`. Comments?

3 7

HoF Problems with Boost 1.68 / LLVM-Clang / Windows
by Adam Hartshorne 20 Sep '18

20 Sep '18

The following two bits of code compile ok with MSVC, but using LLVM/Clang produces the following errors. Using the code in print.cpp BOOST_HOF_STATIC_FUNCTION(simple_print) = fix(first_of( BOOST_HOF_LIFT(print_with_cout), BOOST_HOF_LIFT(print_with_range), BOOST_HOF_LIFT(print_with_tuple) )); produces the following error 1>./boost_hof_functions.h(45): error : templates cannot be declared inside of a local class 1>C:\boost_1_68_0\boost/hof/lift.hpp(90): note: expanded from macro 'BOOST_HOF_LIFT' 1>C:\boost_1_68_0\boost/hof/lift.hpp(105): note: expanded from macro 'BOOST_HOF_LIFT_CLASS' And BOOST_HOF_STATIC_LAMBDA_FUNCTION(print) = boost::hof::proj(simple_print); produces >./boost_hof_functions.h(51): error : non-const lvalue reference to type 'reveal_adaptor<...>' cannot bind to a temporary of type 'reveal_adaptor<...>' 1>C:\boost_1_68_0\boost/hof/lambda.hpp(241): note: expanded from macro 'BOOST_HOF_STATIC_LAMBDA_FUNCTION'] There are nearly identical errors with functions from in.cpp.

2 1