일반 클래스 라이브러리 - 버그, 설명, 질문, 사용 기능 및 제안 사항 - 페이지 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


DBMS, 데이터 구조 에서 ZERO를 이해하는 사람에게 무엇을 문지르고 있습니까?
그런 ArrayList(C ++의 벡터)라는 개념이 없다면 우리는 무엇에 대해 이야기 할 수 있습니까 .....


당신의 부주의가 더...
사용 가능한 전체 목록을 확인하십시오 - https://www.mql5.com/ru/docs/standardlibrary/generic

CArrayList는 C++의 std::vector와 유사합니다.
CLinkedList는 C++의 std::list와 유사할 가능성이 큽니다.

 
fxsaber :

런칭

그리고 그것을 얻었다

CArrayList는 해시 변형보다 빠릅니다. CArrayList의 내부로 올라갔고 바로 거기에 있습니다.

나는 지금 사기를 느낀다. CArrayList는 일반 배열의 래퍼로 판명되었습니다. Prev/Next 포인터가 있는 일반적인 목록인 줄 알았는데 여기 있습니다.

역사적으로 List는 전혀 시트가 아니라 배열입니다. 따라서 모든 것이 맞습니다. 시트가 제네릭으로 나타나면 LinkedList 또는 이와 유사한 이름이 될 가능성이 큽니다.

 
fxsaber :

인터페이스가 아니라 특정 구현인 배열에서 약간의 실망을 경험했습니다.

음... 이 컨테이너는 배열(즉, C++에서 벡터의 유사체)이고 네이티브 mql 배열은 매우 훌륭하므로 arraylist는 힙에 가깝고 사용하기에 조금 더 편리합니다.
 

거래, 자동 거래 시스템 및 거래 전략 테스트에 관한 포럼

일반 클래스 라이브러리 - 버그, 설명, 질문, 사용법 및 제안

Sergey Dzyublik , 2017.12.09 01:12


가능한 개선을 위한 몇 가지 제안 사항이 있습니다.

1) 내 겸손한 의견으로는 구현에 완전히 올바르지 않은 용량 선택이 포함되어 있습니다. 초기 크기 3과 해시 테이블이 다시 빌드될 때 후속 크기 모두입니다.
네 맞습니다. 균일 분포를 위해서는 소수를 선택해야 합니다.
그러나 CPrimeGenerator의 구현은 기대를 충족하지 못하고 누락된 소수를 포함합니다.
이러한 "생성기"의 목적은 명확합니다. 자동으로 소수를 생성하여 1.2 정도의 성장 인자를 제공하는 것입니다.
하지만, 너무 작은 요소가 아닌가? 벡터에 대한 C++에서 계수는 일반적으로 라이브러리에 따라 1.5-2.0입니다(연산의 평균 복잡성에 크게 영향을 미치기 때문에).
출력은 상수 계수일 수 있으며 소수 목록에서 이진 검색을 통해 숫자를 소수로 반올림할 수 있습니다.
그리고 3의 초기 용량 크기는 너무 작습니다. 우리는 지난 세기에 살고 있지 않습니다.

2) 현재 해시 테이블의 재구축(Resize)은 100% 채우기(모든 m_entries[] 채우기)로만 수행됩니다.
이와 관련하여 매우 균일하지 않은 분포를 갖는 키에 대해 상당한 수의 충돌이 가능합니다.
옵션으로 해시 테이블 재구축을 수행하는 데 필요한 제한만큼 100% 감소하는 채우기 비율을 도입하는 것을 고려하십시오.

1) 볼륨 성장 계수(용량)가 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);
  }

이 방법에서는 컬렉션의 이전 크기에 2를 곱한 다음 결과 값에 대해 위에서 가장 가까운 소수를 찾아 새 볼륨으로 반환합니다.

용량의 초기 값에 대해 - 동의합니다. 매우 작습니다.

그러나 반면에 초기 볼륨을 명시적으로 지정할 수 있는 생성자가 항상 있습니다.

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

