How to perform a Depth First Search iteratively using async/parallel processing?
- by Prabhu
Here is a method that does a DFS search and returns a list of all items given a top level item id. How could I modify this to take advantage of parallel processing? Currently, the call to get the sub items is made one by one for each item in the stack. It would be nice if I could get the sub items for multiple items in the stack at the same time, and populate my return list faster. How could I do this (either using async/await or TPL, or anything else) in a thread safe manner?
private async Task<IList<Item>> GetItemsAsync(string topItemId)
{
var items = new List<Item>();
var topItem = await GetItemAsync(topItemId);
Stack<Item> stack = new Stack<Item>();
stack.Push(topItem);
while (stack.Count > 0)
{
var item = stack.Pop();
items.Add(item);
var subItems = await GetSubItemsAsync(item.SubId);
foreach (var subItem in subItems)
{
stack.Push(subItem);
}
}
return items;
}
EDIT:
I was thinking of something along these lines, but it's not coming together:
var tasks = stack.Select(async item =>
{
items.Add(item);
var subItems = await GetSubItemsAsync(item.SubId);
foreach (var subItem in subItems)
{
stack.Push(subItem);
}
}).ToList();
if (tasks.Any())
await Task.WhenAll(tasks);
UPDATE:
If I wanted to chunk the tasks, would something like this work?
foreach (var batch in items.BatchesOf(100))
{
var tasks = batch.Select(async item =>
{
await DoSomething(item);
}).ToList();
if (tasks.Any())
{
await Task.WhenAll(tasks);
}
}
The language I'm using is C#.
