[Python] Noob behöver hjälp med optimering av kod till uppgift

Trädvy Permalänk
Medlem
Registrerad
Mar 2012

[Python] Noob behöver hjälp med optimering av kod till uppgift

Är total nybörjare vad gäller all form av programmering så ber om ursäkt för följande kod Det är en uppgift i Codecademy's Python-kurs där funktionen ska returnera medianen och input är en lista med tal. Koden fungerar och klarar det den ska men känns inte så elegant och alldeles för lång. Vill inte titta på färdiga lösningar eftersom jag vill lösa det själv, men om någon kan ge mig en liten hint om hur jag kan optimera koden med enkla medel är jag tacksam då jag kört fast lite.

def median(lista): sorterad = sorted(lista) x = len(lista) / 2 median_odd = sorterad[len(lista)/2] split1 = sorterad[0:x] split2 = sorterad[x:] while len(lista) > 1: if len(lista) % 2 != 0: return median_odd else: median_even = (split1[len(split1)-1] + split2[0]) / 2.0 return median_even else: return lista[0]

Trädvy Permalänk
Medlem
Registrerad
Mar 2012

Duh ... Kom på att det är helt meningslöst att splitta listan. Sen ska det givetvis ska vara if len(lista) > 1: och inte while samt att jag kan använda variabeln x på flera ställen för renare kod. Ser betydligt bättre ut, något mer jag bör ändra?

def median(lista): sorterad = sorted(lista) x = len(lista) / 2 y = len(lista) median_odd = sorterad[x] if y > 1: if y % 2 != 0: return median_odd else: median_even = (sorterad[x-1] + sorterad[x]) / 2.0 return median_even else: return lista[0]

Trädvy Permalänk
Medlem
Plats
Linköping
Registrerad
Dec 2010

Ser bra ut, man kan väl alltid klaga på naming conventions ( ganska onödigt);
dvs man ska vara övertydlig med vad dina variablar representerar.

seq_middle = len(lista) / 2
seq_length = len(lista)

Något i den stilen. Vid en sådan liten kodsnutt så spelar det egentligen ingen roll men man kan börja ha det i vana tills man kommer till den punkten då man har definierat flera funktioner för ett visst program.

Stationära:[Fractal Design R2], [Asrock Fatal1ty Professional] , [Vengeance low profile 1600mhz]
[Intel Core i5 2500k 3.3 ghz (Kyld av Noctua nh-d14)], [ Referens XFX HD 6970],
[Corsair TX 650 watt], [ca 750 GB utrymme], [2x Gentletyphoon Utblås och 2x Fractal design inblås]

Trädvy Permalänk
Medlem
Registrerad
Mar 2012
Skrivet av Uzor:

Ser bra ut, man kan väl alltid klaga på naming conventions ( ganska onödigt);
dvs man ska vara övertydlig med vad dina variablar representerar.

seq_middle = len(lista) / 2
seq_length = len(lista)

Något i den stilen. Vid en sådan liten kodsnutt så spelar det egentligen ingen roll men man kan börja ha det i vana tills man kommer till den punkten då man har definierat flera funktioner för ett visst program.

Tackar för input, det låter vettigt. Lika bra att göra det till en vana från början.

Trädvy Permalänk
Forumledare
Registrerad
Okt 2002

Att optimera för hastighet hävdar jag och många andra med mig sällan (notera ordval) är värt så mycket i sig själv i ett första skede, men att däremot optimera läsbarhet och intention är värt desto mer. Dessutom så brukar hastighet följa med på köpet om man följer vanliga idiom i respektive språk, då dessa ofta grundar sig på just effektiva lösningar.


En sak jag tänker på direkt är att använda ett "tidigt avslut" för ditt specialfall där listan bara består av ett element, dvs att ändra logiken till något i stil med (där jag även ändrat en del variabelnamn: håll dig till ett (människo)språk; med fördel engelska):

def median(sequence): length = len(sequence) if length == 1: return sequence[0] sorted_ = sorted(sequence) mid_odd_index = len(sequence) / 2 median_odd = sorted_[mid_odd_index] if length % 2 != 0: return median_odd else: median_even = (sorted_[mid_odd_index - 1] + sorted_[mid_odd_index]) / 2.0 return median_even

Det avslutande understrecket i sorted_ är en vanlig konvention för att namnge variabler som annars skulle krocka med inbyggda funktioner.

Jag döper om lista till sequence, dels för att migrera till engelska, men också för att koden faktiskt inte kräver att input är just en "lista", utan det räcker med en "sekvens" (som stödjer längdberäkning, dvs inte är oändlig), som är ett bredare begrepp. Därutöver behöver sekvensens element stödja jämförelse och division, men det har inte att göra med om det är just en list som skickats in eller ej. En stor poäng med dynamiskt typade språk som Python är just att de per automatik (utan att behöva brottas alltför mycket med ordrika designmönster; inget språk nämnt, inget glömt ) jobbar med beteenden snarare än explicita datatyper, så det kan vara intressant att ha i bakhuvudet.

