Explication détaillée des structures de données et des algorithmes de recherche couramment utilisés (implémentation Python)

1. Concepts de base

La recherche consiste à déterminer un élément de données (ou un enregistrement) dont la clé est égale à la valeur donnée dans la table de recherche en fonction d'une valeur donnée.

Tableau de recherche : une collection d'éléments de données (ou d'enregistrements) du même type.

Clé : la valeur d'un élément de données dans l'élément de données, également appelée valeur clé.

Clé primaire : un mot-clé qui identifie de manière unique un élément de données ou un enregistrement.

Les tables de recherche peuvent être divisées en :

Table de recherche statique : une table de recherche qui effectue uniquement des opérations de recherche. Ses principales opérations sont :

Requête si un élément de données "spécifique" est dans le tableau

Récupérer un élément de données "spécifique" et divers attributs

Tableau de recherche dynamique : Insérer ou les opérations de suppression sont effectuées simultanément pendant la recherche :

Insérer des données pendant la recherche

Supprimer les données pendant la recherche

2. La recherche de table non ordonnée

est une recherche linéaire qui traverse les éléments de données sans trier les données.

Analyse d'algorithme : le meilleur des cas est qu'il se trouve à la première position, qui est O(1) ; le pire des cas est qu'il se trouve à la dernière position, qui est O(n) ; ); donc le nombre moyen de recherches est de (n 1)/2. La complexité temporelle finale est O(n)

# 最基础的遍历无序列表的查找算法
# 时间复杂度O(n)
 
def sequential_search(lis, key):
  length = len(lis)
  for i in range(length):
    if lis[i] == key:
      return i
    else:
      return False
 
 
if __name__ == '__main__':
  LIST = [1, 5, 8, 123, 22, 54, 7, 99, 300, 222]
  result = sequential_search(LIST, 123)
  print(result)

3. Recherche de table ordonnée

Les données de la table de recherche doivent être triées selon une clé primaire !

1. Recherche binaire

Le cœur de l'algorithme : comparez en continu les éléments intermédiaires de la table de recherche avec la valeur de recherche et réduisez la plage de la table d'un facteur de moitié.

# 针对有序查找表的二分查找算法
# 时间复杂度O(log(n))
 
def binary_search(lis, key):
  low = 0
  high = len(lis) - 1
  time = 0
  while low < high:
    time += 1
    mid = int((low + high) / 2)
    if key < lis[mid]:
      high = mid - 1
    elif key > lis[mid]:
      low = mid + 1
    else:
      # 打印折半的次数
      print("times: %s" % time)
      return mid
  print("times: %s" % time)
  return False
 
if __name__ == &#39;__main__&#39;:
  LIST = [1, 5, 7, 8, 22, 54, 99, 123, 200, 222, 444]
  result = binary_search(LIST, 99)
  print(result)

2. Recherche par interpolation

Bien que la méthode de recherche binaire soit déjà très bonne, il existe encore des domaines qui peuvent être optimisés.

Parfois, filtrer en deux n'est pas assez strict. Ne serait-il pas préférable d'exclure les neuf dixièmes des données à chaque fois ? Le choix de cette valeur est la question clé. Le sens de l'interpolation est : réduire à une vitesse plus rapide.

Le cœur de l'interpolation est d'utiliser la formule :

value = (key - list[low])/(list[high] - list[low])

Utilisez cette valeur pour remplacer 1/2 dans la recherche binaire.

Le code ci-dessus peut être utilisé directement, il vous suffit de modifier une phrase.

# 插值查找算法
# 时间复杂度O(log(n))
 
def binary_search(lis, key):
  low = 0
  high = len(lis) - 1
  time = 0
  while low < high:
    time += 1
    # 计算mid值是插值算法的核心代码
    mid = low + int((high - low) * (key - lis[low])/(lis[high] - lis[low]))
    print("mid=%s, low=%s, high=%s" % (mid, low, high))
    if key < lis[mid]:
      high = mid - 1
    elif key > lis[mid]:
      low = mid + 1
    else:
      # 打印查找的次数
      print("times: %s" % time)
      return mid
  print("times: %s" % time)
  return False
 
