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

Question

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

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

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

预期的结果是"空间"没有关系，而"公牛"和"牛肉"这两个词彼此之间有一种关系。我得到的是，所有的文字都没有任何关系。我很难理解问题到底是什么。

Answer 1

您也应该Main方法async并等待Task.WhenAll。否则，WhenAll的结果任务将不会运行其执行。您还可以使用Linq简化任务创建

static async Task Main()
{
var tasks = _words.Select(CheckRelationShipsAsync);
await Task.WhenAll(tasks);
}

您还可以使用Wait()或WaitAll方法，该方法同步运行并阻止当前线程(因此，这不是推荐的方法(。但它不需要使方法Mainasync

var tasks = _words.Select(CheckRelationShipsAsync);
var task = Task.WhenAll(tasks);
task.Wait();

或

static void  Main()
{
var tasks = _words.Select(CheckRelationShipsAsync);
Task.WaitAll(tasks.ToArray());
}

第二点是，当你检查关系时，你没有跳过单词本身，最后的每个单词都与自身有关系。您应该在循环中添加leftWord != rightWord条件foreach以获得预期的结果

预期的结果是"空间"没有关系，而 "公牛"和"牛肉"这两个词彼此之间有一种关系。

Answer 2

您的算法具有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数组的长度。

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

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