Notera hur indenteringsnivån för stora delar av koden minskade: detta är ofta ett tecken på att man uttryckt sin logik på ett tydligare sätt. Den tidiga returen minskar också den kognitiva lasten av koden, i någon mån, då man efter första raderna slipper hålla specialfallet i huvudet. Vissa avskyr "tidiga returer" beroende på vilka språk de är mest vana vid, då vettigheten kan vara språkberoende, men i enklare funktioner tycker jag att fördelarna bör vara tydliga för alla.


Det kan också funderas på om det ens verkligen är ett specialfall med en sekvens med ett enda element, då det hanteras som det ska av den generella lösningen. Söker man optimeringar så försöker lösningen ovan optimera för fallet när sekvenser bara har ett element, med kostnad av en extra jämförelse för alla andra fall. Jagar man optimeringar i "verkligheten" så måste man här ha något hum om vilka data man generellt vill använda funktionen med, men jag känner spontant att en-elementssekvenser är rätt exotiska, så specialfallet kan lika gärna skippas helt.

Snarare är kanske en sekvens med noll element något att se upp för, men felhanteringen är inte definierad här.

def median(sequence): length = len(sequence) sorted_ = sorted(sequence) mid_odd_index = len(sequence) / 2 median_odd = sorted_[mid_odd_index] if length % 2 != 0: return median_odd else: median_even = (sorted_[mid_odd_index - 1] + sorted_[mid_odd_index]) / 2.0 return median_even


En andra sak jag noterade var att det sällan är någon poäng med att lagra en listas längd i en speciell variabel. Pythons listor är implementerade som dynamiska arrayer och håller längden i minnet, så det är ett enkelt O(1)-uppslag att hämta den. Det går visserligen via ett funktionsanrop som man kan se tar lite extra tid om man försöker mikrooptimera saker, men sannolikt är det så många andra saker som översköljer denna tid (här typiskt listsorteringen) att det inte är värt att offra läsbarheten för att mellanlagra listans längd. Dessutom så använder du ju faktiskt len(sequence) explicit en andra gång trots att du lagrad längden som length i din nuvarande kod.

Nu argumenterade jag visserligen nyss för att generalisera funktionen till sekvenser vilket gör att jag inte på förhand kan veta exakt hur len är implementerat för den datatyp användaren skickar in, men man kan väl fortfarande anta att typanvändningen gäller listor. Med rätt gott samvete:

def median(sequence): sorted_ = sorted(sequence) mid_odd_index = len(sequence) / 2 median_odd = sorted_[mid_odd_index] if len(sequence) % 2 != 0: return median_odd else: median_even = (sorted_[mid_odd_index - 1] + sorted_[mid_odd_index]) / 2.0 return median_even


Tilldelningen av median_odd skulle kunna ha ett existensberättigande i att förklara koden, men tja, en medianberäkning är rätt given, så även om jag är en stark förespråkare av bra variabelnamn så skulle jag gott kunna tänka mig att skippa denna mellantilldelning här. Likaså i returen för en jämn sekvens. En funktionsförklaring i form av exempelvis en docstring bör göra det mer än tydligt vad som händer. Eftersom "median" är ett rätt vedertaget begrepp så skulle """Return median of sequence.""" egentligen räcka långt, men om man vill vara tydligare:

def median(sequence): """Sort a copy of the input sequence. Return middle element if the sequence length is odd, or the arithmetic mean of the two mid elements otherwise.""" sorted_ = sorted(sequence) mid_odd_index = len(sequence) / 2 if len(sequence) % 2 != 0: return sorted_[mid_odd_index] else: return (sorted_[mid_odd_index - 1] + sorted_[mid_odd_index]) / 2.0


Garanterade int-jämförelser med 0 kan nyttja språkets inbyggda booleska konventioner, och är man bekant med moduloräkning så bör man inte bli alltför förvånad av att se:

def median(sequence): """Sort a copy of the input sequence. Return middle element if the sequence length is odd, or the arithmetic mean of the two mid elements otherwise.""" sorted_ = sorted(sequence) mid_odd_index = len(sequence) / 2 if len(sequence) % 2: return sorted_[mid_odd_index] else: return (sorted_[mid_odd_index - 1] + sorted_[mid_odd_index]) / 2.0

Koden har kortats ned, vilket här gör det betydligt enklare att snabbt se vad den gör i mina ögon, och den har fått lite dokumentation på köpet.


