


Quel est le principe d'implémentation de Dict en Python ?
1. Implémentation de Dict non ordonné
Dict peut trouver rapidement des clés, grâce à sa stratégie espace-temps et à son implémentation de table de hachage. Lors de la lecture et de l'écriture de la clé, la clé sera hachée (la clé doit donc être d'un type immuable. S'il s'agit d'un type variable, sa valeur de hachage ne peut pas être calculée), puis en fonction de la valeur calculée et de la valeur actuelle. La longueur de l'espace du tableau est calculée modulo et la valeur obtenue est l'indice de la clé actuelle dans le tableau. Enfin, via l'indice, la valeur peut être lue avec une complexité temporelle de O(1). is Distributed est une approche courante, mais il y a aussi des problèmes. Que dois-je faire si le tableau est plein, ou que dois-je faire si les résultats de hachage sont les mêmes malgré les différentes clés ?
La solution au premier problème est de augmentez la capacité au moment approprié. Dans Python
, lorsque le nombre placé dans le Dict représente les 2/3 de la capacité, le Dict commencera à s'étendre. La capacité totale après expansion est doublée avant le. expansion. Ceci afin de réduire les expansions fréquentes. En conséquence, le nombre de migrations de clés augmente ;Python
中, 当Dict中放置的数量占容量的2/3时, Dict就会开始扩容, 扩容后的总容量是扩容之前的一倍, 这是为了减少频繁扩容, 导致key的迁移次数变多;
而针对第二个问题则有两个解法:
链接法: 原本数组里面存的是Key对应的值, 而链接法的数组存的是一个数组, 这个数组存了一个包含key和对应值的数组, 如下所示, 假设key1和key2的哈希结果都是0, 那就会插入到数组的0下标中, key1在0下标的数组的第一位, 而key2在插入时,发现已经存在key1了, 再用key2与key1进行对比, 发现它们的key其实是不一样的, 那就在0下标进行追加.
array = [ [ # 分别为key, hash值, 数值 ('key1', 123, 123), ('key2', 123, 123) ], [ ('key3', 123, 123) ] ]
开发寻址法: 开发寻址法走的是另外一个思路, 采取借用的思想, 在插入数据时, 如果遇到了冲突那就去使用当前下标的下一位, 如果下一位还是冲突, 就继续用下一位.在查找数据时则会对哈希值对应的key进行比较, 如果有值且对不上就找下一位, 直到或者空位找到为止。
上面两个的方案的实现都很简单, 对比下也很容易知道他们的优缺点:
链表法的优点:
删除记录方便, 直接处理数组对应下标的子数组即可.
平均查找速度快, 如果冲突了, 只需要对子数组进行查询即可
链表法的缺点:
用到了指针, 导致了查询速度会偏慢一点, 内存占用可能会较高, 不适合序列化. 而开放寻址法的优缺点是跟链表法反过来的, 由于Python万物基于Dict, 且都需要序列化, 所以选择了开放寻址法.
通过对比链表法和开放寻执法都可以发现, 他们都是针对哈希冲突的一个解决方案, 如果存数据的数组够大, 那么哈希冲突的可能性就会很小, 不用频繁扩容迁移数据, 但是占用的空间就会很大.所以一个好的哈希表实现初始值都不能太大, 在Python
的Dict的初始值是8. 另外哈希表还需要让存数据的数组的未使用空位保持在一个范围值内波动, 这样空间的使用和哈希冲突的概率都会保持在一个最优的情况, 但由于每次扩容都会消耗很大的性能, 也不能每次更改都进行一次扩容, 所以需要确定一个值, 当未使用/使用的占比达到这个值时, 就自动扩容, 在Python
arrray = [None, None, None, None, True, True, True, True]
- 🎜Supprimer les enregistrements Pratique, traitez simplement le sous-tableau correspondant à l'indice du tableau.🎜
- 🎜La vitesse de recherche moyenne est rapide S'il y a un conflit, il vous suffit d'interroger le sous-tableau🎜
- 🎜Des pointeurs sont utilisés, ce qui entraîne une vitesse de requête plus lente, une utilisation de la mémoire plus élevée et n'est pas adapté à la sérialisation.La méthode de recherche ouverte Les avantages et les inconvénients de la méthode d'adressage sont à l'opposé de la méthode de liste chaînée Puisque tout en Python est basé sur Dict et doit être sérialisé, la méthode d'adressage ouverte a été choisie 🎜
Python.
, cette valeur est de 2/3. C'est-à-dire que lorsque 2/3 est utilisé dans le Dict, une fois l'espace alloué, il s'étendra automatiquement pour atteindre un nouvel équilibre optimal, afin de le réduire. le nombre de migrations de clés lors de chaque extension, la capacité totale après l'extension doit être le double de la capacité totale avant l'extension, donc si c'est le cas, seulement la moitié du nombre de clés doit être migrée 🎜🎜La raison pour laquelle seulement la moitié des clés le seront. migré si la table de hachage est doublée, c'est que l'obtention de l'indice de la clé dans le tableau se fait en prenant le modulo de la valeur de hachage, comme un hachage. La capacité de la table de hachage est de 8. La valeur modulo d'une clé avec un la valeur de hachage de 20 est 4. Une fois la table de hachage développée, la longueur devient 16. À ce stade, le résultat modulo est toujours 4. Une clé avec une valeur de hachage de 11 a une valeur modulo de 3, et après expansion, la valeur modulo est de 11. On voit clairement qu'une fois la table de hachage étendue, les clés dont la valeur de hachage est supérieure à la capacité d'origine n'ont pas besoin d'être migrées, tandis que les clés dont la valeur de hachage est inférieure à la capacité doivent être migrées. 🎜🎜Mais si vous suivez la déclaration ci-dessus, il y a toujours un problème avec la méthode d'adressage ouverte, comme le tableau suivant :🎜arrray = [None, None, None, None, True, True, True, True]
以True代表当前数组的位置已经被占用, None代表未被占用, 可以看出当前并未满足使用了数组的2/3空间, 数组还未到扩容阶段。 此时假设要插入一个Key, 刚好落在数组下标4, 那么插入的时候就要一直查询下去, 最后发现只有数组下标0的位置的空的, 才可以真正的插入数据. 对于一个长度只有8的数组, 需要执行5次才能插入数据, 那也太浪费性能了, 所以Python
要实现一个算法, 尽量让冲突的数据插在别的地方. 在源码中, Python
用到了公式x = ((5*y) + 1) % 2**i
来实现跳跃插入冲突数据. 式子中x为数组的下一个坐标, y为当前发生冲突的坐标,i为容量系数, 比如初始化时, i为3, 那么容量就是8了, 第一次插入数据到坐标0冲突时, y = 0, 带入公式后, 求得x 等于1, 第二次插入数据到坐标0时, y = 1, 求得x 等于 6, 通过这样算下去, 可以发现数字生成轨迹是0>1>6>7>4>5>2>3>0一直循环着, 这样跳着插数据就能完美解决上面场景的问题.
2.有序Dict的原理
Python
3.6之前说的差不多, 它的数组大概是长这样的, 数组中存了子数组, 第一项为hash值, 第二项为key, 第三项为值.
array = [ [], [123456, "key1", 1], [], [], [], [234567, "key2", 2], [], [] ]
这种实现的空间大小在初始化时就固定了, 直到下次扩容再发送变化, 在遍历字典时, 实际上就是遍历数组, 只是把没有占用的空间进行跳过.可以看出这种遍历的生成的顺序只跟哈希结果相关, 无法跟插入顺序相关, 所以这种方法的实现是无序的(同时由于每次启动程序时, 他们的哈希计算是不一样的, 所以每次遍历的顺序也就各不相同了).
而在Python
3.7之后, Python
的Dict使用了新的数据结构, 使Python
新Dict的内存占用也比老的Dict少了, 同时新的Dict在遍历时是跟插入顺序是一致的, 具体的实现是, 初始化时会生成两个数组, 插入值时, 在数组二追加当前的数据, 并获得当前追加数据所在的下标A, 然后对key进行哈希取模算出下标B, 最后对数组下标B的值更新为A, 简单的演示如下:
# 初始的结构 # -1代表还未插入数据 array_1 = [-1, -1, -1, -1, -1, -1, -1, -1] array_2 = [] # 插入值后, 他就会变为: array_1 = [-1, 0, -1, -1, -1, 1, -1, -1] array_2 = [ [123456, "key1", 1], [234567, "key2", 2], ]
可以看出, 数组2的容量跟当前放入的值相等的, 数组1虽然还会保持1/3的空闲标记位, 但他只保存数组二的下标, 占用空间也不多, 相比之前的方案会节省一些空间, 同时在遍历的时候可以直接遍历数组2, 这样Python
的Dict就变为有序的了. 注: 为了保持操作高效, 在删除的时候, 只是把数组1的值设置为-2, 并把数组2对应的值设置为None, 而不去删除它, 在查找时会忽略掉数组1中值为-2的元素, 在遍历时会忽略掉值为None的元素.
3.有序字典的实现
通过上面的了解后, 可以使用Python
来写一个新版Dict的实现, 具体说明见注释:
from typing import Any, Iterable, List, Optional, Tuple class CustomerDict(object): def __init__(self): self._init_seed: int = 3 # 容量因子 self._init_length: int = 2 ** self._init_seed # 初始化数组大小 self._load_factor: float = 2 / 3 # 扩容因子 self._index_array: List[int] = [-1 for _ in range(self._init_length)] # 存放下标的数组 self._data_array: List[Optional[Tuple[int, Any, Any]]] = [] # 存放数据的数组 self._used_count: int = 0 # 目前用的量 self._delete_count: int = 0 # 被标记删除的量 def _create_new(self): """扩容函数""" self._init_seed += 1 # 增加容量因子 self._init_length = 2 ** self._init_seed old_data_array: List[Tuple[int, Any, Any]] = self._data_array self._index_array: List[int] = [-1 for _ in range(self._init_length)] self._data_array: List[Tuple[int, Any, Any]] = [] self._used_count = 0 self._delete_count = 0 # 这里只是简单实现, 实际上只需要搬运一半的数据 for item in old_data_array: if item is not None: self.__setitem__(item[1], item[2]) def _get_next(self, index: int): """计算冲突的下一跳,如果下标对应的值冲突了, 需要计算下一跳的下标""" return ((5*index) + 1) % self._init_length def _core(self, key: Any, default_value: Optional[Any] = None) -> Tuple[int, Any, int]: """获取数据或者得到可以放新数据的方法, 返回值是index_array的索引, 数据, data_array的索引""" index: int = hash(key) % (self._init_length - 1) while True: data_index: int = self._index_array[index] # 如果是-1则代表没有数据 if data_index == -1: break # 如果是-2则代表之前有数据则不过被删除了 elif data_index == -2: index = self._get_next(index) continue _, new_key, default_value = self._data_array[data_index] # 判断是不是对应的key if key != new_key: index = self._get_next(index) else: break return index, default_value, data_index def __getitem__(self, key: Any) -> Any: _, value, data_index = self._core(key) if data_index == -1: raise KeyError(key) return value def __setitem__(self, key: Any, value: Any) -> None: if (self._used_count / self._init_length) > self._load_factor: self._create_new() index, _, _ = self._core(key) self._index_array[index] = self._used_count self._data_array.append((hash(key), key, value)) self._used_count += 1 def __delitem__(self, key: Any) -> None: index, _, data_index = self._core(key) if data_index == -1: raise KeyError(key) self._index_array[index] = -2 self._data_array[data_index] = None self._delete_count += 1 def __len__(self) -> int: return self._used_count - self._delete_count def __iter__(self) -> Iterable: return iter(self._data_array) def __str__(self) -> str: return str({item[1]: item[2] for item in self._data_array if item is not None}) def keys(self) -> List[Any]: """模拟实现keys方法""" return [item[1] for item in self._data_array if item is not None] def values(self) -> List[Any]: """模拟实现values方法""" return [item[2] for item in self._data_array if item is not None] def items(self) -> List[Tuple[Any, Any]]: """模拟实现items方法""" return [(item[1], item[2]) for item in self._data_array if item is not None] if __name__ == '__main__': customer_dict: CustomerDict = CustomerDict() customer_dict["demo_1"] = "a" customer_dict["demo_2"] = "b" assert len(customer_dict) == 2 del customer_dict["demo_1"] del customer_dict["demo_2"] assert len(customer_dict) == 0 for i in range(30): customer_dict[i] = i assert len(customer_dict) == 30 customer_dict_value_list: List[Any] = customer_dict.values() for i in range(30): assert i == customer_dict[i] for i in range(30): assert customer_dict[i] == i del customer_dict[i] assert len(customer_dict) == 0
Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!

Outils d'IA chauds

Undresser.AI Undress
Application basée sur l'IA pour créer des photos de nu réalistes

AI Clothes Remover
Outil d'IA en ligne pour supprimer les vêtements des photos.

Undress AI Tool
Images de déshabillage gratuites

Clothoff.io
Dissolvant de vêtements AI

AI Hentai Generator
Générez AI Hentai gratuitement.

Article chaud

Outils chauds

Bloc-notes++7.3.1
Éditeur de code facile à utiliser et gratuit

SublimeText3 version chinoise
Version chinoise, très simple à utiliser

Envoyer Studio 13.0.1
Puissant environnement de développement intégré PHP

Dreamweaver CS6
Outils de développement Web visuel

SublimeText3 version Mac
Logiciel d'édition de code au niveau de Dieu (SublimeText3)

MySQL a une version communautaire gratuite et une version d'entreprise payante. La version communautaire peut être utilisée et modifiée gratuitement, mais le support est limité et convient aux applications avec des exigences de stabilité faibles et des capacités techniques solides. L'Enterprise Edition fournit une prise en charge commerciale complète pour les applications qui nécessitent une base de données stable, fiable et haute performance et disposées à payer pour le soutien. Les facteurs pris en compte lors du choix d'une version comprennent la criticité des applications, la budgétisation et les compétences techniques. Il n'y a pas d'option parfaite, seulement l'option la plus appropriée, et vous devez choisir soigneusement en fonction de la situation spécifique.

L'article présente le fonctionnement de la base de données MySQL. Tout d'abord, vous devez installer un client MySQL, tel que MySQLWorkBench ou le client de ligne de commande. 1. Utilisez la commande MySQL-UROot-P pour vous connecter au serveur et connecter avec le mot de passe du compte racine; 2. Utilisez Createdatabase pour créer une base de données et utilisez Sélectionner une base de données; 3. Utilisez CreateTable pour créer une table, définissez des champs et des types de données; 4. Utilisez InsertInto pour insérer des données, remettre en question les données, mettre à jour les données par mise à jour et supprimer les données par Supprimer. Ce n'est qu'en maîtrisant ces étapes, en apprenant à faire face à des problèmes courants et à l'optimisation des performances de la base de données que vous pouvez utiliser efficacement MySQL.

Le fichier de téléchargement mysql est corrompu, que dois-je faire? Hélas, si vous téléchargez MySQL, vous pouvez rencontrer la corruption des fichiers. Ce n'est vraiment pas facile ces jours-ci! Cet article expliquera comment résoudre ce problème afin que tout le monde puisse éviter les détours. Après l'avoir lu, vous pouvez non seulement réparer le package d'installation MySQL endommagé, mais aussi avoir une compréhension plus approfondie du processus de téléchargement et d'installation pour éviter de rester coincé à l'avenir. Parlons d'abord de la raison pour laquelle le téléchargement des fichiers est endommagé. Il y a de nombreuses raisons à cela. Les problèmes de réseau sont le coupable. L'interruption du processus de téléchargement et l'instabilité du réseau peut conduire à la corruption des fichiers. Il y a aussi le problème avec la source de téléchargement elle-même. Le fichier serveur lui-même est cassé, et bien sûr, il est également cassé si vous le téléchargez. De plus, la numérisation excessive "passionnée" de certains logiciels antivirus peut également entraîner une corruption des fichiers. Problème de diagnostic: déterminer si le fichier est vraiment corrompu

Les principales raisons de la défaillance de l'installation de MySQL sont les suivantes: 1. Problèmes d'autorisation, vous devez s'exécuter en tant qu'administrateur ou utiliser la commande sudo; 2. Des dépendances sont manquantes et vous devez installer des packages de développement pertinents; 3. Conflits du port, vous devez fermer le programme qui occupe le port 3306 ou modifier le fichier de configuration; 4. Le package d'installation est corrompu, vous devez télécharger et vérifier l'intégrité; 5. La variable d'environnement est mal configurée et les variables d'environnement doivent être correctement configurées en fonction du système d'exploitation. Résolvez ces problèmes et vérifiez soigneusement chaque étape pour installer avec succès MySQL.

MySQL a refusé de commencer? Ne paniquez pas, vérifions-le! De nombreux amis ont découvert que le service ne pouvait pas être démarré après avoir installé MySQL, et ils étaient si anxieux! Ne vous inquiétez pas, cet article vous emmènera pour le faire face calmement et découvrez le cerveau derrière! Après l'avoir lu, vous pouvez non seulement résoudre ce problème, mais aussi améliorer votre compréhension des services MySQL et vos idées de problèmes de dépannage, et devenir un administrateur de base de données plus puissant! Le service MySQL n'a pas réussi et il y a de nombreuses raisons, allant des erreurs de configuration simples aux problèmes système complexes. Commençons par les aspects les plus courants. Connaissances de base: une brève description du processus de démarrage du service MySQL Service Startup. Autrement dit, le système d'exploitation charge les fichiers liés à MySQL, puis démarre le démon mysql. Cela implique la configuration

MySQL peut s'exécuter sans connexions réseau pour le stockage et la gestion des données de base. Cependant, la connexion réseau est requise pour l'interaction avec d'autres systèmes, l'accès à distance ou l'utilisation de fonctionnalités avancées telles que la réplication et le clustering. De plus, les mesures de sécurité (telles que les pare-feu), l'optimisation des performances (choisissez la bonne connexion réseau) et la sauvegarde des données sont essentielles pour se connecter à Internet.

Guide d'optimisation des performances de la base de données MySQL dans les applications à forte intensité de ressources, la base de données MySQL joue un rôle crucial et est responsable de la gestion des transactions massives. Cependant, à mesure que l'échelle de l'application se développe, les goulots d'étranglement des performances de la base de données deviennent souvent une contrainte. Cet article explorera une série de stratégies efficaces d'optimisation des performances MySQL pour garantir que votre application reste efficace et réactive dans des charges élevées. Nous combinerons des cas réels pour expliquer les technologies clés approfondies telles que l'indexation, l'optimisation des requêtes, la conception de la base de données et la mise en cache. 1. La conception de l'architecture de la base de données et l'architecture optimisée de la base de données sont la pierre angulaire de l'optimisation des performances MySQL. Voici quelques principes de base: sélectionner le bon type de données et sélectionner le plus petit type de données qui répond aux besoins peut non seulement économiser un espace de stockage, mais également améliorer la vitesse de traitement des données.

L'optimisation des performances MySQL doit commencer à partir de trois aspects: configuration d'installation, indexation et optimisation des requêtes, surveillance et réglage. 1. Après l'installation, vous devez ajuster le fichier my.cnf en fonction de la configuration du serveur, tel que le paramètre innodb_buffer_pool_size, et fermer query_cache_size; 2. Créez un index approprié pour éviter les index excessifs et optimiser les instructions de requête, telles que l'utilisation de la commande Explication pour analyser le plan d'exécution; 3. Utilisez le propre outil de surveillance de MySQL (ShowProcessList, Showstatus) pour surveiller la santé de la base de données, et sauvegarde régulièrement et organisez la base de données. Ce n'est qu'en optimisant en continu ces étapes que les performances de la base de données MySQL peuvent être améliorées.
