lundi 25 mars 2019

How to optimize deletion of left node if it is bigger than right node using a large list as input? Complete in two seconds or less

I have an input file with 32400 entries. I read entries into a list data structure in reverse order (but it could be any data structure if there is something that is more efficient).

I compare the left node to the right node. If the left node is bigger than the right node, then delete the left node. Continue doing this until each left node is smaller than each right node. Each pass through the list data structure will count as a day. I am trying to figure out how many days it will take to reach the desired state.

I have implemented a solution that works for all of my test cases. However, one of my test cases has 32400 entries and this case takes about 35 minutes to find the solution. I have to find the solution in two seconds or less.

How do I optimize my solution so that it completes in two seconds or less when a larger number of values have to be examined?

I tried using a forward_list, queues, stacks, etc and everything takes too long to complete. I am thinking I might have to use something like a heap sort or a binary search sort but am not sure how that would work in this scenario.

Complete code below:

#include <iostream>
#include <fstream>
#include <string>
#include <list>

int main(int argc, char* argv[])
{
    // Create input file stream object.
    ifstream ifs("input1.txt");

    // Read input file. First line will contain number of students in class. Second line will contain percentage each student is likely to fail.
    string line;
    string inputFileArray[2];
    int inputFileCount = 0;
    while (getline(ifs, line))
    {
        // If line is not empty or if it is not all whitespace, read the line into the array.
        if ((line != "") && !(all_of(line.begin(), line.end(), isspace)))
        {
            inputFileArray[inputFileCount] = line;
            inputFileCount++;
        }
    }

    // Define the delimiter that will be used to split each student's percentage of failing.
    string delimiter = " ";
    // Initialize the start position for the first student's percentage of failing the class to the start of the string.
    auto start = 0U;
    // Initialize the end position for the first student's percentage of failing to the first found instance of the delimiter.
    auto end = inputFileArray[1].find(delimiter);

    // Parse each student's percentage of failing the class.
    list<int> lastStudentStanding;
    while (end != string::npos)
    {
        lastStudentStanding.push_front(stoi(inputFileArray[1].substr(start, end - start)));
        start = end + delimiter.length();
        end = inputFileArray[1].find(delimiter, start);
    }
    // Add the last student's percentage of failing the class to the queue.
    lastStudentStanding.push_front(stoi(inputFileArray[1].substr(start, end)));


    /*printf("Given Linked List: ");
    for (auto it = lastStudentStanding.begin(); it != lastStudentStanding.end(); ++it)
    {
        cout << *it << " ";
    }
    cout << endl;*/


    // Delete left node if it is bigger than right node.
    int numOfDays = 1;
    //cout << numOfDays << " day" << endl;
    bool isStudentsDropped = true;
    while (isStudentsDropped)
    {
        bool isErased = false;
        for (auto it = lastStudentStanding.begin(); it != lastStudentStanding.end(); )
        {
            if ((next(it, 1) != lastStudentStanding.end()) && (*it > *next(it, 1)))
            {
                it = lastStudentStanding.erase(it);
                isErased = true;
            }
            else
            {
                ++it;
            }
        }

        if (isErased)
        {
            numOfDays++;
            //cout << numOfDays << " days" << endl;
        }
        else
        {
            isStudentsDropped = false;
        }
    }


    /*printf("\nModified Linked List: ");
    for (auto it = lastStudentStanding.begin(); it != lastStudentStanding.end(); ++it)
    {
        cout << *it << " ";
    }
    cout << endl;*/

    string dayText = " days";
    if (numOfDays == 1)
    {
        dayText = " day";
    }
    cout << numOfDays << dayText << endl;


    system("pause");
    return 0;
}


I need to optimize this operation so that it happens in 2 seconds or less:

    // Delete left node if it is bigger than right node.
    int numOfDays = 1;
    //cout << numOfDays << " day" << endl;
    bool isStudentsDropped = true;
    while (isStudentsDropped)
    {
        bool isErased = false;
        for (auto it = lastStudentStanding.begin(); it != lastStudentStanding.end(); )
        {
            if ((next(it, 1) != lastStudentStanding.end()) && (*it > *next(it, 1)))
            {
                it = lastStudentStanding.erase(it);
                isErased = true;
            }
            else
            {
                ++it;
            }
        }

        if (isErased)
        {
            numOfDays++;
            //cout << numOfDays << " days" << endl;
        }
        else
        {
            isStudentsDropped = false;
        }
    }

Input files and expected results:

input1.txt: https://pastebin.com/L4gdxs4w Expected result: 3 days

input2.txt: https://pastebin.com/j08s6Lrv Expected result: 3 days

input3.txt: https://pastebin.com/0TJPk62m Expected result: 32400 days

Aucun commentaire:

Enregistrer un commentaire