[Python] Efficientie algoritme

[doltishDuke]

Hallo,

Ik ben bezig in Python een algoritme te schrijven. Momenteel draait dit op 64 bit Linux Ubuntu, de bedoeling was echter om dit op een Raspberry Pi first gen te draaien. Probleem is echter dat de Athlon A6-3500 in mijn desktop al tegen de 70% gaat onder dit proces. Ik moet eerlijk toegeven het nog niet daadwerkelijk op mijn Pi getest te hebben, maar die kroop al bang in een hoekje bij het zien van de code

Doel is om een 50 pixel LED string aan te sturen met WS2811 IC's om zodoende een moodlight te bouwen. Hardware heb ik werkend en kan ik uit Python aansturen, dat is het probleem niet.


(code en probleemstelling staan onderaan, eerst een wat uit de hand gelopen uitleg van het eigenlijke doel)


Om effecten te kunnen maken op deze LED string ga ik uit van het volgende principe. Ik maak 'waves' van kleuren. Een wave kan door de main class op elk willekeurig moment toegevoegd worden en heeft als informatie een kleur, een fadetime, een lifetime, een walkspeed en een wobblefactor. Kleur spreekt voor zich, een lifetime geeft aan hoe lang de wave moet blijven leven en de fadetime geeft aan in hoeveel tijd de wave moet in- en uitfaden. De walkspeed (die overigens nog niet geimplementeerd is) geeft aan hoe snel de wave moet bewegen over de LED string. De wobblefactor geeft aan in hoeverre de wave aan de hand van een random waarde moet 'groeien' (infaden) of 'krimpen' (uitfaden). Dit zodat het geheel wat levendiger wordt. Tijdens het programmeren heb ik geprobeerd dit voor me te zien als een 2D beeld. Een vlak op de grond van 50 vakjes (LEDs) en daar bovenop de waves die zich als bergen op het landschap vormen. Een stuk omhoog, de top, en dan weer omlaag.

De implementatie dan. Om die bergvorm te kunnen maken, ga ik uit van de formule y=1-x^2. Zo krijg ik een parabool die op x=-1 en x=1 de nullijn kruist en zijn top op 1 heeft. Dit bereik van 2 verdeel ik in bijvoorbeeld 6 vakjes, en daarvan pak ik de gemiddelde waarde (ongeveer, ik ga uit van de linker en rechter grenzen van de vakjes, pak daar de waardes van, en neem daar het gemiddelde van. Dat het een gebogen lijn betreft en het dus geen exact gemiddelde is, vind ik niet zo belangrijk: zo nauw komt het niet). Dan heb ik een waarde tussen 1 en 0. Die waarde vermeningvuldig ik vervolgens met een waarde die ik afleid uit de fader. Die geeft, afhankelijk van waar de wave is in zijn lifespan, een waarde aan. Stel dat ik op de helft tussen de linker grens van de wave en de top zit, en de wave 1 seconde bestaat met een fadetime van 3 seconden. Dan krijg ik dus 0.5 * 0.3 = 0.15. Die factor vermeningvuldig ik eventueel met de wobbleFactor, en en met elk van de drie kleuren om uit te komen op de uiteindelijke waarde. Dit doe ik elke 30 ms, omdat ik ongeveer 30 'fps' wil bereiken. Elke 30ms wordt van het object colorWave de functie beat aangeroepen om dat te bewerkstelligen.

De praktijk dan:

Python:

import math
from time import sleep
from random import random
import socket

UDP_IP = "127.0.0.1"
UDP_PORT = 5005

sock = socket.socket(socket.AF_INET, # Internet
                     socket.SOCK_DGRAM) # UDP

