Algorithm optimization - c#

Question

I have this algorithm which I have been working on for some time, but my problem is that it is kinda slow. I will have to optimize it somehow but I find it a little hard. The current speed is O(n^4) with some extra execution in for loops.

What am I trying to accomplish?

I have a lot of testcases stored in a "run section" and some testcases stored in a "suite section". I would like to compare the testcases to be able to see which testcases has failed in the "suite section". But to get all the failen testcases I first have to loop through the build to get to the test runs then loop through the testruns to get to the testcases and then I compare the "run section testcases" with the "suite section testcases" in the 4'th loop.

Is there any way or methods i could use to simplify this job?

The algorithm is listed below.

/// <summary>
/// Check if the sortet masterList matches any other testcases. If it does then return them.
/// </summary>
/// <algorithm>
/// The following soring algorithm is running O(n^4) which we have to optimize somehow. 
/// </algorithm>
/// <param name="builds"></param>
/// <returns></returns>
/// <summary>
public IEnumerable<Entities.TestResult> RetrieveTestcasesFromSuite(string project, string buildNumber, int suiteId)
{
    SuiteSorting aps = new SuiteSorting();

    IBuilds build = TSBuilds.GetBuildByBuildNumber(project, buildNumber);

    List<Entities.TestResult> failedTestcases = new List<Entities.TestResult>();

    //Gets us a list of the testcase names from the suite number
    List<string> dataen = new List<string>();
    var testcaseSortingID = aps.GetTestcasesFromSuite(suiteId);
    foreach (var element in testcaseSortingID)
    {
        dataen.Add(GetTitleFromTestcaseID(element));
    }

    //For the build we select, we want to see...
    for (int i = 0; i < build.Count; i++)
    {
        ITestRuns testRuns = TS.Runs.TSRuns.GetTestRunByBuildUri(project, build.Value[i].Uri);
        // Show only test runs that have completed
        IEnumerable<TestRun> sortTestRuns = testRuns.Value.Where(p => p.State == TestState.Completed.ToString());

        //Foreach testrun in the build we want to see..
        foreach (ITestRun testRun in sortTestRuns)
        {
            ITestResults testResults = TS.Results.TSResults.GetListOfTestResultsByID(project, testRun.Id);
            // Show only test results that have not passed 
            IEnumerable<TestResult> sortedTestResults = testResults.Value.Where(p => p.Outcome != TestOutcome.Passed.ToString());

            //Foreach test result in each testrun we would like to...
            foreach (ITestResult testResult in sortedTestResults)
            {
                //Foreach testcase found within suites, compare it with all testcases looped from above..
                foreach (var element in dataen)
                {
                    //Foreach testcase in suite, compare with testcases from run.
                    if (element.Equals(testResult.TestCaseTitle))
                    {
                        failedTestcases.Add(new Entities.TestResult()
                        {
                            RunId = testResult.TestRun.Id,                      // The test Run ID
                            RunTitle = testResult.TestRun.Name,                 // The test run Title
                            TestResultId = testResult.Id,
                            Area = testResult.Project.Name,
                            ComputerName = testResult.ComputerName,
                            FailureType = testResult.FailureType,
                            ErrorMessage = testResult.ErrorMessage,
                            TestCaseId = testResult.TestCase.Id,
                            TestCaseTitle = testResult.TestCaseTitle,
                            TestRunId = testResult.TestRun.Id,
                            Reason = ReasonHandler.GiveReasonFromErrorMessage(testResult.ErrorMessage), //Reason
                            Match = ReasonHandler.CompareReasonWithErrorMessageOne(testResult.ErrorMessage),
                            ReasonCategorie = GiveCategorieFromReason(testResult.ErrorMessage, ReasonHandler.GiveReasonFromErrorMessage(testResult.ErrorMessage)), //Retrurns Categorie of reason                                                                                                                                                     // numberInRow = dataToReturn.Count, do we use it?
                            JiraIssueUrl = JiraCommunication.CreatejiraUrlFromReason(ReasonHandler.GiveReasonFromErrorMessage(testResult.ErrorMessage)),           //Creates the JiraIssueUrl
                            JiraKey = JiraCommunication.GetJiraKeyFromReason(ReasonHandler.GiveReasonFromErrorMessage(testResult.ErrorMessage)),
                            TestcaseTfsUrl = TfsHandler.GetTestcaseUrl(testResult.TestRun.Id.ToString(), testResult.Id.ToString()),
                            ResolutionStateId = testResult.ResolutionStateId
                        });
                    }
                }
            }
        }
    }
    return failedTestcases;
}

