Programování pro fyziky 2023/24 – přednáška č. 6

Strukturované datové typy

Mezi strukturované datové typy se řadí především pole, řetězce a struktury (záznamy). Některé jazyky rozumějí množinám.

Pole

Pole (array) je strukturovanou proměnnou (nebo konstantou) složenou z prvků (elements) stejného datového typu. Prvky pole jsou obvykle značeny celočíselnými indexy. Jednorozměrná (1D) pole (vektory) jsou indexována jedním indexem, dvourozměrná (2D) pole (matice) dvěma indexy atd. Pole bývají uložena v souvislém úseku paměti, což prospívá rychlosti sekvenčního přístupu k jejich prvkům. V Pythonu a skriptovacích jazycích, kde se proměnné nedeklarují, se pole vytvářejí přiřazovacím příkazem, tedy dynamicky za chodu programu a jejich velikost (počet prvků) i datový typ se pak mohou měnit. V klasických programovacích jazycích se datový typ polí deklaruje staticky a velikost je buď dána také deklarací a nelze ji pak měnit (statická pole) nebo se stanoví za chodu programu (dynamická pole).

V Pythonu se dynamická pole vhodná pro výpočty vytvářejí pomocí modulu NumPy. Paměť pro pole je žádoucí alokovat jednorázově voláním vhodné NumPy funkce, přičemž lze specifikovat i datový typ prvků. Indexuje se od nuly, indexy jsou v hranatých závorkách. V ukázce vytváříme reálné pole inicializované nulami funkcí np.zeros a celočíselné pole bez nastavení hodnot prvků funkcí np.empty, prvky inicializujeme přiřazováním v cyklu a zpracujeme redukční funkcí. Dealokovat pole lze příkazem del a nebo přiřazením hodnoty a=None. Pro srovnání zapíšeme podobnou akci pomocí pythonského seznamu, který vytváříme inkrementálně, a přidáme také inkrementální vytváření pole, co do času běhu zcela tragické. Čas měříme užitím funkce time() z modulu time.

# Python: alokace a inicializace polí a seznamů
import numpy as np
import time
nmax=1_000_000

# Vytvoření np.float64 pole jednorázově
t0=time.time()
a=np.zeros(nmax)                   # alokace pole
for n in range(nmax): a[n]=n+1     # update prvků v cyklu
s=np.sum(a)
print(s,time.time()-t0,type(a[0]))
del a

# Vytvoření np.int64 pole jednorázově
t0=time.time()
a=np.empty(nmax,dtype=np.int64)    # alokace pole
for n in range(nmax): a[n]=n+1     # update prvků v cyklu
s=np.sum(a)
print(s,time.time()-t0,type(a[0]))
del a

# Vytváření pythonského seznamu inkrementálně (PRO VÝSTRAHU)
t0=time.time()
a=[]                                 # založení seznamu
for n in range(nmax): a.append(n+1)  # přidávání prvků
s=sum(a)
print(s,time.time()-t0,type(a[0]))
del a

# Vytváření pole inkrementálně
t0=time.time()
a=np.array([])                                 # založení pole s prvky np.float64
for n in range(nmax): a.resize(n+1); a[n]=n+1  # přidávání prvků
s=np.sum(a)
print(s,time.time()-t0,type(a[0]))
del a

Fortranská dynamická pole se vyznačují v popisech datového typu atributem allocatable a závorkami se specifikací počtu rozměrů. Paměť se alokuje příkazem allocate nebo přiřazovacím příkazem, dealokuje se příkazem deallocate nebo automaticky. Indexuje se celočíselně, pole mohou mít libovolnou dolní i horní mez, implicitní dolní mezí je 1, indexy píšeme do kulatých závorek.

! Fortran: alokace a inicializace dynamických polí
real(8),allocatable :: a(:)  ! popis alokovatelného vektoru (pole o jedné dimenzi)
real(8) s
nmax=1000000

call cpu_time(t0)
allocate (a(nmax))           ! alokační příkaz
do n=1,nmax; a(n)=n; enddo   ! update prvků v cyklu
s=sum(a)
call cpu_time(t1)
print *,s,t1-t0
deallocate (a)               ! dealokace pole

call cpu_time(t0)
a=[(n,n=1,nmax)]             ! alokace přiřazením konstruktoru pole
s=sum(a)
call cpu_time(t1)
print *,s,t1-t0
deallocate (a)
end program

Matlab a Octave mají pole (vlastně matice) jako implicitní datový typ, default bázovým typem je 8bytový reálný double. Indexuje se od 1. Ukázka je podobná jako v Pythonu; pro inicializaci užijeme funkci zeros. Ta a obdobné funkce zde při jediném argumentu, zeros(nmax), vytvářejí čtvercové matice; pro (řádkové, resp. sloupcové) vektory je třeba použít volání zeros(1,nmax), resp. zeros(nmax,1).

