Find the 1st and 2nd largest num in an array, O(log N) + O(N) version

Question

I have implemented the \$O(logN) + O(N)\$ version for the problem: How to find 1st and 2nd largest element in a non-negative unique array? The algorithm principle is from this stackoverflow answer.The comparison information in finding 1st helps find 2nd faster (\$log N\$ time).

But I am really depressed that my code is even slower than the easiest method. Theoretically, lower the numbers of comparison, smaller the cost time. I guess maybe my implementation need be optimized.

Can anyone know how to make algorithm2 faster than the easiest method?

---

Tested the code in VS2013, win 10, CPU i5 6500, release version.

The result: algo1 30ms, algo2 96ms.

My code, mian.cpp:

// You need focus on algo2 function.
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>

#include <stdlib.h>
#include <time.h>

#include "gettime.h"
using namespace std;

vector<int> algo1(vector<int> src_data);
vector<int> algo2(vector<int> src_data);
vector<int> generateRandNum(unsigned int size);

int main() {
    vector<int> src_data;
    vector <int> result;
    src_data = generateRandNum(10000000);

    uint64 t0 = GetTimeMs64();
    result = algo1(src_data);
    uint64 t1 = GetTimeMs64();
    cout << "Algo1 cost " << (t1 - t0) << "ms" << endl;
    cout << "1st: " << result.at(0) << " 2rd: " << result.at(1) << endl;

    t0 = GetTimeMs64();
    result = algo2(src_data);
    t1 = GetTimeMs64();
    cout << "Algo2 cost " << (t1 - t0) << "ms" << endl;
    cout << "1st: " << result.at(0) << " 2rd: " << result.at(1) << endl;

    return 0;
}

// generate unique random numbers in the range[0...N]
vector<int> generateRandNum(unsigned int size) {
    int num = 0;
    vector<int> src_data;

    for (size_t i = 0; i <= size; i++) {
        src_data.push_back(i);
    }
    std::random_shuffle(src_data.begin(), src_data.end());

    return src_data;
}

vector<int> algo1(vector<int> src_data) {
    int max1st = -1, max2rd = -1;
    int record = 0;
    vector<int> result;
    // find maximum num
    for (size_t i = 0; i < src_data.size(); i++) {
        if (src_data[i] > max1st) {
            max1st = src_data[i];
            record = i;
        }
    }
    for (size_t i = 0; i < src_data.size(); i++) {
        if (src_data[i] < max1st && src_data[i] > max2rd) {
            max2rd = src_data[i];
        }
    }
    result.push_back(max1st);
    result.push_back(max2rd);
    return result;
}

vector<int> algo2(vector<int> src_data) {
    vector<vector <int>> matrix;
    // initial first row
    matrix.push_back(src_data);

    // build the tree using 2D vector
    int layer_size = src_data.size();
    int height = 0;
    int maximum = 0;
    int lastnode = 0;
    int newsize = 0;
    int num1, num2;
    int aplus = 0, isnegtive = 0;
    while (layer_size != 1) {
        newsize = layer_size / 2 + layer_size % 2;
        vector<int> new_row(newsize, 0);
        for (int i = 0; i < layer_size / 2; i++) {
            num1 = matrix[height][2 * i];
            num2 = matrix[height][2 * i + 1];
            maximum = max(num1, num2);
            new_row[i] = maximum;
        }
        if (layer_size % 2) {
            lastnode = matrix[height].back();
            new_row[newsize - 1] = lastnode;
        }
        matrix.push_back(new_row);
        layer_size = newsize;
        height++;
    }

    int max1st = matrix.back().front();

    // find 2nd laygest number
    int index_record = 0;
    int max2rd = -1;
    int candidate = 0;
    int leftnode_index = 0, rightnode_index = 0;
    for (int i = matrix.size() - 1; i > 0; i--) {
        leftnode_index = index_record * 2;
        rightnode_index = index_record * 2 + 1;
        if (matrix[i - 1][leftnode_index] == max1st) {
            candidate = matrix[i - 1][rightnode_index];
            index_record = leftnode_index;
        }
        else {
            candidate = matrix[i - 1][leftnode_index];
            index_record = rightnode_index;
        }
        if (candidate != max1st && candidate > max2rd) {
            max2rd = candidate;
        }
    }

    vector<int> result;
    result.push_back(max1st);
    result.push_back(max2rd);
    return result;
}

