通用类库 - 错误、说明、问题、使用功能和建议 - 页 5

新评论
 
谢尔盖-迪尤布利 克。

如果字典的大小和预期元素的数量允许，哈希值平均为O(1)。
然后取决于碰撞 处理的实现，它可以通过一个列表，也许更多的subhash....

我在术语方面的无知阻碍了我进入其中的进程。我将等着看例子。我希望简明扼要，切中要害--权证、蜱虫之类的。

 
fxsaber:

我在术语方面的无知阻碍了我进入其中的进程。我将等着看例子。我希望简明扼要，切中要害--权证、蜱虫之类的。


逮捕证是不可能的。我对交易感兴趣。

 
fxsaber:

我是在维基上读到的。这种情况下，你根本不了解直觉推理的逻辑。


365天是对字典大小的限制
课堂上的学生人数是集合中的预期项目数
巧合的生日是一种碰撞

 
谢尔盖-迪尤布利 克。

365天是对字典大小的一个限制。
课堂上的学生人数是集合中的预期项目数
巧合的生日是一种碰撞

谢谢你，这个术语定义更清楚了。我只是不明白这个 "悖论 "与这个主题有什么关系？

 
谢尔盖-迪尤布利 克。

365天是对字典大小的限制
课堂上的学生人数是预期的收藏品的数量
巧合的生日是一种碰撞


在这个例子中，哈希值是学生的生日。
我们有一个有365个架子的柜子，学生的日记就放在那里。
我们把每本日记放在与学生的生日相对应的架子上。

我们需要学生彼得罗夫的日记，我们知道他的出生时间。
现在通过O(1)中的出生日期，我们可以很容易地找到彼得罗夫的日记，以及任何其他学生的日记。
例外情况是两个学生有相同的生日--这被称为撞车。

解决碰撞问题是利用额外的信息来找出我们需要的两个或多个期刊中的哪一个。
通过列表进行碰撞解决，就是简单地将碰撞中的所有条目一个一个地找出来，找到一个匹配。撕下每本日记，看看是谁的。
一个子哈希就是把参与碰撞的项目整理成一个哈希表，但以不同的标准。例如，按学生出生的时间。


如果你对这个话题感兴趣，我建议你去看看MailRu的关于算法和数据结构 的youtube课程。

 
谢尔盖-迪尤布利 克。

在这个例子中，哈希值是学生的生日。
我们有一个有365个架子的橱柜，里面放着学生的日记。
我们把每本日记放在与学生的生日相对应的架子上。

我们需要彼得罗夫的日记，我们知道他的出生时间。
现在通过O(1)中的出生日期，我们可以很容易地找到彼得罗夫以及另一个学生的日记。
例外情况是两个学生有相同的生日--这被称为撞车。

解决碰撞问题是利用额外的信息来找出我们需要的两个或多个期刊中的哪一个。
通过列表进行碰撞解决，就是简单地将碰撞中的所有条目一个一个地找出来，找到一个匹配。撕下每本日记，看看是谁的。
一个子标题是组织一个参与碰撞的项目的哈希表，但以不同的标准。例如，按一个学生出生的时间来计算。


如果你对这个话题感兴趣，我建议你去看看MailRu的关于算法和数据结构 的youtube课程。

我最初就是这样想象的。我只是不明白突出显示的那条。Hash不是一个索引，所以你可以通过指针数组中的偏移量找到它。同样，我们应该在名单中搜索。而这是一个有适当排序的二进制搜索。

 
fxsaber:

这就是我从一开始所想象的情况。我只是不明白突出显示的那条。Hash不是一个索引，所以你可以通过指针数组中的偏移量来找到它。不过，你必须在列表中搜索。而这是一个有适当排序的二进制搜索。


突出显示的是口头上的错别字))而且已经改正。
哈希值是一个索引。它被赋予了字典的大小。

每个架子都有相同的高度，通过架子的编号，你可以准确地知道在什么高度寻找它。O(1)

 

尽可能简单的关于关联数组#1

Generic中介绍的很多算法都以这样或那样的方式基于关联数组或字典。它也是最常用的两种算法之一。如果我说90%的编程任务都是用数组和字典来完成的，我想我已经接近事实了。在进入实践之前，让我们以最清晰、最直接的方式来描述字典的工作，故意简化一些细节。

