Ryzen 3600 | ASUS X470-F | 16GB B-die | GTX 1070
[Python] Noob behöver hjälp med optimering av kod till uppgift
Senast redigerat
Visa signatur
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]
Visa signatur
Ryzen 3600 | ASUS X470-F | 16GB B-die | GTX 1070
Citera flera
Citera
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.
Visa signatur
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]
Citera flera
Citera
(2)
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.
Visa signatur
Ryzen 3600 | ASUS X470-F | 16GB B-die | GTX 1070
Citera flera
Citera
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]
ordered = sorted(sequence)
mid_odd_index = len(ordered) / 2
if length % 2 != 0:
median_odd = ordered[mid_odd_index]
return median_odd
else:
median_even = (ordered[mid_odd_index - 1] + ordered[mid_odd_index]) / 2.0
return median_even
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 ä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.
Jag passade på att flytta in tilldelningen av median_odd
till grenen där den returneras, då det är onödigt att tilldela en variabel som vi ändå bara kastar om vi landar i else
-grenen.
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)
ordered = sorted(sequence)
mid_odd_index = len(ordered) / 2
if length % 2 != 0:
median_odd = ordered[mid_odd_index]
return median_odd
else:
median_even = (ordered[mid_odd_index - 1] + ordered[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 lagrat 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, men däremot vet jag att min variabel ordered
är just en lista, med snabb längduppslagning.
Jag kan också passa på att generalisera funktionen ännu mer: jag behöver egentligen inte ens indata som har en fastställd längd, utan vilken "iterabel" (något som går att iterera över) som helst fungerar, så länge den har finit längd.
def median(iterable):
ordered = sorted(iterable)
mid_odd_index = len(ordered) / 2
if len(ordered) % 2 != 0:
median_odd = ordered[mid_odd_index]
return median_odd
median_even = (ordered[mid_odd_index - 1] + ordered[mid_odd_index]) / 2.0
return median_even
I viss analogi med "tidigt avslut" så kan man också skippa else
-satsen och tjäna en indenteringsnivå på sista raderna utan att ändra logiken det minsta.
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. Här tar jag mig friheten att inte gå in i detalj vad "median" betyder eftersom det är ett så vedertaget begrepp, så jag nöjer mig med:
def median(iterable):
"""Return median of iterable."""
ordered = sorted(iterable)
mid_odd_index = len(ordered) / 2
if len(ordered) % 2 != 0:
return ordered[mid_odd_index]
return (ordered[mid_odd_index - 1] + ordered[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(iterable):
"""Return median of iterable."""
ordered = sorted(iterable)
mid_odd_index = len(ordered) / 2
if len(ordered) % 2:
return ordered[mid_odd_index]
return (ordered[mid_odd_index - 1] + ordered[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(iterable):
"""Return median of iterable."""
ordered = sorted(iterable)
mid_odd_index, is_odd = divmod(len(ordered), 2)
if is_odd:
return ordered[mid_odd_index]
return (ordered[mid_odd_index - 1] + ordered[mid_odd_index]) / 2.0
Nu är vi nere på ett enstaka anrop till längdfunktionen, och gillar man mikrooptimering så har divmod
åtminstone potential att vara snabbare än en division följt av en modulooperation, beroende på kompilatoroptimeringar (i Python-fallet kan man med fördel mäta med timeit
-modulen, vilket ger resultatet att det i CPython spelar absolut noll roll vilken av lösningarna man väljer i prestandasyfte). 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 då divisionoperatorn ger flyttal som standard (PEP 238):
def median(iterable):
"""Return median of iterable."""
ordered = sorted(iterable)
mid_odd_index, is_odd = divmod(len(ordered), 2)
if is_odd:
return ordered[mid_odd_index]
return (ordered[mid_odd_index - 1] + ordered[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 ävenkth_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 .
Senast redigerat
Hittade inlägget igen efter några år. Adderar PEP 238-länk, nämner `timeit`-modulen.
Visa signatur
Nu med kortare användarnamn, men fortfarande bedövande långa inlägg.
Citera flera
Citera
(3)
Hårdvara
- Idag Intel skyller Raptor Lake-krascher på moderkortstillverkare 26
- Idag TSMC utvecklar enorma kretsar med effekt mätt i kilowatt 11
- Idag Så mycket långsammare blir Intels värstingkretsar med ”Intel Baseline” i BIOS 51
- 26 / 4 Corsair Platform 6: För dig som inte nöjer dig med Ikea-skrivbord 11
- 26 / 4 Rykte: Switch 2 släpps i höst – OLED-variant dröjer 51
Mjukvara
Övrigt
- Idag Google nöjda med annonsexperiment: Youtube kan få pausreklam 16
- Igår Övergivet skadeprogram infekterar miljontals maskiner 17
- Igår Helgsnack: Är all reklam till ondo? 85
- 26 / 4 NetonNet varnar om läckta kunduppgifter 23
- 26 / 4 Premiär på SweClockers! Månadens drop med gamingskärm hos Elgiganten 74
Datorkomponenter
Ljud, bild och kommunikation
- Blåskärm och andra krascher14
- Upgraderade till win 11 men nu funkar inte mitt raidkort.2
- Rengöra skärm.7
- Veckans fråga: Hur mycket lagringsutrymme har din dator?113
- Blandade VR-nyheter1575
- Intel skyller Raptor Lake-krascher på moderkortstillverkare26
- Rykte: Switch 2 släpps i höst – OLED-variant dröjer51
- Elbilar - Tråden för intresserade23199
- Värderingshjälp stationär dator1
- Konsol åt 10-åring11
- Säljes Elgato Wave 3 mikrofon
- Säljes TC-Helicon GoXLR Mini
- Säljes Komplett dator, 2700x, GTX 1070
- Säljes Vårstädning - i5-6600, GA-H170N-WIFI, 2x8GB DDR4, GTX 760, Noctua NH-U12S, FD Tesla 650W
- Köpes Uppgraderingspaket am4/am5/lga1700, ssd, gpu
- Säljes Flertal sata SSD'er 480GB-2TB
- Säljes Playstation 5 Digital 825gb
- Köpes Billig / gratis moderkort & cpu sökes till behövande pojk!
- Säljes ASUS ROG Ally 512GB + väska Ny oöpnad
- Säljes CaseLabs SMA8 (Gigantiskt sällsynt datorchassi)
- Google nöjda med annonsexperiment: Youtube kan få pausreklam16
- Intel skyller Raptor Lake-krascher på moderkortstillverkare26
- TSMC utvecklar enorma kretsar med effekt mätt i kilowatt11
- Så mycket långsammare blir Intels värstingkretsar med ”Intel Baseline” i BIOS51
- Stöd för komprimering i fler format på gång till Windows19
- Krönika: "Early access" är utstuderad girighet46
- Övergivet skadeprogram infekterar miljontals maskiner17
- Helgsnack: Är all reklam till ondo?85
- Microsoft släpper källkoden till MS‑DOS 4.0020
- Ny caps lock-symbol i Windows förbryllar HP-användare21
Externa nyheter
Spelnyheter från FZ
- Dragon’s Dogma 2 har sålt så bra att Capcom betalar ut mer pengar till aktieägarna idag
- Silent Hill 2 – Snart avslöjas släppdatum och till vilka plattformar det släpps idag
- River City Girls 2 gästas av Double Dragon i sommar idag
- Sand Land delar en sista hälsning från Akira Toriyama igår
- Alien: Rogue Incursion släpps till VR senare i år igår