class colorWave( object ):
    
    def __init__(self, colorRed, colorGreen, colorBlue, intensityWobble, intensityWobbleChance, walkPace, fadeTime, lifeTime, blockWidth, blockLocation, worldLength):

        self.colorRed = colorRed
        self.colorGreen = colorGreen
        self.colorBlue = colorBlue
        self.intensityWobble = intensityWobble
        self.intensityWobbleChance = intensityWobbleChance
        self.walkPace = walkPace
        self.fadeTime = fadeTime
        self.lifeTime = lifeTime
        self.blockWidth = blockWidth
        self.blockLocation = blockLocation
        self.worldLength = worldLength
        
        self.timeSinceBirth = 0
        self.wobbleFader = 1
        
    def getFadeValue(self):
        
        # Hier moeten we bedenken hoe helder de Wave moet zijn. Vooralsnog laten
        # we de waves even linear in en uitfaden. Parabolisch moet ook wel kunnen,
        # maar dan zou de Wave gedurende zijn hele leven aan het faden zijn en dat
        # willen we niet. Eigenlijk moet hier dus Iets op gevonden worden zodat
        # we binnen de fadetime, aan het begin en einde van het leven, een halve
        # parabool meenemen in de brekenening. Maar dat is nu even teveel moeite.
        
        # default
        fade = 1 
        
        if( self.timeSinceBirth < ( self.lifeTime / 2 ) ):
            
            # We zitten dus nog voor de helft van de lifetime. Moet er nog 
            # iets gefaded worden?
            
            if( self.timeSinceBirth < self.fadeTime ):
            
                # Ja dus. En nu even uitrekenen hoe ver we in de fade zitten.
                
                # 100% fade zou moeten gebeuren als timeSinceBirth gelijk is aan
                # fadeTime. 0% fade, moet gebeuren als timeSinceBirth gelijk is aan 0.
                
                fade = ( self.timeSinceBirth + 0.0 ) / ( self.fadeTime + 0.0 )
                
        if( self.timeSinceBirth > ( self.lifeTime / 2 ) ):
        
            # Fadeout..
            
            if( self.fadeTime + self.timeSinceBirth >= self.lifeTime ):
            
                # Tijd om te gaan faden, maar nu de andere kant op
                                
                fadeOutProgress = self.timeSinceBirth - ( self.lifeTime - self.fadeTime )
                fade = 1.0 - ( fadeOutProgress + 0.0 ) / ( self.fadeTime + 0.0 )
                
        # IntensityWobble!
        
        if( random() < self.intensityWobbleChance ):
            
            if( random() > 0.5 ):
                
                self.wobbleFader = self.wobbleFader * 1.0+self.intensityWobble
                
            else:
                
                self.wobbleFader = self.wobbleFader * 1.0-self.intensityWobble
                
        # Niet te ver, want dan groeit de parabool te hard en gaat het faden aan
        # de randen eraan
        if self.wobbleFader > 1.5:
            self.wobbleFader = 1.3
        
        fade = fade * self.wobbleFader
        return fade
                
                
        
    def beat(self, time):
        
        # We verzamelen alle blocks die we nodig hebben. Omdat we weten waar
        # deze colorWave zich bevindt, gebruiken we een dictionary, omdat we
        # dan de kleuren met indexes kunnen opslaan.
        blocks = {}
        
        if( self.timeSinceBirth > self.lifeTime ):
            return 0
        
        # Eerst even de fade value. Die is overal gelijk, dus hoeven we maar 
        # een keer op te halen
        
        blockFade = self.getFadeValue()        
        
        # Alle eigen blocks doorlopen
        for block in range( 0, self.blockWidth ):
        
            # Even hardop denken..
            
            # block is 0
            # Aantal is 6
            # Het midden zit op 0
            
            #     B1       B2       B3      B4       B5        B6
            # 1       0.6      0.3      0      0.3        0.6       1
            
            # Dus voor blok 0, moet link op 1 en rechts op 0.6 komen
            # Als ik 1 deel door 6, krijg ik ongeveer 0.16. Twee keer dat,
            # is 0.3. Dus..
  
            blockDivider = ( 1.0 / self.blockWidth ) * 2
           
            # Blockdivider is nu 0.3, dus min of meer de breedte van een blok
            # Als ik nu wil uitrekenen wat de linkerkant van blok 1 is, moet ik dus
            # weten hoe vaak ik 0.3 van 0 af moet halen om bij -1 te komen.
            
            # Er zijn 6 blokken. Waarvan er dus 3 aan de linkerkant zitten. Ik moet
            # dus ook drie keer 0.3 van 0 afhalen.
            
            blockLeftBoundary = -1.0 + block * blockDivider
            
            # En voor de rechterkant dus slechts twee keer
            
            blockRightBoundary = -1.0 + ( block + 1 ) * blockDivider
                        
            # Elk block, heeft nu een linker en rechter kant. Die lopen van -1 tot 1.
            # Das mooi binnen het bereik van y = 1 - x^2.
            
            # Vet!
            
            blockLeftHeight = 1 - blockLeftBoundary**2
            blockRightHeight = 1 - blockRightBoundary**2
            
            # Nu hebben we dus de twee waardes. Dat het een gebogen lijn is en een
            # gemiddeld punt pakken niet werkt interesseert me niet.
            
            blockHeight = ( blockLeftHeight + blockRightHeight ) / 2
            
            # I FUCKING SOLVED IT
                        
    
            # Maar nu nog rekening houden met de fadetime. Die hadden we al klaar
            # liggen, dus die kan meteen mee in de berekening en hoeft niet opniew
            
            # Elk block krijgt een list met daarin 0-255 waarden voor R, G en B
            # Wel eerst even checken of de waarde binnen dit bereik ligt, anders
            # gaat straks de LED string over zijn nek
            thisBlock = []
            calcRed = int( self.colorRed * blockHeight * blockFade );
            if calcRed > 255:
                calcRed = 255
            if calcRed < 0:
                calcRed = 0
            thisBlock.append( calcRed )
            
            calcGreen = int( self.colorGreen * blockHeight * blockFade );
            if calcGreen > 255:
                calcGreen = 255
            if calcGreen < 0:
                calcGreen = 0
            thisBlock.append( calcGreen )
            
            calcBlue = int( self.colorBlue * blockHeight * blockFade );
            if calcBlue > 255:
                calcBlue = 255
            if calcBlue < 0:
                calcBlue = 0
            thisBlock.append( calcBlue )
            
            # En nu het plaatsen van de blocks. En dus weer met de index ten opzichte
            # van de volledige LED string.
            
            currentBlockPosition = ( self.blockLocation - ( self.blockWidth / 2 ) + block )
            
            if currentBlockPosition > 0 and currentBlockPosition < self.worldLength:
                # Alleen als ie niet van het kaartje af dondert natuurlijk
                blocks[ currentBlockPosition ] = thisBlock
            
            
        
        # En om te zorgen dat we FPS on the fly kunnen aanpassen zonder dat de
        # timings in de waves verkeerd gaan lopen, houden we de tijd hier ook bij
        # De herder heeft aangegeven hoeveel tijd er verstreken is, dus dat nemen
        # we over
        self.timeSinceBirth += time
        
        return blocks
        

