时间戳

首页 > 解决方案 > 异步修改相关对象列表会产生意外结果

c# - 异步修改相关对象列表会产生意外结果

问题描述

我有一个对象列表，它们之间可以有一个或多个关系。我想遍历这个列表并将每个对象与列表中的所有其他对象进行比较，在比较对象时设置关系。因为现实生活中的这种比较相当复杂且耗时，所以我尝试异步执行此操作。

我很快整理了一些示例代码，以相当简单的方式说明了手头的问题。

class Program
    {
        private static readonly Word[] _words =
        {
            new Word("Beef"),
            new Word("Bull"),
            new Word("Space")
        };

        static void Main()
        {
            var tasks = new List<Task>();

            foreach (var word in _words)
            {
                tasks.Add(CheckRelationShipsAsnc(word));
            }

            Task.WhenAll(tasks);
        }

        static async Task CheckRelationShipsAsnc(Word leftWord)
        {
            await Task.Run(() =>
            {
                foreach (var rightWord in _words)
                {
                    if(leftWord.Text.First() == rightWord.Text.First())
                    {
                        leftWord.RelationShips.Add(rightWord);
                    }
                }
            });
        }
    }

    class Word
    {
        public string Text { get; }
        public List<Word> RelationShips { get; } = new List<Word>();

        public Word(string text)
        {
            if(string.IsNullOrEmpty(text)) throw new ArgumentException();
            Text = text;
        }

        public override string ToString()
        {
            return $"{Text} ({RelationShips.Count} relationships)";
        }
    }

预期的结果是“Space”没有任何关系，而“Bull”和“Beef”这两个词彼此之间只有一种关系。我得到的是所有的词都没有关系。我无法理解到底是什么问题。

标签： c#algorithmasync-await

解决方案

您的算法具有O(n^2)时间复杂度。如果您有大量要相互比较的项目，这将是一个问题。例如，如果您有 1000 个项目，这会给您 1000 * 1000 = 1000000（一百万）次比较。

考虑使用另一种方法。我不知道这是否适用于您的实际问题，但对于此示例，假设每个单词都以大写字母 A..Z 开头，您可以将相关单词按首字母存储在长度为 26 的单词数组中列表。

var a = new List<Word>[26];

// Initialize array with empty lists
for (int i = 0; i < a.Length; i++) {
    a[i] = new List<Word>();
}

// Fill array with related words
foreach (var word in _words) {
    a[word.Text[0] - 'A'].Add(word); // Subtracting 'A' yields a zero-based index.
}

请注意，您的原始解决方案有两个嵌套循环（其中一个隐藏在 的调用中CheckRelationShipsAsnc）。这个解决方案只有一层循环，时间复杂度O(n)达到这里。

现在，您可以在相应数组位置的一个列表中找到所有相关单词。获取此信息，您现在可以连接同一列表中的单词。这部分还在O(n^2)；但是，这里n要小得多，因为 is 仅指相关列表中的单词，而不是初始_words数组的长度。

根据您的实际问题的表述方式，使用 aDictionary<char, List<Word>>代替 my 数组可能会更好a。数组解决方案需要一个索引。在现实世界的问题中，关系条件可能无法表述为指标。字典需要一个键，任何类型的对象都可以用作键。请参阅：的备注部分Dictionary<TKey,TValue> Class。

以这种方式优化的算法可能比多任务解决方案更快。

推荐阅读