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

[fxsaber]

세르게이 주블리크 :

예상 요소 수에 대한 사전 크기가 허용하는 경우 해시는 평균적으로 O(1)입니다.
그리고 충돌 을 해결하기 위한 구현에 대한 의존성이 있습니다. 이것은 목록, 어쩌면 서브해시를 통할 수도 있습니다....

나의 용어 무지는 이해의 과정을 방해합니다. 예시를 기다리겠습니다. 나는 간결하고 요점 - 주문, 눈금 등을 원합니다.

[Vladimir Karputov]

fxsaber :

나의 용어 무지는 이해의 과정을 방해합니다. 예시를 기다리겠습니다. 나는 간결하고 요점 - 주문, 눈금 등을 원합니다.

용광로에서 주문. 거래에 관심이 있습니다.

[Sergey Dzyublik]

fxsaber :

위키에서 읽어보세요. 직관적 추론의 논리를 전혀 이해하지 못하는 경우.

365일은 사전 크기 제한입니다.
클래스의 학생 수는 컬렉션의 예상 요소 수입니다.
생일 경기는 충돌이다

[fxsaber]

세르게이 주블리크 :

365일은 사전 크기 제한입니다.
클래스의 학생 수는 컬렉션의 예상 요소 수입니다.
생일 경기는 충돌이다

덕분에 이 용어 정의가 더 명확해졌습니다. 나는 이 "역설"이 가지의 주제와 어떤 관련이 있는지 이해하지 못합니까?

[Sergey Dzyublik]

세르게이 주블리크 :

365일은 사전 크기 제한입니다.
클래스의 학생 수는 컬렉션의 예상 요소 수입니다.
생일 경기는 충돌이다

이 예에서 해시는 학생의 생일입니다.
365개의 선반이 있는 벽장에는 학생의 일기장이 들어 있습니다.
우리는 학생의 생일에 해당하는 선반에 각 일기를 넣습니다.

우리는 Petrov의 학생의 일기가 필요하며 그가 언제 태어났는지 압니다.
이제 생일을 기준으로 O(1)에서 다른 학생의 일기와 마찬가지로 Petrov의 일기를 쉽게 찾을 수 있습니다.
두 학생의 생일이 같은 경우는 예외입니다. 이를 충돌이라고 합니다.

충돌 해결은 두 개 이상의 일기 중 어느 것이 필요한지 결정하기 위해 추가 정보를 사용하는 것입니다.
목록을 통해 해결하는 것은 충돌에 참여하는 모든 요소를 원하는 요소와 일치시키기 위해 단순하게 순차적으로 열거하는 것입니다. 각 일기를 찢고 그것이 누구인지 확인하십시오.
Subhash 정렬은 충돌과 관련된 요소의 해시 테이블을 구성하지만 다른 기준에 따릅니다. 예를 들어, 학생이 태어났을 때.

이 주제에 관심이 있다면 알고리즘 및 데이터 구조 에 대한 YouTube의 MailRu 과정을 추천합니다.

[fxsaber]

세르게이 주블릭 :

이 예에서 해시는 학생의 생일입니다.
365개의 선반이 있는 벽장에는 학생의 일기가 들어 있습니다.
우리는 학생의 생일에 해당하는 선반에 각 일기를 넣습니다.

우리는 Petrov의 학생의 일기가 필요하며 그가 언제 태어났는지 압니다.
이제 O(1)의 생일을 기준으로 Petrov의 일기와 다른 학생을 쉽게 찾을 수 있습니다.
두 학생의 생일이 같은 경우는 예외입니다. 이를 충돌이라고 합니다.

충돌 해결은 두 개 이상의 일기 중 어느 것이 필요한지 결정하기 위해 추가 정보를 사용하는 것입니다.
목록을 통해 해결하는 것은 충돌에 참여하는 모든 요소를 원하는 요소와 일치시키기 위해 단순하게 순차적으로 열거하는 것입니다. 각 일기를 찢고 그것이 누구인지 확인하십시오.
Subhash 정렬은 충돌과 관련된 요소의 해시 테이블을 구성하지만 다른 기준에 따릅니다. 예를 들어, 학생이 태어났을 때.

이 주제에 관심이 있다면 알고리즘 및 데이터 구조 에 대한 YouTube의 MailRu 과정을 추천합니다.

원래 구상했던 대로입니다. 강조 표시된 내용을 이해하지 못합니다. 해시는 인덱스가 아니므로 포인터 배열에서 오프셋으로 즉시 찾을 수 있습니다. 마찬가지로 목록을 살펴봐야 합니다. 그리고 이것은 적절한 정렬을 사용한 이진 검색입니다.

[Sergey Dzyublik]

fxsaber :

처음부터 상상했던 그대로입니다. 강조 표시된 내용을 이해하지 못합니다. 해시는 인덱스가 아니므로 포인터 배열에서 오프셋으로 즉시 찾을 수 있습니다. 마찬가지로 목록을 살펴봐야 합니다. 그리고 이것은 적절한 정렬을 사용한 이진 검색입니다.

