1

Есть словарь, в который постоянно добавляются объекты. Отображать словарь на ui не получилось, поэтому все преобразуется в плоский список. Возможно код написан не совсем оптимально - наблюдаются аллокации (например, если приложение будет работать весь день, оперативная память будет "кушать" пару гигабайт). Но сейчас вопрос другой- как мне правильно удалять элементы из словаря? Я написал метод Flatten, могу вот так использовать:

var itemToDelete = Tree.Flatten().FirstOrDefault(**condition**)

Я не совсем понимаю, как удалить из дерева найденный элемент. Из списка удалять нельзя, т.к он основывается на дереве и "удаленный" элемент потом будет снова в дереве

Вот остальной код:

public class Trie
{
    private readonly Dictionary<string, Trie> _trieChildren = new();
    private AvaloniaList<Trie> _visibleChildren = new();
    public IAvaloniaReadOnlyList<Trie> VisibleChildren
          => _visibleChildren;                          

    private void AppendItems()
    {
       var flatTrieList = new AvaloniaList<Trie>();
 
       AppendItems(     
          flatTrieList,
          this );      

      _visibleChildren = flatTrieList;
    }

    private void AppendItems(                                     
       AvaloniaList<Trie> flatTrieList,                          
       Trie node )                                               
    {                                                             
       flatTrieList.Add( node );                                 
                                                          
       if ( !node.IsExpanded                                     
           || IsShowMessagesChecked ) return;                   
                                                          
       foreach ( var ch in node._trieChildren )                  
           AppendItems( flatTrieList, ch.Value );                
    }                                                             

    public IEnumerable<Trie> Flatten()            
    {                                             
       yield return this;                        
                                              
       foreach (var trie in _trieChildren.Values)
       foreach (var child in trie.Flatten())     
          yield return child;                   
    }                                             
}
3
  • Вообще, из дерева префиксного поиска обычно не удаляют элементы – это же своего рода индекс в памяти. Какие у вас кейсы удаления элементов из дерева? Также, у вас в коде очевидно намешана логика хранения данных и их представления, что не очень хорошо, лучше разделять такие вещи. Что касается удаления - то удалять какой-либо элемент из возвращенной коллекции IEnumerable<Trie> бессмысленно, структура дерева от этого не изменится. Для удаления из дерева нужно обойти его, найдя нужный элемент, и удалить. Можно где-то посмотреть более полный код вашего класса Trie, чтобы дать рекомендации?
    – Max S
    14 дек 2022 в 15:21
  • Да, конечно, могу показать полный код, который выглядит отвратительно, как мне кажется и немного стыдно.. gist.github.com/INTERNALINTERFERENCE/… Сейчас дерево строится, но появилась задача - добавить поиск и возможность удалять некоторые элементы из дерева (дерево отображает сообщения, которые приходят из шины по протоколу mqtt. Этот протокол позволяет отправить пустой массив byte. Если пустой массив был отправлен, элемент из дерева, должен исчезнуть)
    – user366767
    14 дек 2022 в 17:05
  • может у вас получится это отрефакторить, ну или дать советов
    – user366767
    14 дек 2022 в 17:06

1 ответ 1

1

Дисклеймер: пришлось догадываться о некоторых вещах касательно назначения и логики работы класса, поэтому если что-то не так интерпретировал – предлагаю обсудить в комментариях и дополнить/изменить ответ.

