Re: factor 50.000 between std::list and std::set?
On Jun 25, 3:51 pm, desktop <f...@sss.com> wrote:
Erik Wikstr=F6m wrote:
On 2007-06-25 22:21, desktop wrote:
If I have a sorted std::list with 1.000.000 elements it takes
1.000.000 operations to find element with value = 1.000.000 (need to
iterator through the whole list).
In comparison, if I have a std::set with 1.000.000 element it will
only take approx lg 1.000.000 = 20 operations! Can it really be true
that the difference is a factor of 1.000.000/20 = 50.000 in this cas=
e?
In operations yes, not necessarily in time. If the operations on the
list takes 1 time and the operations on the set takes 50,000 then
they'll be equally fast. This will of course not be true in any
implementation (the set will be significantly faster than the list) but
it shows that just because one container/algorithm has a better
asymptotic running time it will in fact perform better. All it says is
that for a sufficiently large set of input, the algorithm will perform
better.
In practice you'll often find that using a vector for small sets will be
faster than most other containers, even if you need to traverse the
whole vector.
Is it possible to make an exact measurement in the difference in time
for 1 operation for a set and a list?- Hide quoted text -
- Show quoted text -
sure, just write a benchmark test. There is no more precise way,
because of course the time depends on your CPU, your compiler, your
operating system, and what appliactions are running at the time. A
simple test like the following should work (on windows).
std::vector<int> intVector;
populateIntVector(&intVector);
std::set<int> intSet;
populateIntSet(&intSet);
DWORD d = timeGetTime();
for (int i=0; i < 1000000; ++i)
{
// Perform Vector operation
}
DWORD d2 = timeGetTime();
for (int i=0; i < 1000000; ++i)
{
// Perform set operation
}
DWORD d3 = timeGetTime();
DWORD millisecondsForVector = d2 - d;
DWORD millisecondsForSet = d3 - d2;
double millisecondsForSingleVectorOp = (double)millisecondsForVector /
(double)1000000;
double millisecondsForSingleSetOp = (double)millisecondsForSet /
(double)1000000;