따라서 여기서 무언가를 변경하는 것은 별로 의미가 없습니다.

2) 채우기 계수 매개변수를 추가하면 실제로 경우에 따라 충돌을 방지하는 데 도움이 됩니다. 시행될 가능성이 높습니다.

 
로만 코노펠코 :

1) 볼륨 성장 계수(용량)가 1.2와 같지 않은 경우 CHashMap에서 새 볼륨을 계산하기 위해 CPrimeGenerator::ExpandPrime 메서드가 사용됩니다.

이 방법에서는 컬렉션의 이전 크기에 2를 곱한 다음 결과 값에 대해 위에서 가장 가까운 소수를 찾아 새 볼륨으로 반환합니다.

용량의 초기 값에 대해 - 동의합니다. 매우 작습니다.

그러나 반면에 초기 볼륨을 명시적으로 지정할 수 있는 생성자가 항상 있습니다.

따라서 여기서 무언가를 변경하는 것은 별로 의미가 없습니다.

2) 채우기 계수 매개변수를 추가하면 실제로 경우에 따라 충돌을 방지하는 데 도움이 됩니다. 시행될 가능성이 높습니다.

로만, 당신이 거기에서 그렇게하고 있다고 생각하지 않습니다. 이제 일부 일반 클래스에는 가장 필요한 메서드도 포함되지 않습니다. 당신은 그들을 전혀 시도 했습니까? CRedBlackTree를 예로 들어 보겠습니다. 이는 고전적인 레드-블랙 트리 구현입니다. 꽤 멋진 알고리즘이지만 반복 가능성이 없습니다. 이것은 어떻게 이해해야 합니까? 다른 많은 것들이 필요하지만 어떤 이유로 아무도 구현하려고 하지 않았습니다. 동일한 GetHashCode는 일반적으로 끔찍합니다. 죄송하지만 이것은 MQ 레벨이 아닙니다!

 
바실리 소콜로프 :

로만, 당신이 거기에서 그렇게하고 있다고 생각하지 않습니다. 이제 일부 일반 클래스에는 가장 필요한 메서드도 포함되지 않습니다. 당신은 그들을 전혀 시도 했습니까? 레드-블랙 트리의 고전적인 구현인 CRedBlackTree를 예로 들어 보겠습니다. 꽤 멋진 알고리즘이지만 반복 가능성이 없습니다. 이것은 어떻게 이해해야 합니까? 다른 많은 것들이 필요하지만 어떤 이유로 아무도 구현하려고 하지 않았습니다. 동일한 GetHashCode는 일반적으로 끔찍합니다. 죄송하지만 이것은 MQ 레벨이 아닙니다!

Genric 라이브러리의 모든 템플릿 컬렉션에 대한 반복자의 필요성을 완벽하게 이해하지만 중첩 클래스를 생성하고 인터페이스에서 다중 상속을 생성하는 기능이 없으면 올바르게 구현하지 못할 것입니다.

GetHashCode와 관련하여 좀 더 구체적인 의견을 듣고 싶습니다.

 
로만 코노펠코 :

...

GetHashCode와 관련하여 좀 더 구체적인 의견을 듣고 싶습니다.

문제

분명히 GetHashCode는 MQL5 사용자 환경에서 제대로 구현될 수 없습니다. 모든 개체에 액세스할 수 있는 것은 아니기 때문입니다. 그리고 double int 등과 같은 기본 멤버의 경우 구현이 제대로 작동하면 복잡한 객체(클래스, 구조 및 열거형)의 경우 해시가 이름으로 계산됩니다. 분명히 CObject 또는 ENUM _something_re 유형의 개체가 천 개라면 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는 내부 가상 머신에서 실행되는 유형 안전 사용자 정의 프로그래밍 언어입니다. 그물 같은 것. 이는 개체에 대한 필요한 액세스가 여전히 존재하지만 보다 체계적인 수준에 있음을 의미합니다. 따라서 다음 프로토타입 으로 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...38
새 코멘트