деревья и леса - страница 2

Новый комментарий
 
secret:

По стопам Гудылина?)

Такие высоты для меня совершенно недосягаяемы - ограничусь Мандельбротом)

 
Igor Makanu:

сами деревья портировать в MQL не сложно

В С++ использовал библиотеку tree.hh - работа с деревьями в стиле STL. Было бы весьма неплохо портировать её в MQL5, но сомневаюсь что это возможно)

tree.hh: an STL-like C++ tree class
  • tree.phi-sci.com
The library for C++ provides an STL-like container class for n -ary trees, templated over the data stored at the nodes. Various types of iterators are provided (post-order, pre-order, and others). Where possible the access methods are compatible with the STL or alternative algorithms are available. The library is available under the terms of...
 
Aleksey Nikolayev:

Не нашёл на форуме обсуждений реализации этих структур данных. Как их лучше (в смысле скорости исполнения и удобства программирования) реализовать на MQL5 - через массив или ссылки?

Если конкретнее, то интересуют деревья (и леса) общего вида (не бинарные), с вершинами (и/или рёбрами) помеченными простыми структурами.

Вам какие деревья нужны собсно? 

Случайные леса для обучения Ваших моделей?

Бинарные деревья поиска?

Идеально сбалансированные 2,3-деревья?

b-деревья?

Префиксные trie-деревья?

Красно-черные деревья?

Дерево Меркла для валидации цепочек данных?

Что значит "помечены простыми структурами"? Типа генерики?

 
Vasiliy Sokolov:

Вам какие деревья нужны собсно? 

Случайные леса для обучения Ваших моделей?

Бинарные деревья поиска?

Идеально сбалансированные 2,3-деревья?

Красно-черные деревья?

Что значит "помечены простыми структурами"? Типа генерики?

Если "генерик" означает общий вид, то да. Иногда их ещё вроде бы называют "розовыми" - rose tree.

"Помеченые" - вроде стандартное обозначение, что в каждой вершине (и/или ребре) хранятся "метки" - значения одного типа.

 
Aleksey Nikolayev:

В С++ использовал библиотеку tree.hh - работа с деревьями в стиле STL. Было бы весьма неплохо портировать её в MQL5, но сомневаюсь что это возможно)

с STL сложно будет портировать в MQL, по причине отсутствия аналогичных шаблонов в MQL - писали тут, но для себя 

про SQL - если в массивах можете сделать свое исследование, то SQL прекрасно с этим работает, но сделать быстро выборку в массиве Вы должны сами алгоритм поиска продумать, а БД уже готова к этому из коробки

ЗЫ: Хабр... дает много вариантов уже из готового, когда еще находишься в стадии изысканий https://habr.com/ru/post/303374/

 
Igor Makanu:

с STL сложно будет портировать в MQL, по причине отсутствия аналогичных шаблонов в MQL - писали тут, но для себя 

про SQL - если в массивах можете сделать свое исследование, то SQL прекрасно с этим работает, но сделать быстро выборку в массиве Вы должны сами алгоритм поиска продумать, а БД уже готова к этому из коробки

ЗЫ: Хабр... дает много вариантов уже из готового, когда еще находишься в стадии изысканий https://habr.com/ru/post/303374/

Нашёл дерево в библиотеке GLib. Наверное, попытаюсь сделать что-нибудь похожее (по интерфейсу)

 
Aleksey Nikolayev:

Нашёл дерево в библиотеке GLib. Наверное, попытаюсь сделать что-нибудь похожее (по интерфейсу)

понятно, Вы ищете N-арное дерево

никогда не делал, Ваш пример объёмный, попробовал портировать первый попавшийся пример попроще: https://www.geeksforgeeks.org/depth-n-ary-tree/

была уже заготовка для списков, которую помог @fxsaber сделать https://www.mql5.com/ru/forum/85652/page16#comment_12346740

ну и соберем в MQL-код:

#include <Arrays\List.mqh>
template<typename T>class List
  {
private:
   template <typename TT>
   class TTCList : public CList
   {
   public:  
   virtual CObject  *CreateElement(void) { return(new TT); }
   };
   TTCList<T>            *mlist;
public:
   void List()                { mlist=new TTCList<T>;                               }
   void ~List(void)           { delete mlist;                                       }
   int ArraySize(void)        { return(mlist.Total());                              }
   T* operator[](int index)   { return(mlist.GetNodeAtIndex(index));                }
   void  AddValue (T* value)  { mlist.Add(value);                                   }
   void  Delete(int pos)      { mlist.Delete(pos);                                  }
   string TypeName()          { return(typename(T));                                }
  };
//+------------------------------------------------------------------+
class Node : public CObject
{
public:
   string key;
   List<Node> *child;
   Node()                  {                             }
   Node(string k) :key(k)  { child = new List<Node>();   }
   ~Node()                 { delete child;               }
}; 
//+------------------------------------------------------------------+
int depthOfTree(Node *ptr)
   {
      // Base case
      if (ptr == NULL) return(0);
      // Check for all children and find the maximum depth
      int maxdepth = 0;
      for(int i = ptr.child.ArraySize() - 1; i >= 0; i--)
      {
         Node *it = ptr.child[i];
         maxdepth = fmax(maxdepth, depthOfTree(it));
      }
      return maxdepth + 1 ;
   }