gettime.h is from https://stackoverflow.com/a/1861337/4928269.

Answer 1

Algo 1 still has a lot of headroom for improvement as well:

vector<int> algo1(const vector<int> &src_data) {
    int max1st = src_data[0], max2nd = src_data[1];
    if (max1st < max2nd) {
        swap(max1st, max2nd);
    }

    for_each(src_data.begin() + 2, src_data.end(), [&max1st, &max2nd] (const int &n) {
        if (n > max2nd) {
            if (n > max1st) {
                max2nd = max1st;
                max1st = n;
            } else {
                max2nd = n;
            }
        }
    });

    vector<int> result;
    result.push_back(max1st);
    result.push_back(max2nd);
    return result;
}

For starters, avoid copying src_data on invocation. That is easily 50% of the function cost with the original solution, and 70% for the OP's improved solution.

The second improvement, only ever perform the n > max1st comparison if n > max2nd has confirmed it as a potential candidate. Best case, the number of comparisons drops to \$n\$ with \$\mathcal{O}(1)\$ assignments, and only the worst case remains \$2n\$ comparisons with \$2n\$ assignments.

A quick benchmark of the original, the improved, and this implementation of algo1 (when using the copy free function signature, best out of 3 each), took 19ms, 12ms and 8ms each.

Answer 2

The recommendation in the linked article is correct, but you are taking it too literally. Take a look at the Stepanov's solution. Pay particular attention to a binary_counter class, and how it is used. I highly recommend to watch the lecture (part1 and part2) before digging into the code (I also highly recommend to watch a complete course).

Answer 3

This is a self-answer. Thanks for every reviewer. I modified my code, and found the problem in the function algo2(). Allocation new memory for 2D vector is the chief culprit. I tested the execute time of algo2 if there is only one operation matrix.push_back(src_data):

// just for test, only one operation
vector<int> algo2(vector<int> src_data) {
    vector<vector <int>> matrix;
    matrix.push_back(src_data);

    vector<int> result;
    result.push_back(0);
    result.push_back(1);
    return result;
}

The excute time (compiled in release mode): algo2 41ms, algo1 28ms. So my implementation is too much literally, the code should avoid the memory allocation as much as possible. Maybe I need new data structre or STL class with the full power of C++.

I also modified the algo1, faster slightly but more elegant than former version:

vector<int> algo1(vector<int> src_data) {
    int max1st = src_data[0], max2nd = src_data[1];
    if (max1st < max2nd) {
        swap(max1st, max2nd);
    }

    for (int i = 2; i < src_data.size(); i++) {
        // numbers of comparisons is still 2*N
        if (src_data[i] > max1st) {
            max2nd = max1st;
            max1st = src_data[i];
        }
        else if (src_data[i] > max2nd) {
            max2nd = src_data[i];
        }
    }
    vector<int> result;
    result.push_back(max1st);
    result.push_back(max2nd);
    return result;
}

Finally, without doubt finding 2nd largest element using a tree is faster than linear method due to the fewer number of comparison, but how to build the tree efficiently is a problem.

Answer 4

Trying to take this literally: Can anyone know how to make algorithm2 faster than the easiest method? and // You need focus on algo2 function., with algorithm2 finding the runner-up among the champion's opponents in a tournament.

The straightforward way to find the k-max values of an unordered collection is to feed a priority queue of size k with its elements.

The cases with k <= 2 are special in not warranting an explicit priority queue: after initializing k candidates from the first k elements, just compare each of the remaining elements to the current k-max candidate. If the current element is greater: if looking for the top two elements, compare to the max candidate: if greater, keep that value as the new runner-up and make the current element the max candidate, else just replace the runner-up.

This requires \$kN+O(1)\$ assignments, worst case, and \$kN-O(1)\$ comparisons.

The tournament approach to 2-max requires \$N+ld(N)-O(1)\$ comparisons and \$N+O(ld(N))\$ assignments.

According to this, algorithm2 may use slightly more than half the comparisons and assignments algorithm1 does. Then again, for "random input", I'd expect the number of assignments in the simplistic approach to grow in the ballpark of \$c*lg(N)\$ to \$c*sqrt(N)\$ - strictly lower than \$N/2\$ for "non-trivial" values of \$N\$.

For any contemporary sequential machine implementation, I'd expect simplistic to win hands down against tournament. Design, test, analysis and measurement of parallel renditions left as an exercise…