{"draftJsState":{"blocks":[{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Дерево - очень полезная структура данных. Помимо того, что про него спрашивают на собеседованиях, дерево помогает хранить иерархически упорядоченные данные. Например, дерево элементов HTML, дерево зависимостей сущностей в игре, дерево подразделений в компании. Имплементация дерева лаконична и проста:","type":"unstyled","key":"2tb1a"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"public class Tree(Tree? parent, T value) {\n public readonly List> Children = [];\n public readonly Tree? Parent = parent;\n public readonly T Value = value;\n \n public Tree Add(T value) {\n var child = new Tree(this, value);\n Children.Add(child);\n return child;\n }\n}","type":"blockquote","key":"ffsi"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":4,"offset":33,"style":"ITALIC"}],"text":"\nИспользуя связь по ссылке (ведь Tree это класс), мы можем быстро перемещаться по дереву. Имплементация выше предельно упрощена и лишь передаёт суть происходящего.","type":"unstyled","key":"90rhg"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"При работе с деревом, иногда возникает необходимость собрать ВСЕ дочерние элементы. Например, нам надо ответить на вопрос сколько людей работает во всём \"Департаменте IT\". Это означает, что мы должны просуммировать всех людей, входящих в родительский департамент, потом всех людей из дочерних отделов, а затем всех людей в отделах, входящих в эти отделы, вплоть до самого низа организационной иерархии.","type":"unstyled","key":"68p4t"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":5,"offset":85,"style":"ITALIC"}],"text":"Для решения этой задачи мы можем написать метод с использованием страшного и мощного yield:","type":"unstyled","key":"add15"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"\npublic IEnumerable> GetChildren() {\n if (Children.Count == 0) yield break;\n\n foreach (var child in Children) {\n yield return child;\n foreach (var subChild in child.GetChildren(true)) {\n yield return subChild;\n }\n }\n}","type":"blockquote","key":"ap2t5"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"","type":"unstyled","key":"132ed"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":5,"offset":81,"style":"ITALIC"}],"text":"Получается красиво и лакнично. Но, увы, очень прожорливо по памяти. Напомню, что yield не бесплатен и его мощь является следствием генерации объекта перечисления, который является классом, а, значит, каждое его инстанциирование загрязняет память. \"Вложенность\" при подобном подходе порождает ещё бОльший взрыв потребления памяти. Например, если у родителя 7 дочерних элементов, а у каждого из дочерних ещё 6, а у каждого из них ещё 5... короче, на 13700 элементах потребление памяти составляет 1.2Мб. Это много, особенно, если дерево используется постоянно.","type":"unstyled","key":"4jvj5"},{"data":{},"depth":0,"entityRanges":[{"key":0,"length":9,"offset":66}],"inlineStyleRanges":[],"text":"Впрочем, человечество заметило эту проблему и придумало не только алгоритмы обхода дерева, но и их эффективные имплементации.","type":"unstyled","key":"56ql1"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"[ThreadStatic]","type":"blockquote","key":"4n113"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"private static Stack>? _traverseBuffer;","type":"blockquote","key":"d94b0"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"...","type":"blockquote","key":"7fcev"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":" public IEnumerable> TraverseYield() {\n var buffer = _traverseBuffer ?? new Stack>(128);\n _traverseBuffer = null;\n\n foreach (var child in Children) {\n buffer.Push(child);\n }\n\n while (buffer.Count > 0) {\n var current = buffer.Pop();\n\n foreach (var child in current.Children) {\n buffer.Push(child);\n }\n\n yield return current;\n }\n\n _traverseBuffer = buffer;\n}","type":"blockquote","key":"95cku"},{"data":{"image":{"id":"662c076d31eace3a59dc64f9"}},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"C# Tree performance","type":"atomic:image","key":"4ht3o"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Побный подход не только ускоряет работу (почти в 4 раза), но и позволяет почти избавиться от аллокации (48 байт против 1.2Мб).","type":"unstyled","key":"9veel"},{"data":{},"depth":0,"entityRanges":[{"key":1,"length":9,"offset":33}],"inlineStyleRanges":[],"text":"Текст бенчмарка в комментариях в телеграмм.","type":"unstyled","key":"b3apj"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"","type":"marker","key":"MSVCednqxvxWmYHI0KsL"}],"entityMap":{"0":{"data":{"url":"https://en.wikipedia.org/wiki/Tree_traversal"},"mutability":"MUTABLE","type":"LINK"},"1":{"data":{"url":"https://t.me/csharp_gepard/89?comment=635"},"mutability":"MUTABLE","type":"LINK"}}},"mentions":[]}