Nested Loop 函数耗时运行，反正提高效率？

Question

我知道这个函数会包含很多数据处理，但我没想到它最终会花费小步来处理。

所讨论的函数被输入一个锯齿状的二维数组，该数组由段落>句子组成，这是由用户输入的文本文件制成的，因此可能很大。它采用这个数组并将每个句子相互比较并保存每个句子之间的分数，即常用单词的数量。

这需要很长时间，老实说，我认为不会。

我的主要测试文本只有 181 个句子长，但这转化为二维数组中的 32700 个值。

然后使用这个值矩阵来计算和select每个段落中最多"relevant"个句子，以及其他事情。

处理181句文本需要1分15秒，处理只有70句的文本需要35秒，但这是基于句子的数量而不是单词，但它给了你一个想法。我不敢想真正的文件需要多长时间。

有问题的功能：

    protected void Intersection2DArray()
    {
        mainSentenceCoord = -1;
        for (int x1 = 0; x1 < results.Length; x1++)
        {
            for (int x2 = 0; x2 < results[x1].Length; x2++)
            {
                var mainSentencesWords = wordSplit(results[x1][x2]);
                secondarySentenceCoord = -1;
                mainSentenceCoord++;

                for (int y1 = 0; y1 < results.Length; y1++)
                {
                    for (int y2 = 0; y2 < results[y1].Length; y2++)
                    {
                        var secondarySentencesWords = wordSplit(results[y1][y2]);
                        int commonElements = mainSentencesWords.Intersect(secondarySentencesWords).ToList().Count();
                        secondarySentenceCoord++;
                        intersectionArray[mainSentenceCoord, secondarySentenceCoord] = commonElements;
                    }
                }
            }
        }
    }

分词功能：

        protected List<String> wordSplit(string sentence)
        {
            var symbols = "£$€#&%+-.";
            var punctuationsChars = Enumerable.Range(char.MinValue, char.MaxValue - char.MinValue)
                                        .Select(i => (char)i)
                                        .Where(c => char.IsPunctuation(c))
                                        .Except(symbols)
                                        .ToArray();

            var words = sentence.Split(punctuationsChars)
                             .SelectMany(x => x.Split())
                             .Where(x => !(x.Length == 1 && symbols.Contains(x[0])))
                             .Distinct()
                             .ToList();
            return words;
        }

我最初想使用一条 Regex 行来进行此拆分，但没有弄清楚，这可能会使速度更快。

这会循环到 select 每个句子相互对立，这是我能想到的最好结果。如果它会大大提高速度，我完全可以接受。

编辑：使用 Moby Disk 建议这是我的新即时代码：

现在调用一次的Word Split函数和returns一个List of List

    public List<List<string>> createWordList()
    {
        List<List<string>> wordList = new List<List<string>>();
        var symbols = "£$€#&%+-.";
        var punctuationsChars = Enumerable.Range(char.MinValue, char.MaxValue - char.MinValue)
                                    .Select(i => (char)i)
                                    .Where(c => char.IsPunctuation(c))
                                    .Except(symbols)
                                    .ToArray();

        for (int x1 = 0; x1 < results.Length; x1++)
        {
            for (int x2 = 0; x2 < results[x1].Length; x2++)
            {
                var words = results[x1][x2].Split(punctuationsChars)
                                            .SelectMany(x => x.Split())
                                            .Where(x => !(x.Length == 1 && symbols.Contains(x[0])))
                                            .Distinct()
                                            .ToList();
                wordList.Add(words);                    
            }
        }
        return wordList;
    }

还有现在超薄的交集函数

    protected void intersectionMatrix()
    {
        List<List<string>> wordList =  createWordList();
        mainSentenceCoord = -1;
        for (var x = 0; x < wordList.Count; x++)
        {
            secondarySentenceCoord = -1;
            mainSentenceCoord++;
            for (var y = 0; y < wordList.Count; y++)
            {
                secondarySentenceCoord++;
                intersectionArray[mainSentenceCoord, secondarySentenceCoord] = wordList[x].Intersect(wordList[y]).Count();
            }
        }
    }

Answer 1

更新见文末：

这里有一些 "low-hanging fruit" 可以在不改变算法本身的情况下大大加快速度：

wordSplit() 每次调用时都会重新计算 "punctuationsChars"。预先做一次。
您正在为同一个句子调用 wordSplit() N^2 次而不是 N 次，因为它同时在外层 (x1,x2) 循环和内层 (y1,y2) 循环中.你只需要拆分 181 个句子，而不是 181^2 个句子。因此，改为循环遍历结果，对每个句子调用一次 wordSplit，然后存储该结果。如果这占用了太多内存，请查看记忆 (http://en.wikipedia.org/wiki/Memoization)，尽管我认为你应该没问题，因为它只会导致文本多一份副本。
您不需要在 Intersect() 之后使用 ToList()。这会创建一个您不使用的列表。

我对 mainSentenceCoord 和 secondarySentenceCoord 的值感到困惑。生成的 intersectionArray 的维度是多少？

天哪！ #1 是它！这将速度提高了 80 倍。看这一行：

Enumerable.Range(char.MinValue, char.MaxValue - char.MinValue)

char.MaxValue 是 65536。因此，如果 N=181，则循环 181 x 181 x 65536！我只是运行探查器来确认它：CPU 98.4% 的时间花在了 wordSplit 中的 ToArray() 调用上。

Nested Loop 函数耗时运行，反正提高效率？

Nested Loop function taking minuets to run, anyway to improve efficiency?

c#

arrays

performance

loops

jagged-arrays