Оптимизация построения дерева из базы данных в .NET

Загрузить примеры к статье - 24.9 кб

Введение

Но недавно я начал использовать ANTS Profiler и обнаружил, что построение дерева было довольно медленным. Я проверил мой старый код снова и нашел способ значительно его ускорить...

Эта статья объясняет, как рекуррентная основа DataView может быть использована для значительных улучшений его представления.

Замечание: метод, который здесь представлен, не основывается на восходящей сортировке DataView. Это будет работать для обратно отсортированного и даже для не отсортированного вовсе случая. Это достаточно полезное свойство для случая, когда данные дерева извлекаются из внешнего, не управляемого источника.

Что содержится в ZIP?

ZIP-файл содержит код библиотеки для построения дерева и код тестового приложения. Также туда включено дерево DataSet в XML формате. Дерево состоит из 745 узлов, глубина дерева - 5 уровней. Тестовое приложение представляет из себя простое консольное приложение, которое создает TreeNodes, используя "медленный" и "быстрый" способы и показывает время построения в секундах. Эта пятикратная разница позволяет лучше понять преимущества такого подхода.

С точки зрения дерева

В моем первоначальном коде я рассматривал проблему с точки зрения дерева. У дерева всегда есть корневой узел (root node), так что я начал именно с него и исследовал его узлы-потомки в DataView. Для каждого узла-потомка я проверял его узлы-потомки и так далее.

DataSet содержит коллекцию записей (records) с тремя колонками: NodeID, ParentNodeID и NodeText. Данные рекуррентны: ParentNodeID ссылается на NodeID родительского узла. База данных (database) убеждается в соблюдении следующего правила: узел не может быть присоединен к не существующему родительскому узлу. Из-за этого правила, корневой узел (root node) вынужден иметь указатель на самого себя.

  
public class 
TreeNode
  {
    // Объявления
    
private int id;               
// ID узла
    
private TreeNode parentNode;  
// Родительский узел узла
    
private string text;          
// полезная нагрузка узла (та информация, которую мы будем хранить в собственных целях)
    
private ArrayList childNodes; 
// Содержит узлы-потомки описываемого узла

    
// Конструктор
    
public 
TreeNode(int id, TreeNode parentNode)
    
{
      // Инициализация УзлаБыстрогоДерева (FastTreeNode)
      
this.id = id;
      
this.parentNode = parentNode;
      
this.text = "";
      
childNodes = new ArrayList();

     
 // Проверяем был ли указан родитель
      
if (parentNode != null)
  
    {
        
///Если да, то даем знать родительскому узлу, что у него появился новый узел
        
parentNode.ChildNodes.Add(this);
      }
    }

    
// Свойства
    public 
int ID
    {
      get 
{return id;}
    }

    public 
TreeNode ParentNode
    {
      get 
{return parentNode;}
      
set
      {
        parentNode = value;
        
// Говорим родительскому узлу, что у него появился новый потомок,
        
//  если возможно, и если необходимо
        
if (parentNode != null
 && !parentNode.ChildNodes.Contains(this))
          
parentNode.ChildNodes.Add(this);
      }
    }

    
public string Text
    {
      
get {return text;}
      
set {text = value;}
    }

    
public ArrayList ChildNodes
    {
      
get {return childNodes;}
    
}
  }

Класс TreeNode в основном отражает структуру базы данных. У него есть идентификатор - ID, и он указывает на родителя. Корневой узел (root node) имеет нулевого null родителя. В качестве простейшей "полезной нагрузки" узел может иметь свойство Text.

public TreeNode LoadTree(DataView dataTree)
    
