Временная сложность этого кода
return all.Keys.ToDictionary(i => i, i => links.Where(k => IsLinkedTo(k, i)).ToList());
- это квадратичные c O(N*M), где N - all.Keys.Count, а M - links.Count. Поэтому неудивительно, что это медленный. . Такая структура данных существует и называется Префиксное дерево . Ниже приведена быстрая реализация для вашего случая:
class ItemMap : IReadOnlyCollection<KeyValuePair<string, IReadOnlyList<Link>>>
{
class Node
{
public Node(char key) => Key = key;
public char Key { get; }
public NodeMap Children;
public ILinkable Item;
public List<Link> Links;
public IReadOnlyList<Link> ItemLinks => Links ?? (Item != null ? NoLinks : null);
public static IReadOnlyList<Link> NoLinks => Array.Empty<Link>();
}
struct NodeMap
{
Dictionary<char, Node> items;
public IEnumerable<Node> Items => items?.Values;
public bool TryGetItem(char key, out Node item, bool create = false)
{
item = null;
if ((items == null || !items.TryGetValue(key, out item)) && create)
(items ?? (items = new Dictionary<char, Node>())).Add(key, item = new Node(key));
return item != null;
}
}
NodeMap RootNodes;
IEnumerable<Node> Nodes
=> RootNodes.Items?.Expand(e => e.Children.Items) ?? Enumerable.Empty<Node>();
IEnumerable<Node> ItemNodes
=> Nodes.Where(n => n.Item != null);
IEnumerable<KeyValuePair<string, IReadOnlyList<Link>>> Items
=> ItemNodes.Select(n => new KeyValuePair<string, IReadOnlyList<Link>>(n.Item.Id, n.ItemLinks));
public ItemMap(ILinkable tree)
{
if (tree == null) return;
var items = new[] { tree }.Expand(e => e.Children);
foreach (var item in items)
AddItem(item);
var links = Nodes.Where(n => n.Item?.Links != null).SelectMany(n => n.Item.Links);
foreach (var link in links)
AddLink(link);
}
void AddItem(ILinkable item)
{
var node = GetNode(item.Id, create: true);
if (node == null) return;
if (node.Item != null) throw new Exception($"Duplicate key: {item.Id}");
node.Item = item;
Count++;
}
void AddLink(Link link)
{
var key = link.TargetId;
if (string.IsNullOrEmpty(key)) return;
ref var nodes = ref RootNodes;
for (int i = 0; i < key.Length; i++)
{
if (!nodes.TryGetItem(key[i], out var node)) break;
// Add to each item in the prefix path
if (node.Item != null && node.Item != link.Source)
(node.Links ?? (node.Links = new List<Link>())).Add(link);
nodes = ref node.Children;
}
}
Node GetNode(string key, bool create = false)
{
if (string.IsNullOrEmpty(key)) return null;
Node node = null;
ref var nodes = ref RootNodes;
for (int i = 0; i < key.Length; i++)
{
if (!nodes.TryGetItem(key[i], out node, create)) break;
nodes = ref node.Children;
}
return node;
}
public int Count { get; private set; }
public IEnumerator<KeyValuePair<string, IReadOnlyList<Link>>> GetEnumerator() => Items.GetEnumerator();
IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
}
(Примечание: вместо рекурсивного обхода дерева во многих местах я использую метод generi c DRY Expand из моего ответа на Как сгладить дерево через LINQ? ))
Вся тяжелая работа выполняется в конструкторе класса. Первый проход добавляет все элементы в префиксное дерево. Затем второй проход связывает ссылки с каждым элементом. Первая операция - O(N), вторая - O(M), так что в целом получается O(M+N), т.е. линейно и намного быстрее, чем оригинал.
Теперь вы можете легко создать нужный словарь (я изменил интерфейсы к их ReadOnly вариантам):
public IReadOnlyDictionary<string, IReadOnlyList<Link>> CalculateUsageMap()
=> new ItemMap(Root).ToDictionary(e => e.Key, e => e.Value);
Но учтите, что это даже не нужно, потому что дерево префиксов может эффективно использоваться как словарь. Реализовать интерфейс словаря только для чтения довольно просто - измените объявление класса на
class ItemMap : IReadOnlyDictionary<string, IReadOnlyList<Link>>
и добавьте следующие несколько строк внутри
public IEnumerable<string> Keys => Items.Select(e => e.Key);
public IEnumerable<IReadOnlyList<Link>> Values => Items.Select(e => e.Value);
public IReadOnlyList<Link> this[string key]
=> TryGetValue(key, out var value) ? value : throw new KeyNotFoundException();
public bool ContainsKey(string key) => TryGetValue(key, out _);
public bool TryGetValue(string key, out IReadOnlyList<Link> value)
=> (value = GetNode(key)?.ItemLinks) != null;
Теперь вы можете удалить вызов ToDictionary:
public IReadOnlyDictionary<string, IReadOnlyList<Link>> CalculateUsageMap()
=> new ItemMap(Root);
Приведенная выше реализация префиксного дерева использует Dictionary<char, Node> для хранения / обхода списка дочерних узлов. Это может занять гораздо больше памяти. Поскольку вся реализация инкапсулирована в NodeMap, вы можете экспериментировать с различными структурами данных и измерять производительность и использование памяти.
Например, следующая реализация, которая использует null, одиночный Node или отсортированный List<Node> в качестве хранилища и двоичный поиск для поиска Node по ключу в отсортированном списке:
struct NodeMap
{
object items; // null, Node or sorted List<Node>
public IEnumerable<Node> Items => items is Node node ? new[] { node } : items as IEnumerable<Node>;
public bool TryGetItem(char key, out Node item, bool create = false)
{
item = null;
if (items == null)
{
if (create) items = item = new Node(key);
}
else if (items is Node node)
{
if (node.Key == key) item = node;
else if (create) items = node.Key < key ? new List<Node>(2) { node, (item = new Node(key)) } : new List<Node>(2) { (item = new Node(key)), node };
}
else
{
var nodeList = (List<Node>)items;
int lo = 0, hi = nodeList.Count - 1;
while (lo <= hi)
{
int mid = lo + ((hi - lo) >> 1);
node = nodeList[mid];
if (node.Key == key) { item = node; break; }
if (node.Key < key) lo = mid + 1; else hi = mid - 1;
}
if (item == null && create) nodeList.Insert(lo, item = new Node(key));
}
return item != null;
}
}