if __name__ == &#39;__main__&#39;:
  LIST = [1, 5, 7, 8, 22, 54, 99, 123, 200, 222, 444]
  result = binary_search(LIST, 444)
  print(result)

La complexité temporelle globale de l'algorithme d'interpolation est toujours au niveau O(log(n)). L'avantage est que pour les tables de recherche contenant une grande quantité de données et une répartition relativement uniforme des mots-clés, les performances moyennes de l'utilisation de l'algorithme d'interpolation sont bien meilleures que celles de la recherche binaire. Au contraire, pour des données dont la répartition est extrêmement inégale, l’algorithme d’interpolation n’est pas adapté.

3. Recherche de Fibonacci

Inspiré de l'algorithme d'interpolation, l'algorithme de Fibonacci a été inventé. L’essentiel est également de savoir comment optimiser le taux de réduction afin de minimiser le nombre de recherches.

Utilisez cet algorithme, en supposant qu'il existe déjà une liste contenant des données de Fibonacci

F = [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,...]

# 斐波那契查找算法
# 时间复杂度O(log(n))
 
def fibonacci_search(lis, key):
  # 需要一个现成的斐波那契列表。其最大元素的值必须超过查找表中元素个数的数值。
  F = [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,
     233, 377, 610, 987, 1597, 2584, 4181, 6765,
     10946, 17711, 28657, 46368]
  low = 0
  high = len(lis) - 1
   
  # 为了使得查找表满足斐波那契特性，在表的最后添加几个同样的值
  # 这个值是原查找表的最后那个元素的值
  # 添加的个数由F[k]-1-high决定
  k = 0
  while high > F[k]-1:
    k += 1
  print(k)
  i = high
  while F[k]-1 > i:
    lis.append(lis[high])
    i += 1
  print(lis)
   
  # 算法主逻辑。time用于展示循环的次数。
  time = 0
  while low <= high:
    time += 1
    # 为了防止F列表下标溢出，设置if和else
    if k < 2:
      mid = low
    else:
      mid = low + F[k-1]-1
     
    print("low=%s, mid=%s, high=%s" % (low, mid, high))
    if key < lis[mid]:
      high = mid - 1
      k -= 1
    elif key > lis[mid]:
      low = mid + 1
      k -= 2
    else:
      if mid <= high:
        # 打印查找的次数
        print("times: %s" % time)
        return mid
      else:
        print("times: %s" % time)
        return high
  print("times: %s" % time)
  return False
 
if __name__ == &#39;__main__&#39;:
  LIST = [1, 5, 7, 8, 22, 54, 99, 123, 200, 222, 444]
  result = fibonacci_search(LIST, 444)
  print(result)

Analyse de l'algorithme : La complexité temporelle globale de la recherche de Fibonacci est également O(log (n)). Mais en termes de performances moyennes, c'est mieux que la recherche binaire. Mais dans le pire des cas, par exemple, si la clé est ici 1, la recherche se fait toujours dans la moitié gauche. À ce stade, son efficacité est inférieure à la recherche binaire.

Résumé : L'opération intermédiaire de la recherche binaire est l'addition et la division, la recherche d'interpolation est constituée de quatre opérations arithmétiques complexes et la recherche de Fibonacci n'est que l'opération d'addition et de soustraction la plus simple. Lors de la recherche de données massives, cette différence subtile peut affecter l'efficacité finale de la recherche. Par conséquent, les trois méthodes de recherche de tableaux ordonnés sont essentiellement des choix de points de partage différents, chacun ayant ses propres avantages et inconvénients, et le choix doit être basé sur la situation réelle.

4. Recherche d'index linéaire

Pour les données massives non ordonnées, afin d'améliorer la vitesse de recherche, une table d'index est généralement construite pour cela.

L'indexation est le processus d'association d'un mot-clé à son enregistrement correspondant.

Un index se compose de plusieurs éléments d'index, et chaque élément d'index contient au moins des informations telles que des mots-clés et leurs emplacements d'enregistrement correspondants dans la mémoire.

Les indices peuvent être divisés en index linéaires, index arborescents et index multi-niveaux selon leurs structures.