{
      // Подготавливаем результирующий корневой узел (тот, который возвращается функцией).
      
TreeNode rootNode = null;

      
// Цикл по элементу dataview
      
foreach (DataRowView dataNode 
in dataTree)
      {
        
// Храним текущую запись в определенных переменных
        
int 
nodeID = (int)dataNode["NodeID"];

        int 
parentNodeID = (int)
dataNode["ParentNodeID"];
        
string 
text = dataNode["NodeText"].ToString();

        
// Проверяем является ли текущий узел корневым узлом
        
if (nodeID == parentNodeID)
        {
          
//  Если да, то создаем узел и начинаемt
          
// искать его узлов-потомков
          
rootNode = new 
TreeNode(nodeID, null);
          
rootNode.Text = text;
          LoadChildNodes(rootNode, dataTree);
        }
      }

      
// Возвращаем результат
      
return rootNode;
    }

    
private 

void LoadChildNodes(TreeNode parentNode, DataView dataTree)
    
{
      // Цикл по элементу dataview
      
foreach (DataRowView dataNode 
in dataTree)
      
{
        
// Храним текущую запись в определенных переменных
        
int
 nodeID = (int)
dataNode["NodeID"];
        
int 
parentNodeID = (int)
dataNode["ParentNodeID"];
        
string 
text = dataNode["NodeText"].ToString();

        
// Проверяем является ли текущий узел корневым,
        
// является он узлом - потомком
        
// переданного в параметрах функции родительского узла
        
if (nodeID != parentNodeID && 
parentNodeID == parentNode.ID)
        {
          
// Если да, то создаем узел
          
// и начинаем поиск его узлов-потомков.
          
TreeNode node = new TreeNode(nodeID, parentNode);
          
node.Text = text;
          LoadChildNodes (node, dataTree);
        }
      }
    }

Метод LoadTree вызывает рекурсивный метод LoadChildNodes. Это делает код достаточно компактным, в то же время, появляется одна большая проблема: для каждого узла он сканирует DataView полностью, включая уже обработанные узлы. Таким образом, для тестового элемента DataSet, будут прочитаны 555770 записей. Учитывая также тот факт, что операция чтения DataView является не такой уж быстрой, получается что общее время, затрачиваемое на расположение всех узлов, довольно большое.

Также, если вы попытаетесь загрузить сильно разветвленное дерево, то вы можете столкнуться с проблемой переполнения стека(stack overflow).

** Всему виной рекуррентность. Когда вызывается новая функция, программа обязана сохранить все необходимые данные (значение различных переменных - точнее их адреса), все это сохраняется в стеке (области памяти, которая выделяется под нужды программы), поэтому когда вы многократно вызываете такие рекуррентные функции, объем данных которые должна хранить программа растет и в определенный момент выделенной для хранения этих данных памяти не хватает(точнее чаще всего новые данные записываются поверх старых, а значит, старые данные теряются). И происходит сбой - обычно программа не может выйти из функции или восстановить значение переменных (т.к. эта информация была утеряна).

С точки зрения DataView

DataView имеет линейный характер: он начинается с записи 0 и заканчивается на записи x. Простым перебором записей с 0 по x создание каждого узла выглядит на первый взгляд невозможным: если родительский узел не был создан ранее, то не возможно создать текущий узел. Ведь так?

Весь фокус в том, чтобы воплотить идею о том, что каждый объект должен быть полноценным. Мне ничего не известно о родительском узле, но я знаю ID, который он будет иметь. Так что я могу создать новый узел зная только родительский ID и не имея самого родительского узла, и сохранить его в Hashtable. Если позднее я найду ID пустого узла в DataSet, я не буду его создавать, а получу сохраненный узел из Hashtable и заполню пустые не заданные ранее свойства.

public TreeNode LoadTree(DataView dataTree)
    
