Map performance
Kaba
What are the requirements the standard places on the asymptotic
behaviour of the std::map container?
>From Wikipedia:
http://en.wikipedia.org/wiki/Map_%28C%2B%2B_container%29
The article claims O(n log n) for copying and O(log n) for iterator
increment/decrement. It also claims O(n) for visiting all elements, but
this contradicts the iterator increment/decrement behaviour.
However, a common implementation using a red-black tree achieves
amortized constant time for increment/decrementing an iterator.
Similarly, copying takes O(n).
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
Greg Herlihy
> What are the requirements the standard places on the asymptotic
> behaviour of the std::map container?
>
> >From Wikipedia:
>
> http://en.wikipedia.org/wiki/Map_%28C%2B%2B_container%29
>
> The article claims O(n log n) for copying and O(log n) for iterator
> increment/decrement. It also claims O(n) for visiting all elements, but
> this contradicts the iterator increment/decrement behaviour.
The O(log n) complexity for incrementing or decrementing a std::map
iterator is a worst-case complexity. Moreover, the worst case occurs
infrequently enough that iterating an entire map has only linear
complexity, or O(n).
> However, a common implementation using a red-black tree achieves
> amortized constant time for increment/decrementing an iterator.
> Similarly, copying takes O(n).
There is no contradiction here. Since iterating an entire map has O(n)
complexity, it stands to reason that incrementing or decrementing an
iterator has an (amortized) constant time complexity - even if, in the
worst case, the operation has a O(log n) complexity.
Copying a map to another map with the same sort order does have linear
complexity. Copying a map to to a map with a different sort order has
O(n log n) complexity.
Greg
--
Jerry Coffin
says...
> Hi,
>
> What are the requirements the standard places on the asymptotic
> behaviour of the std::map container?
Copying is N log(N) in general, but linear if the elements are sorted
(in the order expected by that map's comparison function).
Inserting an item is logarithmic in general, but amortized constant if
you use an accurate hint.
std::set uses BiDirectional iterators, which support incrementing and
decrementing functions.
"All the categories of iterators require only those functions that are
realizable for a given category in constant time (amortized)."
--
Later,
Jerry.
The universe is a figment of its own imagination.
Jiri Palecek
> However, a common implementation using a red-black tree achieves
> amortized constant time for increment/decrementing an iterator.
Not really, unless you maintain something like a linked list of node in the
tree in the order of their elements.
For example, imagine that you get an iterator to the root of the tree.
Clearly, incrementing the iterator takes log(N), and subsequent
decrementing too. So if you increment-decrement-increment-decrement... the
iterator, the time it'll take O(log N)*(number of rounds) which cannot be
paid by 2*(number of rounds) O(1) operations.
The O(1) amortised complexity for tree iterator increment only applies to
iterators that only move one direction.
Regards
Jiri Palecek
--
Juha Nieminen
> The article claims O(n log n) for copying and O(log n) for iterator
> increment/decrement. It also claims O(n) for visiting all elements, but
> this contradicts the iterator increment/decrement behaviour.
Actually it doesn't. O() denotes the *worst-case* scenario. In other
words, what is the worst possible amount of steps required to perform
the operation. It doesn't denote the average case. O(log n) does not
mean that if the operation is performed n times, the total amount of
operations will be O(n*log n) because it depends on how often the log n
behavior happens.
In this case, while the worst-case of an iterator increment is
O(log n), a traversal is O(n).
To understand why this is, think about two situations:
1) The iterator points to the largest element of the left sub-tree of
the root node. Incrementing this iterator will make it point to the
smallest element of the right sub-tree of the root node, thus requiring
approximately 2*log n steps. Thus the increment in this case required an
amount of operations proportional to log n.
2) However, traversing the tree from the smallest element to the largest
can be thought differently: Think about the amount of steps required at
each individual node. These steps are, roughly:
- Arrive at the node from the parent.
- Go to the left sub-tree.
- Arrive at the node from the left sub-tree.
- Go to the right sub-tree.
- Arrive at the node from the right sub-tree.
- Go to the parent.
Notice that this is a *fixed* amount of steps. It doesn't depend on
the amount of elements in the tree in any way. These steps are executed
for each node, ergo they are executed n times. Thus the total number of
steps needed to traverse the entire tree is, roughly, something like
6*n, which is O(n).
And this still even though one individual iterator increment may
require 2*log n steps.
--
Stuart Golodetz
news:4791ec38$0$15003$4f79...@news.tdc.fi...
> Kaba wrote:
>> The article claims O(n log n) for copying and O(log n) for iterator
>> increment/decrement. It also claims O(n) for visiting all elements, but
>> this contradicts the iterator increment/decrement behaviour.
>
> Actually it doesn't. O() denotes the *worst-case* scenario. In other
> words, what is the worst possible amount of steps required to perform
> the operation. It doesn't denote the average case. O(log n) does not
> mean that if the operation is performed n times, the total amount of
> operations will be O(n*log n) because it depends on how often the log n
> behavior happens.
Just a minor nitpick (sorry): I know what you mean, but actually if
something is O(log n) and is performed n times, the total cost will be O(n
log n). The fact that it may also be O(n) doesn't matter since Big-O
notation is an upper bound.
Cheers,
Stu
<snip>
Kaba
Thanks for the replies.
I gather the requirements are (all worst cases):
Searching for an element: O(log n)
Insertion: O(log n) (with correct hint O(1))
Iterator increment/decrement: O(log n)
Iterating _unidirectionally_ over all elements: O(n)
Removing an element: O(log n)
Copying: O(n log n)
These are almost the same as given by the Wikipedia article.
Quoting a quote by Jerry Coffin:
"All the categories of iterators require only those functions that are
realizable for a given category in constant time (amortized)."
Jiri mentions that by combining iterator increments and decrements in a
suitable manner you get O(log n) worst case. It raises an interesting
question whether the performances should be given isolated from other
functionalities (e.g. iterator incrementation separate from
decrementation) or by taking them into account. The quote by Jerry
Coffin seems to indicate that the standard chooses the former way.
I think the Wikipedia article could benefit from mentioning that the
linear time for the unidirectional traversal is because of amortization.
Jiri Palecek
Just few notes
Kaba wrote:
> Thanks for the replies.
You're welcome.
> I gather the requirements are (all worst cases):
>
> Searching for an element: O(log n)
> Insertion: O(log n) (with correct hint O(1))
That O(1) is amortised complexity, the worst case is still O(log N)
> Iterator increment/decrement: O(log n)
> Iterating _unidirectionally_ over all elements: O(n)
This can be even strengthened in the way you needn't iterate over all
elements. Depending on how you do the analysis, you can say eg. that
in/decrementing an iterator is O(log N), except if you move in the same
direction as the last move, when it would be O(1). Everything amortised
complexity.
> Removing an element: O(log n)
> Copying: O(n log n)
>
> These are almost the same as given by the Wikipedia article.
>
> Quoting a quote by Jerry Coffin:
> "All the categories of iterators require only those functions that are
> realizable for a given category in constant time (amortized)."
>
> Jiri mentions that by combining iterator increments and decrements in a
> suitable manner you get O(log n) worst case. It raises an interesting
> question whether the performances should be given isolated from other
> functionalities (e.g. iterator incrementation separate from
> decrementation) or by taking them into account. The quote by Jerry
> Coffin seems to indicate that the standard chooses the former way.
Well, it doesn't make much sense to do that with amortised complexity,
because the point of amortised complexity is that cheap operations
contribute part of their time to the expensive ones, but
this "contributing" should work in any execution of the program. However,
there are some things to consider
- I (and hopefully the others too) was talking only about one
implementation, the RB-tree without any other helper structure of any kind.
I don't know whether this is the implementation you'll find in compiler's
libraries. There are ways to implement maps which have O(1) worst-case
iterator increment/decrement, but don't know about such implementation
(probably, a hash_map would do in this regard).
- Specifying iterator increment/decrement complexity in the iterator
concept is a tricky thing, since there are many cases where the complexity
guarantee simply can't be fulfilled and yet you want to call the
beast "iterator". For example, boost::filter_iterator (which returns only
elements that satisfy a given predicate) can't give any guarantee on
increment if it has to skip an unbounded number of elements that don't
satisfy the predicate. boost::function_output_iterator's increment
complexity is trivially lower-bounded by complexity of the function it
calls. std::istream_iterator<int> also cannot fulfil the constant
complexity guarantee, because if you have an expression *it++ and there is
something like
000000000000000000000000...more zeros...0000000001
in the input, the time spent on that expression is proportional to the
number of zeros which cannot be bounded by anything sensible, never a
constant.
Regards
Jiri Palecek
--
Jerry Coffin
[ ... ]
> - I (and hopefully the others too) was talking only about one
> implementation, the RB-tree without any other helper structure of any kind.
> I don't know whether this is the implementation you'll find in compiler's
> libraries. There are ways to implement maps which have O(1) worst-case
> iterator increment/decrement, but don't know about such implementation
> (probably, a hash_map would do in this regard).
A hash map makes O(K) increment/decrement easy -- but doesn't produce
the output in any meaningful order.
A threaded tree makes it trivial for a map to support O(K) increment and
decrement on iterators as well, though this does add a small constant to
insertions and deletions (time taken to update the threading pointers).
Most of what I mentioned wasn't really specific to a particular
implementation though -- it was the requirements from the standard that
apply regardless of the implementation.
--
Later,
Jerry.
The universe is a figment of its own imagination.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]