Обсуждение статьи "Основы программирования на MQL5 - Списки"

[MetaQuotes]

Опубликована статья Основы программирования на MQL5 - Списки:

Новая версия языка MQL дала программисту, работающему над своими проектами МТС, эффективные инструменты для реализации сложных задач. Нельзя отрицать тот факт, что программные возможности языка стали намного шире. Чего стоит хотя бы наличие арсенала ООП в MQL5. Да и нельзя, пожалуй, не упомянуть Стандартную библиотеку. Судя по тому, что есть ошибка за кодом 359, скоро появятся шаблоны классов.

В своей статье я хотел бы затронуть тему, которая может явиться своего рода расширением или продолжением тем, описывающих типы данных и их совокупности. Здесь сошлюсь на статейный материал MQL5.community. Принципы и логику работы с массивами очень подробно и системно описал Дмитрий Федосеев (Integer) в своей статье «Основы программирования на MQL5 - Массивы».

Итак, предлагаю заняться сегодня списками, а точнее связными линейными списками. Мы начнём с того, что изучим состав, смысл и логику построения списка. Затем посмотрим на уже имеющиеся инструменты в Стандартной библиотеке, касающиеся нашей темы. В заключительной части я представлю примеры того, как можно использовать списки в своей работе на языке MQL5.

Рис.1 Узлы для односвязного списка

Автор: Dennis Kirichenko

[Sergey Pavlov]

Спасибо автору за отличную статью!

[Sergey Dzyublik]

Кроме узла для односвязного списка есть ещё другие. Пожалуй, самым популярным является узел для двусвязного списка.

есть ещё другие, кто-что? как-то незаконченная мысль 

Итак, возможности узла для двусвязного списка будут аналогичны тем, которыми обладает односвязный узел, разве что нужно будет ещё обработать указатель на предыдущий узел. 

разве нужно обработать указатель на предыдущий узел, чтобы обладать возможностями односвязного узла? Смысл который хотел донести автор уловил, но сама формулировка - не очень....

Рис.3 Узлы для кольцевого двусвязного списка 

1) самый верхний указатель - стрелка чуть кривая

2) понимаю, что, возможно, это стиль статей - но описание рисунка уж очень мелким шрифтом и довольно тускло (личное мнение плохого зрения)

Ещё нам понадобится такой узел, который будет обслуживать потребности двусвязного списка. От предыдущего вида он  отличается тем, что вмещает в себя ещё один указатель, который ссылается на предыдущий узел. И естественно, что такой узел головного элемента списка будет равен NULL.

 1) От предыдущего вида - от чего? на сколько предыдущего? Почему я должен искать что под предыдущим автор имеет ввиду "Узел для односвязного списка", а может я ошибаюсь.

 2)  "узел головного элемента списка будет равен NULL". Узел, или указатель? Возможно в виду ранее изложенного утверждения  "В списке можно хранить не элементы, а узлы." правильнее было бы сказать:

 " один из указатель головного узла  двусвязного списка будет равен NULL" 

А вот в хвостовом узле ссылка на следующий пустой не будет, т.к. она заполнится указателем на голову.

 1) ссылка не будет -  не будет кого-чего ???  падежи не держатся

 2) А вот в хвостовом узле ссылки на следующий пустой (кого-что???) не будет. Незаконченная мысль

 3)  она (ссылка) заполнится указателем. Ссылка заполняется указателем, или все таки указатель будет иметь ссылку куда-то ???

Что касается операций удаления, то они практически дублируют аналогичные из группы добавления:

• удалить головной узел;
• удалить хвостовой узел;
• удалить узел из указанного места списка;
  
• деструктор.

1) они практически дублируют аналогичные (кого-что???) из группы добавления. Опять незаконченная мысль

2) разве удалить узел из указанного места списка  не является общим случаем "для удалить головной узел" и "удалить хвостовой узел" ??? аналогично касается и добавить

3)  "Что касается операций удаления", а перед этим было "К методам добавления можно отнести следующие:" ( там методы, тут операции - хочется одного формата)

 

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

[Anatoli Kazharski]

Мне понравилось. Спасибо. Хорошо, когда после прочтения появляются идеи, где это можно применить у себя. )

[Denis Kirichenko]

tol64:
Мне понравилось. Спасибо. Хорошо, когда после прочтения появляются идеи, где это можно применить у себя. )

tol64, спасибо за мнение авторитетного специалиста  :-)

[Denis Kirichenko]

2ALXIMIKS: это вы ещё не читали литературы по программированию... В общем и целом, с Вашей стороны - это придирки...

[Anatoli Kazharski]

denkir:
tol64, спасибо за мнение авторитетного специалиста  :-)

Я себя специалистом не считаю и авторитетом тоже. И это не от скромности, а действительно так. ))) Здесь есть программисты, которые многократно опытнее и в программировании и в математике и в трейдинге. А мне ещё плыть и плыть. )))

[Denis Kirichenko]

