search

allendaicool / thrust

Automatically exported from code.google.com/p/thrust
Apache License 2.0
0 stars 0 forks source link

implement binary search functions #2

Closed GoogleCodeExporter closed 9 years ago

GoogleCodeExporter commented 9 years ago 
Thrust needs implementations of 
  * lower_bound
  * upper_bound
  * binary_search

In addition to the standard STL versions of these functions that perform a
single query we require vectorized versions that perform many queries.  Fo
example, the prototype for lower_bound should be:

template <class ForwardIterator, class InputIterator, class OutputIterator>
OutputIterator lower_bound(ForwardIterator begin, ForwardIterator end,
                InputIterator queries_begin, InputIterator queries_end,
                ResultIterator output_begin);

The returned OutputIterator is the end of the output range, which is usually:
  output_begin + distance(queries_begin, queries_end)
However, like transform(), it is necessary to return it since an
OutputIterator can't be advanced arbitrarily.

Original issue reported on code.google.com by wnbell on 2 Jun 2009 at 6:22

GoogleCodeExporter commented 9 years ago 
[deleted comment]
GoogleCodeExporter commented 9 years ago 
First draft committed in r151

The current device implementation assumes that OutputIterator has integral 
type.  The
implementation does not exploit shared memory to cache the frequently accessed 
range
elements.

For completeness a scalar version of equal_range() was added.  It's not clear 
that we
want/need a vector version.

doxygen documentation still needs to be written for binary_search.h

Original comment by wnbell on 11 Jun 2009 at 2:39

GoogleCodeExporter commented 9 years ago 
[deleted comment]
GoogleCodeExporter commented 9 years ago 
I've needed a vectorized version of equal_range in at least a couple of unique 
instances.

Here are two interfaces we could provide (we could provide one or both):

template<typename ForwardIterator, typename InputIterator, typename 
OutputIterator>
OutputIterator equal_range(ForwardIterator begin, ForwardIterator end,
                           InputIterator queries_begin, InputIterator queries_end,
                           OutputIterator result);

OutputIterator's value_type is assignable from pair

template<typename ForwardIterator,
         typename InputIterator,
         typename OutputIterator1,
         typename OutputIterator2>
pair<OutputIterator1, OutputIterator2>
equal_range(ForwardIterator begin, ForwardIterator end,
            InputIterator queries_begin, InputIterator queries_end,
            OutputIterator1 lower_bound_begin,
            OutputIterator2 upper_bound_begin);

You could build the 2nd version with the first plus zip_iterator.

Original comment by jaredhoberock on 19 Aug 2009 at 6:42

GoogleCodeExporter commented 9 years ago 
r403 mostly implements the desired functionality.  Let's revisit the remaining 
items
in Milestone-Release1.2

Original comment by wnbell on 30 Aug 2009 at 7:50

GoogleCodeExporter commented 9 years ago 
bumping to Milestone-Release1.x

Original comment by wnbell on 24 Jan 2010 at 3:47

GoogleCodeExporter commented 9 years ago 
If we need additional algorithms, we can file issues for them separately

Original comment by jaredhoberock on 7 May 2012 at 9:41