Index linéaire : organisez la collection d'éléments d'index à travers une structure linéaire, également appelée table d'index.

L'index linéaire peut être divisé en : index dense, index de bloc et index inversé

1 Index dense

L'index dense fait référence à en ligne dans un. index sexuel, une entrée d’index est créée pour chaque enregistrement de la collecte de données.

Cela équivaut en fait à construire une liste linéaire ordonnée pour un ensemble non ordonné. Les éléments de l'index doivent être classés dans l'ordre selon le code clé.

Cela équivaut également à effectuer à l'avance le travail de tri requis dans le processus de recherche.

1. L'index de bloc

divise un grand nombre d'ensembles de données non ordonnés en blocs, de sorte qu'il y ait du désordre au sein du bloc et de l'ordre entre les blocs.

这其实是有序查找和无序查找的一种中间状态或者说妥协状态。因为数据量过大，建立完整的稠密索引耗时耗力，占用资源过多；但如果不做任何排序或者索引，那么遍历的查找也无法接受，只能折中，做一定程度的排序或索引。

分块索引的效率比遍历查找的O(n)要高一些，但与二分查找的O(logn)还是要差不少。

1.倒排索引

不是由记录来确定属性值，而是由属性值来确定记录的位置，这种被称为倒排索引。其中记录号表存储具有相同次关键字的所有记录的地址或引用（可以是指向记录的指针或该记录的主关键字）。

倒排索引是最基础的搜索引擎索引技术。

五、二叉排序树

二叉排序树又称为二叉查找树。它或者是一颗空树，或者是具有下列性质的二叉树：

若它的左子树不为空，则左子树上所有节点的值均小于它的根结构的值；

若它的右子树不为空，则右子树上所有节点的值均大于它的根结构的值；

它的左、右子树也分别为二叉排序树。

构造一颗二叉排序树的目的，往往不是为了排序，而是为了提高查找和插入删除关键字的速度。

二叉排序树的操作：

1.查找：对比节点的值和关键字，相等则表明找到了；小了则往节点的左子树去找，大了则往右子树去找，这么递归下去，最后返回布尔值或找到的节点。

2.插入：从根节点开始逐个与关键字进行对比，小了去左边，大了去右边，碰到子树为空的情况就将新的节点链接。

3.删除：如果要删除的节点是叶子，直接删；如果只有左子树或只有右子树，则删除节点后，将子树链接到父节点即可；如果同时有左右子树，则可以将二叉排序树进行中序遍历，取将要被删除的节点的前驱或者后继节点替代这个被删除的节点的位置。

#!/usr/bin/env python
# -*- coding:utf-8 -*-
# Author: Liu Jiang
# Python 3.5
 
 
class BSTNode:
  """
  定义一个二叉树节点类。
  以讨论算法为主，忽略了一些诸如对数据类型进行判断的问题。
  """
  def __init__(self, data, left=None, right=None):
    """
    初始化
    :param data: 节点储存的数据
    :param left: 节点左子树
    :param right: 节点右子树
    """
    self.data = data
    self.left = left
    self.right = right
 
 