% Matlab/Octave: alokace a inicializace pole
format long
nmax=1000000;
tic
a=zeros(1,nmax);           % alokace dynamického pole
for n=1:nmax, a(n)=n; end  % inicializace cyklem
disp(sum(a))               % výpis celého pole
toc
clear a                    % dealokace

Array language

Programovací jazyky často poskytují významnou podporu pro práci s poli. Array language je od kolébky vlastností Matlabu. Vše od něj opsal Octave a inspiroval se u něj i pythonský modul NumPy a moderní Fortran. Z Matlabu do NumPy přichází i inspirace pro názvy funkcí generujících pole s inicializací hodnot: empty, zeros, ones, eye, diag, tril, triu, linspace, rand, realmax, inf, nan aj.

Array language mívá tyto komponenty:

  • Pole (i jen jejich části, zvané sekce či řezy) mohou být přenášena přiřazovacím příkazem naráz, nikoliv jen po prvcích v cyklu.

  • Podobně jsou zobecněny (přetíženy) aritmetické operátory, mj. +-*/, relační operátory, logické operátory (not, and, or) aj.

  • Volat s poli na místě argumentu lze i funkce definované pro skalární argumenty, vracejí pak také pole vyhodnocená prvkově, prvek po prvku.

  • Kromě toho bývá k dispozici sada funkcí provádějících na polích redukční operace typu sumace, součin, hledání extrémů aj., a také funkce z lineární algebry, jako skalární součin nebo maticové násobení.

  • Patří sem i pojem maska neboli logické pole obsahující (typicky) výsledky prvkově vyhodnocené relace; maska se pak může nasadit na pole téhož tvaru a omezit tak provedení akce jen na prvky, jimž odpovídají prvky masky s hodnotou True.

Následují dvě ekvivalentní ukázky array language pro Python a Fortran:

# Python a NumPy: array language
import numpy as np
nmax=3           # velikost polí
# alokace přiřazením
a=np.ones(nmax); b=np.full(nmax,a[0]); c=np.array((1.,2,3)); d=np.arange(1.,nmax+1); print(a,b,c,d)
# sekce polí
a=a[0:nmax]; b=b[:]; c=c[-1::-1]; d=d[::-1]; print(a,b,c,d)
# velikost a tvar pole
print(np.size(a),np.shape(a))
# konverze ze seznamu, aritmetická posloupnost pomocí arange a linspace
a=np.array([1.,2,3]); b=np.arange(1.,nmax+1); c=np.linspace(1,nmax,nmax); print(a,b,c)
# prvkové operace
a=np.zeros(nmax); b=np.ones(nmax); a=a+b; a=a*b; a=a/b; a=a**2; print(a)
# prvkové funkce
a=np.array([-1,0,1],dtype=np.float64); b=np.abs(a); c=np.log(np.exp(a)); d=np.arctan(np.tan(a)); print(a,b,c,d)
# maska
a=np.array([-1,0,1]); mask=a>0; bool1=all(a>0); bool2=any(a>0); nz=np.count_nonzero(a>0); print(mask,bool1,bool2,nz)
# podmíněné přiřazení
b=np.ma.where(a>=0,a,-a); print(b)
# filtrace
a=a[a>=0]; print(a)
# redukce
a=np.arange(1.,nmax+1); r1=np.sum(a); r2=np.prod(a); r3=np.min(a); r4=np.max(a); print(r1,r2,r3,r4)
# lineární algebra
a2=np.ones((2,2)); b2=np.copy(a2); print(np.size(a2),np.shape(a2))
c2=a2*b2; d2=a2@b2; e2=np.matmul(a2,b2); print(c2); print(d2); print(e2)
! Fortran: array language
integer,parameter :: nmax=3              ! velikost polí
real,allocatable :: a(:),b(:),c(:),d(:)  ! alokovatelná pole
real,allocatable,dimension(:,:) :: a2,b2,c2,d2
logical :: mask(nmax),bool1,bool2        ! maska a logické skaláry
! alokace alokačním příkazem a přiřazením
allocate (a(nmax),b(nmax))
a=1; b=a(1); c=[1,2,3]; d=[(n,n=1,nmax)]; print *,a,b,c,d
! sekce polí
a=a(1:nmax); b=b(:); c=c(nmax:1:-1); d=d(ubound(d,1):lbound(d,1):-1); print *,a,b,c,d
! velikost a tvar pole
print *,size(a),shape(a)
! aritmetická posloupnost
a=[1,2,3]; a=[(n,n=1,nmax)]; print *,a,b
! prvkové operace
a=0; b=1; a=a+b; a=a*b; a=a/b; a=a**2; print *,a
! prvkové funkce
a=[-1,0,1]; b=abs(a); c=log(exp(a)); d=atan(tan(a)); print *,a,b,c,d
! maska
a=[-1,0,1]; mask=a>0; bool1=all(a>0); bool2=any(a>0); nz=count(a>0); print *,mask,bool1,bool2,nz
! podmíněné přiřazení
where (a>=0); b=a; elsewhere; b=-a; endwhere; print *,b
! filtrace
a=pack(a,a>=0); print *,a
! redukce
a=[1,2,3]; r1=sum(a); r2=product(a); r3=minval(a); r4=maxval(a); print *,r1,r2,r3,r4
! lineární algebra
allocate (a2(2,2)); a2=1; b2=a2; print *,size(b2),shape(b2)
c2=a2*b2; d2=matmul(a2,b2); print '(2(f0.0,x))',transpose(c2),transpose(d2)
end program