tol64:
Я себя специалистом не считаю и авторитетом тоже. И это не от скромности, а действительно так. ))) Здесь есть программисты, которые многократно опытнее и в программировании и в математике и в трейдинге. А мне ещё плыть и плыть. )))

По-моему, авторитет штука субъективная. Это как признание суверенитета одной страны другой страной...

Цитата:

Авторитет заключается в признании за субъектом (носителем) выдающихся достижений, знаний, умений, навыков, способностей, его особого положения в обществе...

Так вот, Ваш мною признаётся :-)

tol64, ждём новых Ваших статей.

[Vasiliy Sokolov]

В следующем блоке (Пример 4) предлагаю обратить внимание на один из главных недостатков такого контейнера данных, как список, - скорость доступа к элементам. Дело в том, что доступ к элементам списка осуществляется линейно, а в случае со списочным классом CList - бинарно, что немного уменьшает трудоёмкость алгоритма.

При линейном поиске имеем трудоёмкость вида O(N), а при бинарном - log2(N).

При линейном поиске имеем трудоёмкость вида O(N), а при бинарном - log2(N).

Вот такой код для примера доступа к элементам совокупности данных:

Где вы нашли бинарный доступ к элементам CList со сложностью log2(N)!?

CList - список, а для бинарного доступа со сложностью log2(N) требуется моментальный переход к узлу с индексом CurrentIndex +/- (СurrentIndex/2), где CurrentIndex - текущий узел в списке.

В реализации CList используется стандартный QuickSearch(), который в случае сортировки действительно ищет элемент обращаясь к узлу  CurrentIndex +/- (СurrentIndex/2). Однако сам этот узел ищется функцией GetNodeAtIndex(), а в ней ни каких чудес нет. Вся сложность операции доступа ложиться именно на нее, конкретно на эти строки:

if(revers)
     {
      //--- search from right to left
      for(;i>index;i--)
        {
         result=result.Prev();
         if(result==NULL)
            return(NULL);
        }
     }
   else
     {
      //--- search from left to right
      for(;i<index;i++)
        {
         result=result.Next();
         if(result==NULL)
            return(NULL);
        }
     }

Взглянув на них сразу становиться понятным, что сложность поиска элемента составляет в пределе O(N/2), т.к. список двунаправленный, и значит доступ к элементу с одного из концов не будет превышать N/2 переходов. Автору неплохо было бы более досконально разбираться в алгоритме, прежде чем писать статью о нем.

По собственному опыту могу сказать, что т.к. работа с данными почти всегда связана с их поиском и сортировкой, то использовать классический CList для реальных задач практически  всегда неэффективно. Список силен прежде всего в комбинированных коллекциях, где доступ по индексу сочетается с доступом по списку.

Еще почему-то мало кто задумывается о том, что переход по указателю, гораздо, гораздо медленнее чем прямая адресация по индексу. Перебрать тысячу раз  result.Next() гораздо медленне чем тысячу раз перебрать индекс в for. 

[TheXpert]

denkir:

Комом.

Начиная сразу с картинок. Указатель идет на ноду а не данные, данные всего часть ноды, т.е. сразу коллизия с реализацией и потенциальная непонятка.

Текст по большей части нормальный, справедливости ради.

По реализации. Такие вещи реализовываются шаблонами. Оптимальный вариант представление контейнеров в STL, правда здесь с итераторами и функторами пролет, хотя придумать скорее всего что-то можно.

В итоге ваши пустые виртуальные методы выглядят не просто непонятно, а просто вырвиглаз. Сортировка ) листа доставила. Реализация и даже декларация некоторых методов вызывает сомнение и даже недоумение.

Инкапсуляции ноль.

Откровения про сложность и бинарный(!) поиск у списка(! гг) добили.

В итоге имеем текущую просто ВЕЗДЕ непонятную и неудобную хрень, не пригодную к использованию даже как пример для обучения (имхо).

Без обид ) хотите в программисты учитесь программировать НОРМАЛЬНО. Вы в состоянии реализовать это намного лучше.

C-4:

Взглянув на них сразу становиться понятным, что сложность поиска элемента составляет в пределе O(N/2), т.к. список двунаправленный, и значит доступ к элементу с одного из концов не будет превышать N/2 переходов. Автору неплохо было бы более досконально разбираться в алгоритме, прежде чем писать статью о нем.

Вам бы тоже не мешало бы освежить память, что такое O, написанное выше во-первых неправильно посчитано, во-вторых неправильно записано.

_____________________________________

Самое интересное состоит в том, что это далеко не худшая статья ресурса.

[Vasiliy Sokolov]

TheXpert:

...

Без обид ) хотите в программисты учитесь программировать НОРМАЛЬНО. Вы в состоянии реализовать это намного лучше. 

Вам бы тоже не мешало бы освежить память, что такое O, написанное выше во-первых неправильно посчитано, во-вторых неправильно записано.

... 

Того же и Вам желаю.  Глядишь и Вы попадете в когорту избранных)).