class colorHerder( object ):
    
    leds = 50
    
    colorRed = 255
    colorRedDiffer = 50
    
    colorGreen = 10
    colorGreenDiffer = 10
    
    colorBlue = 0
    colorBlueDiffer = 5
    
    spawnRate = 4000
    spawnRateDiffer = 1000
    
    walkPace = 2000
    walkPaceDiffer = 750
    
    fadeTime = 3000
    fadeTimeDiffer = 2000
    
    lifeTime = 10000
    lifeTimeDiffer = 4000
    
    intensityWobble = 0.1
    intensityWobbleChance = 0.3
    
    blockWidth = 7
    blockWidthDiffer = 3
    
    maxAlive = 3
    
    def __init__(self):
        
        self.colors = []    # Hier slaan we de kleuren op
        self.ticker = 0     # Debug.. Even scripten wanner kleuren erbij moeten komen
        
    def beat(self):
        
        self.ticker = self.ticker+1
        
        # Om te beginnen twee rooie
        if self.ticker == 0:
            self.colors.append( colorWave(255,0,0, 0.02, 0.02, 2000, 6000, 20000, 14, 5, self.leds-1) )        
            self.colors.append( colorWave(220,0,0, 0.044, 0.14, 2000, 9000, 20000, 6, 27, self.leds-1) )   
        
        if self.ticker == 180:
            # Na 100 ticks nog een groene
            self.colors.append( colorWave(0,255,0, 0.03, 0.4, 2000, 6000, 20000, 23, 15, self.leds-1) )
            
        if self.ticker == 250:
            # En na 250 ticks nog een blauwe
            self.colors.append( colorWave(105,250,250, 0.025, 0.18, 2000, 6000, 20000, 20, 38, self.leds-1) )
            
        # Voor elk block houden we de kleur bij, we beginnen altijd met een lege
        blocks = []
        
        # En die vullen we met zwarte pixels
        for x in range(0,self.leds-1):
            blocks.append([0,0,0])
            
        # En nu loopen we door de lijst met waves
        for colorid, color in enumerate( self.colors ):
            
            # Beat.. Er zijn zo'n 30ms verstreken
            wave = color.beat( 30 )
            
            # Een wave stuurt 0 terug als ie klaar is, anders gaan we hem overnemen
            if isinstance( wave, dict ):
                for i, block in wave.iteritems():
                    
                    # Als het block van de wave een hogere waarde heeft dan van het bestaande block
                    if block[0] > blocks[i][0]:
                        # dan houden we die aan
                        blocks[i][0] = block[0]            
                    else:
                        # zo niet, dan pakken we een gemiddelde
                        blocks[i][0] = ( blocks[i][0] + block[0] ) / 2                    
                    
                    if blocks[i][1] == 0:
                        blocks[i][1] = block[1]
                    else:
                        blocks[i][1] = ( blocks[i][1] + block[1] ) / 2
                    
                    if blocks[i][2] == 0:
                        blocks[i][2] = block[2]
                    else:
                        blocks[i][2] = ( blocks[i][2] + block[2] ) / 2
                    
            else:
                # Hij gad 0 terug, dus weg hiermee
                del self.colors[colorid]
                
        
        # Resultaat naar de server sturen
        for index,bl in enumerate(blocks):
            lt = bl[0]            
            # printstring = int( (lt) / 7 )
            # print "#" * printstring, " " * ( int(255/7) - printstring ), "| "
            #C.itemconfigure( demoBlocks[index-1], fill='#%02x%02x%02x' % (bl[0], bl[1], bl[2]))
                        
            message = "0" + str(index).zfill(2) + str(bl[0]).zfill(3) + str(bl[1]).zfill(3) + str(bl[2]).zfill(3)            
            sock.sendto( message, (UDP_IP, UDP_PORT) )
            
        sock.sendto( "1push", (UDP_IP, UDP_PORT) )
        
