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 1455
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_acc ess_iterator_ta g);
template <class FwdIt>
void f(FwdIt beg, FwdIt end, std::forward_it erator_tag);
template <class It>
void f(It beg, It end)
{
typedef typename
std::iterator_t raits<It>::iter ator_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 solved already in the
os.path module.
The interesting part can be found in the commentaries, as this turned out to
be a quest for the most efficient algorithm to solve this particular
problem.
All of this can be found at...
|
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?
Considerring that .Net is supposed to be a system for writing applications
for servers & clients, which in both cases has may have multi-users, I'm
amazed that this is not possible in the framework.
Initially I looked for something like:
...
|
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, drivers,
network protocols, etc...? Couple years ago, yes, I understand this is
definitely true. However, as the software applications become more and
more complicated, some people try to argue that. Some people argue the
definition of systems...
|
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 I'm comparing two
structs. The struct test1 has information with regards to data_size
and pointer
to address. The struct test2 has information with regards to data_size
and value. I will compare test1 and test2. For each matching data
size,...
|
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 std::search_n alot to
find a particular value in a range of memory. I'm fairly pleased with
std::search_n - in that my benchmark ( below ) shows on average an 8
second performance gain comparable to a for loop. The question.
Since I haven't quite...
| |
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 automated. My question is
how do I copy the contents of a Record set to a Table. This is what I
have so far:
Sub ImportDecap()
|
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, if N=3 then ConsecutiveIntegers(vec, N) should return
true because 1, 2, 3 and 5, 6, 7 are consecutive. If N=4, then
|
by: marktang |
last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look !
Part I. Meaning of...
|
by: Hystou |
last post by:
Overview:
Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
|
by: tracyyun |
last post by:
Dear forum friends,
With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the choice of these technologies. I'm particularly interested in Zigbee because I've heard it does some...
|
by: agi2029 |
last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own....
Now, this would greatly impact the work of software developers. The idea...
| |
by: isladogs |
last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 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 a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules.
He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms.
Adolph will...
|
by: conductexam |
last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one.
At the time of converting from word file to html my equations which are in the word document file was convert into image.
Globals.ThisAddIn.Application.ActiveDocument.Select();...
|
by: TSSRALBI |
last post by:
Hello
I'm a network technician in training and I need your help.
I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs.
The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols.
I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...
|
by: muto222 |
last post by:
How can i add a mobile payment intergratation into php mysql website.
|
by: bsmnconsultancy |
last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating effective websites that not only look great but also perform exceptionally well. In this comprehensive...
| |