Like Tree2Likes

Speed in array or list structure

This is a discussion on Speed in array or list structure within the C++ Programming forums, part of the General Programming Boards category; Originally Posted by überfuzz I've been tinkering with vectors and I always seem to end up slowing things down... Shame ...

  1. #16
    Registered User manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    Kolkata@India
    Posts
    2,498
    Quote Originally Posted by überfuzz View Post
    I've been tinkering with vectors and I always seem to end up slowing things down... Shame on those who give in!
    Can you give a demonstration..?
    What made you think that 'things' were slow ?
    Did you compare the performance with a list or (de)queue ?
    Manasij Mukherjee | gcc-4.8.2 @Arch Linux
    Slow and Steady wins the race... if and only if :
    1.None of the other participants are fast and steady.
    2.The fast and unsteady suddenly falls asleep while running !



  2. #17
    Registered User
    Join Date
    Jun 2005
    Posts
    6,174
    Quote Originally Posted by überfuzz View Post
    Ok, I guess I don't need any links to any articles then. Thanks!

    oogabooga I've been tinkering with vectors and I always seem to end up slowing things down... Shame on those who give in!
    Note that I did not recommend vector because I consider it in any way optimal for your needs. I recommended vector because your (lack of) requirements means that any choice of container is sufficient. Vector is a workable default choice, nothing more.

    If you care about performance, you need to articulate stronger requirements. If you actually do that, you will actually need to read some articles about the design trade-offs related to selecting containers.

    It is possible to slow down things regardless of your choice of container: just pick a series of operations that plays to the weakness of each container. There is no universally optimal container (i.e. each container type supports some operations efficiently by some measure, and other operations inefficiently). It is also possible to hit program performance by unnecessarily creating (non-lazy) copies of entire containers.
    Right 98% of the time, and don't care about the other 3%.

  3. #18
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,313
    Quote Originally Posted by überfuzz
    However, I believe wrote that I'm use to work with java, not C++ hence my questions and inexperience. Further, for someone with some code experience it should then be quite obvious that I don't know much about how different libraries preforms in C++.
    Ah, but Java has a bunch of standard library components too, including useful containers similiar to those available in the C++ standard library

    If I were programming in Java, I would consider the container to use based on similiar considerations of how the elements are to be inserted and how they are to be accessed. For example, if I want to map from keys to values such that the keys are sorted, I might go for TreeMap in Java and std::map in C++. If I just want to map from keys to values with the aim of accessing the keys as fast as possible, I might go for HashMap in Java and std::unordered_map in C++, with a suitable hash function.

    I would not ask if HashMap might not be good enough such that I should implement my own hash table, unless after testing I really do discover that the general purpose HashMap is not good enough, yet a hash table is appropriate. This is why your question stunned me: it is like a Java programmer asking if he/she should implement a red/black tree instead of using TreeMap because TreeMap might not be good, even before having any evidence that a custom balanced binary tree implementation might beat TreeMap to satisfy performance requirements in this case... when it may well be that choosing HashMap instead is the way to go, or perhaps the performance requirements will already be met by TreeMap.

    Quote Originally Posted by oogabooga
    You may be able to speed up the vector by reserving some reasonable amount of space initially:
    Yeah, then push_back will go from amortised constant time to constant time, at least until the size of the vector exceeds the reserved capacity.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  4. #19
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,288
    So far my asessment is still that std::vector is best, however I appear to have forgotten to ask more about how the data will be accessed.
    Once you put something in there, do you intend to search for it at some point, or are you only ever just going to process the whole lot at once?
    Also, will there ever be any duplicates?
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  5. #20
    Registered User
    Join Date
    Mar 2012
    Posts
    110
    oogabooga - Test runs showed: 220 seconds when I stored data or more precisely hits in the form of an integer with push_back in a vector. 177 seconds when I just counted hits. I'll couldn't see any significant different in performance while preallocating a bigger vector. (I don't remember how big i tried, but I'll try a real big and report back.)

  6. #21
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,313
    Quote Originally Posted by überfuzz
    I'll couldn't see any significant different in performance while preallocating a bigger vector.
    Yeah, that coincides with Stroustrup's observation in his answer to the FAQ Why are the standard containers so slow?:
    Quote Originally Posted by Bjarne Stroustrup
    People sometimes worry about the cost of std::vector growing incrementally. I used to worry about that and used reserve() to optimize the growth. After measuring my code and repeatedly having trouble finding the performance benefits of reserve() in real programs, I stopped using it except where it is needed to avoid iterator invalidation (a rare case in my code).
    You might also want to read the rest of that FAQ, though much of it does not apply in your case because you are storing objects of a built-in integer type.

    By the way, what compiler are you using?
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  7. #22
    Registered User
    Join Date
    Mar 2012
    Posts
    110
    Quote Originally Posted by laserlight View Post
    You might also want to read the rest of that FAQ, ...
    Yes, it's a nice article. Thanks!

Page 2 of 2 FirstFirst 12
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 1
    Last Post: 04-02-2009, 06:51 AM
  2. Array Speed
    By ch4 in forum C Programming
    Replies: 3
    Last Post: 12-17-2008, 11:27 AM
  3. Speed of pointers vs. speed of arrays/structs
    By Kempelen in forum C Programming
    Replies: 32
    Last Post: 06-27-2008, 10:16 AM
  4. what does a linked list structure look like?
    By MalickT in forum C Programming
    Replies: 9
    Last Post: 05-26-2008, 05:19 PM
  5. Speed comparison between vector and 2*2 array
    By cunnus88 in forum C++ Programming
    Replies: 5
    Last Post: 11-25-2007, 01:05 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21