我们将在一个非常简单的例子上展示这个词典：一个普通的单词表。假设我们只有几个词，都以不同的字母开头。

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

英语字母表包含26个字符。让我们创建一个字符串数组，大小为26个元素。

string dictionary[26];

现在，如果我们同意将单词存储在与它们的第一个字母相对应的索引中，我们将得到一个简单的字典。我们将从头开始索引。字'苹果'将被存储在我们的索引0，因为字符'a'是字母表的第一个字母，'猫'将被存储在索引1，'狗'在索引3，雾将被存储在索引4，步行在索引24，零在最后的索引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");
  }
//+------------------------------------------------------------------+

如果我们把 "苹果 "这个词加进去，然后找到它，找到这个词的权限的操作将是瞬间的。因为我们事先知道可以找到这个词的索引。不可能有其他的索引变体，所以没有必要翻阅整个列表。这大致上是所有字典的基础。

在下面的例子中，我们将改进它，使其能够存储以相同字母开头的单词。

 

尽可能简单的关于关联数组#2

有时会出现不同的词以同一个字母开头的情况。如果我们把 "apple "放在我们以前的字典里，然后试图把 "application "放在那里，就不会成功了。索引0将被苹果这个词占据。在这种情况下，我们说的是哈希函数的碰撞。我们的哈希函数非常简单--它返回单词的第一个字符的数字，所以这个函数的碰撞会非常频繁。为了存储不同的单词，以相同的字母开头，我们将做加法：我们将不在数组中存储元素，而是在数组的数组中存储。在这种情况下，索引0将包含另一个有两个词的数组："苹果 "和 "应用"。

//+------------------------------------------------------------------+
//|                                                         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");
  }
//+------------------------------------------------------------------+

现在，我们的字典里储存了甚至以相同字母开头的单词。但访问具有相同首字母的单词的成本会增加。因为现在我们需要对所有以'a'开头的词进行全面搜索，以找出'application'这个词是否在字典中。 如果我们的哈希函数产生不同的数字，即使这些词只相差一个字符，那么尝试具有相同索引的词的概率将趋于零，对一个任意元素的访问将趋于o(1).在真正的字典中，这正是发生的情况，在那里使用的函数是防碰撞的，所以我们可以有把握地说，对这些集合中的项目的访问是非常快的，几乎没有蛮力。

 
瓦西里-索科洛夫。

尽可能地保持关联数组的简单性

Generic中提出的许多算法都以这样或那样的方式基于关联阵列或字典。这也是最常用的两种算法之一。如果我说90%的编程任务都是由数组和字典涵盖的，我想我已经接近事实了。在进入实践之前，让我们以最清晰、最直接的方式来描述词典的工作，故意简化一些细节。

我们将在一个非常简单的例子上展示这个词典：一个普通的单词表。假设我们只有几个词，都以不同的字母开头。

英语字母表包含26个字符。让我们创建一个字符串数组，大小为26个元素。

现在，如果我们同意将单词存储在与它们的第一个字母相对应的索引中，我们将得到一个简单的字典。我们将从头开始索引。苹果 "这个词将被存储在我们的字典中的索引0，因为字符 "a "是字母表的第一个字母，"猫"--在索引1，"狗"--在索引3，雾--将占据索引4，步行--索引24，零--最后的索引25。

请注意，索引5至23将不被使用。这是一种额外的内存浪费，但我们可以立即访问例如单词 "walk"，因为我们知道，如果它存在，它位于索引24处。

让我们写出我们的第一个空字典。

如果我们把 "苹果 "这个词加进去，然后找到它，访问这个词的搜索操作将是即时的。因为我们事先知道可以找到这个词的索引。不可能有其他的索引变体，所以没有必要翻看整个列表。这大致上是所有字典的基础。

在下一个例子中，我们将对其进行改进，以便我们能够存储以相同字母开头的单词。

这个解决方案是完美的。一切都是尽可能的简单。只有函数、数组和正确的数据组织。这就是我所说的。
123456789101112...38
新评论