Ознакомившись с исходным кодом, выложенным здесь:

  1. Хотелось бы обратить внимание, что вы назвали ваш класс Trie, что не совсем соответствует функциям, которые он выполняет. Термином Trie принято называть префиксное дерево поиска (более точная информация на англ. wiki). У вас же это просто обычное дерево каталогов. Лучше выбрать для класса другое имя – например, просто Tree, чтобы не вводить в заблуждение ни себя, ни тех, кто смотрит ваш код.

  2. Рефакторить в классе безусловно есть что, но эта тема для отдельного ответа, поэтому здесь сфокусируемся на вашей текущей задаче.

  3. Просто удалять какой-либо элемент из возвращенной методом Flatten() коллекции IEnumerable<Trie> бессмысленно, структура дерева от этого не изменится. Для удаления из дерева нужно обойти его, найдя нужный элемент, и удалить (возможно даже рекурсивно).

  4. Исходя из структуры класса нужно полагать, что ключом объектов в дереве является массив строк (string[] topic), верно? Тогда и удаляем мы объект по такому же ключу? Если так, то мы можем найти объект по ключу так, например (метод должен вызываться у корня дерева):

     public Trie Find(string[] topic)
     {
         if (topic == null) return null;
    
         var currentTree = this;
         for (int i = 0; i < topic.Length; i++)
         {
             if (!currentTree._trieChildren.TryGetValue(topic[i], out currentTree))
                 return null; // или бросать InvalidOperationException(), в зависимости от ожидаемой логики
         }
    
         return currentTree;
     }
    
  5. Как всё же удалить элемент из дерева? Неважно, как мы его получили: через метод Find(...), описанный выше или же через Tree.Flatten().FirstOrDefault(...) - и в первом и во втором случае мы получим инстанс класса Trie, который нам нужно удалить из дерева. Удалить из дерева – это значит убрать элемент из списка поддеревьев его родительского узла. У вас в классе уже реализовано свойство public Trie? Parent { get; }, так что всё будет довольно просто:

     // удалить текущий узел из дерева, которому он принадлежит 
     public void Detach()
     {
         if (Parent == null) return; // или бросать InvalidOperationException(), в зависимости от ожидаемой логики
    
         Parent._trieChildren.Remove(Part); // удаляем "себя" из словаря поддеревьев родительского узла
    
         // вероятно, здесь ещё нужно пересчитать MessagesCount, TopicsCount у узла Parent
    
         // если у вас логически в дерева есть "листья" и поддеревья, а удаляете вы тогда листья как правило, то можно проверить если у родителя не осталось больше поддерьев, и его тогда тоже рекурсивно удалить:
         if (Parent._trieChildren.Count == 0)
             Parent.Detach();
     }
    

Использовать можно так:

Tree.Flatten().FirstOrDefault(...).Detach();
// или
Root.Find(...).Detach();

Надеюсь, мой ответ поможет разобраться с возникшей сложностью.

5
  • Спасибо за ответ! Мне показалось, что это префиксное дерево, где префикс - это "/", поэтому и название такое. Ну хорошо, я сейчас попробую применить все то, что вы написали. А по поводу рефакторинга.. Что именно вам не понравилось? Могу отдельный вопрос задать
    – user366767
    15 дек 2022 в 8:59
  • 1
    @penancewarrior это, конечно, похоже на префиксное дерево (более того, некоторые реализации префиксного дерева очень похожи на вашу), но есть важные отличия. В префиксном дереве ребра всё-таки обычно интерпретируют минимально делимый элемент - символ, если мы говорим про строки. Но важнее то, что в префиксных деревьях строго ограничено (математической мощностью алфавита) максимальное число поддеревьев у каждого узла, что позволяет делать крутые оптимизации при операциях вставки и поиска. У вас же у каждого узла может быть любое (ограниченное памятью и структурами данных) число дочерних узлов.
    – Max S
    15 дек 2022 в 9:17
  • 1
    @penancewarrior по поводу рефакторинга - отдельный вопрос, думаю, будет не совсем уместен здесь. Я оставлю вам свои комментарии под вашим кодом на гитхабе.
    – Max S
    15 дек 2022 в 9:17
  • @penancewarrior добавил комментарий к вашему коду на гитхабе.
    – Max S
    15 дек 2022 в 11:50
  • спасибо, я все посмотрел, поправил, но с одним я не согласен - вы советуете убрать метод Update и вынести все в ForceResync. Если посмотреть на метод ForceResync, то видно, что он вызывает Root.Update(). Если вынести в Update, то это будет немного другая логика, как мне кажется. ForceResync вообще вызывается при инициализации TreeRoot
    – user366767
    15 дек 2022 в 13:01

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.