Porovnáme rychlost skalárních přiřazení v cyklu a vektorového přiřazení mezi poli v ukázce s výpočtem harmonických čísel. V Pythonu čekejme řádový rozdíl v rychlostech ve prospěch array language. Ve Fortranu je array language také rychlá, ale cykly ještě rychlejší. Array language často potřebuje alokovat pomocná pole pro mezivýsledky, což stojí – proti překládaným cyklům – čas navíc.

# Python: pole v cyklu vs. array language
import numpy as np
import time
fmt='%.15f %.2f'
nmax=10_000_000

# NumPy pole v cyklu
t0=time.time()
a=np.zeros(nmax)                         # alokace pole
for n in range(1,nmax+1): a[n-1]=1/n     # update pole pomocí cyklu
s=np.sum(a)
print(fmt%(s,time.time()-t0))
del a

# NumPy array language
t0=time.time()
a=np.arange(1.,nmax+1)                   # alokace pole
# a=np.arange(1,nmax+1,dtype=np.double)
# a=np.array(np.arange(1,nmax+1),dtype=np.double)
a=1/a                                    # update pole bez cyklu
s=np.sum(a)
print(fmt%(s,time.time()-t0))
del a

# Aproximační vzorec, https://en.wikipedia.org/wiki/Harmonic_number
s=np.log(nmax)+np.euler_gamma+1/(2*nmax)-1/(12*nmax**2)+1/(120*nmax**4)
print(fmt%(s,0))
! Fortran: alokovatelné pole v cyklu vs. array language
real(8),allocatable :: a(:)           ! popis alokovatelného vektoru (pole o jedné dimenzi)
real(8) s

nmax=10000000

call cpu_time(t0)
allocate (a(nmax))                    ! alokační příkaz
do n=1,nmax; a(n)=1/real(n,8); enddo  ! update pole pomocí cyklu
s=sum(a)                              ! redukční funkce
call cpu_time(t1)
print '(f0.15,x,f0.2)',s,t1-t0
deallocate (a)                        ! dealokace pole

call cpu_time(t0)
a=[(n,n=1,nmax)]                      ! alokace přiřazením
a=1/a                                 ! update pole bez cyklu
s=sum(a)
call cpu_time(t1)
print '(f0.15,x,f0.2)',s,t1-t0
deallocate (a)

end program

Zdůrazníme na závěr vlastnost pythonského přiřazovacího příkazu, spočívající v preferenci předávání adresy cíli přiřazení: přiřazením b=a ukazují obě proměnné do téhož místa paměti, jejich id(a) a id(b) jsou stejná. Fortran preferuje přenos hodnot: přiřazení b=a kopíruje hodnoty z a do b. Pro přiřazení adres Fortran nabízí ukazatelové přiřazení c=>a, podmíněné explicitními deklaracemi ukazatelů pointer i jejich cílů target.

# Python: přiřazovací příkaz a přenos adres (default) nebo hodnot
import numpy as np
a=np.ones(2)
b=a                    # přiřazení adresy
c=np.copy(a)           # přiřazení kopie, tj. přenos hodnot
print(a[0],b[0],c[0])  # 1.0 1.0 1.0
b[0]=2                 # přiřazení hodnoty do b i a
print(a[0],b[0],c[0])  # 2.0 2.0 1.0
c[0]=3                 # přiřazení hodnoty pouze do c
print(a[0],b[0],c[0])  # 2.0 2.0 3.0
! Fortran: přiřazovací příkaz a přenos hodnot (default) nebo adres
integer,allocatable :: a(:),b(:)  ! alokovatelná pole
integer,pointer :: c(:)           ! ukazatelové pole
target a                          ! potenciální cíl ukazatele
a=[1,1]
b=a                     ! přiřazení s přenosem hodnot
c=>a                    ! přiřazení adresy
print *,a(1),b(1),c(1)  ! 1 1 1
b(1)=2                  ! přiřazení hodnoty pouze do b
print *,a(1),b(1),c(1)  ! 1 2 1
c(1)=3                  ! přiřazení hodnoty do c i a
print *,a(1),b(1),c(1)  ! 3 2 3
end program

