J'ai étudié le temps de calcul de "X dans la liste" (recherche linéaire / recherche dichotomique) et "X dans l'ensemble"

** (* Ajouté le 13 mai 2020: lorsque le nombre d'éléments de la liste est modifié) **

Contexte

Chez ABC167 à Atcoder l'autre jour, j'ai viré TLE avec le problème suivant. ・ ABC167D-Teleporter

Téléportez les villes à tour de rôle, arrêtez-vous lorsque la boucle se produit et le nombre de fois restant J'ai réalisé que je devais utiliser mod pour le trouver.

Devenir une boucle ⇔ Rejoindre la même ville ⇔ Déjà dans la liste des villes visitées

J'ai pensé qu'il serait bon de réfléchir, et il a fallu beaucoup de temps pour traiter en utilisant X in list en Python.

Après tout, j'ai réalisé que je devrais utiliser «X in set» à la place. Je me demandais si la vitesse changerait autant, alors j'ai résumé les résultats de mes recherches.

Qu'est-ce que le type d'ensemble?

Extrait de la [documentation officielle] de Python (https://docs.python.org/ja/3/library/stdtypes.html#set-types-set-frozenset)

L'objet set est une collection non ordonnée d'objets hachables uniques. Les utilisations courantes incluent les tests d'attribution, la déduplication des séquences, les ensembles de produits, les ensembles de sommes, les ensembles de différences et les calculs arithmétiques tels que les différences symétriques (sommes logiques exclusives).

Les agrégats, comme les autres collections, prennent en charge x dans l'ensemble, len (ensemble), pour x dans l'ensemble. La collection n'étant pas ordonnée, l'ensemble n'enregistre ni l'ordre d'insertion ni la position des éléments. Par conséquent, l'ensemble ne prend pas en charge l'indexation, le découpage ou tout autre comportement séquentiel.

De plus, les fonctionnalités sont résumées de manière facile à comprendre dans here.

  • Le même élément ne contient qu'un seul </ strong>.
  • opérations de type liste telles que x dans l'ensemble, len (ensemble), pour x dans l'ensemble </ strong>
  • Les éléments peuvent être ajoutés / supprimés plus tard (le tuple ne peut pas être changé, la liste peut être modifiée, donc elle est plus proche de la liste)
  • Un calcul agrégé est possible (des calculs tels qu'être inclus dans A mais pas dans B, être inclus à la fois dans A et B, etc. peuvent être faciles et rapides </ strong>) --Parce que la commande n'est pas conservée, le premier que vous mettez n'est pas toujours le premier
  • Le fonctionnement de "x in set" est super rapide par rapport à la liste </ strong>

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.

nombre Type de données Ordre des données Méthode de recherche
1 list Aléatoire Recherche linéaire
2 list Trié Recherche linéaire
3 list Trié Recherche de bisection
4 set (Trié) (Recherche de bisection)

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

Méthode de recherche 10^2Total(sec) 10^3Total(sec) 10^4Total(sec)
Liste aléatoire / recherche linéaire 5.14 4.01 \times 10 4.65 \times 10^2
Liste triée / recherche linéaire 1.13 8.36 1.29 \times 10^2
Liste triée / dichotomie 3.46 \times 10^{-3} 2.03 \times 10^{-2} 1.16 \times 10^{-1}
définir le type 8.44 \times 10^{-5} 9.92 \times 10^{-4} 5.45 \times 10^{-3}

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

(** 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é.

Méthode de recherche\Nombre d'éléments de liste 10^4Total(sec) 10^5Total(sec) 10^6Total(sec)
Liste aléatoire / recherche linéaire 1.68 2.58 \times 10 5.37 \times 10^2
Liste triée / recherche linéaire 9.26 \times 10^{-1} 1.29 \times 10 1.34 \times 10^2
Liste triée / dichotomie 8.93 \times 10^{-2} 1.75 \times 10^{-1} 1.76 \times 10^{-1}
définir le type 5.62 \times 10^{-3} 4.02 \times 10^{-3} 1.01 \times 10^{-2}

image.png

(** 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.

Recommended Posts