Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > vector vs map iterator

Reply
Thread Tools

vector vs map iterator

 
 
xyz
Guest
Posts: n/a
 
      07-02-2008
I have to run the simulation of a trace file around (7gb contains
116million entries)...
presently i am using vector iterators to check the conditions in my
program.....
it is taking 2 days to finish whole simulation.....

my question are the map iterators are faster than vector
iterators.....
does it improve the performance....
thanks to all
 
Reply With Quote
 
 
 
 
AnonMail2005@gmail.com
Guest
Posts: n/a
 
      07-02-2008
On Jul 2, 9:31*am, xyz <(E-Mail Removed)> wrote:
> I have to run the simulation of a trace file around (7gb contains
> 116million entries)...
> presently i am using vector iterators to check the conditions in my
> program.....
> it is taking 2 days to finish whole simulation.....
>
> my question are the map iterators are faster than vector
> iterators.....
> does it improve the performance....
> thanks to all

Since a vector is guarenteed to be contiguous memory, it's iterator
*could* be implemented internally as a pointer - which is fast. A
map is list-like in that is has nodes so it's iterator would have
to dereference a pointer - which is slower. So, in very general
terms, I think maps iterators would be slower.

But...

Use a good profiler to determine which parts of your program are
time consuming. Without a profiler, you're just guessing.

HTH
 
Reply With Quote
 
 
 
 
Joe Greer
Guest
Posts: n/a
 
      07-02-2008
xyz <(E-Mail Removed)> wrote in news:fb7c6ce6-5af3-4e24-8a0b-
http://www.velocityreviews.com/forums/(E-Mail Removed):

> I have to run the simulation of a trace file around (7gb contains
> 116million entries)...
> presently i am using vector iterators to check the conditions in my
> program.....
> it is taking 2 days to finish whole simulation.....
>
> my question are the map iterators are faster than vector
> iterators.....
> does it improve the performance....
> thanks to all
>


I am not sure what operations you are performing on your iterators, but
vector iterators are about as fast as you get. Maps are generally a tree
structure of some sort and moving from one node to the next will generally
require loading a value from memory whereas with a vector, it will simply
add or subtract a fixed amount from the address already in the iterator.
This tends to be faster. Same thing applies to a list. Vectors also have
better locality of reference so when an item is read, the whole page comes
into memory and you get the objects surrounding the target for free. maps,
sets, lists etc are better if their semantics match what you want to do
better. That is, if you find yourself searching for objects a lot, then
maps and sets are more natural. Though even then, sorting the vector and
using the binary search algorithms may perform better. The other thing to
consider is that maps, sets, and lists have more overhead per object. With
116M objects, that can add up.

HTH,
joe
 
Reply With Quote
 
Joe Greer
Guest
Posts: n/a
 
      07-02-2008
Joe Greer <(E-Mail Removed)> wrote in
news:Xns9ACF63DE02FB0jgreerdoubletakecom@85.214.90 .236:

> xyz <(E-Mail Removed)> wrote in news:fb7c6ce6-5af3-4e24-8a0b-
> (E-Mail Removed):
>
>> I have to run the simulation of a trace file around (7gb contains
>> 116million entries)...
>> presently i am using vector iterators to check the conditions in my
>> program.....
>> it is taking 2 days to finish whole simulation.....
>>
>> my question are the map iterators are faster than vector
>> iterators.....
>> does it improve the performance....
>> thanks to all
>>

>
> I am not sure what operations you are performing on your iterators,
> but vector iterators are about as fast as you get. Maps are generally
> a tree structure of some sort and moving from one node to the next
> will generally require loading a value from memory whereas with a
> vector, it will simply add or subtract a fixed amount from the address
> already in the iterator. This tends to be faster. Same thing applies
> to a list. Vectors also have better locality of reference so when an
> item is read, the whole page comes into memory and you get the objects
> surrounding the target for free. maps, sets, lists etc are better if
> their semantics match what you want to do better. That is, if you
> find yourself searching for objects a lot, then maps and sets are more
> natural. Though even then, sorting the vector and using the binary
> search algorithms may perform better. The other thing to consider is
> that maps, sets, and lists have more overhead per object. With 116M
> objects, that can add up.
>
> HTH,
> joe
>


I also agree with the comment to use a profiler to be sure you are
optimizing the proper thing.

joe
 
Reply With Quote
 
xyz
Guest
Posts: n/a
 
      07-02-2008
On Jul 2, 3:49*pm, Joe Greer <(E-Mail Removed)> wrote:
> xyz <(E-Mail Removed)> wrote in news:fb7c6ce6-5af3-4e24-8a0b-
> (E-Mail Removed):
>
> > I have to run the simulation of a trace file around (7gb contains
> > 116million entries)...
> > presently i am using vector iterators to check the conditions in my
> > program.....
> > it is taking 2 days to finish whole simulation.....

