for循环花费太多时间才能完成。

Question

以下代码工作正常。唯一的问题是如果我给出一个长度为200,000的数组值，需要大约1个小时才能完成。以下是我的代码。

我有一个数据文件在此处，其中包含data和data2字符串值。 data数组以降序排列，data2以升序排列。

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();
    }

- maxspan

---

太长的长度是多久？ - Richard Ev

也许如果您告诉我们这段代码的目标，我们可以为您提供选项。 - M.kazem Akhgary

其实，我认为它比O(n^2)还要糟糕，因为涉及到IndexOf调用。 - Joel Lee

在循环内部不需要再次检查索引。你已经有了索引 - i 和 j。因此跳过 IndexOf 函数，你还可以简化循环内部的逻辑。 - Aamir Masood

我想我明白他想做什么。他有一个关于Alice的分数列表，并想找出它们与所有时间分数表的排名。他正在收集每个分数的排名。 - JuanR

Answer 1

这可以通过以下方式轻松高效地完成：

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/zh-cn/library/2cy9f6wb(v=vs.110).aspx

这将为您提供O(log n)的性能（在搜索上）。

将其与Linq结合使用，您就拥有了一个相当快的算法。

更新：

昨晚我正在入睡，很抱歉。这是一个实现：

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

我在本地测试了它，处理您的数据共花费1.05秒，包括控制台输出和时间计算 :-)

- JuanR

Answer 2

将 rank = distinctScores.IndexOf(distinctScores[i]); 替换为 rank = i 可以简化你的代码并提高性能。

如果有其他更改，请进一步澄清你的目标。

- ydoow

---

它只会稍微提高性能。但它仍然非常缓慢。 - maxspan

@maxspan 这取决于你想要实现什么。从你的代码中我看不出你在使用 rank 做什么。如果它只是一个纯输出，而顺序并不重要，那么 @Juan 提供的排序答案可能会给你更好的性能。但是，再次问一下，输出是什么？ - ydoow

Answer 3

这是另一种非linq版本。我不确定rank += 2是否符合您的要求。我反转了数据/分数数组的元素。虽然不如二进制搜索方法快，但在控制台应用程序中只需要几秒钟。

    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();
    }

- user6424206

Answer 4

我所做的唯一变动以提高性能，就是确保内部循环从其上一次循环索引继续。

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();
}

- maxspan

Answer 5

将它们排序，然后只需使用索引即可！如果您知道您的数组已经排序，您可以检查每个aliceScore在distinctScores中的位置。然后，您就会知道有多少distinctScores是向上或向下的，并且可以按照您想要的方式进行操作。

- RusArt