강조 표시된 부분은 언어 오타임)) 이미 수정되었습니다.
해시는 인덱스입니다. 사전의 크기로 캐스팅됩니다.

각 선반은 높이가 동일하며 선반 번호를 통해 정확히 어느 높이에서 찾아야 하는지 알 수 있습니다. 오(1)

[Vasiliy Sokolov]

연관 배열 #1에 대해 가능한 한 간단합니다.

Generic에 제공된 많은 알고리즘은 연관 배열 또는 사전을 기반으로 합니다. 또한 가장 일반적으로 사용되는 두 가지 알고리즘 중 하나입니다. 프로그래밍의 모든 작업의 90%가 배열과 사전으로 이루어진다고 하면 진실에 가까울 것이라고 생각합니다. 연습을 진행하기 전에 사전 작업을 가능한 한 간단하고 알기 쉽게 설명하여 일부 세부 사항을 의도적으로 단순화합니다.

우리는 아주 간단한 예를 사용하여 사전을 분석할 것입니다: 일반적인 단어 사전. 이 단어 중 몇 개만 있고 모두 다른 알파벳 문자로 시작한다고 가정합니다.

 string words[] = { "apple" , "cat" , "fog" , "dog" , "walk" , "zero" };

영어 알파벳은 26자입니다. 차원이 26개 요소인 문자열 배열을 만들어 보겠습니다.

 string dictionary[ 26 ];

이제 첫 글자에 해당하는 인덱스에 단어를 저장하는 데 동의하면 가장 간단한 사전을 얻습니다. 처음부터 인덱싱을 수행합니다. "apple"이라는 단어는 인덱스 0에 저장됩니다. 문자 'a'가 알파벳의 첫 글자이기 때문입니다. "cat" - 인덱스 1, "dog" - 인덱스 3, fog - 인덱스 4, 걷기 - 인덱스 24이고 0은 마지막 25번째 인덱스입니다.

인덱스 5~23은 사용되지 않습니다. 이것은 추가 메모리 비용이지만, 예를 들어 "walk"라는 단어가 있으면 인덱스 24에 있다는 것을 알기 때문에 즉시 액세스할 수 있습니다.

첫 번째 빈 사전을 작성해 보겠습니다.

 //+------------------------------------------------------------------+
//|                                                         Dict.mq5 |
//|                        Copyright 2017, MetaQuotes Software Corp. |
//|                                              http://www.mql5.com |
//+------------------------------------------------------------------+
#property copyright "Copyright 2017, MetaQuotes Software Corp."
#property link        "http://www.mql5.com"
#property version    "1.00"
string words[ 26 ];

bool Contains( string word)
{
   uchar index = ( uchar ) StringGetCharacter (word, 0 )- 97 ;
   return words[index] != NULL ;
}
bool Add( string word)
{
   uchar index = ( uchar ) StringGetCharacter (word, 0 )- 97 ;
   if (words[index] == NULL )
   {
      words[index] = word;
       return true ;
   }
   return false ;
}
//+------------------------------------------------------------------+
//| Script program start function                                    |
//+------------------------------------------------------------------+
void OnStart ()
  {
//---
   Add( "apple" );
   if (Contains( "apple" ))
       printf ( "Словарь содержит слово apple" );
   else
       printf ( "Словарь не содержит слово apple" );
  }
//+------------------------------------------------------------------+

"사과"라는 단어를 추가한 다음 찾으면 이 단어에 대한 액세스를 찾는 작업이 즉시 수행됩니다. 이 단어를 찾을 수 있는 색인을 미리 알고 있기 때문입니다. 인덱스에 대한 다른 옵션이 있을 수 없으므로 전체 목록을 반복할 필요가 없습니다. 거의 모든 사전이 이 속성을 기반으로 합니다.

다음 예제에서는 같은 문자로 시작하는 단어를 저장할 수 있도록 개선합니다.

[Vasiliy Sokolov]

연관 배열 #2에 대해 가능한 한 간단합니다.

다른 단어가 같은 알파벳 문자로 시작하는 경우가 있습니다. 우리가 이전 사전에 "사과"라는 단어를 넣고 거기에 "응용 프로그램"을 넣으려고하면 아무 것도 나오지 않을 것입니다. 인덱스 0은 이미 사과라는 단어로 채워져 있습니다. 이 경우 해시 함수 충돌에 대해 이야기합니다. 해시 함수는 매우 간단합니다. 단어의 첫 번째 문자 수를 반환하므로 이 함수에서 충돌이 매우 자주 발생합니다. 같은 문자로 시작하는 다른 단어를 저장하기 위해 추가할 것입니다. 요소를 배열이 아닌 배열의 배열에 저장합니다. 그런 다음 인덱스 0에는 "apple"과 "application"이라는 두 단어가 포함된 또 다른 배열이 있습니다.

 //+------------------------------------------------------------------+