//+------------------------------------------------------------------+
void OnStart()
{
   Node *root = new Node("A");
   root.child.AddValue(new Node("B"));
   root.child.AddValue(new Node("F")); 
   root.child.AddValue(new Node("D")); 
   root.child.AddValue(new Node("E"));
   root.child[0].child.AddValue(new Node("K")); 
   root.child[0].child.AddValue(new Node("J")); 
   root.child[2].child.AddValue(new Node("G")); 
   root.child[3].child.AddValue(new Node("C")); 
   root.child[3].child.AddValue(new Node("H")); 
   root.child[3].child.AddValue(new Node("I"));
   root.child[0].child[0].child.AddValue(new Node("N")); 
   root.child[0].child[0].child.AddValue(new Node("M")); 
   root.child[3].child[2].child.AddValue(new Node("L"));

   Print(depthOfTree(root));                                   // 4

   Print(root.child[3].child[2].child[0].key);                 // L
   for(int i=root.child[3].child.ArraySize()-1; i>=0; i--)
   {
      Node n = root.child[3].child[i];
      Print(n.key);                                            // L     I       H       C
   }
   delete root;
}
 
Igor Makanu:

понятно, Вы ищете N-арное дерево

никогда не делал, Ваш пример объёмный, попробовал портировать первый попавшийся пример попроще: https://www.geeksforgeeks.org/depth-n-ary-tree/

была уже заготовка для списков, которую помог @fxsaber сделать https://www.mql5.com/ru/forum/85652/page16#comment_12346740

ну и соберем в MQL-код:

Спасибо, очень интересно. Всё же, опасаюсь использовать стандартную библиотеку (после неприятного опыта с библиотекой статистики). Думаю, полноценные деревья (со всеми видами обхода, свёртками и тд) для анализа делать в других языках (делал в Хаскеле, но хочу попробовать Rust). На MQL5 же - только какие-то усечённые варианты на основе динамических массивов с минимальным необходимым функционалом и только при наличии практической необходимости.

 
Aleksey Nikolayev:

Спасибо, очень интересно. Всё же, опасаюсь использовать стандартную библиотеку (после неприятного опыта с библиотекой статистики). Думаю, полноценные деревья (со всеми видами обхода, свёртками и тд) для анализа делать в других языках (делал в Хаскеле, но хочу попробовать Rust). На MQL5 же - только какие-то усечённые варианты на основе динамических массивов с минимальным необходимым функционалом и только при наличии практической необходимости.

опять к вопросу ... друг спрашивает, что хотите найти в этих деревьях?

если тестер не нужен - вопросов нет, скорее всего можно и софт найти который с графами работает из коробки, т.е. нет смысла писать и программировать

если все таки MQL - сомневаюсь, что Rust так просто к "тестеру прикрутить"


мой пример только данные хранить, еще работы много - обход дерева, добавление узлов....

прогуглил, ибо сам теорией графов все мечтаю посмотреть на графики - опять к SQL вернулся, вот даже готовые SQL-запросы в статье "Деревья в SQL" (3 части - ссылки вверху) http://www.codenet.ru/db/other/trees/ 

 
Igor Makanu:

опять к вопросу ... друг спрашивает, что хотите найти в этих деревьях?

если тестер не нужен - вопросов нет, скорее всего можно и софт найти который с графами работает из коробки, т.е. нет смысла писать и программировать

если все таки MQL - сомневаюсь, что Rust так просто к "тестеру прикрутить"


мой пример только данные хранить, еще работы много - обход дерева, добавление узлов....

прогуглил, ибо сам теорией графов все мечтаю посмотреть на графики - опять к SQL вернулся, вот даже готовые SQL-запросы в статье "Деревья в SQL" (3 части - ссылки вверху) http://www.codenet.ru/db/other/trees/ 

Нужна возможность всех видов обхода деревьев (штук шесть их), свёртка (фолдинг), чтение/запись в файл, добавление/удавление ветвей. Удобно в хаскеле, но он медленный. Думаю попробовать в rust, там есть много уже готового - не люблю делать всё с нуля) SQL, наверное, тоже окажется медленным.

Если в содержательном плане, то это дерево из ценовых вершин (в духе идей Мандельброта) для подсчёта мультифрактального спектра. Сильно сомневаюсь, что дойдёт дело до тестера - просто поиграться в математику немного) Периодически MQL5 начинает казаться языком вполне подходящим для общих целей, но потом быстро понимаешь что опять ошибся)

trees - Rust
trees - Rust
  • docs.rs
General purpose tree library. The current version provides two implementions of heap-allocated, child-sibling linked trees and one implementation of vec-backed tree. The default implementation is linked::fully, which stores previous/next sibling and parent/child pointers in one node, with size information tracked. The alternative linked tree is...
1234
Новый комментарий