# Workertje maken    
worker = colorHerder()

while True:
    # En loopen
    worker.beat()
    sleep(0.03)

Ik denk zelf dat het probleem zit in het geklooi met al die floats, gecombineerd met het voor elk block twee keer moeten machtverheffen. Echter heb ik geen idee hoe ik daar onderuit kan komen en óf het daadwerkelijk het probleem is. Opzich zijn dat natuurlijk snelle berekeningen, maar ze gebeuren zo wel 2 berekeningen * 20 pixels * 4 waves * 30 is 4800 keer per seconde.

Ik heb al geprobeerd niet met floats te werken maar met integers, dat geeft natuurlijk een zeer hoekig effect of ik moet met integers van 16 bits gaan werken. Ten eerste krijg ik dat niet voor elkaar (als in, ik krijg gigantische koppijn van het implementeren daarvan) en ten tweede blijken testen die ik met stukjes van de code gedaan heb daarmee (de fader en wobble) eigenlijk nauwelijks van invloed. Ook heb ik geprobeerd in plaats van de dictionary (die ik maak op 95 en vul op 187) een list te maken. Ik ging er vanuit dat die sneller zouden zijn omdat ze niet associated zijn, maar dat had ik dus mis: de load gaat omhoog.


Iemand enig idee hoe ik dit geheel wat lichter kan maken, of uberhaupt wat nou datgene is waar die load vandaan komt? Of is eigenlijk de enige goede manier om dit te gaan herschrijven in een gecompileerde taal met fixed data types?


Overigens ben ik mij ervan bewust dat er diverse stukken software rondzwerven die iets vergelijkbaars doen. Mijn toepassing is echter vrij specifiek en daarnaast moet ik in de toekomst meer van dit soort gerelateerde problemen op gaan lossen, dus ik zou graag inzien wat ik hier nou fout doe of wat er beter kan.

[Juup]

Hang er eens een profiler aan en kijk waar de CPU het meeste tijd mee kwijt is.

[ZaPPZion]

Waar in elk geval een efficientieslag in te maken valt, is het gebruik van je arrays. Neem bijvoorbeeld regel 256 tm 260. Je kunt prima die array 1 keer maken, opslaan op class niveau en daarna de waardes wijzigen. Het telkens opnieuw moeten allocaten van memory en het vergroten van arrays is over het algemeen iets wat behoorlijk impact kan hebben op je algorithme.