>
> > my question are the map iterators are faster than vector
> > iterators.....
> > does it improve the performance....
> > thanks to all

>
> I am not sure what operations you are performing on your iterators, but
> vector iterators are about as fast as you get. *Maps are generally a tree
> structure of some sort and moving from one node to the next will generally
> require loading a value from memory whereas with a vector, it will simply
> add or subtract a fixed amount from the address already in the iterator. *
> This tends to be faster. *Same thing applies to a list. *Vectors also have
> better locality of reference so when an item is read, the whole page comes
> into memory and you get the objects surrounding the target for free. *maps,
> sets, lists etc are better if their semantics match what you want to do
> better. *That is, if you find yourself searching for objects a lot, then
> maps and sets are more natural. *Though even then, sorting the vector and
> using the binary search algorithms may perform better. *The other thing to
> consider is that maps, sets, and lists have more overhead per object. *With
> 116M objects, that can add up.
>
> HTH,
> joe


for example i am doing the operation as below in my program
whenever i receive a packet or something ...i will check does it
contain in my vector list....
so if I contain around 2 million entreis in my vector and i received
around 100 packets...
then the computation would be 100 packets * 2 million iterations...

as my list goes on incresing I will have more iterations..
this is the problem i am facing with my simulation..
 
Reply With Quote
 
xyz
Guest
Posts: n/a
 
      07-02-2008
On Jul 2, 3:50*pm, Joe Greer <(E-Mail Removed)> wrote:
> Joe Greer <(E-Mail Removed)> wrote innews:Xns9ACF63DE02FB0jgreerdoubletakecom@85.214. 90.236:
>
>
>
> > xyz <(E-Mail Removed)> wrote in news:fb7c6ce6-5af3-4e24-8a0b-
> > (E-Mail Removed):

>
> >> I have to run the simulation of a trace file around (7gb contains
> >> 116million entries)...
> >> presently i am using vector iterators to check the conditions in my
> >> program.....
> >> it is taking 2 days to finish whole simulation.....

>
> >> my question are the map iterators are faster than vector
> >> iterators.....
> >> does it improve the performance....
> >> thanks to all

>
> > I am not sure what operations you are performing on your iterators,
> > but vector iterators are about as fast as you get. *Maps are generally
> > a tree structure of some sort and moving from one node to the next
> > will generally require loading a value from memory whereas with a
> > vector, it will simply add or subtract a fixed amount from the address
> > already in the iterator. *This tends to be faster. *Same thing applies
> > to a list. *Vectors also have better locality of reference so when an
> > item is read, the whole page comes into memory and you get the objects
> > surrounding the target for free. *maps, sets, lists etc are better if
> > their semantics match what you want to do better. *That is, if you
> > find yourself searching for objects a lot, then maps and sets are more
> > natural. *Though even then, sorting the vector and using the binary
> > search algorithms may perform better. *The other thing to consider is
> > that maps, sets, and lists have more overhead per object. *With 116M
> > objects, that can add up.

>
> > HTH,
> > joe

>
> I also agree with the comment to use a profiler to be sure you are
> optimizing the proper thing.
>
> joe


I have already used the profiler to know the time consuming places in
my program....
I checked smaller protion of my 7gb file...which showed the time
consuming part is at what i mentioned
 
Reply With Quote
 
Juha Nieminen
Guest
Posts: n/a
 
      07-02-2008
xyz wrote:
> I have to run the simulation of a trace file around (7gb contains
> 116million entries)...
> presently i am using vector iterators to check the conditions in my
> program.....
> it is taking 2 days to finish whole simulation.....
>
> my question are the map iterators are faster than vector
> iterators.....
> does it improve the performance....


It's not a question of iterators. It's a question of what is it that
you are doing with your vector/map and how you are using those iterators.

(And no, when measured in clock cycles, no operation done to a map
iterator is faster than to a vector iterator. On the contrary. However,
I have the feeling you are not really talking about the iterators
per se.)
 
Reply With Quote
 
Jim Langston
Guest
Posts: n/a
 
      07-02-2008
"xyz" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...
>I have to run the simulation of a trace file around (7gb contains
> 116million entries)...
> presently i am using vector iterators to check the conditions in my
> program.....
> it is taking 2 days to finish whole simulation.....
>
> my question are the map iterators are faster than vector
> iterators.....
> does it improve the performance....
> thanks to all


Performance for what? Insertions? Deletions? Insertions in middle? End?
Beginning? Deletion is middle? End? Beginning? Lookups in beginning?
End? Middle?

Different containers (vector, set, map, etc...) are designed for different
tasks and each has it's power and it's weakness.

Maybe this link will help: http://www.linuxsoftware.co.nz/cppcontainers.html
maybe it won't. Check the bottom anyway to determine which container to
chose.

