Kategória: python

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.

Kapcsolódó szócikkek:

Python cikksorozat
FreePascal