Was ist ein Array und was kostet Einfügen?
Ein Array ist eine Reihe gleich großer Plätze, die im Speicher direkt hintereinander liegen. Wer weiß, wie es gespeichert wird, kann sagen, warum der Zugriff schnell ist und das Einfügen in der Mitte teuer.
Eine Bibliothek führt eine Warteliste mit 5000 Namen. Wer sich vorn einträgt, schiebt 5000 Namen um einen Platz weiter.
Am Ende dieser Lektion
Notiz
Ich kann erklären, wie eine Liste gespeichert wird und was das Einfügen kostet.
Schlüsselwörter
| Begriff | Was er bedeutet | Beispiel |
|---|---|---|
| Array | eine Reihe gleich großer Plätze direkt hintereinander | |
| Index | die Nummer eines Platzes, gezählt ab null | preise[0] |
| Schritt | ein Lesen oder Schreiben eines Platzes | |
| Verschieben | einen Wert auf den Nachbarplatz kopieren | |
| Kapazität | die Zahl der Plätze, die reserviert sind |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Der Index führt direkt zum Platz
Alle Plätze eines Arrays sind gleich groß. Eine ganze Zahl braucht zum Beispiel vier Byte. Der Computer rechnet: Adresse des Anfangs plus Index mal Platzgröße. Diese eine Rechnung dauert immer gleich lang. Es spielt keine Rolle, ob das Array zehn oder zehn Millionen Plätze hat.
Beispiel: Anfang bei Adresse 1000
| Index | Rechnung | Adresse |
|---|---|---|
| 0 | 1000 + 0 mal 4 | 1000 |
| 1 | 1000 + 1 mal 4 | 1004 |
| 2 | 1000 + 2 mal 4 | 1008 |
| 3 | 1000 + 3 mal 4 | 1012 |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Das Modul array zeigt die Platzgröße
Eine Python-Liste versteckt, wie groß ein Platz ist. Das Modul array legt dagegen ein echtes Array an. itemsize ist die Größe eines Platzes in Byte. Der Befehl legt drei ganze Zahlen ab und gibt Platzgröße, Zahl der Plätze und Gesamtgröße aus.
Platzgröße und Gesamtgröße ausgeben
python3 -c "import array; a = array.array('i', [10, 20, 30]); print(a.itemsize, len(a), a.itemsize * len(a))"Hier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Beim Einfügen müssen alle Werte dahinter weichen
Soll ein Wert in die Mitte, muss erst Platz entstehen. Alle Werte hinter der Stelle rücken einen Platz nach hinten, und zwar von hinten angefangen. Sonst würde ein Wert überschrieben. Beim Löschen rücken sie einen Platz nach vorn. Die Zahl der Schritte wächst mit der Zahl der Werte hinter der Stelle.
Beispiel: die 6 einfügen
| Schritt | Was passiert | Liste danach |
|---|---|---|
| Start | Platz am Ende schaffen | 3 5 8 12 _ |
| 1 | Die 12 rückt nach hinten | 3 5 8 _ 12 |
| 2 | Die 8 rückt nach hinten | 3 5 _ 8 12 |
| 3 | Die 6 kommt auf den freien Platz | 3 5 6 8 12 |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Sortiert einfügen und Verschiebungen zählen
# Einen Preis sortiert einfuegen und zaehlen, wie viele Werte weichen.
preise = [3, 5, 8, 12]
neu = 6
preise.append(0) # erst Platz am Ende schaffen
i = len(preise) - 1
verschoben = 0
while i > 0 and preise[i - 1] > neu:
preise[i] = preise[i - 1] # den groesseren Wert einen Platz nach hinten
i = i - 1
verschoben = verschoben + 1
preise[i] = neu
print(preise, verschoben)
# Aendern Sie neu auf 1 und fuehren Sie erneut aus.
Einfügen und Löschen am echten Array
Die zwei Befehle machen dasselbe mit einem echten Array. insert(1, 15) setzt die 15 auf Index 1 und rückt die anderen weiter. pop(0) nimmt den ersten Wert heraus, und alle anderen rücken nach vorn.
Mit insert einen Wert einfügen
python3 -c "import array; a = array.array('i', [10, 20, 30]); a.insert(1, 15); print(a.tolist())"Hier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Mit pop den ersten Wert löschen
python3 -c "import array; a = array.array('i', [10, 20, 30]); a.pop(0); print(a.tolist())"Hier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Ein volles Array wird größer kopiert
Ein Array hat eine feste Kapazität. Ist es voll, legt das Programm ein größeres an und kopiert alle Werte hinüber. Viele Listen verdoppeln dabei die Kapazität. Das Kopieren kostet einmal viel, danach ist lange Platz. Im Durchschnitt bleibt das Anhängen am Ende billig.
Beispiel: Anfangskapazität 4 wird verdoppelt
| Anhängen Nr. | Kapazität danach | Kopierte Werte |
|---|---|---|
| 1 bis 4 | 4 | Keine |
| 5 | 8 | 4 |
| 6 bis 8 | 8 | Keine |
| 9 | 16 | 8 |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Ein häufiger Fehler
Warnung
Viele denken, das Einfügen am Anfang einer Liste koste so wenig wie am Ende. Das stimmt nur für das Ende. Vorn müssen alle Werte weichen, hinten keiner. Fragen Sie darum immer, wie viele Werte hinter der Stelle liegen.