Implémentez un double tableau sur Python et mesurez son utilisation de la mémoire et son temps de recherche. J'ai cherché diverses évaluations des performances, mais je n'ai pas trouvé d'implémentation satisfaisante, j'ai donc décidé de la faire moi-même. À l'origine, nous devrions considérer l'efficacité du processus de création d'un double tableau, mais cette fois, nous ne nous concentrerons pas sur cela. Le but est d'évaluer les performances de la double matrice terminée. (Par conséquent, l'addition dynamique est également exclue.) De plus, l'opération avec des fichiers n'est pas prise en compte. Créez-le en mémoire et mesurez-y ses performances.
C'est l'une des méthodes pour gérer les données de chaînes de caractères et peut réaliser la recherche à une vitesse efficace. Bien qu'il ait une structure simple en théorie, il peut ne pas être très efficace selon la méthode de mise en œuvre.
"Double array" est l'une des méthodes de mise en œuvre de la structure TRIE et peut réaliser une recherche à grande vitesse.
Pour le double tableau, veuillez vous référer aux explications faciles à comprendre à divers endroits.
J'ai déjà implémenté des "doubles tableaux" dans d'autres langages de programmation (C, C ++, Java, etc.), mais c'est la première fois que je l'implémente en Python. Je pense qu'il existe une méthode d'amélioration de l'efficacité propre à Python, mais je vais l'implémenter selon l'algorithme de base. J'ai utilisé la structure de données de base (List, Array, etc.) fournie avec le langage, mais j'ai créé l'implémentation de l'algorithme en plein zéro.
Si vous ne pouvez pas voir l'image complète du lien dans un nœud, vous ne pouvez pas vérifier où il peut être stocké dans le tableau, alors commencez par faire une implémentation TRIE simple (sans vitesse) afin de voir l'intégralité du lien, puis faites-le. Essayez de stocker dans un double tableau.
Dans cette implémentation à double tableau, Tail est pris en compte. Il est possible de représenter toutes les chaînes dans une structure TRIE. Cela simplifie l'algorithme. Cependant, il n'y a pas de branchement dans la chaîne de caractères vers la fin, et un lien est créé avec un nœud connecté, et par conséquent, le coût de la mémoire et du temps augmente. Par conséquent, nous pouvons améliorer cela en gérant la chaîne terminale sans branches comme Tail. En d'autres termes, nous avons implémenté un double tableau avec Tail du point de vue de la mise en œuvre de meilleures performances dans l'évaluation des performances.
Méthode de mesure des performances
Mesurer la recherche de correspondance exacte Essayez 100 fois et obtenez la valeur moyenne
Environnement d'exécution
Mot de recherche --87,379 mots anglais obtenus à partir de wordnet
Temps d'exécution et mémoire utilisée --Nombre de mots de recherche --50 000 caisses --Résultat: temps d'exécution --0,281 seconde --Résultat: Mémoire utilisée - 7.5MB