Effizienzvergleich von Python-Listen und -Sets

Betriebseffizienz des Programms

Die Betriebseffizienz des Programms ist in zwei Typen unterteilt: Der erste ist die Zeiteffizienz und der zweite die Platzeffizienz. Zeiteffizienz wird als Zeitkomplexität bezeichnet, während Raumeffizienz als Raumkomplexität bezeichnet wird. Die Zeitkomplexität misst hauptsächlich die Ausführungsgeschwindigkeit eines Programms, während die Raumkomplexität hauptsächlich den zusätzlichen Speicherplatz misst, den ein Programm benötigt.

Die Zeit, die zum Ausführen eines Programms benötigt wird, kann nicht theoretisch berechnet werden. Nur wenn Sie das Programm auf einer Maschine ausführen, können Sie wissen, dass die Ergebnisse, die verschiedene Maschinen zu unterschiedlichen Zeiten erzielen, unterschiedlich sein können. Aber müssen wir jedes Programm auf dem Computer testen? Dies ist offensichtlich unrealistisch, daher wird die Analysemethode der Zeitkomplexität entwickelt. In der Praxis müssen wir bei der Berechnung der Zeitkomplexität nicht unbedingt die genaue Anzahl der Ausführungen berechnen, sondern nur die ungefähre Anzahl der Ausführungen. Wir verwenden im Allgemeinen die asymptotische Darstellung von Big O. Wenn die Anzahl der Ausführungen normalerweise 1 beträgt Sagen wir, die Zeitkomplexität sei O(1). Wenn es n-mal dauert, kann man sagen, dass die Zeitkomplexität O(n) ist.

Die Speicherplatzkomplexität ist ein Maß für die Menge an Speicherplatz, die ein Algorithmus während des Betriebs vorübergehend belegt. Die Speicherplatzkomplexität gibt nicht an, wie viele Bytes Speicherplatz das Programm einnimmt, da die Berechnung während des tatsächlichen Betriebs schwierig ist. Daher zählt die Speicherplatzkomplexität die Anzahl der Variablen. Die Berechnungsregeln für die Raumkomplexität ähneln im Wesentlichen denen der Zeitkomplexität und verwenden auch die asymptotische Big-O-Notation.

Die in Python häufig verwendeten Kombinationsdatentypen sind Tupel, Listen, Mengen und Wörterbücher. Informationen zur zeitlichen Komplexität der verschiedenen Operationen jedes Datentyps finden Sie auf dem offiziellen Link von Python.

• https :/ /wiki.python.org/moin/TimeComplexity

Sowohl Tupel als auch Listen sind Sequenztypen, und ihre Speichermechanismen sind grundsätzlich gleich; Mengen und Wörterbücher sind ebenfalls grundsätzlich gleich, der einzige Unterschied besteht darin, dass jedes Element der set hat keinen entsprechenden Wert. Als nächstes nehmen wir Sets und Listen als Beispiele, um deren Sucheffizienz und Speicheraufwand zu sehen.

Effizienz der Datensuche

Wie groß ist der Unterschied zwischen der Effizienz der Datensuche in Mengen und Listen? Schauen wir uns zunächst eine Reihe von Beispielen an:

import time
import random
nums = [random.randint(0, 2000000) for i in range(1000)]
list_test = list(range(1000000))
set_test = set(list_test)
count_list, count_set = 0, 0
t1 = time.time()# 测试在列表中进行查找
for num in nums:
 if num in list_test:
 count_list += 1
t2 = time.time()
for num in nums:# 测试在集合中进行查找
 if num in set_test:
 count_set += 1
t3 = time.time()# 测试在集合中进行查找
print('找到个数，列表：{}，集合：{}'.format(count_list, count_set))
print('使用时间，列表：{:.4f}s'.format(t2 - t1))
print('使用时间，集合：{:.4f}s'.format(t3 - t2))

Das Ausgabeergebnis lautet:

找到个数，列表：515，集合：515
使用时间，列表：7.7953s
使用时间，集合：0.0010s

Aus dem obigen Beispiel ist deutlich ersichtlich, dass die Sucheffizienz von Sätzen viel höher ist als die von Listen, also in verschiedenen Anwendungsszenarien Sie müssen den entsprechenden Datentyp auswählen. Bei einer kleinen Datenmenge ist kein Leistungsunterschied erkennbar. Sobald jedoch eine große Datenmenge geändert wird, wird der Unterschied sehr groß.

Datenspeicheraufwand

Die Sucheffizienz von Sets ist viel schneller als die von Listen. Der Hauptgrund dafür ist, dass Sets mehr Platz zum Speichern zusätzlicher Informationen benötigen Schauen wir uns als Nächstes den Unterschied im Speicheraufwand durch die Funktion getiszeof() an. Die Funktion getiszeof() wird im sys-Modul von Python verwendet. Die zurückgegebene Größe wird in Bytes angegeben.

import sys
import random
list_test = list(range(1000000))
set_test = set(range(1000000))
print('列表占用大小：', sys.getsizeof(list_test))
print('集合占用大小：', sys.getsizeof(set_test))

Das Ausgabeergebnis ist:

列表占用大小：9000112
集合占用大小：33554656

Aus den Ergebnissen ist ersichtlich, dass für denselben Dateninhalt die Kosten für die Sammlungsspeicherung um ein Vielfaches höher sind als für eine Liste.

Das obige ist der detaillierte Inhalt vonEffizienzvergleich von Python-Listen und -Sets. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!