Thread: Poor performance of code

  1. #1
    Registered User
    Join Date
    Nov 2018
    Posts
    5

    Poor performance of code

    I just did an online coding test and my code was said to be correct but performance is an issue. Could anyone help me improve it?
    Code:
        // C++ 14
        // 'solution' checks an uneven-length array of integers (i.e. vector) wherein
        // each element has a paired value, while the array has only one value that does not
        // have a paired couterpart. That value that is a singleton should be returned by
        // the function
    #include <algorithm>
    #include <vector>
    #include <functional>
    #include <cassert>
    bool inRange(int a)
    {
      return (a > 0) && (a <= 1000000);
    }
    
    int solution(std::vector < int >&A)
    {
      auto N = A.size();
      if (N % 2 == 0 || !inRange(N)) {
        return -1;
      }
    
    for (const auto i:A) {
        if (!inRange(i)) {
          return -2;
        }
      }
    
      std::vector < int >B {
      };
      int odd {
      -99};
      while (B.size() != N) {
        // remove first number discovered        
        // after copying it to B        
        B.push_back(A.back());
        A.pop_back();
    
        const auto res = std::find(A.begin(), A.end(), B.back());
        if (res != A.end()) {
          B.push_back(*res);
          A.erase(res);             // 2nd number discovered so remove                 
          continue;        
        }
        odd = B.back();
      }
      return odd;
    }
    
    // Run example
    int main()
    {
      std::vector < int >v = { 1, 7, 1, 8, 3, 7, 8 };
      assert(solution(v) == 3);
    }
    Last edited by Salem; 08-13-2021 at 03:40 AM. Reason: Removed crayola colour scheme.

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,362
    Perhaps the issue is at the level of the algorithm rather than the implementation. For example, perhaps it would be more efficient to sort the vector, then do a single pass to find the first number that does not have an adjacent paired value?
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User
    Join Date
    Nov 2018
    Posts
    5
    Thanks for your reply. Yes, it actually occurred to me to sort the vector first and check for adjacent equal pairs. However I think the problem requires a traversal of the whole vector because only one element is supposed not to have a counterpart. I also thought that I could do away with the for-loop I used in the first version.

    Code:
    // you can use includes, for example:
    #include <algorithm>
    #include <functional>
    #include <vector>
    #include <cassert>
    #include <iostream>
    #include <iterator>
    
    
    int solution(std::vector<int> &A) 
    {
        const auto N = A.size();
        auto inRange = [](const int a) { return (a > 0) && (a <= 1000000); };
        if (N % 2 == 0 || !inRange(N))
        {
            return -1;
        }
    
    
        if (!std::is_sorted(std::begin(A), std::end(A))) 
        {
            std::sort(std::begin(A), std::end(A));
        }
        
        auto odd{-99};
        auto it = A.begin();
        while (it != A.end())
        {
            if (!inRange(*it))
            {
                return -2;
            }
            
            if (*it == *(it + 1))
            {
                it = it + 2;
                continue;
            }
            odd = *it;
            ++it;
        }
        return odd;
    }
    
    
    int main() 
    {
        std::vector<int> v = {1, 7, 1, 8, 3, 7, 8};
        assert(solution(v) == 3);
        // std::cout << "The odd number is: " << solution(v) << "\n";
    }

  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,362
    Quote Originally Posted by BroVic
    However I think the problem requires a traversal of the whole vector because only one element is supposed not to have a counterpart.
    That's precisely why you don't have to traverse the whole vector. Once you find an element that doesn't have an adjacent counterpart, you know for sure it is the odd element as long as the input parameters are satisfied.

    I might suggest something like this:
    Code:
    int solution(std::vector<int>& numbers)
    {
        if (numbers.size() % 2 == 0)
        {
            return -1;
        }
    
        for (const auto i : numbers)
        {
            if (!(i > 0 && i <= 1000000))
            {
                return -2;
            }
        }
    
        std::sort(std::begin(numbers), std::end(numbers));
    
        auto last_element_it = numbers.end() - 1;
        for (auto it = numbers.begin(); it != last_element_it; it += 2)
        {
            if (*it != *(it + 1))
            {
                return *it;
            }
        }
        return *last_element_it;
    }
    My reasoning:
    • No point applying the range check to the size of the vector; you only care that it has an odd number of elements.
    • Since we can stop early when finding the odd element, doing the range check for all elements before sorting would ensure we validate the entire input.
    • On one hand, having the inRange function is good for readability. On the other hand, it is only used once, and the code obviously validates that the value is within a range, so I have removed the function.
    • It seems unlikely that the input will be sorted, so there's no point checking if it is not sorted before sorting.
    • Instead of checking for end() in the loop condition, we check for the iterator to the last element. This avoids the problem where you're at the last element, and then try to compare with *(it + 1) which does not exist.
    Last edited by laserlight; 08-12-2021 at 09:19 PM.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #5
    Registered User
    Join Date
    Nov 2018
    Posts
    5
    Thanks again. The reason I created `inRange` is because one of the requirements of the task was to check the bounds of both the length of the array AND the value of each element in the array.

  6. #6
    Registered User
    Join Date
    Sep 2020
    Posts
    84
    Wouldn't it be more sensible to check the number before you add it to the vector ?

  7. #7
    Registered User
    Join Date
    Nov 2018
    Posts
    5
    Quote Originally Posted by thmm View Post
    Wouldn't it be more sensible to check the number before you add it to the vector ?
    Makes sense, though the task was agnostic as to how the input vector was generated. Like I said originally, it was for a coding test and the emphasis was on both code correctness and efficiency.

  8. #8
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    38,803
    Perhaps you could post a link to the site where you got the exercise from.

    Most of these online exercise sites are crafted in such a way that the first program you think of will typically fail either the space or time requirement.
    Basically, you win or lose based on the amount of thinking you did before you got to the point of writing "int main".
    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.

  9. #9
    Registered User
    Join Date
    Nov 2018
    Posts
    5
    Quote Originally Posted by Salem View Post
    Perhaps you could post a link to the site where you got the exercise from.

    Most of these online exercise sites are crafted in such a way that the first program you think of will typically fail either the space or time requirement.
    Basically, you win or lose based on the amount of thinking you did before you got to the point of writing "int main".
    It's Log in - Codility. You'd have to sign up though. It's the second exercise among the training tasks.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. How can I improve the performance of this code?
    By bot in forum C Programming
    Replies: 4
    Last Post: 01-04-2018, 05:42 PM
  2. bad performance for the code to send Http request
    By Checker1977 in forum C# Programming
    Replies: 8
    Last Post: 08-20-2008, 07:16 PM
  3. How can I monitor the performance of my C++ Code?
    By honeysting in forum C++ Programming
    Replies: 1
    Last Post: 03-26-2006, 08:10 AM
  4. calling exe from in a Dll? Help the poor VB guy!
    By nmessick in forum C++ Programming
    Replies: 5
    Last Post: 09-16-2002, 02:01 PM
  5. please help me....this little poor man...
    By DavidP in forum A Brief History of Cprogramming.com
    Replies: 2
    Last Post: 08-09-2002, 11:42 AM

Tags for this Thread