class BinarySortTree:
  """
  基于BSTNode类的二叉排序树。维护一个根节点的指针。
  """
  def __init__(self):
    self._root = None
 
  def is_empty(self):
    return self._root is None
 
  def search(self, key):
    """
    关键码检索
    :param key: 关键码
    :return: 查询节点或None
    """
    bt = self._root
    while bt:
      entry = bt.data
      if key < entry:
        bt = bt.left
      elif key > entry:
        bt = bt.right
      else:
        return entry
    return None
 
  def insert(self, key):
    """
    插入操作
    :param key:关键码
    :return: 布尔值
    """
    bt = self._root
    if not bt:
      self._root = BSTNode(key)
      return
    while True:
      entry = bt.data
      if key < entry:
        if bt.left is None:
          bt.left = BSTNode(key)
          return
        bt = bt.left
      elif key > entry:
        if bt.right is None:
          bt.right = BSTNode(key)
          return
        bt = bt.right
      else:
        bt.data = key
        return
 
  def delete(self, key):
    """
    二叉排序树最复杂的方法
    :param key: 关键码
    :return: 布尔值
    """
    p, q = None, self._root   # 维持p为q的父节点，用于后面的链接操作
    if not q:
      print("空树！")
      return
    while q and q.data != key:
      p = q
      if key < q.data:
        q = q.left
      else:
        q = q.right
      if not q:        # 当树中没有关键码key时，结束退出。
        return
    # 上面已将找到了要删除的节点，用q引用。而p则是q的父节点或者None（q为根节点时）。
    if not q.left:
      if p is None:
        self._root = q.right
      elif q is p.left:
        p.left = q.right
      else:
        p.right = q.right
      return
    # 查找节点q的左子树的最右节点，将q的右子树链接为该节点的右子树
    # 该方法可能会增大树的深度，效率并不算高。可以设计其它的方法。
    r = q.left
    while r.right:
      r = r.right
    r.right = q.right
    if p is None:
      self._root = q.left
    elif p.left is q:
      p.left = q.left
    else:
      p.right = q.left
 
  def __iter__(self):
    """
    实现二叉树的中序遍历算法,
    展示我们创建的二叉排序树.
    直接使用python内置的列表作为一个栈。
    :return: data
    """
    stack = []
    node = self._root
    while node or stack:
      while node:
        stack.append(node)
        node = node.left
      node = stack.pop()
      yield node.data
      node = node.right
 
 
if __name__ == &#39;__main__&#39;:
  lis = [62, 58, 88, 48, 73, 99, 35, 51, 93, 29, 37, 49, 56, 36, 50]
  bs_tree = BinarySortTree()
  for i in range(len(lis)):
    bs_tree.insert(lis[i])
  # bs_tree.insert(100)
  bs_tree.delete(58)
  for i in bs_tree:
    print(i, end=" ")
  # print("\n", bs_tree.search(4))

二叉排序树总结：

二叉排序树以链式进行存储，保持了链接结构在插入和删除操作上的优点。

在极端情况下，查询次数为1，但最大操作次数不会超过树的深度。也就是说，二叉排序树的查找性能取决于二叉排序树的形状，也就引申出了后面的平衡二叉树。

给定一个元素集合，可以构造不同的二叉排序树，当它同时是一个完全二叉树的时候，查找的时间复杂度为O(log(n))，近似于二分查找。

当出现最极端的斜树时，其时间复杂度为O(n)，等同于顺序查找，效果最差。

六、 平衡二叉树

平衡二叉树（AVL树，发明者的姓名缩写）：一种高度平衡的排序二叉树，其每一个节点的左子树和右子树的高度差最多等于1。

平衡二叉树首先必须是一棵二叉排序树！

平衡因子（Balance Factor）：将二叉树上节点的左子树深度减去右子树深度的值。

对于平衡二叉树所有包括分支节点和叶节点的平衡因子只可能是-1,0和1，只要有一个节点的因子不在这三个值之内，该二叉树就是不平衡的。

最小不平衡子树：距离插入结点最近的，且平衡因子的绝对值大于1的节点为根的子树。

平衡二叉树的构建思想：每当插入一个新结点时，先检查是否破坏了树的平衡性，若有，找出最小不平衡子树。在保持二叉排序树特性的前提下，调整最小不平衡子树中各结点之间的连接关系，进行相应的旋转，成为新的平衡子树。

下面是由[1,2,3,4,5,6,7,10,9]构建平衡二叉树

7. Arbre de recherche multi-voies (arbre B)

Arbre de recherche multi-voies (arbre de recherche multi-voies) : les enfants de chaque nœud Il peut y en avoir plus de deux et chaque nœud peut stocker plusieurs éléments.
Pour les arbres de recherche multidirectionnels, la clé est le nombre d'éléments que chaque nœud peut stocker et le nombre de ses enfants. Il existe quatre formes couramment utilisées : l'arbre 2-3, l'arbre 2-3-4 et l'arbre B. et les arbres B.

Arbre 2-3

Arbre 2-3 : Chaque nœud a 2 enfants, 3 enfants ou aucun enfant.

