[Fixed] C++ run-time calculation problem in OJ


  • 1
    V

    Two solutions below use the same approach and have O(n * log n) complexity. However, they produce radically different run-time: ~150-200 ms vs. 6 ms.

    The first solution should be even faster as we do not have the overhead of BST. So, I ran tests using 100K sequences (increasing, random, and shuffled), and, in average, the first solution was 4 times faster than the the second one (not ~30 times slower as in OJ).

    int lengthOfLIS(vector<int>& nums) 
    {
        vector<int> dp;
        for (auto n : nums)
        {
            auto it = lower_bound(begin(dp), end(dp), n);
            if (it == dp.end()) dp.push_back(n);
            else *it = n;
        }
        return dp.size(); // ~150-200 ms
    }
    
    int lengthOfLIS(vector<int>& nums) {
        set<int> s;
        for (auto n : nums) {
            auto res = s.insert(n);
            if (res.second && next(res.first, 1) != s.end()) s.erase(next(res.first, 1));
        }
        return s.size(); // 6 ms
    }
    

  • 0
    V

    I think that the C++ compiler/run-time used by OJ has an issue with the lower_bound implementation on vector. I just noticed a similar solution that uses hand-coded binary search instead, and the run-time in OJ is 3 ms. This is in-line with my observations.


  • 0

    The second solution is quite interesting. Not sure I'd be able to understand it if I didn't know the "normal" solution already :-)


  • 0
    V

    After the fix to OJ (described here), the first solution now takes only 3 ms, which is as expected.


  • 0
    V

    @StefanPochmann Right, the second solution initially looked like the first one, but I wanted to make it shorter and now I agree it's pretty obscure. I am usually avoiding in-line increment/decrement operators - poor readability/debug-ability. Also, in C++ set.insert() return a pair of results, which is efficient but less readable. In C#, for example, SortedSet.Add() just returns the Boolean flag.


  • 0

    @votrubac Nah, those things weren't my problem. The increment was obvious, and the insert return value I simply looked up. So I easily understood what the algorithm does, I just don't find it so obvious why it does what it does.

    With the DP vector, I think of it as dp[i]telling me the smallest tail of an LIS of length i+1 (or the smallest tail of an LIS of length i being stored at dp[i-1]). Could be made even more clear by adding and ignoring a dummy entry at index 0, so I don't have to do the ±1 thinking. The point is that I can easily express this meaning of the table entries.

    But with the set, I don't have an index. I do realize that it's sorted so that I can make up an index in my mind, but that just goes against what my mind thinks of sets. I also realize that you're just inserting an element and removing the next larger one, but to see that that is the right thing to do, I had to compare it with the behavior of the vector version and see that that's doing the same thing. With the set, I just can't so easily express the meaning of each element.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.