Chaîne de hachage que je voulais éviter (2)

Bonsoir. Merci pour votre soutien continu. m (_ _) m

Suite de la session précédente. Je l'ai écrit en douceur Supplément sur dump.

test.py


    def dump(self):
        #je suis table[*]Parce que c'est un pointeur vers une table[i] 
        for i in range(self.capacity):
            # table[i]La clé stockée dans,value,Appeler np
            p = self.table[i]
            # end=""Est une description qui se connecte à l'impression suivante
            print(i,end="")
            while p is not None:
                #Afficher la description suivante immédiatement après i ci-dessus
                # p.key , p.Continuer à afficher la valeur
                print(f"=>{p.key}({p.value})",end="")
                #Remplacez np par p et la clé suivante,value,Connectez-vous à np
                p = p.np
            #nouvelle ligne
            print()

Si vous avez une image qui stocke des données avec une chaîne de perles que j'ai écrite la dernière fois Je pense que c'est facile à imaginer.

Jusqu'à présent, en utilisant la chaîne Hash, J'ai stocké les données. Maintenant que nous l'avons stocké, remettons en question l'approche de recherche de données. Fondamentalement, il recherche des données en les associant à la clé du nœud déjà stockée.

test.py


    def search(self,key):
        #Trouvez le pointeur de la table à partir de la clé.
        Vhash = key % self.capacity
        p = self.table[Vhash]
        
        while p is not None:
            #Lorsque la clé stockée et la clé d'entrée correspondent. ..
            if p.key == key:
                #Afficher les données avec impression
                return print(f"searched value is {p.value}")
            p = p.np
        #S'il n'y a rien même si vous recherchez les données correspondantes jusqu'à la fin avec while, échouez
        print("faile to search")

Si vous le recherchez en l'ajoutant au tableau préparé, Vous pouvez également supprimer les éléments inutiles, non? Défions. Identique à la recherche, recherchez essentiellement le nœud correspondant par clé. Après cela, changez le point de connexion de Nœud à Nœud pour terminer la suppression. Oui, nous éditerons le np à l'intérieur du nœud.

test.py


    def remove(self,key):
        Vhash = key % self.capacity
        p  = self.table[Vhash]
        pp = None #Valeur initiale Aucune
        while p is not None:
            if p.key == key
                #Description lors de la suppression des premières données
                if pp is None:
                    self.table[Vhash] = self.table[Vhash].np
                #Modifier les points de connexion np autres que le premier élément
                else:
                    #pp sera décrit plus tard, mais l'image est Node avant que la clé ne corresponde.
                    #p est le nœud auquel correspond la clé.
                    # pp.En substituant np du Node dont la clé correspond à np
                    #Supprimer le nœud correspondant de clé de la connexion de données
                    pp.np = p.np
        #Si p au début.key !=Si c'est la clé, remplacez p par pp et tampon
        pp = p            
        #Réglez la valeur de p sur p pour passer au nœud de pointe avec while.Mis à jour avec np
        p  = p.np

Je n'ai pas expliqué ce qu'est Hash ?? Je crois comprendre qu'en fournissant une clé, vous pouvez obtenir un pointeur vers le tableau correspondant en une seule fois. Vous pouvez le trouver, puis vous pouvez trouver la valeur correspondante par recherche linéaire. C'était une méthode de recherche intéressante. Bien entendu, pour atteindre ce qui précède, il doit être stocké selon cette règle.

Jusqu'à présent, les articles ont été organisés à partir d'un arrangement donné ou du même arrangement. L'approche d'exploration était basique.

Cette fois, ce n'est pas le cas, examinez la méthode de stockage elle-même C'était un algorithme intéressant qui facilitait l'exploration. (`) Non

Je vais mettre l'image entière. Il existe un plan optimal Si vous rencontrez des problèmes, faites-le moi savoir. M (_ _) m.

Chained_hash.py


class Node:
    def __init__(self,key,value,np):
        self.key = key
        self.value = value
        self.np = np

