일반 클래스 라이브러리 - 버그, 설명, 질문, 사용 기능 및 제안 사항 - 페이지 17

새 코멘트
 
알렉세이 오레쉬킨 :

훌륭한 이론적 예! 실제로, 누가 쓰레드를 언제-쓰레드가 수천 개의 트랜잭션으로 운영했습니까?

추신 나는 이것이 쓰레기이고 아무도 필요로하지 않는다는 것을 증명하려는 것이 아닙니다. 나는 실제 거래의 가치를 이해하려고 노력하고 있습니다. 저는 이론가가 아니라 순수한 실천가입니다.

약 1000번의 거래나 10번의 거래가 아닙니다. 트릭은 우리가 10번과 1000000번 거래 모두에서 동등하게 효과적으로 작동하는 짧은 코드를 작성한다는 것입니다.
 

CHashMap의 현재 구현에 대해 간략하게: 

template<typename TKey,typename TValue>
class CHashMap: public IMap<TKey,TValue>
  {
protected :
   int                m_buckets[];                        
   Entry<TKey,TValue>m_entries[];
   int                m_count;
   int                m_free_list;
   int                m_free_count;
   IEqualityComparer<TKey>*m_comparer;
   bool               m_delete_comparer;

     .................................

     .................................

  }

먼저 Entry<TKey,TValue> 가 무엇인지 이해해야 합니다.
사실, 이것은 다음을 포함하는 CLinkedList와 같은 노드입니다.

- 키 및 값 컨테이너에 배치
- 키에 대한 캐시된 해시 값 - hash_code
- next - 단일 연결 목록을 통해 충돌을 해결하기 위해 다음 Entry<TKey,TValue> 에 대한 "포인터"


m_entries[] - 추가된 키와 값인 hash_code 다음이 배치되는 "셀"의 배열입니다. 어레이의 크기는 용량에 해당합니다.
m_count - m_entries에서 사용되지 않은 첫 번째 셀의 인덱스를 나타냅니다. 초기 값은 0이고 용량까지 증가하고 모든 어레이는 모든 어레이의 용량 및 크기가 증가하여 재구축됩니다.
m_buckets[] - m_entries[]의 인덱스 배열. 기본값은 -1입니다. 어레이의 크기는 용량에 해당합니다.


충돌 없음, CHashMap 컨테이너에 고유 값 추가:

  1. 키로 해시를 계산하면 hash_code를 얻습니다.
  2. 인덱스 m_count의 m_entries[]에 key, value, hash_code 값을 배치합니다. (예제에 충돌이 없기 때문에 다음 = -1)
  3. index hash_code % (ArraySize(m_buckets))에 m_buckets[]를 m_entries[]에 새로 추가된 요소의 인덱스 값(m_count)에 넣습니다.
  4. m_count의 값을 +1 증가시킵니다.

충돌 없음, CHashMap 컨테이너에서 키로 값 가져오기:

  1. 키로 해시를 계산하면 hash_code를 얻습니다.
  2. m_buckets[]에서 index hash_code %(ArraySize(m_buckets))로 배열 m_entries[]에서 인덱스인 값을 얻습니다.
  3. 얻은 인덱스 m_buckets[hash_code % (ArraySize(m_buckets))]에 의해 배열 m_entries[]에서 값 값을 얻습니다.

충돌 해결:

다른 키의 경우 hash_code_key_1 %(ArraySize(m_buckets))는 hash_code_key_2 %(ArraySize(m_buckets))와 같습니다. 이것을 충돌이라고 합니다.
m_entries[]에 추가된 모든 충돌 요소는 다음을 통해 단일 연결 목록으로 연결됩니다( Entry<TKey,TValue> 구조 참조).
그리고 m_buckets[]는 항상 이 충돌 목록에서 첫 번째 헤드 요소의 인덱스를 가리킵니다.
충돌이 있는 하나의 큰 목록이 아니라 많은 작은 목록이 나타납니다.


충돌, CHashMap 컨테이너에서 키로 값 가져오기:

  1. 키로 해시를 계산하면 hash_code를 얻습니다.
  2. m_buckets[]에서 index hash_code %(ArraySize(m_buckets))로 배열 m_entries[]에서 인덱스인 값을 얻습니다.
  3. 다음 값이 충돌이 있음을 나타내는 -1과 같지 않음을 알 수 있습니다.
  4. m_entries[] 요소의 단일 연결 목록을 살펴보고 원하는 값을 저장된 키와 동일한지 비교합니다.


CHashMap 컨테이너에서 값 제거:

- m_entries[]에서 셀을 삭제할 때 삭제가 발생하지 않는 셀은 free로 지정되고 hash_code = -1입니다.
- 자유 셀은 고유한 자유 셀 목록을 형성합니다(Entry<TKey,TValue>의 동일한 다음을 통해). m_free_list 는 목록 헤드 인덱스를 담당합니다.
 - 컨테이너에 새 값이 추가되면 빈 셀이 먼저 사용됩니다.