Un 2-nœuds contient un élément et deux enfants (ou aucun enfant, ne peut pas avoir un seul enfant). Semblable à un arbre trié binaire, les éléments contenus dans le sous-arbre de gauche sont tous plus petits que l'élément, et les éléments contenus dans le sous-arbre de droite sont plus grands que l'élément.

Un 3 nœuds contient deux éléments et trois enfants (ou aucun enfant, pas seulement un ou deux enfants).

2-3 Toutes les feuilles de l'arbre doivent être au même niveau.

L'opération d'insertion est la suivante :

L'opération de suppression est la suivante :

2- L'arbre 3-4

est en fait une extension de l'arbre 2-3, comprenant l'utilisation de 4 nœuds. Un nœud à 4 contient trois éléments, petit, moyen et grand, et quatre enfants (ou aucun enfant).

Son opération d'insertion :

Son opération de suppression :

Arbre B

B-tree est un arbre de recherche multidirectionnel équilibré. Le nombre maximum d’enfants d’un nœud est appelé l’ordre du B-tree. L’arbre 2-3 est un arbre B du troisième ordre et le 2-3-4 est un arbre B du quatrième ordre.

La structure de données de B-tree est principalement utilisée dans l'interaction des données entre la mémoire et la mémoire externe.

Arbre B

Afin de résoudre le parcours de tous les éléments de l'arbre B, etc. Le problème fondamental est qu'après avoir ajouté une nouvelle méthode d'organisation des éléments à la structure d'origine, un arbre B est formé.

B-tree est un arbre déformé de B-tree qui apparaît en réponse aux besoins du système de fichiers à proprement parler, ce n'est plus l'arbre le plus basique.

Dans un arbre B, les éléments qui apparaissent dans un nœud de branche seront à nouveau répertoriés comme leurs successeurs dans l'ordre (nœuds feuilles) à cette position de nœud de branche. De plus, chaque nœud feuille enregistrera un pointeur vers le nœud feuille suivant.

Tous les nœuds feuilles contiennent des informations sur tous les mots-clés et les pointeurs associés. Les nœuds feuilles eux-mêmes sont liés par ordre croissant en fonction de la taille des mots-clés

Le. La structure du B-tree est particulièrement adaptée aux recherches avec des plages. Par exemple, recherchez des personnes âgées entre 20 et 30 ans.

8. Table de hachage (table de hachage)

Table de hachage : Il n'y a aucune relation entre tous les éléments. L'emplacement de stockage de l'élément est directement calculé via une fonction utilisant le mot-clé de l'élément. Cette fonction de relation un-à-un est appelée fonction de hachage ou fonction de hachage.

La technologie de hachage est utilisée pour stocker des enregistrements dans un espace de stockage continu, appelé table de hachage ou table de hachage (Hash Table). L'emplacement de stockage correspondant au mot-clé est appelé adresse de hachage.

La table de hachage est une structure de stockage orientée recherche. Le problème pour lequel il est le mieux adapté est de trouver des enregistrements égaux à une valeur donnée. Cependant, il ne convient pas aux situations dans lesquelles un certain mot-clé peut correspondre à de nombreux enregistrements, comme par exemple la recherche de tous les genres « masculins ». Il ne convient pas non plus aux recherches par distance, telles que la recherche de personnes âgées de 20 à 30 ans. Le tri, le plus grand, le plus petit, etc. est également inapproprié.

Par conséquent, les tables de hachage sont généralement utilisées pour les structures de données où les mots-clés ne sont pas répétés. Par exemple, le type de données du dictionnaire Python.

La conception d'une fonction de hachage simple, uniforme et à utilisation élevée du stockage est le problème le plus critique de la technologie de hachage.

Cependant, les fonctions de hachage générales sont confrontées à des problèmes de conflit.

Conflit : Deux mots-clés différents ont le même résultat après avoir été calculés par la fonction de hachage. collision.

8.1 Méthode de construction de la fonction de hachage

Bonne fonction de hachage : calcul simple, distribution uniforme des adresses de hachage

Méthode d'adressage direct

Par exemple, prenons une fonction linéaire de la clé comme fonction de hachage :

