Библиотека Generic классов - ошибки, описание, вопросы, особенности использования и предложения - страница 18

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

Запустил такое

#include <Generic\ArrayList.mqh>
#include <Generic\HashMap.mqh>

CHashMap<int, int> MagicsByDeals;

#define AMOUNT 1000000

template <typename T>
int Test( T &Object )
{
  int Res = 0;
  
  for(int i = 0; i < AMOUNT; i++)
  {
    int Tmp = 0;
    
    if (Object.TryGetValue(i, Tmp))    
      Res += Tmp;
  }
  
  return(Res);
}

#define BENCH(A)                                                              \
{                                                                             \
  const ulong StartTime = GetMicrosecondCount();                              \
  A;                                                                          \
  Print("Time[" + #A + "] = " + (string)(GetMicrosecondCount() - StartTime)); \
} 

void OnStart()
{   
  CArrayList<int> CollectionList;
  CHashMap<int, int> CollectionHash;
  
  for(int i = 0; i < AMOUNT; i++)
  {      
    CollectionHash.Add(i, i);
    CollectionList.Add(i);
  }
  
  BENCH(Print(Test(CollectionList)));
  BENCH(Print(Test(CollectionHash)));
}


и получил это

1783293664
Time[Print(Test(CollectionList))] = 24819
1783293664
Time[Print(Test(CollectionHash))] = 91270


CArrayList быстрее хэш-варианта. Залез во внутренности CArrayList, а там такое сразу

template<typename T>
class CArrayList: public IList<T>
  {
protected:
   T                 m_items[];
   int               m_size;

Чувствую теперь себя обманутым. CArrayList оказался оберткой обычного массива. Думал, это нормальный список с указателями Prev/Next, а тут такое

template<typename T>
bool CArrayList::TryGetValue(const int index,T &value)
  {
//--- check index
   if((uint)index<(uint)m_size)
     {
      //--- get value by index
      value=m_items[index];
      return(true);
     }
   return(false);
  }
 
fxsaber:
Кроме собственно алгоритмов работы со структурами есть еще проблема выбора нужного контейнера исходя из специфики задачи.
 
Комбинатор:
Кроме собственно алгоритмов работы со структурами есть еще проблема выбора нужного контейнера исходя из специфики задачи.

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

 
fxsaber:

Чувствую теперь себя обманутым. CArrayList оказался оберткой обычного массива. Думал, это нормальный список с указателями Prev/Next, а тут такое


Форум по трейдингу, автоматическим торговым системам и тестированию торговых стратегий

Алгоритмы, методы решений, сравнение их производительности

Sergey Dzyublik, 2017.12.10 20:52


Какие СУБД, что вы втираете человеку понимающему НОЛЬ в структурах данных. 
Если нет понятия такое ArrayList (vector из С++), о чем тут речь может идти.....


Тут скорее  ваша невнимательность...
Ознакомитесь со всем списком доступного - https://www.mql5.com/ru/docs/standardlibrary/generic

СArrayList - это аналог std::vector из С++
CLinkedList - это, скорее всего, аналог std::list из С++

 
fxsaber:

Запустил такое

и получил это

CArrayList быстрее хэш-варианта. Залез во внутренности CArrayList, а там такое сразу

Чувствую теперь себя обманутым. CArrayList оказался оберткой обычного массива. Думал, это нормальный список с указателями Prev/Next, а тут такое

Исторически сложилось что List это вовсе не лист, а массив. Поэтому все правильно. Если в generic появится лист, то называться он будет скорее всего как LinkedList или как-то так.

 
fxsaber:

Некоторое разочарование испытал не от интерфейса, а именно от конкретной реализации - массив.

ну... этот контейнер и есть массив (т.е. аналог вектора в С++), а родной mql массив очень даже неплох, так что arraylist скорее до кучи, чуть удобнее пользоваться.
 

Форум по трейдингу, автоматическим торговым системам и тестированию торговых стратегий

Библиотека Generic классов - ошибки, описание, вопросы, особенности использования и предложения

Sergey Dzyublik, 2017.12.09 01:12


Есть несколько предложений по возможному улучшению:

1) По скромному мнению реализация содержит не совсем корректный выбор capacity - как начальный размер 3, так и последующие при перестройке хеш-таблицы.
Да, все верно, что нужно выбирать простое число для равномерности распределения. 
Однако реализация CPrimeGenerator не отвечает ожиданиям и содержит пропуски простых чисел.
Цель такого "генератора" понятна - обеспечить коэффициент прироста порядка 1.2 с автоматическим получением простых чисел.
Однако, разве это не слишком маленький коэффициент? В C++ для vectors обычно коэффициент составляет 1.5-2.0 в зависимости от библиотеки (так как сильно влияет на среднюю сложность операции).
Выходом может быть константный коэффициент с последующим округлением числа до простого через бинарный поиск в списку простых чисел.
И начальный размер capacity в 3 - это уж слишком мало, мы же не в прошлом веке живем.

2) На данный момент перестройка хеш-таблицы (Resize) выполняется исключительно при 100% заполнении capacity (заполнении всех m_entries[])
В связи с чем возможно значительное количество коллизий для ключей с не очень равномерным распределением.
Как вариант рассмотреть возможность введение коэффициента заполнения, который уменьшит 100% на необходимый лимит для выполнения перестройки хеш-таблицы.