- m_free_count 는 현재 사용 가능한 셀 수를 제어하는 데 사용됩니다.


해시 테이블 재구축(용량 증가 프로세스):

- 재구축은 용량이 100% 찼을 때만 발생합니다.
- 목록에서 다음 용량을 가져옵니다.

 const static int   CPrimeGenerator::s_primes[]=
  {
   3 , 7 , 11 , 17 , 23 , 29 , 37 , 47 , 59 , 71 , 89 , 107 , 131 , 163 , 197 , 239 , 293 , 353 , 431 , 521 , 631 , 761 , 919 ,
   1103 , 1327 , 1597 , 1931 , 2333 , 2801 , 3371 , 4049 , 4861 , 5839 , 7013 , 8419 , 10103 , 12143 , 14591 ,
   17519 , 21023 , 25229 , 30293 , 36353 , 43627 , 52361 , 62851 , 75431 , 90523 , 108631 , 130363 , 156437 ,
   187751 , 225307 , 270371 , 324449 , 389357 , 467237 , 560689 , 672827 , 807403 , 968897 , 1162687 , 1395263 ,
   1674319 , 2009191 , 2411033 , 2893249 , 3471899 , 4166287 , 4999559 , 5999471 , 7199369
  };

- m_entries[] 및 m_buckets[] 배열의 크기가 증가합니다.
- m_buckets[]가 지워지고 m_entries[]의 데이터를 기반으로 완전히 다시 채워집니다(키에 대한 캐시된 해시 값 - hash_code).



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

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

Sergey Dzyublik , 2017.12.09 01:12

CHashMap 의 구현에 대해 알게 되었습니다.
 솔직히, 나는 그것을 좋아했다.


개선할 수 있는 몇 가지 제안 사항이 있습니다.

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

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


 
알렉세이 오레쉬킨 :

실제로, 누가 쓰레드를 언제-쓰레드가 수천 개의 트랜잭션으로 운영했습니까?

예, 많은 사람들이 한 번에 수백만 건의 역사 참조를 연습합니다.

 
바실리 소콜로프 :

Forts에서는 모든 것이 처음입니다.

공습 경보 해제.

알고리즘으로 hft 주문 을 보낸 다음 분석을 위해 선택하는 것은 다른 두 가지입니다. 이 해시는 나중에 완전히 다른 것이 분석되기 때문에 분석을 위해 전송에도 필요하지 않습니다.

일반적으로 범죄가 없습니다. 이론도 필요하다.

 
알렉세이 오레쉬킨 :

공습 경보 해제.

알고리즘으로 hft 주문을 보낸 다음 분석을 위해 선택하는 것은 다른 두 가지입니다. 이 해시는 나중에 완전히 다른 것이 분석되기 때문에 분석을 위해 전송에도 필요하지 않습니다.

일반적으로 범죄가 없습니다. 이론도 필요하다.


나는 식기 세척기를 사용하지 않습니다. 스펀지가 있습니다.
일반적으로 범죄가 없습니다. 식기 세척기는 미쳤습니다. 왜 필요한지.

 
알렉세이 오레쉬킨 :

공습 경보 해제.

알고리즘으로 hft 주문을 보낸 다음 분석을 위해 선택하는 것은 다른 두 가지입니다. 이 해시는 나중에 완전히 다른 것이 분석되기 때문에 분석을 위해 전송에도 필요하지 않습니다.

일반적으로 범죄가 없습니다. 이론도 필요하다.

어떤 불만? 목발을 더 쓰십시오.

 
세르게이 주블릭 :

CHashMap 의 현재 구현에 대해 간략하게

감사합니다. 소스를 파싱할 때 사용하겠습니다.

 
바실리 소콜로프 :

어떤 불만? 목발을 더 쓰십시오.

문제는 제가 여기서 제안한 주제를 사용하지 않고 제가 옳고 그름을 이해하려고 노력한다는 것입니다. 나는 평범한 연관 배열을 충분히 가지고 있지만 항상 더 나은 것을 원합니다.
 
fxsaber :

감사합니다. 소스를 파싱할 때 사용하겠습니다.


새로운 키-값 쌍을 추가할 때 컨테이너에 키가 있는지 확인을 생략했는데 먼저 수행됩니다.
하지만 그것은 중요하지 않습니다.

 
이 부재로 인해 발생 하는 오류 메시지 발생
 //+------------------------------------------------------------------+
//| Gets the element at the specified index.                         |
//+------------------------------------------------------------------+
template < typename T>
bool CArrayList::TryGetValue( const int index,T &value) const

모든 Generic에서 이 문제를 해결하세요.

1...101112131415161718192021222324...38
새 코멘트