Sommige implementaties van compilers/talen/interpreters/whateverdevertaalslagmaakt kiezen er namelijk voor om een array in zijn geheel in memory te verplaatsen als er niet genoeg ruimte is om de array uit te breiden. Dus als je bv 200 items in je array hebt, worden deze items geheel gekopieerd naar een ander stuk geheugen waar en 201 items achter elkaar kunnen staan. Niet echt heel handig dus . Daarom altijd (nouja, 99.999%) je arrays proberen fixed size te houden als je geen dynamic size array nodig hebt.

Verder heb je best veel loops achter elkaar, zijn ze afhankelijk van elkaar (heb niet je hele code bestudeerd), of zou je het eventueel in 1 keer kunnen doen? (hoeft je pc niet 3 keer de hele lijst door)

[H!GHGuY]

Aangezien je maar tot de 2de macht verheft:
(x^2) is vele malen trager dan (x*x)

Verder dacht ik dat de Linux tool perf support had voor python profiling...

[ Voor 32% gewijzigd door H!GHGuY op 20-07-2015 21:18 ]

[deadinspace]

doltishDuke schreef op maandag 20 juli 2015 @ 17:36:
Ik ben bezig in Python een algoritme te schrijven. Momenteel draait dit op 64 bit Linux Ubuntu, de bedoeling was echter om dit op een Raspberry Pi first gen te draaien. Probleem is echter dat de Athlon A6-3500 in mijn desktop al tegen de 70% gaat onder dit proces.

Dat is vreemd, op mijn computer (quad i5 2.4GHz, Python 2.7.9, Debian amd64) gebruikt hij ongeveer 3.3% CPU.

Ik heb hem even herschreven om de worker.beat() method te timen, door onderaan je oneindige loop te vervangen door:

Python:

for i in range(1000):
    worker.beat()

Uitvoeren kost 490ms (gemeten met time ./jeprogramma.py), waarmee ik uitkom op minder dan 0.5ms per beat. Dat is snel zat. Ik zie in je code ook weinig geks qua performance (je maakt geen enorme lijsten of superveel objecten aan per beat, wat typische performance-problemen zijn).

Wat meer testen of je programma inderdaad zo traag is als je denkt lijkt me een goed idee. Doe eens wat ik deed, een directe forloop voor 1000 iteraties van ColorHerder.beat(). En anders profilen zoals Jaaap al voorstelde

Ik denk zelf dat het probleem zit in het geklooi met al die floats, gecombineerd met het voor elk block twee keer moeten machtverheffen.

Dat is sowieso het probleem niet. In een strak geïmplementeerde C versie zou je daar misschien nog een verschil in kunnen zien (al is floating point op moderne CPUs echt wel snel), maar Python is zodanig veel trager dan C dat zo'n verschil compleet in het niet valt. En ook machtverheffen is tegenwoordig geen probleem meer tenzij je het een miljard keer per seconde wil doen. Zeker niet als het simpelweg kwadrateren is.

In een dynamische high-level taal als Python kost het instantieren van een simpel leeg object zo al 300 CPU cycles. Dat zijn 300 optellingen op een moderne CPU (ongeveer - het gaat even om de ordegrootte).

Echter heb ik geen idee hoe ik daar onderuit kan komen en óf het daadwerkelijk het probleem is. Opzich zijn dat natuurlijk snelle berekeningen, maar ze gebeuren zo wel 2 berekeningen * 20 pixels * 4 waves * 30 is 4800 keer per seconde.

Maar qua rauwe performance moet je CPU simpele berekeningen (zoals integers optellen) miljarden keren per seconde kunnen

Wat random opmerkingen op je code trouwens:

Python:

from random import random

Dat kun je beter niet doen; nu kun je de andere functies van de random module niet meer gebruiken. Beter is om "import random" te doen en dan verderop "random.random()" te gebruiken.

Python:

if( self.timeSinceBirth < ( self.lifeTime / 2 ) ):

De buitenste haakjes zijn overbodig en kunnen beter weggelaten worden. De binnenste ook eigenlijk

Python:

blocks = []

for x in range(0,self.leds-1):
    blocks.append([0,0,0])

