Return to Question

I have implemented the O(logN) + O(N) version for the problem: How to find 1st and 2nd largest element in a non-negtive 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?

The result: algo1 30ms, algo2 96ms.

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?

The result: algo1 30ms, algo2 96ms.

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

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

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

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

// 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 = src_data[0], max2nd = src_data[0];
    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] > max2nd) {
            max2nd = src_data[i];
        }
    }
    result.push_back(max1st);
    result.push_back(max2nd);
    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 max2nd = src_data[0];
    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 > max2nd) {
            max2nd = candidate;
        }
    }

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

// 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;
}