Obsah
1. Balíček array ze standardní knihovny Pythonu
2. Konstrukce pole s určením typů jeho prvků
4. Obsazení operační paměti Pythonovským objektem
5. Balíček Pympler pro přesnější informace o obsazení paměti Pythonem
6. Obsazení paměti prázdným seznamem popř. prázdným polem
7. Obsazení paměti seznamem popř. polem se sto prvky a 10000 prvky
8. Sekvenční přístup k prvkům seznamů a polí
9. Vložení hodnoty do seznamu či pole na určené místo (operace insert)
10. Interní struktura prvků polí
11. Uložení obsahu polí do souboru
12. Načtení obsahu polí z binárních souborů
13. Složitěji strukturované binární soubory
14. Teoretická a praktická rychlost přístupu k prvkům polí
15. Tentýž výpočet, ovšem realizovaný s využitím polí
16. Interní způsob uložení pole v paměti
17. Algoritmus pro alokaci paměti pro zvětšující a zmenšující se pole
19. Repositář s demonstračními příklady
1. Balíček array ze standardní knihovny Pythonu
Ve standardní knihovně programovacího jazyka Python se nachází množství užitečných ale i méně užitečných balíčků a modulů. V některých případech se může stát užitečným balíček nazvaný jednoduše array. Tento balíček umožňuje paměťově efektivní ukládání homogenních polí, tj. polí, jejichž prvky jsou všechny stejného typu. Tato pole interně obsahují skutečná céčková pole (viz další kapitoly) a uloženy jsou zde přímo hodnoty prvků, nikoli objekty (běžně se totiž v Pythonu pracuje s referencemi, což je z pohledu lokality i obsazení paměti velmi neefektivní řešení).
Navíc mohou pole růst nebo se zmenšovat, lze do nich přidávat prvky na libovolné místo, je podporována operace řezu (slice) (používá se naprosto stejný zápis, jako v případě seznamů) a navíc je možné taková pole ukládat do binárních souborů nebo je naopak z těchto souborů číst. Pole realizovaná v balíčku array je tak možné v odůvodněných případech využít namísto klasických seznamů. Dnes si však ukážeme i některé nedostatky tohoto způsobu reprezentace polí.
2. Konstrukce pole s určením typů jeho prvků
Homogenní jednorozměrné pole se při použití standardního balíčku array vytváří konstruktorem nazvaným taktéž array. Tomuto konstruktoru se musí předat jednoznakový kód typu prvků (viz tabulka zobrazená níže) a popř. hodnota, z níž se odvodí prvky pole. Touto hodnotou může být seznam popř. hodnota typu bytes nebo bytearray, tj. neměnitelné popř. naopak měnitelné sekvence bajtů (připomeňme si, že hodnotu typu bytes můžeme v případě potřeby zapsat formou b"znaky").
Příklad konstrukce prázdného pole:
from array import array a1 = array(kód_typu_prvků)
Příklad konstrukce pole se specifikací hodnoty prvků seznamem:
from array import array a1 = array(kód_typu_prvků, [1, 2, 3, 4])
popř.
from array import array
a1 = array("B", range(100))
Odlišný příklad konstrukce pole se specifikací hodnoty prvků sekvencí bajtů:
from array import array a2 = array(kód_typu_prvků, b"ABCDEFGH")
from array import array
a2 = array("h", b"ABCDEFG")
V tomto případě dojde k vyhození výjimky:
Traceback (most recent call last): File "<stdin>", line 1, in <module> ValueError: bytes length not a multiple of item size
3. Podporované typy prvků
Typ prvků je zakódován v jednoznakovém řetězci, který je předán jako první parametr do konstruktoru array.array. Podporovány jsou následující kódy, které vždy odpovídají jednomu datovému typu jazyka C a a mají (tak) i specifikovánu minimální velikost v bajtech:
| Zápis typu | Odpovídající typ v C | Minimální velikost v B |
|---|---|---|
| „b“ | signed char | 1 |
| „B“ | unsigned char | 1 |
| „h“ | signed short | 2 |
| „H“ | unsigned short | 2 |
| „i“ | signed int | 2 |
| „I“ | unsigned int | 2 |
| „l“ | signed long | 4 |
| „L“ | unsigned long | 4 |
| „q“ | signed long long | 8 |
| „Q“ | unsigned long long | 8 |
| „f“ | float | 4 |
| „d“ | double | 8 |
Jen pro zajímavost se podívejme, jaké typy prvků jsou podporovány v knihovně NumPy při konstrukci n-rozměrných polí. Jedná se sice o interně odlišnou datovou strukturu s jiným způsobem použití, ale mnoho kódů je shodných:
| Zápis typu | Odpovídající typ v C |
|---|---|
| „b“ | signed char |
| „B“ | unsigned char |
| „h“ | signed short |
| „H“ | unsigned short |
| „i“ | signed int |
| „I“ | unsigned int |
| „l“ | signed long |
| „L“ | unsigned long |
| „q“ | signed long long |
| „Q“ | unsigned long long |
| „e“ | half float |
| „f“ | float |
| „d“ | double |
| „g“ | long double |
| „F“ | complex float |
| „D“ | complex double |
| „G“ | complex long double |
4. Obsazení operační paměti Pythonovským objektem
Největší předností (a pravděpodobně i jedinou předností) balíčku array je jeho schopnost efektivně uložit prvky určitého datového typu do kontinuálního bloku operační paměti. To vede resp. mělo by to vést k velkým paměťovým úsporám. Ovšem toto tvrzení je vhodné si ověřit v praxi. Konkrétně tedy budeme porovnávat celkovou velikost seznamu s n-položkami s jednotlivými poli realizovanými balíčkem array.
Velikost, kterou nějaká hodnota zabírá v operační paměti, můžeme získat s využitím standardní funkce sys.getsizeof. Největší (a možná i jedinou) předností této funkce je fakt, že se jedná o funkci ze standardní knihovny sys. To mj. znamená, že tuto funkci je možné zavolat prakticky kdykoli a kdekoli, a to bez nutnosti instalace nějakých dalších balíčků.
Ovšem na tomto místě je vhodné upozornit na to, že tato funkce není příliš dokonalá, protože například neumožňuje zjistit velikost hodnot v operační paměti po zarovnání, protože alokátor paměti alokuje nové bloky vždy na adresách dělitelných nějakou konstantou 4, 8 či 16 (podle použitého operačního systému a architektury mikroprocesoru) a tudíž vlastně nebudou využity bajty umístěné těsně za koncem bloku v případě, že velikost bloku není dělitelná výše uvedenou konstantou. A navíc má tato standardní funkce problémy se zjištěním velikosti tříd a objektů, protože automaticky nezapočítává velikosti jednotlivých atributů atd. A totéž platí i pro kolekce, mezi jinými i pro seznamy.
5. Balíček Pympler pro přesnější informace o obsazení paměti Pythonem
Existují však i další (ovšem nutno dodat, že již nestandardní) balíčky, které „opravují“ chování funkce sys.getsizeof a navíc nabízí uživatelům i další zajímavou a potenciálně užitečnou funkcionalitu. Tyto balíčky je však pochopitelně nutné nejdříve nainstalovat. Prvním z balíčků, o nichž se dnes alespoň ve stručnosti zmíníme, je balíček nazvaný Pympler. Vzhledem k tomu, že je zaregistrovaný na PyPi, je instalace tohoto balíčku triviální a můžeme ji provést (pro právě přihlášeného uživatele) tímto příkazem:
$ pip install --user pympler
Alternativně pro systémy, které ještě mají paralelní instalaci Pythonu 2 a Pythonu 3, použijeme příkaz:
$ pip3 install --user pympler
Samotná instalace proběhne prakticky okamžitě:
Collecting pympler
Downloading Pympler-1.0.1-py3-none-any.whl (164 kB)
|████████████████████████████████| 164 kB 1.5 MB/s
Installing collected packages: pympler
Successfully installed pympler-1.0.1
6. Obsazení paměti prázdným seznamem popř. prázdným polem
V dnešním prvním demonstračním příkladu zjistíme, jak velkou kapacitu operační paměti musíme použít pro uložení prázdného seznamu (což je standardní kolekce Pythonu) nebo prázdného pole s prvky zvoleného typu. Vytvoříme tedy prázdný seznam konstruktorem:
l1 = []
a několik prázdných polí určených pro uložení prvků různého typu:
a1 = array("B")
a2 = array("H")
a3 = array("I")
a4 = array("L")
a5 = array("Q")
a6 = array("f")
a7 = array("d")
Následně si s využitím funkce asizeof.asizeof necháme vypočítat velikost obsazené paměti:
#!/usr/bin/env python3
# vim: set fileencoding=utf-8
from pympler.asizeof import asizeof
from array import array
# prázdné struktury
l1 = []
a1 = array("B")
a2 = array("H")
a3 = array("I")
a4 = array("L")
a5 = array("Q")
a6 = array("f")
a7 = array("d")
# výpis skutečných velikostí
print("List: ", asizeof(l1))
print("Array of bytes: ", asizeof(a1))
print("Array of shorts: ", asizeof(a2))
print("Array of ints: ", asizeof(a3))
print("Array of longs: ", asizeof(a4))
print("Array of quads: ", asizeof(a5))
print("Array of floats: ", asizeof(a6))
print("Array of doubles: ", asizeof(a7))
Výsledky budou vypadat následovně (hodnoty jsou reprezentovány v bajtech):
List: 56 Array of bytes: 64 Array of shorts: 64 Array of ints: 64 Array of longs: 64 Array of quads: 64 Array of floats: 64 Array of doubles: 64
7. Obsazení paměti seznamem popř. polem se sto prvky a 10000 prvky
Nyní se pokusíme zjistit, kolik paměti bude obsazeno seznamem a poli se sto prvky a posléze s tisíci prvky. Zdrojový kód příkladu upravíme následujícím způsobem (povšimněte si, jak se do polí přidávají další prvky):
#!/usr/bin/env python3
# vim: set fileencoding=utf-8
from pympler.asizeof import asizeof
from array import array
# prázdné struktury
l1 = []
a1 = array("B")
a2 = array("H")
a3 = array("I")
a4 = array("L")
a5 = array("Q")
a6 = array("f")
a7 = array("d")
# naplnit daty
for i in range(100):
l1.append(i)
a1.append(i)
a2.append(i)
a3.append(i)
a4.append(i)
a5.append(i)
a6.append(i)
a7.append(i)
# výpis skutečných velikostí
print("List: ", asizeof(l1))
print("Array of bytes: ", asizeof(a1))
print("Array of shorts: ", asizeof(a2))
print("Array of ints: ", asizeof(a3))
print("Array of longs: ", asizeof(a4))
print("Array of quads: ", asizeof(a5))
print("Array of floats: ", asizeof(a6))
print("Array of doubles: ", asizeof(a7))
Výsledky pro stoprvkové kolekce:
List: 4096 Array of bytes: 168 Array of shorts: 272 Array of ints: 472 Array of longs: 880 Array of quads: 880 Array of floats: 472 Array of doubles: 880
Pro pole s tisíci hodnotami nepatrně upravíme programový kód určený pro vkládání prvků, protože do polí s hodnotami typu bajt je možné uložit jen hodnoty s omezeným rozsahem (127 resp. 255):
for i in range(10000):
l1.append(i)
a1.append(i % 100)
a2.append(i % 100)
a3.append(i)
a4.append(i)
a5.append(i)
a6.append(i)
a7.append(i)
Výsledky pro kolekce s 10000 prvky:
List: 407608 Array of bytes: 10152 Array of shorts: 20240 Array of ints: 40408 Array of longs: 80744 Array of quads: 80744 Array of floats: 40408 Array of doubles: 80744
Z výsledků je patrné, že u seznamů roste spotřeba paměti poměrně výrazně, což by ale nemělo být překvapivé, protože hodnoty jsou zde boxovány. Zajímavé ovšem je, že i u polí je obsazená paměť větší, než by to odpovídalo výpočtu počet_prvků×velikost_jednoho prvku. U rozsáhlejších polí je „nadbytečná“ spotřeba paměti rovna přibližně jednomu až třem procentům, takže se většinou nejedná o výrazný problém. A opět si ještě řekneme, proč tomu tak je.
8. Sekvenční přístup k prvkům seznamů a polí
V případě, že použijeme standardní seznamy, je sekvenční průchod prvky seznamů v Pythonu realizován tímto idiomatickým zápisem:
lst = ["foo", "bar", "baz"]
for item in lst:
print(item)
Naprosto stejným způsobem je možné procházet i prvky polí, což je velmi rozumné. Příkladem může být průchod polem se čtyřmi prvky typu „bajt“:
arr = array("B", [1, 2, 3, 4])
for item in arr:
print(item)
Všemi typy polí se prochází naprosto stejným způsobem, nezávisle na typu jejich prvků:
#!/usr/bin/env python3
# vim: set fileencoding=utf-8
from array import array
# prázdné struktury
l1 = []
a1 = array("B")
a2 = array("H")
a3 = array("I")
a4 = array("L")
a5 = array("Q")
a6 = array("f")
a7 = array("d")
# naplnit daty
for i in range(100):
l1.append(i)
a1.append(i)
a2.append(i)
a3.append(i)
a4.append(i)
a5.append(i)
a6.append(i)
a7.append(i)
def print_all_items(name, struct):
"""Vytištění všech prvků uložených ve struktuře."""
print(name)
for item in struct:
print(item, end=" ")
print("\n")
print_all_items("List:", l1)
print_all_items("Array of bytes:", a1)
print_all_items("Array of shorts:", a2)
print_all_items("Array of ints:", a3)
print_all_items("Array of longs:", a4)
print_all_items("Array of quads:", a5)
print_all_items("Array of floats:", a6)
print_all_items("Array of doubles:", a7)
Výsledky zobrazené tímto příkladem na terminálu:
List: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 Array of bytes: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 Array of shorts: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 Array of ints: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 Array of longs: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 Array of quads: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 Array of floats: 0.0 1.0 2.0 3.0 4.0 5.0 6.0 7.0 8.0 9.0 10.0 11.0 12.0 13.0 14.0 15.0 16.0 17.0 18.0 19.0 20.0 21.0 22.0 23.0 24.0 25.0 26.0 27.0 28.0 29.0 30.0 31.0 32.0 33.0 34.0 35.0 36.0 37.0 38.0 39.0 40.0 41.0 42.0 43.0 44.0 45.0 46.0 47.0 48.0 49.0 50.0 51.0 52.0 53.0 54.0 55.0 56.0 57.0 58.0 59.0 60.0 61.0 62.0 63.0 64.0 65.0 66.0 67.0 68.0 69.0 70.0 71.0 72.0 73.0 74.0 75.0 76.0 77.0 78.0 79.0 80.0 81.0 82.0 83.0 84.0 85.0 86.0 87.0 88.0 89.0 90.0 91.0 92.0 93.0 94.0 95.0 96.0 97.0 98.0 99.0 Array of doubles: 0.0 1.0 2.0 3.0 4.0 5.0 6.0 7.0 8.0 9.0 10.0 11.0 12.0 13.0 14.0 15.0 16.0 17.0 18.0 19.0 20.0 21.0 22.0 23.0 24.0 25.0 26.0 27.0 28.0 29.0 30.0 31.0 32.0 33.0 34.0 35.0 36.0 37.0 38.0 39.0 40.0 41.0 42.0 43.0 44.0 45.0 46.0 47.0 48.0 49.0 50.0 51.0 52.0 53.0 54.0 55.0 56.0 57.0 58.0 59.0 60.0 61.0 62.0 63.0 64.0 65.0 66.0 67.0 68.0 69.0 70.0 71.0 72.0 73.0 74.0 75.0 76.0 77.0 78.0 79.0 80.0 81.0 82.0 83.0 84.0 85.0 86.0 87.0 88.0 89.0 90.0 91.0 92.0 93.0 94.0 95.0 96.0 97.0 98.0 99.0
9. Vložení hodnoty do seznamu či pole na určené místo (operace insert)
V předchozích demonstračních příkladech jsme prvky do seznamu a polí připojovali, což je u obou zmíněných datových struktur realizováno operací se stejným jménem – append. Díky tomu, že prvky byly připojovány vždy až na konec pole (přesněji řečeno za konec pole), nebylo nutné specifikovat index přidávaného prvku. Ovšem jinak je tomu u operace vkládaní neboli insert. V tomto případě specifikujeme index, do kterého bude nový prvek přidán (a zbytek prvků bude odsunut). Pravděpodobně je zřejmé, že se jedná o obecně časově náročnou operaci, která může vyžadovat jak realokaci samotného pole, tak i přesuny prvků. I operace insert má stejnou sémantiku pro seznamy i pro pole včetně kontroly hodnoty indexu, možnosti použití záporných indexů (pro indexování zprava) atd.
Seznamy:
l = ["foo", "bar"] l.insert(0, "baz") print(l) ['baz', 'foo', 'bar'] l.insert(3, "END") print(l) ['baz', 'foo', 'bar', 'END'] l.insert(-1, ".") print(l) ['baz', 'foo', 'bar', '.', 'END'] l.insert(1000, "not-possible?") print(l) ['baz', 'foo', 'bar', '.', 'END', 'not-possible?']
Pole:
a = array("B", [10, 20])
a.insert(0, 5)
print(a)
array('B', [5, 10, 20])
a.insert(3, 30)
print(a)
array('B', [5, 10, 20, 30])
a.insert(-1, 0)
print(a)
array('B', [5, 10, 20, 0, 30])
a.insert(10000, 40)
print(a)
array('B', [5, 10, 20, 0, 30, 40])
To znamená, že jak pole tak seznamy můžeme naplnit operací „připojení zleva“, protože sémantika insert(0, hodnota) vlastně odpovídá sémantice append(hodnota) v případě, pokud by se prvky připojovaly před začátek sekvence a nikoli za konec sekvence:
#!/usr/bin/env python3
# vim: set fileencoding=utf-8
from array import array
# prázdné struktury
l1 = []
a1 = array("B")
a2 = array("H")
a3 = array("I")
a4 = array("L")
a5 = array("Q")
a6 = array("f")
a7 = array("d")
# naplnit daty
for i in range(100):
l1.insert(0, i)
a1.insert(0, i)
a2.insert(0, i)
a3.insert(0, i)
a4.insert(0, i)
a5.insert(0, i)
a6.insert(0, i)
a7.insert(0, i)
def print_all_items(name, struct):
"""Vytištění všech prvků uložených ve struktuře."""
print(name)
for item in struct:
print(item, end=" ")
print("\n")
print_all_items("List:", l1)
print_all_items("Array of bytes:", a1)
print_all_items("Array of shorts:", a2)
print_all_items("Array of ints:", a3)
print_all_items("Array of longs:", a4)
print_all_items("Array of quads:", a5)
print_all_items("Array of floats:", a6)
print_all_items("Array of doubles:", a7)
S výsledky, které nejsou ničím překvapující:
List: 99 98 97 96 95 94 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 74 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 Array of bytes: 99 98 97 96 95 94 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 74 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 Array of shorts: 99 98 97 96 95 94 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 74 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 Array of ints: 99 98 97 96 95 94 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 74 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 Array of longs: 99 98 97 96 95 94 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 74 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 Array of quads: 99 98 97 96 95 94 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 74 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 Array of floats: 99.0 98.0 97.0 96.0 95.0 94.0 93.0 92.0 91.0 90.0 89.0 88.0 87.0 86.0 85.0 84.0 83.0 82.0 81.0 80.0 79.0 78.0 77.0 76.0 75.0 74.0 73.0 72.0 71.0 70.0 69.0 68.0 67.0 66.0 65.0 64.0 63.0 62.0 61.0 60.0 59.0 58.0 57.0 56.0 55.0 54.0 53.0 52.0 51.0 50.0 49.0 48.0 47.0 46.0 45.0 44.0 43.0 42.0 41.0 40.0 39.0 38.0 37.0 36.0 35.0 34.0 33.0 32.0 31.0 30.0 29.0 28.0 27.0 26.0 25.0 24.0 23.0 22.0 21.0 20.0 19.0 18.0 17.0 16.0 15.0 14.0 13.0 12.0 11.0 10.0 9.0 8.0 7.0 6.0 5.0 4.0 3.0 2.0 1.0 0.0 Array of doubles: 99.0 98.0 97.0 96.0 95.0 94.0 93.0 92.0 91.0 90.0 89.0 88.0 87.0 86.0 85.0 84.0 83.0 82.0 81.0 80.0 79.0 78.0 77.0 76.0 75.0 74.0 73.0 72.0 71.0 70.0 69.0 68.0 67.0 66.0 65.0 64.0 63.0 62.0 61.0 60.0 59.0 58.0 57.0 56.0 55.0 54.0 53.0 52.0 51.0 50.0 49.0 48.0 47.0 46.0 45.0 44.0 43.0 42.0 41.0 40.0 39.0 38.0 37.0 36.0 35.0 34.0 33.0 32.0 31.0 30.0 29.0 28.0 27.0 26.0 25.0 24.0 23.0 22.0 21.0 20.0 19.0 18.0 17.0 16.0 15.0 14.0 13.0 12.0 11.0 10.0 9.0 8.0 7.0 6.0 5.0 4.0 3.0 2.0 1.0 0.0
10. Interní struktura prvků polí
Všechny prvky pole tak, jak jsou uloženy v paměti, je možné si nechat vypsat ve formě sekvence hexadecimálních hodnot. Tak například zjistíme, jakým způsobem jsou uloženy celočíselné hodnoty širší než jeden bajt, jak jsou uloženy hodnoty s plovoucí řádovou čárkou a samozřejmě je taktéž možné rozlišit mezi způsoby uložení vícebajtových hodnot: little endian či big endian. Vytvoříme si tedy pomocnou funkci, která získá jako svůj parametr libovolné pole a následně vypíše jeho obsah v hexadecimální formě na standardní výstup:
def print_all_items_as_hex(name, struct):
print(name)
print(struct.tobytes().hex(" "))
print()
Tuto funkci následně zavoláme a postupně jí předáme pole všech typů, abychom mohli prozkoumat případné rozdíly:
#!/usr/bin/env python3
# vim: set fileencoding=utf-8
from array import array
# prázdné struktury
a1 = array("B")
a2 = array("H")
a3 = array("I")
a4 = array("L")
a5 = array("Q")
a6 = array("f")
a7 = array("d")
# naplnit daty
for i in range(10):
a1.append(i)
a2.append(i)
a3.append(i)
a4.append(i)
a5.append(i)
a6.append(i)
a7.append(i)
def print_all_items_as_hex(name, struct):
print(name)
print(struct.tobytes().hex(" "))
print()
print_all_items_as_hex("Array of bytes:", a1)
print_all_items_as_hex("Array of shorts:", a2)
print_all_items_as_hex("Array of ints:", a3)
print_all_items_as_hex("Array of longs:", a4)
print_all_items_as_hex("Array of quads:", a5)
print_all_items_as_hex("Array of floats:", a6)
print_all_items_as_hex("Array of doubles:", a7)
Pole bajtů je nejjednodušší – prvky jsou uloženy za sebou bez jakýchkoli výplní:
Array of bytes: 00 01 02 03 04 05 06 07 08 09
U polí obsahujících „širší“ celočíselné hodnoty je patrné, že je na počítači s architekturou x86–64 použit little endian:
Array of shorts: 00 00 01 00 02 00 03 00 04 00 05 00 06 00 07 00 08 00 09 00 Array of ints: 00 00 00 00 01 00 00 00 02 00 00 00 03 00 00 00 04 00 00 00 05 00 00 00 06 00 00 00 07 00 00 00 08 00 00 00 09 00 00 00 Array of longs: 00 00 00 00 00 00 00 00 01 00 00 00 00 00 00 00 02 00 00 00 00 00 00 00 03 00 00 00 00 00 00 00 04 00 00 00 00 00 00 00 05 00 00 00 00 00 00 00 06 00 00 00 00 00 00 00 07 00 00 00 00 00 00 00 08 00 00 00 00 00 00 00 09 00 00 00 00 00 00 00 Array of quads: 00 00 00 00 00 00 00 00 01 00 00 00 00 00 00 00 02 00 00 00 00 00 00 00 03 00 00 00 00 00 00 00 04 00 00 00 00 00 00 00 05 00 00 00 00 00 00 00 06 00 00 00 00 00 00 00 07 00 00 00 00 00 00 00 08 00 00 00 00 00 00 00 09 00 00 00 00 00 00 00
A konečně jsou vypsány i prvky typu float a double:
Array of floats: 00 00 00 00 00 00 80 3f 00 00 00 40 00 00 40 40 00 00 80 40 00 00 a0 40 00 00 c0 40 00 00 e0 40 00 00 00 41 00 00 10 41 Array of doubles: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 f0 3f 00 00 00 00 00 00 00 40 00 00 00 00 00 00 08 40 00 00 00 00 00 00 10 40 00 00 00 00 00 00 14 40 00 00 00 00 00 00 18 40 00 00 00 00 00 00 1c 40 00 00 00 00 00 00 20 40 00 00 00 00 00 00 22 40
11. Uložení obsahu polí do souboru
Obsah polí lze uložit (serializovat) do souboru. Jako výsledek získáme binární soubory, které nebudou obsahovat žádnou hlavičku, výplně, ani žádné další doplňují struktury. To znamená, že velikost výsledného binárního souboru bude striktně odpovídat počtu prvků vynásobenou šířkou prvků v bajtech. Ostatně se o tom můžeme velmi snadno přesvědčit. Pro uložení pole do souboru použijeme metodu tofile, které se předá handle otevřeného souboru:
#!/usr/bin/env python3
# vim: set fileencoding=utf-8
from array import array
# prázdné struktury
a1 = array("B")
a2 = array("H")
a3 = array("I")
a4 = array("L")
a5 = array("Q")
a6 = array("f")
a7 = array("d")
# naplnit daty
for i in range(100):
a1.append(i)
a2.append(i)
a3.append(i)
a4.append(i)
a5.append(i)
a6.append(i)
a7.append(i)
def export_to_file(filename, struct):
"""Export celé struktury do souboru."""
with open(filename, "wb") as f:
struct.tofile(f)
export_to_file("bytes.bin", a1)
export_to_file("shorts.bin", a2)
export_to_file("ints.bin", a3)
export_to_file("longs.bin", a4)
export_to_file("quads.bin", a5)
export_to_file("floats.bin", a6)
export_to_file("doubles.bin", a7)
Podívejme se nyní na velikosti výsledných souborů. Pro větší přehlednost jsme si nechali soubory seřadit podle jejich délky:
$ ls -lSr *.bin
Výsledky:
-rw-rw-r-- 1 ptisnovs ptisnovs 100 Dec 29 16:05 bytes.bin -rw-rw-r-- 1 ptisnovs ptisnovs 200 Dec 29 16:05 shorts.bin -rw-rw-r-- 1 ptisnovs ptisnovs 400 Dec 29 16:05 ints.bin -rw-rw-r-- 1 ptisnovs ptisnovs 400 Dec 29 16:05 floats.bin -rw-rw-r-- 1 ptisnovs ptisnovs 800 Dec 29 16:05 quads.bin -rw-rw-r-- 1 ptisnovs ptisnovs 800 Dec 29 16:05 longs.bin -rw-rw-r-- 1 ptisnovs ptisnovs 800 Dec 29 16:05 doubles.bin
Pro zajímavost si prohlédněme alespoň soubor shorts.bin, který obsahuje pole se 100 prvky typu short (šestnáctibitové hodnoty):
$ od -tx1 shorts.bin 0000000 00 00 01 00 02 00 03 00 04 00 05 00 06 00 07 00 0000020 08 00 09 00 0a 00 0b 00 0c 00 0d 00 0e 00 0f 00 0000040 10 00 11 00 12 00 13 00 14 00 15 00 16 00 17 00 0000060 18 00 19 00 1a 00 1b 00 1c 00 1d 00 1e 00 1f 00 0000100 20 00 21 00 22 00 23 00 24 00 25 00 26 00 27 00 0000120 28 00 29 00 2a 00 2b 00 2c 00 2d 00 2e 00 2f 00 0000140 30 00 31 00 32 00 33 00 34 00 35 00 36 00 37 00 0000160 38 00 39 00 3a 00 3b 00 3c 00 3d 00 3e 00 3f 00 0000200 40 00 41 00 42 00 43 00 44 00 45 00 46 00 47 00 0000220 48 00 49 00 4a 00 4b 00 4c 00 4d 00 4e 00 4f 00 0000240 50 00 51 00 52 00 53 00 54 00 55 00 56 00 57 00 0000260 58 00 59 00 5a 00 5b 00 5c 00 5d 00 5e 00 5f 00 0000300 60 00 61 00 62 00 63 00 0000310
12. Načtení obsahu polí z binárních souborů
Opakem operace pro uložení pole do binárního souboru je pochopitelně operace, která toto pole naopak ze souboru načte. Pro tento účel je nejdříve nutné pole zkonstruovat (může být ovšem i prázdné) a následně jeho obsah načíst ze souboru metodou fromfile. Této metodě se kromě handle otevřeného souboru předává i počet prvků, které se mají načíst. Soubor musí obsahovat potřebná data; v opačném případě dojde k vyhození výjimky:
#!/usr/bin/env python3
# vim: set fileencoding=utf-8
from array import array
# prázdné struktury
a1 = array("B")
a2 = array("H")
a3 = array("I")
a4 = array("L")
a5 = array("Q")
a6 = array("f")
a7 = array("d")
def import_from_file(filename, struct):
"""Import celé struktury ze souboru."""
with open(filename, "rb") as f:
struct.fromfile(f, 100)
return struct
print(import_from_file("bytes.bin", a1))
print(import_from_file("shorts.bin", a2))
print(import_from_file("ints.bin", a3))
print(import_from_file("longs.bin", a4))
print(import_from_file("quads.bin", a5))
print(import_from_file("floats.bin", a6))
print(import_from_file("doubles.bin", a7))
Z vypsaných výsledků je patrné, že se všechna pole korektně načetla:
array('B', [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32,
33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49,
50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66,
67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83,
84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99])
array('H', [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32,
33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49,
50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66,
67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83,
84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99])
array('I', [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32,
33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49,
50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66,
67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83,
84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99])
array('L', [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32,
33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49,
50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66,
67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99])
array('Q', [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32,
33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49,
50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66,
67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99])
array('f', [0.0, 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0,
11.0, 12.0, 13.0, 14.0, 15.0, 16.0, 17.0, 18.0, 19.0, 20.0, 21.0,
22.0, 23.0, 24.0, 25.0, 26.0, 27.0, 28.0, 29.0, 30.0, 31.0, 32.0,
33.0, 34.0, 35.0, 36.0, 37.0, 38.0, 39.0, 40.0, 41.0, 42.0, 43.0,
44.0, 45.0, 46.0, 47.0, 48.0, 49.0, 50.0, 51.0, 52.0, 53.0, 54.0,
55.0, 56.0, 57.0, 58.0, 59.0, 60.0, 61.0, 62.0, 63.0, 64.0, 65.0,
66.0, 67.0, 68.0, 69.0, 70.0, 71.0, 72.0, 73.0, 74.0, 75.0, 76.0,
77.0, 78.0, 79.0, 80.0, 81.0, 82.0, 83.0, 84.0, 85.0, 86.0, 87.0,
88.0, 89.0, 90.0, 91.0, 92.0, 93.0, 94.0, 95.0, 96.0, 97.0, 98.0, 99.0])
array('d', [0.0, 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0,
11.0, 12.0, 13.0, 14.0, 15.0, 16.0, 17.0, 18.0, 19.0, 20.0, 21.0,
22.0, 23.0, 24.0, 25.0, 26.0, 27.0, 28.0, 29.0, 30.0, 31.0, 32.0,
33.0, 34.0, 35.0, 36.0, 37.0, 38.0, 39.0, 40.0, 41.0, 42.0, 43.0,
44.0, 45.0, 46.0, 47.0, 48.0, 49.0, 50.0, 51.0, 52.0, 53.0, 54.0,
55.0, 56.0, 57.0, 58.0, 59.0, 60.0, 61.0, 62.0, 63.0, 64.0, 65.0,
66.0, 67.0, 68.0, 69.0, 70.0, 71.0, 72.0, 73.0, 74.0, 75.0, 76.0,
77.0, 78.0, 79.0, 80.0, 81.0, 82.0, 83.0, 84.0, 85.0, 86.0, 87.0,
88.0, 89.0, 90.0, 91.0, 92.0, 93.0, 94.0, 95.0, 96.0, 97.0, 98.0, 99.0])
13. Složitěji strukturované binární soubory
Tím, že metody array.tofile a array.fromfile vyžadují předání handle souboru, jenž musí být otevřený pro zápis resp. pro čtení (a ideálně navíc v binárním režimu), je umožněna více či méně sofistikovaná práce se složitěji strukturovanými binárními soubory. V takových souborech můžeme kombinovat různé sekce, využít nástroj pickle apod. V dalším příkladu je ukázána tvorba binárního souboru, který obsahuje pět částí:
- Hlavička o délce sedmi bajtů
- Pole se 100 prvky typu bajt (celkem 100 bajtů)
- Rozdělovací prvek o délce deseti bajtů
- Pole se 100 prvky typu short (celkem 200 bajtů)
- Patička o délce tří bajtů
Celková velikost výsledného binárního souboru by měla být:
7 + 100 + 10 + 200 + 3 = 320 bajtů
Realizace zápisu takového souboru může vypadat následovně:
#!/usr/bin/env python3
# vim: set fileencoding=utf-8
from array import array
# prázdné struktury
a1 = array("B")
a2 = array("H")
# naplnit daty
for i in range(100):
a1.append(i)
a2.append(i)
with open("structured.bin", "wb") as f:
f.write(b"HEADER\n")
a1.tofile(f)
f.write(b"\nsplitter\n")
a2.tofile(f)
f.write(b"END")
Po spuštění skriptu zjistíme celkovou velikost souboru:
$ ls -l structured.bin -rw-rw-r-- 1 ptisnovs ptisnovs 320 Jan 12 12:25 structured.bin
Skutečně má délku očekávaných 320 bajtů.
Obsah souboru, umístění hlavičky atd. nám prozradí nástroj hd:
$ hd structured.bin 00000000 48 45 41 44 45 52 0a 00 01 02 03 04 05 06 07 08 |HEADER..........| 00000010 09 0a 0b 0c 0d 0e 0f 10 11 12 13 14 15 16 17 18 |................| 00000020 19 1a 1b 1c 1d 1e 1f 20 21 22 23 24 25 26 27 28 |....... !"#$%&'(| 00000030 29 2a 2b 2c 2d 2e 2f 30 31 32 33 34 35 36 37 38 |)*+,-./012345678| 00000040 39 3a 3b 3c 3d 3e 3f 40 41 42 43 44 45 46 47 48 |9:;<=>?@ABCDEFGH| 00000050 49 4a 4b 4c 4d 4e 4f 50 51 52 53 54 55 56 57 58 |IJKLMNOPQRSTUVWX| 00000060 59 5a 5b 5c 5d 5e 5f 60 61 62 63 0a 73 70 6c 69 |YZ[\]^_`abc.spli| 00000070 74 74 65 72 0a 00 00 01 00 02 00 03 00 04 00 05 |tter............| 00000080 00 06 00 07 00 08 00 09 00 0a 00 0b 00 0c 00 0d |................| 00000090 00 0e 00 0f 00 10 00 11 00 12 00 13 00 14 00 15 |................| 000000a0 00 16 00 17 00 18 00 19 00 1a 00 1b 00 1c 00 1d |................| 000000b0 00 1e 00 1f 00 20 00 21 00 22 00 23 00 24 00 25 |..... .!.".#.$.%| 000000c0 00 26 00 27 00 28 00 29 00 2a 00 2b 00 2c 00 2d |.&.'.(.).*.+.,.-| 000000d0 00 2e 00 2f 00 30 00 31 00 32 00 33 00 34 00 35 |.../.0.1.2.3.4.5| 000000e0 00 36 00 37 00 38 00 39 00 3a 00 3b 00 3c 00 3d |.6.7.8.9.:.;.<.=| 000000f0 00 3e 00 3f 00 40 00 41 00 42 00 43 00 44 00 45 |.>[email protected]| 00000100 00 46 00 47 00 48 00 49 00 4a 00 4b 00 4c 00 4d |.F.G.H.I.J.K.L.M| 00000110 00 4e 00 4f 00 50 00 51 00 52 00 53 00 54 00 55 |.N.O.P.Q.R.S.T.U| 00000120 00 56 00 57 00 58 00 59 00 5a 00 5b 00 5c 00 5d |.V.W.X.Y.Z.[.\.]| 00000130 00 5e 00 5f 00 60 00 61 00 62 00 63 00 45 4e 44 |.^._.`.a.b.c.END| 00000140
14. Teoretická a praktická rychlost přístupu k prvkům polí
V tomto článku jsme již na několika místech porovnávali klasický seznam s poli realizovanými ve standardním balíčku array. Vzhledem k tomu, že prvky pole jsou v této datové struktuře uloženy přímo, tj. bez výplní a boxingu, je spotřeba operační paměti polem menší, než je tomu v případě seznamů. To je vlastně jediná výhoda této datové struktury. Samotné čtení hodnoty prvky či zápis hodnoty prvku je ve skutečnosti časově náročnější, protože je nutné provádět boxing při čtení a unboxing při zápisu (to jsou operace, které obalí hodnotu „objektem“, protože v Pythonu se se všemi hodnotami pracuje jako s objekty).
Větší časovou náročnost čtení a zápisu prvků pole si můžeme ověřit na libovolném algoritmu, který s prvky pole či seznamu intenzivně pracuje. Pro měření a jako jednoduchý benchmark budeme realizovat již několikrát zmíněný algoritmus bublinkového řazení (skutečně se v češtině takto označuje). Ten lze pochopitelně realizovat nad seznamy, a to velmi snadno:
from time import perf_counter
import random
size = 10000
a = [random.randrange(0, 10000) for i in range(size)]
t1 = perf_counter()
for i in range(size - 1, 0, -1):
for j in range(0, i):
if a[j] > a[j + 1]:
a[j], a[j + 1] = a[j + 1], a[j]
t2 = perf_counter()
print(f"Sorted in {t2-t1} seconds:")
print("\nBegins with:")
print(a[:100])
print("\nEnds with:")
print(a[-100:])
15. Tentýž výpočet, ovšem realizovaný s využitím polí
Zápis algoritmu z předchozí kapitoly je možné velmi jednoduše upravit do takové podoby, aby se namísto seznamů požívalo pole. Použijeme pole celých čísel typu integer bez znaménka, které mají minimální rozsah hodnot 0..65535. Povšimněte si, že samotná výkonná část algoritmu (dvojice vnořených smyček a podmínka) zůstala totožná, to díky tomu, že pro seznamy i pro pole se používá stejný zápis operátoru indexování:
from time import perf_counter
from array import array
import random
size = 10000
a = array("I", [random.randrange(0, 10000) for i in range(size)])
t1 = perf_counter()
for i in range(size - 1, 0, -1):
for j in range(0, i):
if a[j] > a[j + 1]:
a[j], a[j + 1] = a[j + 1], a[j]
t2 = perf_counter()
print(f"Sorted in {t2-t1} seconds:")
print("\nBegins with:")
print(a[:100])
print("\nEnds with:")
print(a[-100:])
Nyní začíná nejzajímavější část – porovnání rychlosti běhu obou implementací:
| Implementace | Čas běhu |
|---|---|
| seznam | 10,3 s |
| pole | 12,5 s |
Z výsledků je patrné, že – i když to je neintuitivní – je čtení a zápis prvků do seznamů rychlejší, než provedení týchž operací s polem (primitivních) hodnot. Opět tedy zopakujme – pole array jsou výhodná pouze co se týče ušetření obsazení operační paměti, nikoli z důvodu větší rychlosti.
16. Interní způsob uložení pole v paměti
Na závěr se na chvíli podívejme pod kapotu Pythonu, konkrétně na to, jak vlastně vypadá interní způsob uložení pole v operační paměti. Příslušné zdrojový kódy je možné nalézt v souboru Modules/arraymodule.c.
První datovou strukturou, o které se zmíníme, je struktura nazvaná arraydescr. Ta slouží pro popis jednotlivých typů pole resp. typů prvků, které jsou do zkonstruovaného pole vkládány:
struct arraydescr {
char typecode;
int itemsize;
PyObject * (*getitem)(struct arrayobject *, Py_ssize_t);
int (*setitem)(struct arrayobject *, Py_ssize_t, PyObject *);
int (*compareitems)(const void *, const void *, Py_ssize_t);
const char *formats;
int is_integer_type;
int is_signed;
};
Popis všech podporovaných typů polí nalezneme v poli nazvaném descriptors:
static const struct arraydescr descriptors[] = {
{'b', 1, b_getitem, b_setitem, b_compareitems, "b", 1, 1},
{'B', 1, BB_getitem, BB_setitem, BB_compareitems, "B", 1, 0},
{'u', sizeof(wchar_t), u_getitem, u_setitem, u_compareitems, "u", 0, 0},
{'h', sizeof(short), h_getitem, h_setitem, h_compareitems, "h", 1, 1},
{'H', sizeof(short), HH_getitem, HH_setitem, HH_compareitems, "H", 1, 0},
{'i', sizeof(int), i_getitem, i_setitem, i_compareitems, "i", 1, 1},
{'I', sizeof(int), II_getitem, II_setitem, II_compareitems, "I", 1, 0},
{'l', sizeof(long), l_getitem, l_setitem, l_compareitems, "l", 1, 1},
{'L', sizeof(long), LL_getitem, LL_setitem, LL_compareitems, "L", 1, 0},
{'q', sizeof(long long), q_getitem, q_setitem, q_compareitems, "q", 1, 1},
{'Q', sizeof(long long), QQ_getitem, QQ_setitem, QQ_compareitems, "Q", 1, 0},
{'f', sizeof(float), f_getitem, f_setitem, NULL, "f", 0, 0},
{'d', sizeof(double), d_getitem, d_setitem, NULL, "d", 0, 0},
{'\0', 0, 0, 0, 0, 0, 0} /* Sentinel */
};
Samotná datová struktura představující pole obsahuje především standardní hlavičku všech proměnných spravovaných Pythonem (PyObject_VAR_HEAD), dále ukazatel na céčkovské pole ob_item (to se pochopitelně nejprve musí alokovat), objem alokované paměti allocated a jeden z výše uvedených popisků pole ob_descr:
typedef struct arrayobject {
PyObject_VAR_HEAD
char *ob_item;
Py_ssize_t allocated;
const struct arraydescr *ob_descr;
PyObject *weakreflist; /* List of weak references */
Py_ssize_t ob_exports; /* Number of exported buffers */
} arrayobject;
Pro úplnost si ještě uveďme funkci, která zajistí vytvoření pole zadaného typu a velikosti. Jedná se o poměrně přímočarý kód:
static PyObject *
newarrayobject(PyTypeObject *type, Py_ssize_t size, const struct arraydescr *descr)
{
arrayobject *op;
size_t nbytes;
if (size < 0) {
PyErr_BadInternalCall();
return NULL;
}
/* Check for overflow */
if (size > PY_SSIZE_T_MAX / descr->itemsize) {
return PyErr_NoMemory();
}
nbytes = size * descr->itemsize;
op = (arrayobject *) type->tp_alloc(type, 0);
if (op == NULL) {
return NULL;
}
op->ob_descr = descr;
op->allocated = size;
op->weakreflist = NULL;
Py_SET_SIZE(op, size);
if (size <= 0) {
op->ob_item = NULL;
}
else {
op->ob_item = PyMem_NEW(char, nbytes);
if (op->ob_item == NULL) {
Py_DECREF(op);
return PyErr_NoMemory();
}
}
op->ob_exports = 0;
return (PyObject *) op;
}
17. Algoritmus pro alokaci paměti pro zvětšující a zmenšující se pole
Vzhledem k tomu, že do polí lze přidávat nové prvky, je interně nutné provádět realokaci paměti, což je pochopitelně náročná operace, protože mj. vyžaduje kopii prvků z původního bloku paměti do bloku nového. Z tohoto důvodu je vhodné zvolit takovou strategii, aby se pole realokovalo s relativně malou frekvencí (tedy zcela jistě ne pro každý nový prvek), ovšem na druhé straně nechceme, aby pole zabíralo zbytečně velký blok paměti. Řešení tohoto problému není nijak nové – pokud již kapacita pole nedostačuje, provede se realokace a přitom se naalokuje více paměti. O jak velký kus se jedná je odvozeno z aktuálního počtu prvků. U velkého pole se předpokládá, že poroste ještě více, takže se rezervuje větší blok paměti.
Takto celý algoritmus pro změnu velikosti pole (a tedy i pro realokace v některých okamžicích) vypadá:
static int
array_resize(arrayobject *self, Py_ssize_t newsize)
{
char *items;
size_t _new_size;
if (self->ob_exports > 0 && newsize != Py_SIZE(self)) {
PyErr_SetString(PyExc_BufferError,
"cannot resize an array that is exporting buffers");
return -1;
}
/* Bypass realloc() when a previous overallocation is large enough
to accommodate the newsize. If the newsize is 16 smaller than the
current size, then proceed with the realloc() to shrink the array.
*/
if (self->allocated >= newsize &&
Py_SIZE(self) < newsize + 16 &&
self->ob_item != NULL) {
Py_SET_SIZE(self, newsize);
return 0;
}
if (newsize == 0) {
PyMem_Free(self->ob_item);
self->ob_item = NULL;
Py_SET_SIZE(self, 0);
self->allocated = 0;
return 0;
}
/* This over-allocates proportional to the array size, making room
* for additional growth. The over-allocation is mild, but is
* enough to give linear-time amortized behavior over a long
* sequence of appends() in the presence of a poorly-performing
* system realloc().
* The growth pattern is: 0, 4, 8, 16, 25, 34, 46, 56, 67, 79, ...
* Note, the pattern starts out the same as for lists but then
* grows at a smaller rate so that larger arrays only overallocate
* by about 1/16th -- this is done because arrays are presumed to be more
* memory critical.
*/
_new_size = (newsize >> 4) + (Py_SIZE(self) < 8 ? 3 : 7) + newsize;
items = self->ob_item;
/* XXX The following multiplication and division does not optimize away
like it does for lists since the size is not known at compile time */
if (_new_size <= ((~(size_t)0) / self->ob_descr->itemsize))
PyMem_RESIZE(items, char, (_new_size * self->ob_descr->itemsize));
else
items = NULL;
if (items == NULL) {
PyErr_NoMemory();
return -1;
}
self->ob_item = items;
Py_SET_SIZE(self, newsize);
self->allocated = _new_size;
return 0;
}
18. Průběh alokace
Průběh alokace můžeme sledovat například tímto jednoduchým skriptem. Ten je opět založen na modulu pympler. Do pole bajtů se postupně přidávají jednotlivé prvky a zjišťuje se, ve kterém okamžiku dojde ke zvětšení pole. Informace o tomto zvětšení se následně vypíše na terminál:
#!/usr/bin/env python3
# vim: set fileencoding=utf-8
from array import array
from sys import getsizeof
from pympler.asizeof import asizeof
# prázdná struktura
a1 = array("B")
last_size = asizeof(a1)
last_index = 0
# naplnit daty
for i in range(1000):
a1.append(i%100)
size = asizeof(a1)
if size != last_size:
print(f"{i:5} {size:5} {size-last_size:+5} {last_index:4}-{i:<4}")
last_index = i
last_size = size
Skript spustíme:
$ python3 alloc_details.py
Zajímavé je sledovat třetí sloupec ukazující, o kolik bajtů se pole zvětší při přidání n-tého prvku (jeho index je v prvním sloupci). Zde je nutné upozornit na problém sledování využití paměti – do hry totiž vstupuje jak vlastní realokace, tak i výpočet zarovnání atd. Z tohoto důvodu počty „nesedí“ s očekávaným chováním, tedy že ve třetím sloupci bude monotonně rostoucí řada. Nicméně trend je zcela jasně patrný:
0 80 +8 0-0
8 88 +8 0-8
16 104 +16 8-16
25 112 +8 16-25
34 120 +8 25-34
44 128 +8 34-44
54 144 +16 44-54
65 152 +8 54-65
77 168 +16 65-77
89 176 +8 77-89
102 192 +16 89-102
116 208 +16 102-116
131 224 +16 116-131
147 240 +16 131-147
164 256 +16 147-164
182 280 +24 164-182
201 296 +16 182-201
221 320 +24 201-221
242 344 +24 221-242
265 368 +24 242-265
289 392 +24 265-289
315 416 +24 289-315
342 448 +32 315-342
371 480 +32 342-371
402 512 +32 371-402
435 544 +32 402-435
470 584 +40 435-470
507 624 +40 470-507
546 664 +40 507-546
588 704 +40 546-588
632 752 +48 588-632
679 808 +56 632-679
729 856 +48 679-729
782 912 +56 729-782
838 976 +64 782-838
898 1040 +64 838-898
962 1104 +64 898-962
19. Repositář s demonstračními příklady
Zdrojové kódy všech prozatím popsaných demonstračních příkladů určených pro programovací jazyk Python 3 byly uloženy do Git repositáře dostupného na adrese https://github.com/tisnik/most-popular-python-libs. Odkazy na jednotlivé příklady jsou uvedeny v následující tabulce:
20. Odkazy na Internetu
- array — Efficient arrays of numeric values
https://docs.python.org/3/library/array.html - Top 5 Python Memory Profilers
https://stackify.com/top-5-python-memory-profilers/ - Pympler na GitHubu
https://github.com/pympler/pympler - Pympler na PyPI
https://pypi.org/project/Pympler/ - Dokumentace k balíčku Pympler
https://pympler.readthedocs.io/en/latest/ - Guppy 3 na GitHubu
https://github.com/zhuyifei1999/guppy3/ - Guppy 3 na PyPI
https://pypi.org/project/guppy3/ - Memory Profiler na GitHubu
https://github.com/pythonprofilers/memory_profiler - Memory Profiler na PyPI
https://pypi.org/project/memory-profiler/ - How to use guppy/heapy for tracking down memory usage
https://smira.ru/wp-content/uploads/2011/08/heapy.html - Identifying memory leaks
https://pympler.readthedocs.io/en/latest/muppy.html#muppy - How do I determine the size of an object in Python?
https://stackoverflow.com/questions/449560/how-do-i-determine-the-size-of-an-object-in-python - Why is bool a subclass of int?
https://stackoverflow.com/questions/8169001/why-is-bool-a-subclass-of-int - Memory Management in Python
https://realpython.com/python-memory-management/ - Why do ints require three times as much memory in Python?
https://stackoverflow.com/questions/23016610/why-do-ints-require-three-times-as-much-memory-in-python - cpython/Include/cpython/longintrepr.h
https://github.com/python/cpython/blob/main/Include/cpython/longintrepr.h#L64 - sys — System-specific parameters and functions
https://docs.python.org/3/library/sys.html - Stránky projektu Numpy
https://numpy.org/ - Numpy na GitHubu
https://github.com/numpy/numpy - NumPy documentation
https://numpy.org/doc/stable/ - The N-dimensional array (ndarray)
https://numpy.org/doc/stable/reference/arrays.ndarray.html - numpy.ndarray
https://numpy.org/doc/stable/reference/generated/numpy.ndarray.html
