In article <44***********************@dread15.news.tele.dk> ,
"Henrik Goldman" <he************@mail.tele.dk> wrote:
I'm not quite sure you are asking for but I'm going to assume that
lower_bound, upper_bound, and equal_range won't work.
Yes I'm sorry about beeing unclear. It's very easy to be quite unclear when
you do something quite technical and have been sitting with it for a while.
I think lower_bound might solve my problem though.
The basic idea is that I do statistics at specific intervals e.g. every 10
min. The gathered values are stored as 'second' for the specific time_t.
This way I can go through each record and see at what time it was gathered.
Here is the original (slow!) algorithm:
int CStatistics::GetMaxValueInPeriod(time_t tFrom, time_t tTo)
{
UseMap::iterator it;
int nMaxValue = 0;
for (it = m_pUseMap->begin();
it != m_pUseMap->end();
it++)
{
if (it->first < tFrom)
continue;
if (it->first > tTo)
break;
if (nMaxValue < it->second.m_nTotalFoo)
nMaxValue = it->second.m_m_nTotalFoo;
}
return nMaxValue;
}
Assume it contains values from since 2 years ago which is the worst case
scenario for me.
Then in order to find the first values which fits in my range I scan forward
by omitting all values which were earlier then the time I want.
This takes a lot of time even for a few values. Can lower_bound help me?
bool comp( const UseMap::value_type& lhs, const UseMap::value_type& rhs )
{
return lhs.second.m_m_nTotalFoo < rhs.second.m_m_nTotalFoo;
}
int CStatistics::GetMaxValueInPeriod( time_t tFrom, time_t tTo )
{
assert( tFrom <= tTo );
UseMap::iterator begin = m_pUseMap->lower_bound( tFrom );
UseMap::iterator end = m_pUseMap->upper_bound( tTo );
if ( begin == end )
throw runtime_error( "no such period" );
return max_element( begin, end, &comp )->second.m_m_nTotalFoo;
}
I think you will find something like the above much faster. Of course
I'm guessing as to some of the types because you didn't give compilable
code.
Depending on how many elements are in the map, and how big the range is:
int CStatistics::GetMaxValueInPeriod( time_t tFrom, time_t tTo )
{
assert( tFrom <= tTo );
UseMap::iterator begin = m_pUseMap->lower_bound( tFrom );
UseMap::iterator end = begin;
while ( end->first < tTo )
++end;
if ( begin == end )
throw runtime_error( "no such period" );
return max_element( begin, end, &comp )->second.m_m_nTotalFoo;
}
Might be faster, you'll have to measure the two and see which is better
for you.
Finally there is:
int CStatistics::GetMaxValueInPeriod( time_t tFrom, time_t tTo )
{
assert( tFrom <= tTo );
UseMap::iterator begin = m_pUseMap->lower_bound( tFrom );
if ( begin->first < tTo )
throw runtime_error( "no such period" );
int result = begin->second.m_m_nTotalFoo;
++begin;
while ( begin->first < tTo ) {
if ( begin->second.m_m_nTotalFoo > result )
result = begin->second.m_m_nTotalFoo;
++begin;
}
return result;
}
Which is a little harder to read, but may be a hair faster than the
second example.
--
Magic depends on tradition and belief. It does not welcome observation,
nor does it profit by experiment. On the other hand, science is based
on experience; it is open to correction by observation and experiment.