En bref, il semble s'agir d'un type de données stocké dans un état trié sans duplication. Pour cette raison, la dichotomie est toujours disponible pour les recherches de type set et semble être plus rapide.

Condition de mesure

Afin d'étudier le type «liste» et le type «set», j'ai étudié la recherche dans les quatre cas suivants.

Pour rendre les autres conditions identiques

• Le nombre d'éléments dans la liste est de 10 $ ^ 6 $ et il n'y a pas de duplication.
• L'élément à rechercher $ t $ satisfait $ 1 \ le t \ le 10 ^ 6 $. (Absolument trouvé)
• Générez 10 $ ^ 2 $, 10 $ ^ 3 $, 10 $ ^ 4 $ au hasard et recherchez chacun d'eux.

Je l'ai fait comme.

Code source

main.py

import time
import random
from collections import deque

num = [i+1 for i in range(1000000)]
num_shaffle = random.sample(num, len(num))
num_set = set(num_shaffle)
#Ce qu'il faut chercher
target = [random.randint(1, 1000000) for i in range(10000)]

#type de liste recherche linéaire ou type d'ensemble
def search_seaquence(L):
    each_time = deque([])

    for i in range(10000):
        #écoulé depuis le début_Mesurer le décalage horaire avec le temps
        start = time.time()
        target[i] in L
        elapsed_time = time.time() - start
        each_time.append(elapsed_time)

    return list(each_time)

#recherche de bissection de type de liste
def search_half(L):
    each_time = deque([])

    for i in range(10000):
        low = 0
        high = len(num) - 1
        start = time.time()
        
        while low <= high:
            mid = int((low + high) // 2)
            guess = L[mid]
            if guess == target[i]:
                break
            elif guess > target[i]:
                high = mid - 1
            else:
                low = mid + 1

        elapsed_time = time.time() - start
        each_time.append(elapsed_time)
    return list(each_time)


def cal_time(LIS, mode):
    print(mode)
    #temps total
    sum_time = sum(LIS)
    print ("sum_time:{0}".format(sum_time) + "[sec]")

    return 0


#Liste aléatoire / recherche linéaire
random_list = search_seaquence(num_shaffle)
cal_time(random_list, 'mode: random list')

#Liste de séquences / recherche linéaire
seaquence_list_seq = search_seaquence(num)
cal_time(seaquence_list_seq, 'mode: seaquence list seaquence')

#Liste de séquences / recherche coupée en deux
seaquence_list_half = search_half(num)
cal_time(seaquence_list_half, 'mode: seaquence list half')

#définir la recherche
set_seek = search_seaquence(num_set)
cal_time(set_seek, 'mode: set')

résultat

D'une manière ou d'une autre, j'essaye d'en faire un graphique.

(** Graphique logarithmique double **.)

Comme prévu, c'est vrai, mais ce n'est pas si différent selon la commande. Je pense que l'ordre de la dichotomie était $ O (\ log n) $, mais c'était assez différent. Il était surprenant que le type «set» soit environ 20 fois plus rapide pour 10 $ ^ 4 $ même dans la même dichotomie. (Peut-être que c'est un problème avec mon code)

[Ajout] Lorsque le nombre d'éléments dans la destination de recherche est modifié

Quand j'y ai pensé, j'ai réalisé que l'effet de la commande ne serait pas visible à moins que je ne change le nombre d'éléments dans la destination de recherche (list / set) pour la recherche. De plus, le nombre d'éléments dans la liste de destination de la recherche est défini sur 10 $ 4, 10 ^ 5, 10 ^ 6 $ tandis que la cible de recherche est fixée sur 10 $ 4 4 $. J'ai également enquêté sur le moment où il a été changé.

(** Graphique logarithmique double **.)

C'est exactement comme commandé. Je suis contente. Il semble que la raison pour laquelle le temps est plutôt réduit dans la recherche de deux minutes est que la destination de la recherche est choisie au hasard. En faisant cela, vous pouvez voir la force de l'ordre des journaux.

Résumé

Ne pas utiliser «X dans la liste» lors de la recherche de données en double (commande) Après tout, la recherche de deux minutes est rapide

Il peut également être utilisé lors de la recherche de données spécifiques à partir d'une grande quantité de données. Cependant, s'il s'agit d'un type «set», les informations d'index seront perdues. Quand j'ai voulu cette information, j'ai trouvé qu'il était nécessaire de garder la «liste» séparément.