//|                                                         Dict.mq5 |
//|                        Copyright 2017, MetaQuotes Software Corp. |
//|                                              http://www.mql5.com |
//+------------------------------------------------------------------+
#property copyright "Copyright 2017, MetaQuotes Software Corp."
#property link        "http://www.mql5.com"
#property version    "1.00"
#include <Arrays\ArrayObj.mqh>
#include <Arrays\ArrayString.mqh>
CArrayString* WordsArray[ 26 ];

bool Contains( string word)
{
   uchar index = ( uchar ) StringGetCharacter (word, 0 )- 97 ;
   CArrayString* words = WordsArray[index];
   if (words == NULL )
       return false ;
   for ( int i = 0 ; i < words.Total(); i++)
       if (word == words.At(i))
         return true ;
   return false ;
}
bool Add( string word)
{
   uchar index = ( uchar ) StringGetCharacter (word, 0 )- 97 ;
   CArrayString* words;
   if (WordsArray[index] == NULL )
      WordsArray[index] = new CArrayString();
   words = WordsArray[index];
   for ( int i = 0 ; i < words.Total(); i++)
       if (word == words.At(i))
         return false ;
   words.Add(word);
   return true ;
}
//+------------------------------------------------------------------+
//| Script program start function                                    |
//+------------------------------------------------------------------+
void OnStart ()
  {
//---
   //ArrayResize(WordsArray, 26);
   Add( "apple" );
   Add( "application" );
   if (Contains( "application" ))
       printf ( "Словарь содержит слово application" );
   else
       printf ( "Словарь не содержит слово application" );
  }
//+------------------------------------------------------------------+

이제 우리 사전은 같은 문자로 시작하는 단어를 포함하여 단어를 저장합니다. 그러나 동일한 첫 글자를 가진 단어에 대한 액세스 비용이 증가합니다. 이제 'application'이라는 단어가 사전에 있는지 여부를 이해하려면 'a'로 시작하는 모든 단어를 완전히 검색해야 하기 때문입니다. 단어가 한 문자만큼 다르더라도 해시 함수가 다른 숫자를 생성했다면 동일한 인덱스를 가진 단어를 반복할 확률은 0이 되는 경향이 있고 임의의 요소에 대한 액세스는 o(1) 가 되는 경향이 있습니다 . 이것이 바로 실제 사전에서 일어나는 일이며 거기에서 사용되는 함수는 충돌에 강하므로 이러한 컬렉션의 요소에 대한 액세스는 매우 빠르고 거의 열거할 필요가 없다고 말할 수 있습니다.

[Реter Konow]

바실리 소콜로프 :

연관 배열에 대해 가능한 한 간단합니다.

Generic에 제공된 많은 알고리즘은 연관 배열 또는 사전을 기반으로 합니다. 또한 가장 일반적으로 사용되는 두 가지 알고리즘 중 하나입니다. 프로그래밍의 모든 작업의 90%가 배열과 사전으로 이루어진다고 하면 진실에 가까울 것이라고 생각합니다. 연습을 진행하기 전에 사전 작업을 가능한 한 간단하고 알기 쉽게 설명하여 일부 세부 사항을 의도적으로 단순화합니다.

우리는 아주 간단한 예를 사용하여 사전을 분석할 것입니다: 일반적인 단어 사전. 이 단어 중 몇 개만 있고 모두 다른 알파벳 문자로 시작한다고 가정합니다.

영어 알파벳은 26자입니다. 차원이 26개 요소인 문자열 배열을 생성해 보겠습니다.

이제 첫 글자에 해당하는 인덱스에 단어를 저장하는 데 동의하면 가장 간단한 사전을 얻습니다. 처음부터 인덱싱을 수행합니다. "apple"이라는 단어는 인덱스 0에 저장됩니다. 문자 'a'가 알파벳의 첫 글자이기 때문입니다. "cat" - 인덱스 1, "dog" - 인덱스 3, fog - 인덱스 4, 걷기 - 인덱스 24이고 0은 마지막 25번째 인덱스입니다.

인덱스 5~23은 사용되지 않습니다. 이것은 추가 메모리 비용이지만, 예를 들어 "walk"라는 단어가 있으면 인덱스 24에 있다는 것을 알기 때문에 즉시 액세스할 수 있습니다.

첫 번째 빈 사전을 작성해 보겠습니다.

"사과"라는 단어를 추가한 다음 찾으면 이 단어에 대한 액세스를 찾는 작업이 즉시 수행됩니다. 이 단어를 찾을 수 있는 색인을 미리 알고 있기 때문입니다. 인덱스에 대한 다른 옵션이 있을 수 없으므로 전체 목록을 반복할 필요가 없습니다. 거의 모든 사전이 이 속성을 기반으로 합니다.

다음 예제에서는 같은 문자로 시작하는 단어를 저장할 수 있도록 개선합니다.

솔루션은 완벽합니다. 모든 것이 가능한 한 간단합니다. 기능, 배열 및 적절한 데이터 구성만 가능합니다. 나는 이것에 대해 이야기했다.