Řetězce

Řetězec (string) je strukturovanou proměnnou pro práci se znaky. Řetězce lze chápat jako pole znaků, navíc je pro ně definována sada specifických funkcí a procedur a operátor řetězení. Lze i jinak, ale obvykle se pracuje s dynamickými řetězci (tj. s řetězci o dynamické délce):

# Python: řetězce jako pole znaků
s='ABCD'
for c in s: print(c,end='')                 # ekvivalentní výpis po znacích
print()
for n in range(len(s)): print(s[n],end='')  # ekvivalentní výpis po znacích
print()

Struktury

Struktura (structure) neboli záznam (record) je strukturovanou proměnnou složenou z položek (fields, items) obecně různého typu. Položky struktury jsou pojmenovány; jejich jména mají význam jen v kontextu daného typu, stejná jména mohou být použita v jiném typu i úplně jinde. Oddělovačem jména struktury a jména položek je často ., někdy (Fortran) %.

Nejprve deklarujeme typ, pak záznam, pak přijde inicializace:

! Fortran: struktura pro popis hmotného bodu
type tBod                           ! datový typ
real hmotnost                       ! skalární položka
real poloha(3)                      ! statické pole
logical,allocatable :: vlastnost(:) ! dynamické pole
end type
type(tBod) bod                      ! struktura
bod=tBod(hmotnost=1.,poloha=[0,0,0],vlastnost=[.false.,.true.])  ! inicializace konstruktorem struktury
print *,bod%hmotnost,bod%poloha(1),bod%vlastnost(2)
bod%hmotnost=1                      ! inicializace položek jednotlivě
bod%poloha=[0,0,0]
bod%vlastnost=[.false.,.true.]
print *,bod%hmotnost,bod%poloha(1),bod%vlastnost(2)
end program

V Pythonu se nalezne hned několik možností, jak něco takového realizovat. Pro indexované položky různého typu můžeme použít seznam (list), pojmenování položek umožňuje slovník (dictionary), pro přístup k položkám pomocí oddělovače . nabízí objektový styl programování vytvoření třídy (class) a její instance čili objektu:

# Python: struktury pro popis hmotného bodu
bod=[1,[0,0,0],[False,True]]      # vytvoření seznamu
print(bod,bod[0])                 # výpis seznamu a jedné položky

bod={"hmotnost":1,"poloha":[0,0,0],"vlastnost":[False,True]}  # vytvoření slovníku
print(bod,bod["hmotnost"])        # výpis slovníku a jedné položky

class tBod:                       # definice třídy
  def __init__(self,hmotnost,poloha,vlastnost): # konstruktor, první z dunder (double-underscore) metod
    self.hmotnost=hmotnost
    self.poloha=poloha
    self.vlastnost=vlastnost
  def __repr__(self):             # metoda pro výpis (reprezentaci)
    return f'tBod({self.hmotnost},{self.poloha},{self.vlastnost})'
bod=tBod(1,[0,0,0],[False,True])  # vytvoření instance třídy (objektu)
print(bod,bod.hmotnost)           # výpis instance a jedné položky

x=bod.poloha                      # nový pohled do instance (synonymum, zkratka)
x[0]=1; bod.poloha[1]=2           # update cestou zkratky i celé cesty
print(x,bod.poloha)               # výpis: [1, 2, 0] [1, 2, 0]

Množiny

Množina (set) je strukturovanou proměnnou, která má implementovány vlastnosti matematických množin.

V ukázce vytvoříme množiny malých a velkých písmen, zjistíme jejich průnik a sjednocení, porovnáme je a ověříme přítomnost vybraného prvku v nich:

# Python: množiny
import string
s=set('abcdefghijklmnopqrstuvwxyz')  # inicializace ze znaků řetězce
s=set([chr(n) for n in range(ord('a'),ord('z')+1)])  # inicializace z položek seznamu
s=set(string.ascii_lowercase)        # inicializace z modulu string
print(s)
SS=set('ABCDEFGHIJKLMNOPQRSTUVWXYZ')
# SS=set([chr(n) for n in range(ord('A'),ord('Z')+1)])
# SS=set(string.ascii_uppercase)
print(s&SS==set())                   # je průnik prázdný?
print(s|SS==set())                   # je sjednocení prázdné?
print(s==SS)                         # jsou množiny stejné?
print('a' in s,' ','a' in SS)        # kde je 'a'?