1) Коэффициент прироста объема(capacity) не равен 1.2, для расчета нового объема в CHashMap используется метод CPrimeGenerator::ExpandPrime:

int CPrimeGenerator::ExpandPrime(const int old_size)
  {
   int new_size=2*old_size;
   if((uint)new_size>INT_MAX && INT_MAX>old_size)
      return INT_MAX;
   else
      return GetPrime(new_size);
  }

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

Про начальное значение capacity - согласен, он очень маленький.

Но с другой стороны всегда есть конструкторы, в которых явно можно указать начальный объем:

class CHashMap: public IMap<TKey,TValue>
  {
public:
                     CHashMap(const int capacity);
                     CHashMap(const int capacity,IEqualityComparer<TKey>*comparer);
  }

Поэтому особого смысла здесь что-то менять не вижу.

2) Добавлением параметра коэффициента заполнения действительно в ряде случаев поможет избежать коллизий. Скорее всего будет реализовано.

 
Roman Konopelko:

1) Коэффициент прироста объема(capacity) не равен 1.2, для расчета нового объема в CHashMap используется метод CPrimeGenerator::ExpandPrime:

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

Про начальное значение capacity - согласен, он очень маленький.

Но с другой стороны всегда есть конструкторы, в которых явно можно указать начальный объем:

Поэтому особого смысла здесь что-то менять не вижу.

2) Добавлением параметра коэффициента заполнения действительно в ряде случаев поможет избежать коллизий. Скорее всего будет реализовано.

Роман, Вы там по-моему не тем занимаетесь. Сейчас некоторые классы generic не содержат даже самых необходимых методов. Вы вообще ими пробовали пользоваться? Взять например CRedBlackTree - классическая реализация красно-черного дерева. Довольно крутой алгоритм, но без возможности итерирования. Это как вообще понимать? Есть и много других вещей которые нужны, но которые почему-то никто не озаботился реализовать. Тот же GetHashCode вообще ужасен. Извините, но это не уровень MQ!

 
Vasiliy Sokolov:

Роман, Вы там по-моему не тем занимаетесь. Сейчас некоторые классы generic не содержат даже самых необходимых методов. Вы вообще ими пробовали пользоваться? Взять например CRedBlackTree - классическая реализация красно-черного дерева. Довольно крутой алгоритм, но без возможности итерирования. Это как вообще понимать? Есть и много других вещей которые нужны, но которые почему-то никто не озаботился реализовать. Тот же GetHashCode вообще ужасен. Извините, но это не уровень MQ!

Я прекрасно понимаю необходимость итераторов для всех шаблонных коллекций библиотеки Genric, но без возможностей создания вложенных классов и множественного наследования от интерфейсов, реализовать их правильно не получиться.

Относительно GetHashCode хотелось бы услыхать более конкретные замечания.

 
Roman Konopelko:

...

