2

I use Windows and Visual Studio 2015. As far as I can see from references and others' questions, priority_queue::push() should have O(log(n)) time complexity. This means of course that this simple code:

#include <queue>
using namespace std;
int main()
{
    priority_queue<int> q;
    const int n=100000; //We can vary this
    for (int i = 0; i < n; i++)
    {
        q.push(i);
    }
}

should have complexity O(nlog(n)), which means for n=100 000 as above it should be piece of cake. It takes several minutes for me (the same thing with std::set takes just a second).

I have debugged this code and stopped it at multiples of 10 seconds, and plotted the squares of i for those times. They very (!) accurately lie on a line, which would mean the above code has complexity of O(n^2).

My question is, is not priority_queue::push() guaranteed to run in O(log(n)) or am I doing something very wrong?

Thanks in advance!

EDIT: I have tried the tip in this post. It didn't improve things, so I suppose reallocating the underlying container is not my issue.

EDIT: SOLVED As usual the answer is very simple. I had run the program in debug mode, which apparently changes the complexity of some functions. I was not aware of this, though I suppose it is quite reasonable...

Community
  • 1
  • 1
AlwaysMoving
  • 63
  • 1
  • 6
  • One thing you can try is randomizing the data you put in. I know some sorting algorithm implementations hit worst case performance scenarios if the data is already sorted and you might have hit something similar in this priority queue implementation. – Laserallan Jan 17 '16 at 19:55

2 Answers2

2

The answer is no, it is not guaranteed to run in O(log(n)) at all. That guarantee would be impossible to implement.

BartoszKP
  • 34,786
  • 15
  • 102
  • 130
Puppy
  • 144,682
  • 38
  • 256
  • 465
  • No, nlogn is for the *loop*, which runs N times. `push` needs to run at `log(n)` + complexity of `insert`, which is not the same thing. Then run that `N` times for the loop. So n^2 * log(n) for the whole loop. – Puppy Jan 17 '16 at 19:54
  • You're right, it's the contents of the container that counts. – BartoszKP Jan 17 '16 at 20:22
1

Several minutes for n=100000 seems like a very long time.

Are you by any chance testing in debug mode?

About complexity and performance:

From std::priority_queue:

Priority queues are a type of container adaptors, specifically designed such that its first element is always the greatest of the elements it contains

And:

By default, if no container class is specified for a particular priority_queue class instantiation, the standard container vector is used.

Which would mean that in a loop where i gets incremented, the new item needs to be inserted at the beginning of the vector, meaning that all other elements have to be shifted one - this for each iteration. Since all elements in vector are stored contiguously (while push_back is actually used to insert the items, push_heap is called to rearrange them).

Turning that around (using the default vector container) almost takes no time, even in debug mode.

From Are std::vector elements guaranteed to be contiguous?:

23.2.6 Class template vector [vector]

1 A vector is a sequence container that supports random access iterators. In addition, it supports (amortized) constant time insert and erase operations at the end; insert and erase in the middle take linear time. Storage management is handled automatically, though hints can be given to improve efficiency. The elements of a vector are stored contiguously, meaning that if v is a vector where T is some type other than bool, then it obeys the identity &v[n] == &v[0] + n for all 0 <= n < v.size().

A solution could be to specify a different container type:

template <class T, class Container = vector<T>

So, as for complexity of O(log(n)) for priority_queue::push(), it would be hard to guarantee that, since the underlying container type can differ, and each has it's own implementation for inserting/rearranging items. But O(log(n)) would be the best possible scenario.

But perhaps even more important is the time each operation takes, apart from the complexity factor.

EDIT (question): I have tried the tip in this post. It didn't improve things, so I suppose reallocating the underlying container is not my issue.

It's not so much about reallocating memory for storage of the elements (vector will do that in blocks anyway - although for larger containers preallocation is always desirable), but about inserting eacht element before the first one (if that is really the case, which seems to be so). Even if enough space is allocated, to insert an element in front in a vector, all other elements need to be moved exactly one element-size. It's that moving that takes time.

Community
  • 1
  • 1
Danny_ds
  • 11,201
  • 1
  • 24
  • 46
  • 1
    This doesn't really answer the question fully. – Puppy Jan 17 '16 at 19:31
  • I press "Local Windows Debugger" so I suppose that is in debug mode. But the same happens when I press ctrl+f5, which is a short-cut for some kind of non-debug version. Could this matter? I am aware that I might customize things to make them work out, but in that case std::set or std::multiset are much easier to use as substitutes. – AlwaysMoving Jan 17 '16 at 19:37
  • 1
    @AlwaysMoving - To test the speed, you should build in realease mode (but that might even optimize the whole loop away, so you might need to add some extra code). – Danny_ds Jan 17 '16 at 19:42
  • 1
    ***ctrl+f5, which is a short-cut for some kind of non-debug version*** No that runs the current configuration without the debugger but does not switch from running a Debug build to running a Release build. – drescherjm Jan 17 '16 at 19:46
  • @drescherjm Oh, you are absolutely right! This solved my issue. Thanks! – AlwaysMoving Jan 17 '16 at 19:53