First you could make dataen a Dictionary or even better a Hashset to use Contains() instead of a for loop to compare titles. Secondly i would remove redundant calls to ReasonHandler.GiveReasonFromErrorMessage(), save the result to a variable and use it instead. — ViRuSTriNiTy
– ViRuSTriNiTy, Commented Jun 25, 2018 at 7:14
If this data were stored in a dbase (isn't it already?) then you'd get the advise to run the query optimizer, adding indexes where appropriate, perhaps de-normalize a table intentionally. Data reduction is always an option, in the case of unit tests nobody is particularly interested in tests that did not fail. So you'd, at best, store on only the first and last test run that succeeded. — Hans Passant
– Hans Passant, Commented Jun 25, 2018 at 8:36
There are sure some parts of the code that could be optimized, but are you sure that the slowness of the method actually comes from the iterations and performance of the CPU and not delays like queries? You would most likely make a lot of calls to: GetTestRunByBuildUri and GetListOfTestResultsByID Are these querying remote data? — Mark Reimer
– Mark Reimer, Commented Jun 25, 2018 at 9:06
O(N)+O(N^4) makes little sense. Just write O(N^4). And if you want to perform all these tests, there is no better way than... performing them. The loops in themselves are no concern. — user1196549
– user1196549, Commented Jun 25, 2018 at 10:34
You are right Yves Daoust don't really know why i added the + O(n). — Kristofer Mar Einarsson
– Kristofer Mar Einarsson, Commented Jun 25, 2018 at 11:09

Mark Reimer · Accepted Answer · 2018-06-26 08:13:10Z

1

As we discussed in private @KristoferMarEinarsson(We are colleagues) your performance hit comes from external calls and is not a performance problem of your algorithm/CPU as such.

GetBuildByBuildNumber

GetTestRunByBuildUri

GetListOfTestResultsByID

Are all performing rest queries synchronously and are therefore slowing down your algorithm a lot.

As each iteration on the loops does not depend on the one prior all your logic in your loops could be made to run asynchronously. In theory that would bring the execution time down to the worst case of GetBuildByBuildNumber + GetTestRunByBuildUri + GetListOfTestResultsByID.

answered Jun 26, 2018 at 8:13

Mark Reimer

1164 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

sharmav1 · Accepted Answer · 2018-06-25 09:11:04Z

1

I think you can do something like below for the inner most two loops and get rid of them, I have not tested anything as you haven't provided complete code:

var failedTestCases = sortedTestResults.Where(x => dataen.Contains(x.TestCaseTitle)).Select(testResult => new Entities.TestResult
{
                RunId = testResult.TestRun.Id,                      // The test Run ID
                RunTitle = testResult.TestRun.Name,
                TestResultId = testResult.Id,
                Area = testResult.Project.Name,
                // all other columns here ...
}).ToList();

edited Jun 25, 2018 at 9:11

answered Jun 25, 2018 at 8:00

sharmav1

3192 silver badges10 bronze badges

8 Comments

Kristofer Mar Einarsson Over a year ago

Hmm well thought but im just not able to implement the "failedTestcases.add(new Entities.TestResult() {}); part. It says "cannot assign 'void' to annonymous type propery". there for it doesn't allow me to insert my values RunId, RunTitle and so on..

sharmav1 Over a year ago

@KristoferMarEinarsson I have updated my answer, please check if it works

Kristofer Mar Einarsson Over a year ago

This works much better but i still have a problem when i try to say for example: RunId = testResult.TestRun.Id because we can't find "testResult" because we dont loop through it anymore. Do you know what i could replace it with? the ".TestRun" is inside the interface ITestResult which we looped through before.

sharmav1 Over a year ago

@KristoferMarEinarsson, I am sorry, copy paste errors, I told you I didn't test it, you need to use 'y' variable instead of 'testResult' or you can rename 'y' to 'testResult' whatever suits you. Anyways, I will update my answer

sharmav1 Over a year ago

@KristoferMarEinarsson, it is just a start, you can do many things to improve performance, many have already commented like using dictionary instead of list, checking for remote calls. I would suggest, first check each method call and see which one is really taking time and then break that down to best possible way.

|

Collectives™ on Stack Overflow

Algorithm optimization - c#

2 Answers 2

Comments

8 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

8 Comments

Your Answer

Sign up or log in

Post as a guest

Related