Fastest list/vector/queue ?
Author
I am currently coding in C++ and I need some storage solution (list/vector/queue ... etc) that can do :
-inserts values at random locations
-read values at random locations
-pop of the first or last values
Preferably, if I could do any of these operations in O(1), I would be glad.
Anybody has a guess ?
A list is better for inserting at random locations
A vector is better for accessing random locations
When you insert and delete from a vector, it has to copy every element of the vector and reposition it. So its not that effecient to do that.
A list is maintained as pointers, it is not contiguous in memory. If you insert randomly into a list all it has to do is change a few pointers.
To access data in a list it has to traverse to that location.
To access data in a vector is instant because that element is a fixed offset from the beginning of the vector.
A vector is better for accessing random locations
When you insert and delete from a vector, it has to copy every element of the vector and reposition it. So its not that effecient to do that.
A list is maintained as pointers, it is not contiguous in memory. If you insert randomly into a list all it has to do is change a few pointers.
To access data in a list it has to traverse to that location.
To access data in a vector is instant because that element is a fixed offset from the beginning of the vector.
Author
double queued list is only a list that's bidirectionnal ... how is it going to help me to do random reads and random inserts ?
list & double chained list :
<edit>a read = O(n)</edit>
an insert = O(log(n)) + rebalancing of the tree (cause a list with STL is a tree).
a vector :
a read = O(1)
an insert = O(n) + A LOT of memory changes
list & double chained list :
<edit>a read = O(n)</edit>
an insert = O(log(n)) + rebalancing of the tree (cause a list with STL is a tree).
a vector :
a read = O(1)
an insert = O(n) + A LOT of memory changes
Author
I was looking for some type of storage or maybe some type of combination of storages that could give me the best performance for ALL the operations.
BUT ... in case no one has a better idea, here is an approximate ratio of the type of operations I can do on my storage (wich can contain up to ~10,000 values)
-reads = 90% of the operations (binary search)
-insert = 3%
-pop front = 7%
keep in mind that even if the 3% is very small, moving 10,000 values in the ram is very long ... and thus, the vector is probably the worst solution.
In 1st position, I'm guessing that the list would be the champion ?
BUT ... in case no one has a better idea, here is an approximate ratio of the type of operations I can do on my storage (wich can contain up to ~10,000 values)
-reads = 90% of the operations (binary search)
-insert = 3%
-pop front = 7%
keep in mind that even if the 3% is very small, moving 10,000 values in the ram is very long ... and thus, the vector is probably the worst solution.
In 1st position, I'm guessing that the list would be the champion ?
-inserts values at random locations
-read values at random locations
-pop of the first or last values
deque will require O(n) to insert at random locations, as will vector. deque is really about order n/2 because it shifts up or down depending on which is closer.
reading values at random locations: meaning you have an index number? list will be slow at this because you need to iterate through it. vector and deque are O(1).
pop off first or last: deque does this in O(1), vector would be O(n) for popping off the front.
I recommend a deque. It isn't as simple as a list that has pointers for going forward and backward.
deque info
-read values at random locations
-pop of the first or last values
deque will require O(n) to insert at random locations, as will vector. deque is really about order n/2 because it shifts up or down depending on which is closer.
reading values at random locations: meaning you have an index number? list will be slow at this because you need to iterate through it. vector and deque are O(1).
pop off first or last: deque does this in O(1), vector would be O(n) for popping off the front.
I recommend a deque. It isn't as simple as a list that has pointers for going forward and backward.
deque info
Author
nprz
Quote:reading values at random locations: meaning you have an index number? list will be slow at this because you need to iterate through it. vector and deque are O(1).
Hmmm ... that's very interesting ... how can deque be O(1) for random read ?
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
