Hello!
For those who aren't familar BTW, the "search_n" STL function takes two
iterators, a "count" value and and either a "value" or a "value" and a
binary predicate and searches between the iterators for the first
occurance of "count" values which are all equal "value" (with respect to
the binary predicate if given, == if not).
In my STL manual, the complexity of search_n is given as O(dist.count)
where dist is the distance between the two given iterators. It is
however I would think easy to implement search_n in O(dist), and also
with the further condition it will dereference each iterator at most once.
Furthermore, while it is not possible to get a better worse-case
complexity where the iterators are random-access iterators it is
possible to get average case O(dist/count) in many cases.
Is there some reason the basic complexity is so bad, might be improved
in a future revision, and is there any chance of a more optimised
version for random access operators? (or would such a design decision be
down to implementors?)
Thank you,
Chris 4 1440
Chris Jefferson wrote: Hello!
For those who aren't familar BTW, the "search_n" STL function takes two iterators, a "count" value and and either a "value" or a "value" and a binary predicate and searches between the iterators for the first occurance of "count" values which are all equal "value" (with respect to the binary predicate if given, == if not).
In my STL manual, the complexity of search_n is given as O(dist.count) where dist is the distance between the two given iterators. It is however I would think easy to implement search_n in O(dist), and also with the further condition it will dereference each iterator at most once.
Furthermore, while it is not possible to get a better worse-case complexity where the iterators are random-access iterators it is possible to get average case O(dist/count) in many cases.
Is there some reason the basic complexity is so bad, might be improved in a future revision, and is there any chance of a more optimised version for random access operators? (or would such a design decision be down to implementors?)
Thank you,
Chris
I do not think that there is any good reason for the standard
to be so far off. From the description of the SGI's reference
implementation ( http://www.sgi.com/tech/stl/search_n.html):
Complexity
Linear. Search_n performs at most last - first comparisons.
(The C++ standard permits the complexity to be O(n (last - first)),
but this is unnecessarily lax. There is no reason for search_n to
examine any element more than once.)
So, chances are that the library you are using already provides linear
complexity.
As for your last question, the standard, as far as I can tell, does not go
into specifying average case complexities. So I gather the average case
will be up to the implentation.
Kai-Uwe Bux
"Chris Jefferson" <ca*@cs.york.ac.uk> wrote in message
news:cf*********@pump1.york.ac.uk... Hello!
For those who aren't familar BTW, the "search_n" STL function takes two iterators, a "count" value and and either a "value" or a "value" and a binary predicate and searches between the iterators for the first occurance of "count" values which are all equal "value" (with respect to the binary predicate if given, == if not).
In my STL manual, the complexity of search_n is given as O(dist.count) where dist is the distance between the two given iterators. It is however I would think easy to implement search_n in O(dist), and also with the further condition it will dereference each iterator at most once.
Furthermore, while it is not possible to get a better worse-case complexity where the iterators are random-access iterators it is possible to get average case O(dist/count) in many cases.
Is there some reason the basic complexity is so bad, might be improved in a future revision, and is there any chance of a more optimised version for random access operators? (or would such a design decision be down to implementors?)
Thank you,
Chris
Have a look at this, it seems relevant. http://www.codeproject.com/vcpp/stl/SearchN.asp
john
Kai-Uwe Bux wrote: Chris Jefferson wrote:
Hello!
For those who aren't familar BTW, the "search_n" STL function takes two iterators, a "count" value and and either a "value" or a "value" and a binary predicate and searches between the iterators for the first occurance of "count" values which are all equal "value" (with respect to the binary predicate if given, == if not).
In my STL manual, the complexity of search_n is given as O(dist.count) where dist is the distance between the two given iterators. It is however I would think easy to implement search_n in O(dist), and also with the further condition it will dereference each iterator at most once.
Furthermore, while it is not possible to get a better worse-case complexity where the iterators are random-access iterators it is possible to get average case O(dist/count) in many cases.
Is there some reason the basic complexity is so bad, might be improved in a future revision, and is there any chance of a more optimised version for random access operators? (or would such a design decision be down to implementors?)
Thank you,
Chris
I do not think that there is any good reason for the standard to be so far off. From the description of the SGI's reference implementation (http://www.sgi.com/tech/stl/search_n.html):
Complexity Linear. Search_n performs at most last - first comparisons.
(The C++ standard permits the complexity to be O(n (last - first)), but this is unnecessarily lax. There is no reason for search_n to examine any element more than once.)
So, chances are that the library you are using already provides linear complexity.
As for your last question, the standard, as far as I can tell, does not go into specifying average case complexities. So I gather the average case will be up to the implentation.
Thank you :)
One extra quick related (at least to me) question :)
Is there any way to have a templated function which takes as input two
foward iterators, and then have a specialised version which takes random
access iterators?
Thanks,
Chris
On Mon, 09 Aug 2004 13:47:34 +0100, Chris Jefferson
<ca*@cs.york.ac.uk> wrote: One extra quick related (at least to me) question :)
Is there any way to have a templated function which takes as input two foward iterators, and then have a specialised version which takes random access iterators?
This is the usual way:
template <class RanIt>
void f(RanIt beg, RanIt end, std::random_access_iterator_tag);
template <class FwdIt>
void f(FwdIt beg, FwdIt end, std::forward_iterator_tag);
template <class It>
void f(It beg, It end)
{
typedef typename
std::iterator_traits<It>::iterator_category category;
f(beg, end, category());
}
Many variations are possible of course.
Tom This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics
by: Stephan Diehl |
last post by:
A while ago, I've posted a recipie about finding a common prefix to a list
of strings. While the recipie itself is quite bad (I have to admit) and I
didn't know at that time that this problem was...
|
by: Ayende Rahien |
last post by:
<rant warning="I'm pissed off and have to vent" request="need help>
For the last couple of hours I'm struggling with a very *annoying* problem.
How to check if a user has a write access to a file?...
|
by: Matt |
last post by:
How do we define systems programs? when we say systems programming,
does it necessary mean that the programs we write need to interact
with hardware directly? For example, OS, compiler, kernel,...
|
by: ma740988 |
last post by:
There's a need for me to move around at specified offsets within
memory. As as a result - long story short - unsigned char* is the type
of choice.
At issue: Consider the case ( test code ) where...
|
by: ma740988 |
last post by:
I've been perusing for some time now - I suppose some of the algorithms
in Josuttis. 'Today', I do alot of funny math on data resident within
memory. As part of this. I find myself using...
|
by: paulc05 |
last post by:
Hi,
I have a DB on a remote share that I want to update to a local DB
periodically. My plan is to create a VBA procedure and then trigger the
procedure a few times a day to the process is...
|
by: cesco |
last post by:
Hi,
say I have a vector like the following:
vec =
and I'd like to know via a function (for example,
ConsecutiveIntegers(vec, N)) whether there are N consecutive integers.
So, for example,...
|
by: CloudSolutions |
last post by:
Introduction:
For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
|
by: Faith0G |
last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...
|
by: isladogs |
last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM).
In this session, we are pleased to welcome former...
|
by: ryjfgjl |
last post by:
In our work, we often need to import Excel data into databases (such as MySQL, SQL Server, Oracle) for data analysis and processing. Usually, we use database tools like Navicat or the Excel import...
|
by: taylorcarr |
last post by:
A Canon printer is a smart device known for being advanced, efficient, and reliable. It is designed for home, office, and hybrid workspace use and can also be used for a variety of purposes. However,...
|
by: Charles Arthur |
last post by:
How do i turn on java script on a villaon, callus and itel keypad mobile phone
|
by: aa123db |
last post by:
Variable and constants
Use var or let for variables and const fror constants.
Var foo ='bar';
Let foo ='bar';const baz ='bar';
Functions
function $name$ ($parameters$) {
}
...
|
by: nemocccc |
last post by:
hello, everyone, I want to develop a software for my android phone for daily needs, any suggestions?
|
by: Sonnysonu |
last post by:
This is the data of csv file
1 2 3
1 2 3
1 2 3
1 2 3
2 3
2 3
3
the lengths should be different i have to store the data by column-wise with in the specific length.
suppose the i have to...
| |