En annan sak jag åtminstone noterar (även om det inte är någon märkbar fara i just Python) är en någorlunda vanlig fälla när det gäller att räkna ut medelvärden. Den matematiskt uppenbara metoden

   (a + b) ∕ 2

innehåller ett datormässigt problem: låt säga att a = 42 och b = 237 lagrats som en datatyp vars största representerbara värde är 255. Det är inget fel på varken a eller b, men a + b kan beroende på språkets implementation representera ett tal som inte "får plats" i denna datatyp. Har man tur så konverterar språket automatiskt resultatet till en tillräcklig datatyp (med en viss prestanda/minnesförlust), men troligare är att vi antingen får en krasch, eller som värst helt felaktiga värden utan ens en varning.

Man kan undgå detta genom att inse att:

   (a + b) ∕ 2 = (a − b) ∕ 2 + b = (b − a) ∕ 2 + a

Väljer man den variant av dessa två nykomlingar som beräknar det större talet minus det mindre i täljaren så är beräkningen garanterad att hålla sig inom datatypens gränser i varje steg (i mitt exempel bör jag alltså ta den sista varianten). Eftersom din sortering redan garanterar storleksordningen mellan dina listelement så behöver man inte explicit testa talens storlek. I stället introducerar man ett potentiellt problem med "underflow", ifall a och b är så nära varandra att deras halverade differens trillar bort i flyttalens förlovade värld, så olika situationer kan kräva olika angreppssätt.

Men som sagt: i Python spelar det ingen större roll, då heltal automatiskt konverteras till en datatyp som gör att beräkningens resultat får plats ifall det behövs. Det finns en begränsning i att datorns minne inte kan hantera hur stora heltal som helst vilket den naiva medelvärdesberäkningen skulle kunna trigga, men det ska till rätt exotiska situationer.


Och en sista sak som jag noterar (fast egentligen först) är att du skriver Python 2, vilket det inte finns någon anledning till, förutom just när det finns en anledning till detta (typiskt om man är tvungen att koppla till en äldre kodbas utan Python 3-stöd, vilket bör bli mindre och mindre vanligt med åren). Kör med Python 3 i stället.


Tillägg: Eftersom jag nämnde denna funktion i en parallell tråd så kan jag implementera en ytterligare något förenklad lösning:

def median(sequence): """Sort a copy of the input sequence. Return middle element if the sequence length is odd, or the arithmetic mean of the two mid elements otherwise.""" sorted_ = sorted(sequence) mid_odd_index, is_odd = divmod(len(sequence), 2) if is_odd: return sorted_[mid_odd_index] else: return (sorted_[mid_odd_index - 1] + sorted_[mid_odd_index]) / 2.0

Nu är vi nere på ett enstaka anrop till längdfunktionen, och gillar man mikrooptimering så är divmod snabbare än en division följt av en modulooperation. Negativt med lösningen är att en läsare inte nödvändigtvis vet vad divmod gör, men, tja, det är en av rätt få inbyggda funktioner i Python, så det kanske läsaren får skämmas för .

Nu fungerar koden också direkt i Python 3, men vi kan där förenkla den ytterligare en mikrometer:

def median(sequence): """Sort a copy of the input sequence. Return middle element if the sequence length is odd, or the arithmetic mean of the two mid elements otherwise.""" sorted_ = sorted(sequence) mid_odd_index, is_odd = divmod(len(sequence), 2) if is_odd: return sorted_[mid_odd_index] else: return (sorted_[mid_odd_index - 1] + sorted_[mid_odd_index]) / 2

Ifall man stöter på en skarp situation med en gigantisk mängd mätvärden där man vill hitta medianen effektivt och med ett minimum av oväntade problem så bör man som första instinkt titta på färdiga bibliotekslösningar.

Pythons standardbibliotek erbjuder statistics.median (som dock är implementerad rätt identiskt med sista varianten; se källkoden för CPython), Numpy har numpy.median (källkod), Pandas har pandas.Series.median (källkod (se även kth_smallest)), etc. För just medianberäkningar i Python är det kanske inte extremt kritiskt, men det skadar inte att som reflex fundera på att stå på jättars axlar i liknande fall. Det är tråkigt att behöva lära sig den hårda vägen att den fina och rena matematik man lärt sig inte alltid kommer överens med flyttalsrepresentationer och andra datatypsbegränsningar.

Om man å andra sidan bara vill koda lite för sakens skull, eller snarare jobbar med hundra än hundra miljoner mätvärden så kan man väl få kosta på sig mer kreativa lösningar, i värsta fall .

Tillägg om divmod, bibliotekslösningar, etc.

Nu med kortare användarnamn, men fortfarande bedövande långa inlägg.