Egy Python program sikeres optimalizálása

Python logo

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. Python logo

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

Az oldal használatával elfogadja, hogy az sütiket használ További információ

A sütik használatát érdemes engedélyezni a böngészőben.
The cookie settings on this website are set to "allow cookies" to give you the best browsing experience possible. If you continue to use this website without changing your cookie settings or you click "Accept" below then you are consenting to this.

Bezár