Merk op dat je hier een lijst van leds-1 items maakt, volgensmij is dat ééntje minder dan je wil. De 'to' parameter van range is exclusief in python. Volgensmij wil je dus range(0, self.leds) hebben. Overigens is 0 de default voor de start, dus die kun je weglaten. range(self.leds) dus. En als ik ga mierenneuken; xrange() is iets efficienter want die genereert de waardes on the fly in plaats van een lijst te genereren (of je gebruikt Python 3, waar range dat zelf al doet).

Verder zou ik het geheel als een list expression schrijven; dat is een compacte manier om lijsten te genereren. In totaal krijg je dan zoiets:

Python:

blocks = [[0, 0, 0] for x in xrange(self.leds)]

ZaPPZion schreef op maandag 20 juli 2015 @ 19:29:
Waar in elk geval een efficientieslag in te maken valt, is het gebruik van je arrays.

Python is geen C. Python heeft dan ook geen arrays, maar lists

Sommige implementaties van compilers/talen/interpreters/whateverdevertaalslagmaakt kiezen er namelijk voor om een array in zijn geheel in memory te verplaatsen als er niet genoeg ruimte is om de array uit te breiden. [...] Daarom altijd (nouja, 99.999%) je arrays proberen fixed size te houden als je geen dynamic size array nodig hebt.

Of uitzoeken hoe het in de taal/runtime in kwestie zit. Pythons list append is amortized O(1), dus dat is in de praktijk vaak geen probleem. Zeker voor 30 keer per seconde 50 items zal het weinig uithalen.

Verder heb je best veel loops achter elkaar, zijn ze afhankelijk van elkaar (heb niet je hele code bestudeerd), of zou je het eventueel in 1 keer kunnen doen? (hoeft je pc niet 3 keer de hele lijst door)

En ook dat is een micro-optimalisatie die weinig uit gaat halen. Het is aan te raden als het de leesbaarheid bevordert, maar voor de snelheid hoef je het niet te doen.

H!GHGuY schreef op maandag 20 juli 2015 @ 21:18:
Aangezien je maar tot de 2de macht verheft:
(x^2) is vele malen trager dan (x*x)

Zulk soort dingen zijn compleet overbodige micro-optimalisaties. Je kunt niet zeggen dat x**2 vele malen trager is dan x*x zonder dat eerst te profilen. Met nog geen 5000 iteraties per seconde zal het sowieso geen meetbaar verschil uithalen op de rest van het programma. In Python:

% python -mtimeit 'x = 5; x ** 2'
10000000 loops, best of 3: 0.0783 usec per loop
% python -mtimeit 'x = 5; x * x'
10000000 loops, best of 3: 0.0619 usec per loop

Dat is dus al een klein verschil. Op een compleet programma dat dynamisch lijsten opbouwt en objecten aanmaakt wordt het helemaal verwaarloosbaar.

[ZaPPZion]

Mijn Python is niet heel best merk ik, te veel C concepten in mijn hoofd, had niet verwacht dat een append een O(1) zou zijn. Thanks voor de correctie

[doltishDuke]

Mja, en ik heb teveel javascript concepten in mijn hoofd momenteel. Net klaar met zo'n 10k regels tellend Node.JS servertje. Voor de beroepsprogrammeur misschien niets bijzonders maar voor mij een beste prestatie al zeg ik het zelf

Overigens, @deadinspace, ik weet niet waarom ik 70% in mijn hoofd had, de load van python tijdens het draaien hiervan is 17%. Die info haalde ik uit top, bij het python proces. Klooien met die profiler leverde mij geen bruikbare informatie op, waarschijnlijk gewoon verkeerd geimplementeerd maar goed. 17% komt gezien de verschillen in hardware al beter in de buurt natuurlijk. Voor mijn desktop geen probleem, de moodlight zal immers hoofdzakelijk actief zijn als die niets relevants aan het doen is verder. Vandaar ook dat stukje met die UDP verbinding die er nog in staat, ik was wat aan het testen met het uitrekenen van het geheel op de PC om dan de output naar de Raspberry te sturen zodat die alleen de LEDs hoeft te doen, blijft een first gen bordje natuurlijk.


In ieder geval zeer bedankt voor je uitgebreide antwoord, daar kan ik echt wat mee. Geldt natuurlijk net zo goed voor de rest, ik ga hier morgenavond eens verder mee klooien en jullie suggesties implementeren