f(key) = a*key b (a, b sont des constantes)

2.数字分析法

抽取关键字里的数字，根据数字的特点进行地址分配

3.平方取中法

将关键字的数字求平方，再截取部分

4.折叠法

将关键字的数字分割后分别计算，再合并计算，一种玩弄数字的手段。

5.除留余数法

最为常见的方法之一。

对于表长为m的数据集合，散列公式为：

f(key) = key mod p (p<=m)

mod：取模（求余数）

该方法最关键的是p的选择，而且数据量较大的时候，冲突是必然的。一般会选择接近m的质数。

6.随机数法

选择一个随机数，取关键字的随机函数值为它的散列地址。

f(key) = random(key)

总结，实际情况下根据不同的数据特性采用不同的散列方法，考虑下面一些主要问题：

计算散列地址所需的时间

关键字的长度

散列表的大小

关键字的分布情况

记录查找的频率

8.2 处理散列冲突

1、开放定址法

就是一旦发生冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将记录存入。

公式是：

这种简单的冲突解决办法被称为线性探测，无非就是自家的坑被占了，就逐个拜访后面的坑，有空的就进，也不管这个坑是不是后面有人预定了的。

线性探测带来的最大问题就是冲突的堆积，你把别人预定的坑占了，别人也就要像你一样去找坑。

改进的办法有二次方探测法和随机数探测法。

2、再散列函数法

发生冲突时就换一个散列函数计算，总会有一个可以把冲突解决掉，它能够使得关键字不产生聚集，但相应地增加了计算的时间。

3、链接地址法
碰到冲突时，不更换地址，而是将所有关键字为同义词的记录存储在一个链表里，在散列表中只存储同义词子表的头指针，如下图：

这样的好处是，不怕冲突多；缺点是降低了散列结构的随机存储性能。本质是用单链表结构辅助散列结构的不足。

4、公共溢出区法

其实就是为所有的冲突，额外开辟一块存储空间。如果相对基本表而言，冲突的数据很少的时候，使用这种方法比较合适。

8.3 散列表查找实现

下面是一段简单的实现代码：

#!/usr/bin/env python
# -*- coding:utf-8 -*-
# Author: Liu Jiang
# Python 3.5
# 忽略了对数据类型，元素溢出等问题的判断。
 
 
class HashTable:
  def __init__(self, size):
    self.elem = [None for i in range(size)] # 使用list数据结构作为哈希表元素保存方法
    self.count = size # 最大表长
 
  def hash(self, key):
    return key % self.count # 散列函数采用除留余数法
 
  def insert_hash(self, key):
    """插入关键字到哈希表内"""
    address = self.hash(key) # 求散列地址
    while self.elem[address]: # 当前位置已经有数据了，发生冲突。
      address = (address+1) % self.count # 线性探测下一地址是否可用
    self.elem[address] = key # 没有冲突则直接保存。
 
  def search_hash(self, key):
    """查找关键字，返回布尔值"""
    star = address = self.hash(key)
    while self.elem[address] != key:
      address = (address + 1) % self.count
      if not self.elem[address] or address == star: # 说明没找到或者循环到了开始的位置
        return False
    return True
 
 
if __name__ == '__main__':
  list_a = [12, 67, 56, 16, 25, 37, 22, 29, 15, 47, 48, 34]
  hash_table = HashTable(12)
  for i in list_a:
    hash_table.insert_hash(i)
 
  for i in hash_table.elem:
    if i:
      print((i, hash_table.elem.index(i)), end=" ")
  print("\n")
 
  print(hash_table.search_hash(15))
  print(hash_table.search_hash(33))

   

8.4 散列表查找性能分析

如果没发生冲突，则其查找时间复杂度为O(1)，属于最极端的好了。

但是，现实中冲突可不可避免的，下面三个方面对查找性能影响较大：

散列函数是否均匀

处理冲突的办法

散列表的装填因子（表内数据装满的程度）

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持PHP中文网。

更多Explication détaillée des structures de données et des algorithmes de recherche couramment utilisés (implémentation Python)相关文章请关注PHP中文网！