CODEWITHSUNDEEP
c#
maxspan
maxspan

Reputation: 14157

for loop takes to much time to finish

the below code works fine. The only issue is if i give a array value of length 200,000 its takes too long to complete Approx 1 hour. Below is my code.

I have the data file here which contains data and data2 string values. data array is arrange in descending and data2 in ascending.

public void GetInputs()
{
    string data;
    string data2;
    string[] scores_temp = data.Split(' ');
    int[] scores = Array.ConvertAll(scores_temp, Int32.Parse);

    string[] alice_temp = data2.Split(' ');
    int[] aliceScore = Array.ConvertAll(alice_temp, Int32.Parse);

    var distinctScores = scores.Distinct().ToList();
    int rank = 0;
    for (int j = 0; j <= aliceScore.Length-1; j++)
    {
        for (int i = distinctScores.Count-1; i >= 0; i--)
        {
            if (aliceScore[j] >= distinctScores[i])
            {
                rank = distinctScores.IndexOf(distinctScores[i]);
            }
            else if (aliceScore[j] < distinctScores[i])
            {
                rank = distinctScores.IndexOf(distinctScores[i]);
                rank += 2;
                break;
            }
        }
        if (rank.ToString() == "0") {
            Console.WriteLine(rank.ToString().Replace("0", "1"));
        } else {
            Console.WriteLine(rank); };
        }
        Console.ReadLine();
    }

Upvotes: 3

Views: 1578

Answers (5)

user6424206
user6424206

Reputation:

Here's another non-linq version. I'm not sure of the rank += 2, so maybe this isn't accurate for your requirement. I reversed the elements of the data/scores array. Certainly not as fast as the binary search method, but just a few seconds in a console app.

    public static void GetInputs()
    {
        string[] scores_temp = data.Split(' ');
        var distinctScores = scores_temp.Distinct().ToArray();
        int[] scores = (Array.ConvertAll(distinctScores, Int32.Parse)).Reverse().ToArray();

        string[] alice_temp = data2.Split(' ');
        int[] aliceScores = Array.ConvertAll(alice_temp, Int32.Parse);

        int rank = 0;
        for (int i = 0, j = 0; i < aliceScores.Length && j < scores.Length; ++i)
        {
            while (aliceScores[i] > scores[j])
                rank = j++;
            Console.WriteLine(String.Format("Rank {0}: alice {1} -- Index {2}: score {3}", rank, aliceScores[i], j, scores[j]));
        }
        Console.ReadLine();
    }

Upvotes: 1

JuanR
JuanR

Reputation: 7783

This can easily and efficiently be done with a combination of:

Array.Sort(Array): https://msdn.microsoft.com/en-us/library/6tf1f0bc(v=vs.110).aspx

Array.BinarySearch(T[] array, T value): https://msdn.microsoft.com/en-us/library/2cy9f6wb(v=vs.110).aspx

This will give you O(log n) performance (on the search).

Combine this with Linq and you have yourself a pretty fast algorithm.

UPDATE:

I was falling asleep yesterday night sorry. Here is an implementation:

var sortedScores = Array.ConvertAll(data.Split(' '), int.Parse);
Array.Sort(sortedScores);

var ranks = aliceScore.Select(
    a =>
    {
        var result = Array.BinarySearch(sortedScores, a);
        if (result < 0)
        {
            //Did not find it in array
            var index = ~result;
            if (index > sortedScores.Length - 1)
            {
                //It's greater than all
                return index;
            }
            else
            {
                //Return one up to position it after the larger value
                return index++;
            }
        }
        else
        {
            //Found it, return index
            return result;
        }
    });

foreach (int rankFound in ranks)
{
    Console.WriteLine("Rank: {0}", rankFound);
}

I tested it locally and it took 1.05 seconds to process your data, including the Console writes and time elapsed calculation :-)

Upvotes: 6

maxspan
maxspan

Reputation: 14157

The only change I had to do to increase performance was making sure the inner loop continues from its last loop index.

string[] scores_temp = data.Split(' ');
int[] scores = Array.ConvertAll(scores_temp, Int32.Parse);

string[] alice_temp = data2.Split(' ');
int[] aliceScore = Array.ConvertAll(alice_temp, Int32.Parse);

var distinctScores = scores.Distinct().ToList();
int rank = 0;
int innerLoop = distinctScores.Count - 1;
for (int j = 0; j <= aliceScore.Length-1; j++)
{
    for (int i = innerLoop; i >= 0; i--)
    {
        innerLoop = i;
        if (aliceScore[j] >= distinctScores[i])
        {
            rank = i;
        }
        else if (aliceScore[j] < distinctScores[i])
        {
            rank = i;
            rank += 2;
            break;
        }
    }
    if (rank.ToString() == "0") {
        Console.WriteLine(rank.ToString().Replace("0", "1"));
    } else {
        Console.WriteLine(rank); };
    }
    Console.ReadLine();
}

Upvotes: 0

ydoow
ydoow

Reputation: 3006

Replace rank = distinctScores.IndexOf(distinctScores[i]); with rank = i would simplify your code and give better performance.

Would need further clarification on your goal for other change if any.

Upvotes: 1

RusArt
RusArt

Reputation: 576

Sort them, then just work with indeces! If you know that yours arrays are sorted, you can check position of each aliceScore in distinctScores. Then you will know how many distinctScores are upwards or below, and do whatever you want.

Upvotes: -1

Related Questions