Thread: What is more efficient?

  1. #1
    Its hard... But im here swgh's Avatar
    Join Date
    Apr 2005
    Location
    England
    Posts
    1,688

    What is more efficient?

    Hey guys.

    I am writing a rather large program and there is a part that I want to sort 10 entered vales from the keyboard. Would it be more efficient to use bubblesort or the sort() function using a vector / iterator?

    I was thinking of somthing like this as I am leaning towards the vector:

    Code:
    std::vector<int> scores( 10, 0 );
       
    std::vector<int>::iterator iter;
       
    std::cout << "Enter 10 integers: ";
       
    // add values to vector elements
    for ( int i = 0; i < scores.size(); i++ )
    {
       std::cin >> scores[ i ];
    }
       
    std::cout << "\n\nYou entered:\n\n";
       
    for ( iter = scores.begin(); iter != scores.end(); ++iter )
    {
       std::cout << *iter << std::endl;
    }
       
    std::cout << "\n\nSorted into order:\n\n";
       
    sort ( scores.begin(), scores.end());
       
    for ( iter = scores.begin(); iter != scores.end(); ++iter )
    {
       std::cout << *iter << std::endl;
    }
    I am only asking as I am trying to conserve space and I know that a vector is a more robust type of array.

    Thanks in advance for any input.
    Double Helix STL

  2. #2
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    std::sort is better. And you're not limited to using it with a vector. Could be a raw array, too.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  3. #3
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Do you want to conserve code-space (compiled), code-space (smaller source) or data-space?

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  4. #4
    Its hard... But im here swgh's Avatar
    Join Date
    Apr 2005
    Location
    England
    Posts
    1,688
    Sorry I wasn't clear about that. Yes I mean code-space. ( compiled )

    And thanks CornedBee that is the method I was thinking was better of the two
    Last edited by swgh; 10-17-2007 at 06:26 AM. Reason: Missed a word
    Double Helix STL

  5. #5
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Or do you want to conserve YOUR time by using something which is already present and debugged as opposed to spending time getting your own implementation working.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  6. #6
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by Salem View Post
    Or do you want to conserve YOUR time by using something which is already present and debugged as opposed to spending time getting your own implementation working.
    At least untill you know which chunks of your code are the "big hitters". I'm pretty sure either implementation will be pretty small here, so it may be better to:
    1. Find some other piece of code that can be reduced in size.
    2. Compile the entire project with Optimize for Size "-Os" [certainly the right switch in gcc, and I seem to remember that MS compilers use the same].

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  7. #7
    Its hard... But im here swgh's Avatar
    Join Date
    Apr 2005
    Location
    England
    Posts
    1,688
    True. I was also thinking of "inlining" the smaller functions too that only do small job. Thing with that is, everywhere I read it says inlining a function is poor practice as it can lead to a lareger program output in size. But then again it's the compiler's choice not mine if it does indeed take any notice of the inline command.

    Thanks for all advice so far guys iv taken it all on board.
    Last edited by swgh; 10-17-2007 at 06:59 AM. Reason: typo
    Double Helix STL

  8. #8
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Agressive use of inlining can lead to increased code-size, yes. Letting the compiler inline when it feels it's right will probably not do this too bad. The -Os switch will only inline a function if the resulting code is smaller than the code with outlined functions - so only real tiny functions.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  9. #9
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    Exactly. Some functions are smaller than the code needed to call them, especially in object-oriented language. Consider:
    Code:
    class foo
    {
      int m_i;
    public:
      int get_i() { return i; }
    };
    The body of get_i would look about like this in assembly:
    Code:
    foo@get_i@:
      mov ecx, [esp+4]
      mov eax, [ecx+0] ; offsetof(m_i) = 0
      ret
    Of these three instructions, two are function overhead. And we haven't even established a proper stack frame. Nor have we (as I think we actually should) preserved ecx.

    A call:
    Code:
    int i = foo.get_i();
    Code:
      ; Save registers?
      push &foo
      call foo@get_i@
      mov [esp-4], eax ; Assuming i is at esp-4
    Inlined, the two together become
    Code:
      mov ecx, &foo ; Probably already there
      mov eax, [ecx+0] ; Because mem->mem is not supported
      mov [esp-4], eax
    Three instructions instead of 6, no jump, and better predictability of register use. In fact, if foo's address is already in a register and if i has its own fixed register, the whole thing becomes a single instruction. Depending on the use of i and the aliasing of the foo object, the variable might be elided completely and the access placed there instead.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  10. #10
    and the hat of sweating
    Join Date
    Aug 2007
    Location
    Toronto, ON
    Posts
    3,545
    Do you need the numbers completely sorted, or are you just looking for a certain value like the median value...?

    If you don't need the values completely sorted, one of the other STL sort algorithms might be better.

    From item 86 of "C++ Coding Standards":
    In general order from cheapest to most expensive, your standard sorting algorithm options are: partition, stable_partition, nth_element, partial_sort (with its variant partial_sort_copy), sort, and stable_sort.

  11. #11
    Registered User
    Join Date
    Sep 2006
    Posts
    835
    Quote Originally Posted by matsp View Post
    Agressive use of inlining can lead to increased code-size, yes. Letting the compiler inline when it feels it's right will probably not do this too bad. The -Os switch will only inline a function if the resulting code is smaller than the code with outlined functions - so only real tiny functions.
    Or if the function is nonrecursive and only called in one place. This can happen if parts of the code of a large function are moved out into "helper functions" solely to make it easier to understand and maintain.

  12. #12
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by robatino View Post
    Or if the function is nonrecursive and only called in one place. This can happen if parts of the code of a large function are moved out into "helper functions" solely to make it easier to understand and maintain.
    True - and again, the code produced by this is actually smaller than if there was an external function - because parameter passing and call itself has been removed.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Most Efficient Way to Check a Variable Is A Whole Number
    By bengreenwood in forum C++ Programming
    Replies: 29
    Last Post: 05-28-2009, 01:33 PM
  2. Is std::map efficient for this problem?
    By dudeomanodude in forum C++ Programming
    Replies: 12
    Last Post: 04-10-2008, 02:15 PM
  3. Efficient Algorithm
    By purple in forum C Programming
    Replies: 10
    Last Post: 02-05-2003, 03:01 PM
  4. How do I write more efficient code?
    By minesweeper in forum C++ Programming
    Replies: 4
    Last Post: 08-06-2002, 11:08 AM
  5. Any better & efficient alternative to this C prg.
    By perlguy in forum C Programming
    Replies: 12
    Last Post: 05-24-2002, 03:00 AM