Относительно GetHashCode хотелось бы услыхать более конкретные замечания.

Проблема

Очевидно, что GetHashCode невозможно реализовать в пользовательском окружении MQL5 должным образом. Это так, потому что не ко всем объектам есть доступ. И если на примитивных членах вроде double int и т.п. реализация работает нормально, то для сложных объектов (классы, структуры и даже перечисления) хеш расчитывается по имени. Очевидно, что если у нас тысяча объектов типа CObject или даже ENUM_что-то_там, то и CHashMap и CHashSet вырождаются в обычный LinkedList:

#include <Generic\HashSet.mqh>
//+------------------------------------------------------------------+
//| Безобидное перечисление, но может быть класс или структура       |
//+------------------------------------------------------------------+
enum ENUM_NUMBER
{
   NUMBER_FIRTS,  // First
   NUMBER_SECOND, // Second
   NUMBER_THIRD   // Third
};
//+------------------------------------------------------------------+
//| Script program start function                                    |
//+------------------------------------------------------------------+
void OnStart()
{
   CHashSet<ENUM_NUMBER> set_enum;
   for(int i = 0; i < 3; i++)
      set_enum.Add((ENUM_NUMBER)i);
   //-- Поздравляю, мы выродились в LinkedList.... 
   for(int i = 0; i < 3; i++)
   {
      //-- Здесь дикий оверхед по производительности, который тчательно скрывается...
      string is = set_enum.Contains((ENUM_NUMBER)i) ? " присутствует " : " отсутствует ";
      //...
   }
}

избежать этого не получиться, потому что все что у нас есть на пользовательском уровне это имя объекта:

//+------------------------------------------------------------------+
//| Returns a hashcode for custom object.                            |
//+------------------------------------------------------------------+
template<typename T>
int GetHashCode(T value)
  {
//--- try to convert to equality comparable object  
   IEqualityComparable<T>*equtable=dynamic_cast<IEqualityComparable<T>*>(value);// <-- Здесь будет получено название класса, структуры или перечисление
   if(equtable)
     {
      //--- calculate hash by specied method   
      return equtable.HashCode();
     }
   else
     {
      //--- calculate hash from name of object
      return GetHashCode(typename(value));
     }
  }

Следовательно, хеши у всех объектов сложных типов равны между собой и вот этот код для поиска задействует полный перебор массива:

//+------------------------------------------------------------------+
//| Determines whether a set contains the specified element.         |
//+------------------------------------------------------------------+
template<typename T>
bool CHashSet::Contains(T item)
  {
//--- check buckets
   if(ArraySize(m_buckets)!=0)
     {
      //--- get hash code for item      
      int hash_code=m_comparer.HashCode(item);
      //--- search item in the slots       
      for(int i=m_buckets[hash_code%ArraySize(m_buckets)]-1; i>=0; i=m_slots[i].next)
         if(m_slots[i].hash_code==hash_code && m_comparer.Equals(m_slots[i].value,item))
            return(true);
     }
   return(false);
  }

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


Решение

Очевидно, что MQL5 это типобезопасный пользовательский язык программирования, выполняющийся на внутренней виртуальной машине. Что-то наподобии Net. Это значит, что необходимый доступ к объектам все-таки есть, но на более системном уровне. Следовательно, возможно написать системную функцию GetHashCode со следующим прототипом:

int GetHashCode(void sample);

Как она должна работать? Во-первых она должна быть всеядной и быстрой. Давать равномерное распределение. Например:

int hash = GetHashCode(3);
// hash = 3

hash = GetHashCode(3.14159);
// hash = 2039485

enum EType{E1, E2, E3};
hash = GetHashCode(E2);
// hash = 2

class C1{};
C1* class1 = new C1();
hash = GetHashCode(class1);
//hash = 39203847

struct S1{};
S1 struct1;
hash = GetHashCode(struct1);
//hash = 83928342

Данная функция может располагаться в разделе системных функций. Других решений я не вижу.

з.ы. Чуть позже выскажу другие предложения по поводу интерфейсов, множественного наследования и прочего прочего C++ наследия.
1...111213141516171819202122232425...37
Новый комментарий
Причина обращения: