On Jul 22, 2014, at 8:48 PM, David Majnemer <[email protected]> wrote:
> Should this be merged for 3.5? Yes. — Marshall > > > On Mon, Jul 21, 2014 at 11:07 PM, David Majnemer <[email protected]> > wrote: > Author: majnemer > Date: Tue Jul 22 01:07:09 2014 > New Revision: 213615 > > URL: http://llvm.org/viewvc/llvm-project?rev=213615&view=rev > Log: > Fix std::make_heap's worst case time complexity > > std::make_heap is currently implemented by iteratively applying a > siftup-type algorithm. Since sift-up is O(ln n), this gives > std::make_heap a worst case time complexity of O(n ln n). > > The C++ standard mandates that std::make_heap make no more than O(3n) > comparisons, this makes our std::make_heap out of spec. > > Fix this by introducing an implementation of __sift_down and switch > std::make_heap to create the heap using it. > This gives std::make_heap linear time complexity in the worst case. > > This fixes PR20161. > > Modified: > libcxx/trunk/include/algorithm > > libcxx/trunk/test/algorithms/alg.sorting/alg.heap.operations/make.heap/make_heap_comp.pass.cpp > > Modified: libcxx/trunk/include/algorithm > URL: > http://llvm.org/viewvc/llvm-project/libcxx/trunk/include/algorithm?rev=213615&r1=213614&r2=213615&view=diff > ============================================================================== > --- libcxx/trunk/include/algorithm (original) > +++ libcxx/trunk/include/algorithm Tue Jul 22 01:07:09 2014 > @@ -4794,49 +4794,8 @@ is_heap(_RandomAccessIterator __first, _ > > template <class _Compare, class _RandomAccessIterator> > void > -__push_heap_front(_RandomAccessIterator __first, _RandomAccessIterator, > _Compare __comp, > - typename > iterator_traits<_RandomAccessIterator>::difference_type __len) > -{ > - typedef typename iterator_traits<_RandomAccessIterator>::difference_type > difference_type; > - typedef typename iterator_traits<_RandomAccessIterator>::value_type > value_type; > - if (__len > 1) > - { > - difference_type __p = 0; > - _RandomAccessIterator __pp = __first; > - difference_type __c = 2; > - _RandomAccessIterator __cp = __first + __c; > - if (__c == __len || __comp(*__cp, *(__cp - 1))) > - { > - --__c; > - --__cp; > - } > - if (__comp(*__pp, *__cp)) > - { > - value_type __t(_VSTD::move(*__pp)); > - do > - { > - *__pp = _VSTD::move(*__cp); > - __pp = __cp; > - __p = __c; > - __c = (__p + 1) * 2; > - if (__c > __len) > - break; > - __cp = __first + __c; > - if (__c == __len || __comp(*__cp, *(__cp - 1))) > - { > - --__c; > - --__cp; > - } > - } while (__comp(__t, *__cp)); > - *__pp = _VSTD::move(__t); > - } > - } > -} > - > -template <class _Compare, class _RandomAccessIterator> > -void > -__push_heap_back(_RandomAccessIterator __first, _RandomAccessIterator > __last, _Compare __comp, > - typename > iterator_traits<_RandomAccessIterator>::difference_type __len) > +__sift_up(_RandomAccessIterator __first, _RandomAccessIterator __last, > _Compare __comp, > + typename iterator_traits<_RandomAccessIterator>::difference_type > __len) > { > typedef typename iterator_traits<_RandomAccessIterator>::difference_type > difference_type; > typedef typename iterator_traits<_RandomAccessIterator>::value_type > value_type; > @@ -4869,10 +4828,10 @@ push_heap(_RandomAccessIterator __first, > #ifdef _LIBCPP_DEBUG > typedef typename add_lvalue_reference<__debug_less<_Compare> >::type > _Comp_ref; > __debug_less<_Compare> __c(__comp); > - __push_heap_back<_Comp_ref>(__first, __last, __c, __last - __first); > + __sift_up<_Comp_ref>(__first, __last, __c, __last - __first); > #else // _LIBCPP_DEBUG > typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; > - __push_heap_back<_Comp_ref>(__first, __last, __comp, __last - __first); > + __sift_up<_Comp_ref>(__first, __last, __comp, __last - __first); > #endif // _LIBCPP_DEBUG > } > > @@ -4887,6 +4846,60 @@ push_heap(_RandomAccessIterator __first, > // pop_heap > > template <class _Compare, class _RandomAccessIterator> > +void > +__sift_down(_RandomAccessIterator __first, _RandomAccessIterator __last, > _Compare __comp, > + typename iterator_traits<_RandomAccessIterator>::difference_type > __len, > + _RandomAccessIterator __start) > +{ > + typedef typename iterator_traits<_RandomAccessIterator>::difference_type > difference_type; > + typedef typename iterator_traits<_RandomAccessIterator>::value_type > value_type; > + // left-child of __start is at 2 * __start + 1 > + // right-child of __start is at 2 * __start + 2 > + difference_type __child = __start - __first; > + > + if (__len < 2 || (__len - 2) / 2 < __child) > + return; > + > + __child = 2 * __child + 1; > + _RandomAccessIterator __child_i = __first + __child; > + > + if ((__child + 1) < __len && __comp(*__child_i, *(__child_i + 1))) { > + // right-child exists and is greater than left-child > + ++__child_i; > + ++__child; > + } > + > + // check if we are in heap-order > + if (__comp(*__child_i, *__start)) > + // we are, __start is larger than it's largest child > + return; > + > + value_type __top(_VSTD::move(*__start)); > + do > + { > + // we are not in heap-order, swap the parent with it's largest child > + *__start = _VSTD::move(*__child_i); > + __start = __child_i; > + > + if ((__len - 2) / 2 < __child) > + break; > + > + // recompute the child based off of the updated parent > + __child = 2 * __child + 1; > + __child_i = __first + __child; > + > + if ((__child + 1) < __len && __comp(*__child_i, *(__child_i + 1))) { > + // right-child exists and is greater than left-child > + ++__child_i; > + ++__child; > + } > + > + // check if we are in heap-order > + } while (!__comp(*__child_i, __top)); > + *__start = _VSTD::move(__top); > +} > + > +template <class _Compare, class _RandomAccessIterator> > inline _LIBCPP_INLINE_VISIBILITY > void > __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, > _Compare __comp, > @@ -4895,7 +4908,7 @@ __pop_heap(_RandomAccessIterator __first > if (__len > 1) > { > swap(*__first, *--__last); > - __push_heap_front<_Compare>(__first, __last, __comp, __len-1); > + __sift_down<_Compare>(__first, __last, __comp, __len - 1, __first); > } > } > > @@ -4932,10 +4945,11 @@ __make_heap(_RandomAccessIterator __firs > difference_type __n = __last - __first; > if (__n > 1) > { > - __last = __first; > - ++__last; > - for (difference_type __i = 1; __i < __n;) > - __push_heap_back<_Compare>(__first, ++__last, __comp, ++__i); > + // start from the first parent, there is no need to consider children > + for (difference_type __start = (__n - 2) / 2; __start >= 0; > --__start) > + { > + __sift_down<_Compare>(__first, __last, __comp, __n, __first + > __start); > + } > } > } > > @@ -5010,7 +5024,7 @@ __partial_sort(_RandomAccessIterator __f > if (__comp(*__i, *__first)) > { > swap(*__i, *__first); > - __push_heap_front<_Compare>(__first, __middle, __comp, __len); > + __sift_down<_Compare>(__first, __middle, __comp, __len, __first); > } > } > __sort_heap<_Compare>(__first, __middle, __comp); > @@ -5051,15 +5065,15 @@ __partial_sort_copy(_InputIterator __fir > _RandomAccessIterator __r = __result_first; > if (__r != __result_last) > { > - typename iterator_traits<_RandomAccessIterator>::difference_type > __len = 0; > - for (; __first != __last && __r != __result_last; ++__first, ++__r, > ++__len) > + for (; __first != __last && __r != __result_last; ++__first, ++__r) > *__r = *__first; > __make_heap<_Compare>(__result_first, __r, __comp); > + typename iterator_traits<_RandomAccessIterator>::difference_type > __len = __r - __result_first; > for (; __first != __last; ++__first) > if (__comp(*__first, *__result_first)) > { > *__result_first = *__first; > - __push_heap_front<_Compare>(__result_first, __r, __comp, > __len); > + __sift_down<_Compare>(__result_first, __r, __comp, __len, > __result_first); > } > __sort_heap<_Compare>(__result_first, __r, __comp); > } > > Modified: > libcxx/trunk/test/algorithms/alg.sorting/alg.heap.operations/make.heap/make_heap_comp.pass.cpp > URL: > http://llvm.org/viewvc/llvm-project/libcxx/trunk/test/algorithms/alg.sorting/alg.heap.operations/make.heap/make_heap_comp.pass.cpp?rev=213615&r1=213614&r2=213615&view=diff > ============================================================================== > --- > libcxx/trunk/test/algorithms/alg.sorting/alg.heap.operations/make.heap/make_heap_comp.pass.cpp > (original) > +++ > libcxx/trunk/test/algorithms/alg.sorting/alg.heap.operations/make.heap/make_heap_comp.pass.cpp > Tue Jul 22 01:07:09 2014 > @@ -35,14 +35,35 @@ struct indirect_less > void test(unsigned N) > { > int* ia = new int [N]; > + { > for (int i = 0; i < N; ++i) > ia[i] = i; > - { > std::random_shuffle(ia, ia+N); > std::make_heap(ia, ia+N, std::greater<int>()); > assert(std::is_heap(ia, ia+N, std::greater<int>())); > } > > +// Ascending > + { > + binary_counting_predicate<std::greater<int>, int, int> pred > ((std::greater<int>())); > + for (int i = 0; i < N; ++i) > + ia[i] = i; > + std::make_heap(ia, ia+N, std::ref(pred)); > + assert(pred.count() <= 3*N); > + assert(std::is_heap(ia, ia+N, pred)); > + } > + > +// Descending > + { > + binary_counting_predicate<std::greater<int>, int, int> pred > ((std::greater<int>())); > + for (int i = 0; i < N; ++i) > + ia[N-1-i] = i; > + std::make_heap(ia, ia+N, std::ref(pred)); > + assert(pred.count() <= 3*N); > + assert(std::is_heap(ia, ia+N, pred)); > + } > + > +// Random > { > binary_counting_predicate<std::greater<int>, int, int> pred > ((std::greater<int>())); > std::random_shuffle(ia, ia+N); > > > _______________________________________________ > cfe-commits mailing list > [email protected] > http://lists.cs.uiuc.edu/mailman/listinfo/cfe-commits >
_______________________________________________ cfe-commits mailing list [email protected] http://lists.cs.uiuc.edu/mailman/listinfo/cfe-commits
