Kurz gesagt, es scheint sich um einen Datentyp zu handeln, der in einem sortierten Zustand ohne Duplizierung gespeichert wird. Aus diesem Grund ist die Dichotomie für die Suche nach Mengen immer verfügbar und scheint schneller zu sein.

Messbedingung

Um den Typ "Liste" und den Typ "Menge" zu untersuchen, habe ich die Suche in den folgenden vier Fällen untersucht.

Um andere Bedingungen gleich zu machen

• Die Anzahl der Elemente in der Liste beträgt $ 10 ^ 6 $ und es gibt keine Duplizierung.
• Das zu durchsuchende Element $ t $ erfüllt $ 1 \ le t \ le 10 ^ 6 $. (Absolut gefunden)
• Generiere $ 10 ^ 2 $, $ 10 ^ 3 $, $ 10 ^ 4 $ nach dem Zufallsprinzip und suche nach jedem.

Ich habe es so gemacht.

Quellcode

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)
#Wonach schauen
target = [random.randint(1, 1000000) for i in range(10000)]

#Listentyp lineare Suche oder Set-Typ
def search_seaquence(L):
    each_time = deque([])

    for i in range(10000):
        #von Anfang an verstrichen_Messen Sie den Zeitunterschied zur Zeit
        start = time.time()
        target[i] in L
        elapsed_time = time.time() - start
        each_time.append(elapsed_time)

    return list(each_time)

#Listentyp-Halbierungssuche
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)
    #Gesamtzeit
    sum_time = sum(LIS)
    print ("sum_time:{0}".format(sum_time) + "[sec]")

    return 0


#Zufällige Liste / lineare Suche
random_list = search_seaquence(num_shaffle)
cal_time(random_list, 'mode: random list')

#Sequenzliste / lineare Suche
seaquence_list_seq = search_seaquence(num)
cal_time(seaquence_list_seq, 'mode: seaquence list seaquence')

#Sequenzliste / halbierte Suche
seaquence_list_half = search_half(num)
cal_time(seaquence_list_half, 'mode: seaquence list half')

#Suche einstellen
set_seek = search_seaquence(num_set)
cal_time(set_seek, 'mode: set')

Ergebnis

Irgendwie versuche ich, daraus ein Diagramm zu machen.

(** Doppelter logarithmischer Graph **.)

Wie erwartet ist das richtig, aber es ist nicht so unterschiedlich, je nach Bestellung. Ich denke, die Reihenfolge für die Dichotomie war $ O (\ log n) $, aber es fühlte sich ganz anders an. Es war überraschend, dass der Typ "set" für $ 10 ^ 4 $ selbst in derselben Dichotomie etwa 20-mal schneller ist. (Vielleicht ist es ein Problem mit meinem Code)

[Hinzufügung] Wenn die Anzahl der Elemente im Suchziel geändert wird

Als ich darüber nachdachte, stellte ich fest, dass der Effekt der Reihenfolge nur sichtbar ist, wenn ich die Anzahl der Elemente im Suchziel (list / set) für die Suche geändert habe. Außerdem wird die Anzahl der Elemente in der Suchzielliste auf $ 10 ^ 4, 10 ^ 5, 10 ^ 6 $ festgelegt, während das Suchziel auf $ 10 ^ 4 $ festgelegt ist. Ich habe auch untersucht, wann es geändert wurde.

(** Doppelter logarithmischer Graph **.)

Es ist genau wie bestellt. Ich bin froh. Es scheint, dass der Grund, warum die Zeit bei der zweiminütigen Suche eher verkürzt wird, darin besteht, dass das Suchziel zufällig festgelegt wird. Auf diese Weise können Sie die Stärke der Protokollreihenfolge sehen.

Zusammenfassung

Verwenden Sie nicht "X in Liste", wenn Sie nach doppelten Daten suchen (Gebot) Immerhin ist die zweiminütige Suche schnell

Es kann auch verwendet werden, wenn nach bestimmten Daten aus einer großen Datenmenge gesucht wird. Wenn es sich jedoch um einen "Set" -Typ handelt, gehen die Indexinformationen verloren. Als ich diese Informationen wollte, stellte ich fest, dass es notwendig war, die "Liste" separat zu führen.