{
      // Перебираем все записи в dataview
      
foreach (DataRowView dataNode in 
dataTree)
      {
        
// Сохраняем текущую запись в определенных переменных
        
int nodeID = (int)
dataNode["NodeID"];
        
int 
parentNodeID = (int)dataNode
["ParentNodeID"];
        
string
 text = dataNode["NodeText"].ToString();

        
// Проверяем был ли ранее создан этот узел
        
if (nodeList.Contains(nodeID))
        {
          
// Если да, заполняем недостающие свойства
          
TreeNode node = (TreeNode)nodeList[nodeID];
          node.Text = text;
          
// Если узел не является корневым,
          
// и не задан пока родитель, то просматриваем или создаем
         
 if
 (nodeID != parentNodeID && node.ParentNode == null)
 
         {
            TreeNode parentNode = null;
            
// Проверяем был ли ранее создан узел-родитель
            
if (nodeList.Contains(parentNodeID))
           
 {
              // Если да, то используем его
              
parentNode = (TreeNode)nodeList[parentNodeID];
            }
            
else
            {
              
// Родительский узел еще не существует, поэтому частично создаем.

// родительский узел (частично, потому что нам известно лишь его ID).


              parentNode = new 
TreeNode(parentNodeID, null);
              
nodeList.Add(parentNodeID, parentNode);
            }
            
node.ParentNode = parentNode;
          }
        }
        
else
        {
          
// Новый узел, проверяем не является ли он корневым
          
if (nodeID == parentNodeID)
          {
           
 // Если да, то нет необходимости искать или создавать родительский узел
 
           TreeNode node = new 
TreeNode(nodeID, null);
            
node.Text = text;
            nodeList.Add(nodeID, node);
          }
          
else
          {
            
// Новый узел-потомок
            
TreeNode parentNode = null;
           
 // Проверяем, создан ли уже родительский узел
            
if (nodeList.Contains(parentNodeID))
            {
              
// Если да, то используем его
              
parentNode = (TreeNode)nodeList[parentNodeID];
            }
            
else
            {
              
// Если нет, то частично создаем родительский узел.
              
parentNode = new TreeNode(parentNodeID, 
null);
              
nodeList.Add(parentNodeID, parentNode);
            }

            
// Создание нового узла
            
TreeNode node = new TreeNode(nodeID, parentNode);
            
node.Text = text;
            nodeList.Add(nodeID, node);
          }
        }
      
} 
     
      // Поиск корневого узла
      
IDictionaryEnumerator nodeEnumerator = nodeList.GetEnumerator();
      
while (nodeEnumerator.MoveNext())
      {
        
TreeNode node = (TreeNode)nodeEnumerator.Value;
        if 
(node.ParentNode == null)
          
return node;
      }

      
// В случае, если узел не найден, ничего не возвращается
      
return null;
    }

МетодLoadTree здесь немного длиннее, но он читает каждую запись только один раз. Вместо того, чтобы искать узлы в DataView, они используют поиск на основе гораздо более быстрого элемента Hashtable. Единственное необходимое дополнение, это локализация (определение положения) корневого узла (root node), где превосходство имеет версия SlowTree: Это начальная точка. Дополнительное время затрачиваемое этим улучшенным кодом фактически не заметно по сравнению со скоростью построения самого дерева.

Результаты

На моем 1.8GHz процессоре, тест-приложению потребовалось чуть более, чем 2 секунды для построения дерева медленным способом. Используя "быстрый" метод, это заняло только около 0.004 секунды для построения того же дерева. Что составляет прирост скорости примерно в 500 раз!

Замечание: конечно, тестовое дерево очень простое дерево. В реальных приложениях каждый узел дерева может содержать "полезную нагрузку" не только в виде текста. Это возможно немного замедлит процесс построения, но все равно это будет гораздо быстрее, чем обычное "медленное" дерево. Я наблюдал увеличение в скорости некоторых моих приложений аж в 400 раз.

Заключение

Приложение может показывать плохие результаты когда:

• Они вызывают (fast) методы очень часто, или
• Они вызывают методы, которые очень медленны, или, что хуже всего,
• Они часто вызывают методы, которые являются очень медленными.

Решение, предложенное в этой статье, избегает этого путем сведения к минимуму обращений к медленному методу (чтение записей из |DataView|). Общеизвестно, что из-за тесных связей между объектами родителя и потомка единственным выходом является умное использование той малой информации, которая известна об объектах.

Автор: NielsHoldijk (англ. оригинал). Перевод выполнен cronOS для Realcoding.NET