Re: set find
Roman.Perepelitsa@gmail.com <Roman.Perepelitsa@gmail.com> wrote:
In article <1185362774.896921.277...@o61g2000hsh.googlegroups.com>,
<"Roman.Perepeli...@gmail.com"> wrote:
// complexity is O(log(e1 - b1) * (e2 - b2))
template <class RA1, class RA2, class Out>
void log_intersection(RA1 b1, RA1 e1,
RA2 b2, RA2 e2, Out out)
{
for (; b2 != e2; ++b2)
if (binary_search(b1, e1, *b2))
*out++ = *b2;
}
what makes you think that this is faster std::set_intersection?
its slower!! set_intersection be faster since log2(N1) > 1.
std::set_intersection complexity is O(N1 + N2). Complexity of
log_intersection is log(N1) * N2. If N2 < N1 / (log(N1) - 1) then
log_intersection is faster. It is the case when N2 is very small,
and N1 is very large.
Roman Perepelitsa.
OK mis read the standard. You might try using lower_bound to
move both iterators as your binary_search does not shorten searches
as the loop progresses, and will not provide the same result as
std::set_intersection if there are duplicate entries in both sequences
of some equivalent items.
Something like this tested code that counts the compares of the
data, and works with forward iterators.
test::lower_bound not shown since it from compilers <algorithm>
but counts the compares to the value passed in count.
take your <algorithm> copy lower_bound(For,For,T) into namespace test.
and a long &count parameter and place a ++count just before the
compare to value in lower_bound. That is what test::lower_bound is.
#include <iterator>
namespace test
{
template <class For,class T>
For lower_bound(For begin,For end,const T &value,long &count)
{
// wee above.
}
template <class For1,class For2,class Out>
Out fast_intersection(For1 b1,For1 e1,For2 b2,For2 e2,Out
out,long &count)
{
if(b1==e1 || b2==e2) return out;
for(;;)
{
b2 = lower_bound(b2,e2,*b1,count);
/*
b2 no points to first in [b2,e2) >= *b1
*b1 <= *b2 unlees alll are < *b1
in fact all in [original b2,b2) are < *b1.
*
*/
// everything left is < *b1 = min_element(b1,e1)
// so none left exit loop
if(b2==e2) break;
++count;
// *b2 > = *b1 therefore if(*b1 < *b2) no
match.
if(*b1< *b2)
{
b1=lower_bound(++b1,e1,*b2,count);
if(b1 == e1) break;
}
// a match;
*out = *b1;
++out;
++b1;
if(b1 == e1) break;
++b2;
if(b2==e2) break;
}
return out;
}
}
with a sorted vector of 100 of each of 1 to 10 for large set and
3 dach of 4,6,9 for the small set. 1000/9 is size ratio,
complexity largest first 62 compares to value
complexity with smallest first 92 compares to value
note all though the large set is over 100 times the size of the small
set the comare count is less than 100 but have not found
worst case. It is faster than std::set_intersection since
the first 9 is 801-th entry in lhe large set.
not too bad even if the first set is smallest.
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]