Egy kedves tanuló barátom megkeresett, hogy a python programját írjam át valami compileres nyelvre, mert nagyon lassú. A program a tanulmányi szintjének teljesen megfelel, de kiváló ürügy, hogy az optimalizálásról pár szót ejtsünk, mivel egy naiv algoritmust használt, az algoritmus optimalizálásával jelentős eredményeket lehet leérni. 
A programkódokban az előző verzióhoz képest történt változásokat félkövér szedéssel jeleztem.
Na nézzük a programot:
primes=[2,3,5,7]
def IsPrime(num):
eredm=True
for i in primes:
if num%i==0:
eredm=False
return eredm
for num in range(primes[-1],30000,2):
if IsPrime(num):
primes.append(num)
print(len(primes))
Nagyon jó, de a programot azonnal visszadobtam. Nincsenek benne megjegyzések, amik segítenék a kódban való eligazodást.
#### Prímszám kereső program ####
# Készítette Gipsz Jakab
# A program korlátozások nélkül szabadon felhasználható
# Indulásnak megadunk néhány prímet egy listában
primes=[2,3,5,7]
def IsPrime(num):
#Az argumentumban megadott num integert elosztjuk minden
#ismert prímmel. Ha egyikkel sem osztható, akkor True,
#egyébként False értéket adunk vissza
eredm=True
for i in primes:
if num%i==0:
eredm=False
return eredm
# A főprogram.
# A legnagyobb ismert prím+2-től 30 000-ig minden páratlan számot megnézünk
for num in range(primes[-1]+2,30000,2):
#Ha a szám prím, hozzá adjuk az ismert prímek listájához
if IsPrime(num):
primes.append(num)
print(len(primes))
Így már jobban néz ki, és a program mögötti elképzelésekről is van egy kis képünk.
Tegyünk bele egy idő mérést, hogy mit jelent a “lassú”, mivel az SI mértékegységek között ilyet nem találtam:
Az idő méréséhez szükség van a datetime modulra, ami tartalmazza a now() függvényt, ami az aktuális pontos időt adja vissza.
#### Prímszám kereső program ####
# Készítette Gipsz Jakab
# A program korlátozások nélkül szabadon felhasználható
# Az időméréshez betöltjük a datetime modult
from datetime import datetime
# Indulásnak megadunk néhány prímet egy listában
primes=[2,3,5,7]
def IsPrime(num):
#Az argumentumban megadott num integert elosztjuk minden
#ismert prímmel. Ha egyikkel sem osztható, akkor True,
#egébként False értéket adunk vissza
eredm=True
for i in primes:
if num%i==0:
eredm=False
return eredm
## A főprogram.
# Először progstart változóban rögzítjük a program indulásának időpotját
progstart=now = datetime.now()
# A legnagyobb ismert prím+2-től 30 000-ig minden páratlan számot megnézünk
for num in range(primes[-1]+2,30000,2):
#Ha a szám prím, hozzá adjuk az ismert prímek listájához
if IsPrime(num):
primes.append(num)
#Rögzítjük, hogy mikor ért véget a program
progend=datetime.now()
#Kiírjuk hány prímet találtunk
print(len(primes))
print('Futásidő:',progend-progstart)
Az én gépemen futtatva ez a verzió olyan 26 másodperc alatt futott le
A teszteléshez használt gép
A teszteléshez az én asztali gépemet használtuk.
CPU: Intel(R) Xeon(R) CPU E5-2643 v2 (6 mag 12 szál)
Memória: 32 GB
Háttértár: SSD
Windows 10 64 bit
A program a 12 szálból egyet használ
A számítógép olyan állapotban van, ahogy használni szoktam. Egy pontosabb méréshez frissen telepített Windowsra lenne szükség, az adott esetben azonban nem finom összehasonlítást végzünk. Itt a nagy léptékű változások érdekelnek.
Minden program verziót négy alkalommal futtatok le. A legnagyobb és legkisebb értéket eldobom, a két középső átlagát adom meg. (A mérési tapasztalat, hogy a négy futtatás ideje alig tér el)
Kezdjük el az észszerűsítést
A Python nem a sebességéről híres, elsősorban arra találták ki, hogy a program gyorsan elkészíthető legyen, program futási ideje is ennek van alárendelve. Ebben a programban azonban bőven van tere az optimalizálásnak. Első lépésben csökkentsük a felesleges osztások számát az IsPrime függvényben. Ha egy számról kiderül, hogy osztható valamelyik prímmel, azonnal kilépünk a ciklusból is .
#### Prímszám kereső program ####
# Készítette Gipsz Jakab
# A program korlátozások nélkül szabadon felhasználható
# Az időméréshez betöltjük a datetime modult
from datetime import datetime
# Indulásnak megadunk néhány prímet egy listában
primes=[2,3,5,7]
def IsPrime(num):
#Az argumentumban megadott num integert elosztjuk minden
#ismert prímmel. Ha egyikkel sem osztható, akkor True,
#egébként False értéket adunk vissza
#Ha a szám nem prím, kilép a ciklusból
eredm=True
for i in primes:
if num%i==0:
eredm=False
break #Azonnal kilép a ciklusból
return eredm
# A főprogram.
# A legnagyobb ismert prím+2-től 30 000-ig minden páratlan számot megnézünk
progstart=now = datetime.now()
for num in range(primes[-1]+2,30000,2):
#Ha a szám prím, hozzá adjuk az ismert prímek listájához
if IsPrime(num):
primes.append(num)
progend=datetime.now()
print(len(primes))
print('Futásidő:',progend-progstart)Ez a program 3,6 másodperc alatt futott le. Ez már jelentős gyorsulás
Csökkentsük tovább az osztások számát
A második feltétel kevésbé triviális, de könnyű belátni, hogy a szám négyzetgyökénél nagyobb számokat biztos, hogy a négyzetgyöknél kisebb számmal kell megszorozni, hogy az eredeti számot kapjuk. Ha a négyzetgyök értékét elértük, akkor már az összes annál kisebb számmal próbálkoztunk.
A négyzetgyökvonást a math modul tartalmazza.
#### Prímszám kereső program ####
# Készítette Gipsz Jakab
# A program korlátozások nélkül szabadon felhasználható
# Az időméréshez betöltjük a datetime modult
from datetime import datetime
# A négyzetgyök vonáshoz szükség lesz a math modulra
import math
# Indulásnak megadunk néhány prímet egy listában
primes=[2,3,5,7]
def IsPrime(num):
#Az argumentumban megadott num integert elosztjuk minden
#ismert prímmel. Ha egyikkel sem osztható, akkor True,
#egébként False értéket adunk vissza
#Ha a szám nem prím, kilép a ciklusból
eredm=True
vege=int(math.sqrt(num)+1)
for i in primes:
if num%i==0:
eredm=False
break
if i>vege:
break
return eredm
# A főprogram.
# A legnagyobb ismert prím+2-től 30 000-ig minden páratlan számot megnézünk
progstart=now = datetime.now()
for num in range(primes[-1]+2,30000,2):
#Ha a szám prím, hozzá adjuk az ismert prímek listájához
if IsPrime(num):
primes.append(num)
progend=datetime.now()
print(len(primes))
print('Futásidő:',progend-progstart)Sikerült jelentős teljesítmény növekedést elérni, a program 0,28 másodperc alatt futott le. Ez jelentős javulás. Akárhogy is nézzük, a futásidőt közel az 1%-ára csökkentettük.
A program futása tovább gyorsítható numpy modul és a jit (just in time compiler) használatával. További lehetőség (különösen ilyen sok szálas gép esetén) lehet használni a multiprocessing modult, ami lehetővé teszi egyes programrészek párhuzamos végrehajtását.
Ezek azonban már erősen nyelv függő dolgok, nem ennek a cikknek témája.
Nézzük meg Freepascal használatával
Azért nem csak a páratlan számokat nézem végig, mert a Pascal nem ismeri a for ciklusban a step kiegészítést, természetesen van rá megoldás, de a feladat nem indokolta. A program egyébkén nagy vonalakban megfelel a kiindulási programnak.
A program láthatóan sokkal több programsorból áll, mivel a programnyelv megköveteli, hogy a változókat használat előtt deklaráluk (a var szakasz). Ugyan ezt meg kell ismételni a függvényeken belül is.
Mivel a program nem interpreteres, hanem compileres (a forrásszövegből külön lépésben kell futtatható programot létrehozni) az elkészült program futása gyorsabb, illetve az előre definiált változók segítik a hibakeresést.
// Prímszám rostáló program a Python program optimalizálásról szóló cikkhez
//Bemutató program, szabadon felhasználható
//Készítette Szigetvári Zoltán
//A sysutil ás DateUtils modulok az idő méréséhez szükségesek
uses sysutils, DateUtils;
const
//A maximális vizsgált szám
max=30000;
var
//A pythonnal ellentétben itt előre meg kell adni a változók típusát.
//A primes nevű tömbben tároljuk az eredményt. Mivel memóriánk van bőven, akkora helyet foglalunk, mintha a minden szám prím lenne
primes:array[0..max] of longint;
//A szam a ciklusváltozó
szam:longint;
//Index-ben tároljuk a megtalált prímek sorszámát 0-tól számolva
index:integer;
//A program indulásának időpontja
progstart:TDateTime;
//Az IsPrime függvény minden egyes már megtalált prímmel elosztjuk a vizsgált számot. Ha a maradék nulla (a szám osztható), a függvény false értékkel tér vissza
function IsPrime(num:QWord;darab:Word):boolean;
var
szam: integer;
eredm:boolean;
begin
eredm:=True;
for szam:=0 to darab do
begin
if num mod primes[szam]=0 then
begin
eredm:=false;
end;
IsPrime:=eredm;
end;
end;
Begin
primes[0]:=2;
primes[1]:=3;
primes[2]:=5;
primes[3]:=7;
index:=3;
progstart:=Now;
for szam:=11 to max do
begin
if IsPrime(szam,index) then
begin
index:=index+1;
primes[index]:=szam;
end;
end;
writeln('A program futási ideje',SecondsBetween(Now,progstart));
writeln('A program indulásának és befejezésének időpontja: ',DateTimeToStr(progstart), DateTimeToStr(now));
writeln('A megtalált prímek száma: ',index+1);
End.A program a tesztgépen néhány tized másodperc alatt futott le. Ez mutatja, hogy a kissé komplikáltabb programfelépítés és a valamivel komplikáltabb fejlesztési folyamat eredményeképpen jelentősen gyorsabban futó program készíthető. Mind az Interpreteres,, mind a compileres programnyelveknek megvan a maga helye.