Also, the wiki has a little bit about the speed of some of the containers:
http://en.wikipedia.org/wiki/Standard_Template_Library

Really, without knowing what you are trying to optmize it is hard to say.

std::vector<MyClass> MyVector;
/*... */
MyVector[SomeCounter]
should be a relatively fast operation, very similar to pointer math.

std::map<Mykey, MyClass> MyMap;
/* ... */
MyMap.find( SomeKey );
is a binary search lookup.
MyMap[SomeKey]
is also a binary key lookup, with the additon of possibly adding the key and
data.

Without knowing how you are using the vector it is hard to say. One thing I
would hope, however is that you are preallocating enough memory for your
vector so that it doesn't have to keep newing when it runs out of memory.

I have no idea why your operation is taking 2 days, maybe it should be.
Maybe it shouldn't. :But without knowing more about what you are actually
doing anything we come up with is a shot in the dark.


 
Reply With Quote
 
Michael DOUBEZ
Guest
Posts: n/a
 
      07-02-2008
xyz a écrit :
>>> I have to run the simulation of a trace file around (7gb contains
>>> 116million entries)...
>>> presently i am using vector iterators to check the conditions in my
>>> program.....
>>> it is taking 2 days to finish whole simulation.....
>>> my question are the map iterators are faster than vector
>>> iterators.....
>>> does it improve the performance....
>>> thanks to all

> for example i am doing the operation as below in my program
> whenever i receive a packet or something ...i will check does it
> contain in my vector list....
> so if I contain around 2 million entreis in my vector and i received
> around 100 packets...
> then the computation would be 100 packets * 2 million iterations...
>
> as my list goes on incresing I will have more iterations..
> this is the problem i am facing with my simulation..


I don't understand what you are doing.
If your algorithm has to be in O(n) then, there is not much to do unless
you can reorganize your data to have some kind of decision tree or
another heuristic.

But if you perform, let say a search, sorting the vector or using map
will reduce it to O(log(n)). If you can find a good hash, it can be in O(1).

--
Michael
 
Reply With Quote
 
xyz
Guest
Posts: n/a
 
      07-02-2008
On Jul 2, 4:10*pm, "Jim Langston" <(E-Mail Removed)> wrote:
> "xyz" <(E-Mail Removed)> wrote in message
>
> news:(E-Mail Removed)...
>
> >I have to run the simulation of a trace file around (7gb contains
> > 116million entries)...
> > presently i am using vector iterators to check the conditions in my
> > program.....
> > it is taking 2 days to finish whole simulation.....

>
> > my question are the map iterators are faster than vector
> > iterators.....
> > does it improve the performance....
> > thanks to all

>
> Performance for what? *Insertions? *Deletions? *Insertions in middle? *End?
> Beginning? *Deletion is middle? End? *Beginning? *Lookups in beginning?
> End? *Middle?
>
> Different containers (vector, set, map, etc...) are designed for different
> tasks and each has it's power and it's weakness.
>
> Maybe this link will help:http://www.linuxsoftware.co.nz/cppcontainers.html
> maybe it won't. *Check the bottom anyway to determine which container to
> chose.
>
> Also, the wiki has a little bit about the speed of some of the containers:http://en.wikipedia.org/wiki/Standard_Template_Library
>
> Really, without knowing what you are trying to optmize it is hard to say.
>
> std::vector<MyClass> MyVector;
> /*... */
> MyVector[SomeCounter]
> should be a relatively fast operation, very similar to pointer math.
>
> std::map<Mykey, MyClass> MyMap;
> /* ... */
> MyMap.find( SomeKey );
> is a binary search lookup.
> MyMap[SomeKey]
> is also a binary key lookup, with the additon of possibly adding the key and
> data.
>
> Without knowing how you are using the vector it is hard to say. *One thing I
> would hope, however is that you are preallocating enough memory for your
> vector so that it doesn't have to keep newing when it runs out of memory.
>
> I have no idea why your operation is taking 2 days, maybe it should be.
> Maybe it shouldn't. *:But without knowing more about what you are actually
> doing anything we come up with is a shot in the da



as i said...if my checking element matches one of the element in my
vector list then i will collect the statistics...
if it doesnt matches any one of the vector elements then i will move
this checking elment to a new vector...

i hope u all undestand
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
can I use stl vector iterator to delete a vector of pointers? zl2k C++ 27 09-07-2010 11:47 AM
Initializing vector<vector<int> > and other vector questions... pmatos C++ 6 04-26-2007 05:39 PM
will an iterator to a map becomes invalid when an element is inserted into the map wolverine C++ 3 07-31-2006 12:24 PM
Free memory allocate by a STL vector, vector of vector, map of vector Allerdyce.John@gmail.com C++ 8 02-18-2006 12:48 AM
How to loop in a vector (set, map, etc) from iterator i to iteratorj Tony Young C++ 4 04-09-2005 12:59 AM



Advertisments