class ChainedHash:
    def __init__(self,capacity):
        self.capacity = capacity
        self.table = [None]*self.capacity
        
    def add(self,key,value):
        
        Vhash = key % self.capacity
        p = self.table[Vhash]
        
        while p is not None:
            if p.key == key:
                return False
            p = p.np
        
        temp = Node(key,value,self.table[Vhash])
        self.table[Vhash] = temp
    
    def dump(self):
        for i in range(self.capacity):
            p = self.table[i]
            print(i,end="")
            while p is not None:
                print(f"=>{p.key}({p.value})",end="")
                p = p.np
            print()
            
    def search(self,key):
        Vhash = key % self.capacity
        p = self.table[Vhash]
        
        while p is not None:
            if p.key == key:
                return print(f"searched value is {p.value}")
            p = p.np
        print("faile to search")
        
    def remove(self,key):
        Vhash = key % self.capacity
        p  = self.table[Vhash]
        pp = None
        while p is not None:
            if p.key == key:
                if pp is None:
                    self.table[Vhash] = self.table[Vhash].np
                else:
                    pp.np = p.np
        pp = p            
        p  = p.np

test = ChainedHash(7)

while True:
    num = int(input("select 1.add, 2.dump, 3.search, 4.remove : "))
    if num == 1:
        key = int(input("key: "))
        val = int(input("val: "))
        test.add(key,val)
    elif num == 2:
        test.dump()
    elif num == 3:
        key = int(input("key: "))
        test.search(key)
    elif num == 4:
        key = int(input("key: "))
        test.remove(key)
    else:
        break  

Recommended Posts

Chaîne de hachage que je voulais éviter (2)
Chaîne de hachage que je voulais éviter (1)
Je voulais faire évoluer cGAN vers ACGAN
Je voulais résoudre ABC160 avec Python
Je voulais résoudre ABC159 avec Python
Je voulais résoudre ABC172 avec Python
Je voulais vraiment copier avec du sélénium
Implémentation de DQN avec TensorFlow (je voulais ...)
Je voulais résoudre NOMURA Contest 2020 avec Python
Je voulais jouer avec la courbe de Bézier
Je voulais installer Python 3.4.3 avec Homebrew + pyenv
Je voulais juste comprendre le module Pickle de Python
Je voulais aussi vérifier les indices de type avec numpy
J'ai commencé à analyser
Je voulais utiliser la bibliothèque Python de MATLAB
J'ai essayé de déboguer.
[Échec] Je voulais générer des phrases en utilisant TextRegressor de Flair
Une histoire sur la volonté de modifier un peu le site d'administration de Django
Je voulais résoudre le concours de programmation Panasonic 2020 avec Python
J'ai essayé de créer automatiquement un rapport avec la chaîne de Markov
[Chaîne de Markov] J'ai essayé de charger des émotions négatives dans Python.
[Chaîne de Markov] J'ai essayé de lire les citations en Python.
Je voulais ignorer certaines extensions lors de la création de la documentation Sphinx
Je voulais m'inquiéter du temps d'exécution et de l'utilisation de la mémoire
J'ai capturé le projet Toho avec Deep Learning ... je le voulais.
Je voulais calculer un tableau avec la méthode des subs de Sympy
Je voulais supprimer plusieurs objets en s3 avec boto3
J'ai essayé d'apprendre PredNet
J'ai essayé d'organiser SVM.
J'ai parlé à Raspberry Pi
J'ai essayé d'implémenter PCANet
Introduction à l'optimisation non linéaire (I)
J'ai appliqué LightFM à Movielens
Je veux résoudre SUDOKU
J'ai essayé de réintroduire Linux
J'ai essayé de présenter Pylint
J'ai essayé de résumer SparseMatrix
jupyter je l'ai touché
J'ai essayé d'implémenter StarGAN (1)
Je voulais le faire comme exécuter un cas de test pour AtCoder.
Je voulais convertir ma photo de visage en un style Yuyu.
Je voulais contester la classification du CIFAR-10 en utilisant l'entraîneur de Chainer
Je voulais faire quelque chose comme la pipe d'Elixir en Python
Je voulais résoudre le problème ABC164 A ~ D avec Python
Ce que j'ai fait quand je voulais rendre Python plus rapide -Édition Numba-
[Django] Je voulais tester lors du POST d'un fichier volumineux [TDD]