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 Så ska Louqe få tillbaka chassiälskarna 1
- Igår Nanosys: QDEL-tekniken potentiellt redo för kommersiell lansering 2026 23
- Igår Ny Arc-drivrutin ger kraftigt höjd DX11-prestanda i många spel 18
- 21 / 4 Världens minsta fungerande Nintendo Wii-konsol avtäckt 6
- 21 / 4 Legendarisk processor pensioneras efter 49 år 17
Mjukvara
Övrigt
- Igår Europol ställer sig emot end-to-end-kryptering 100
- Igår Svenska speljätten Embracer splittras – blir tre separata bolag 12
- Igår Snabbkoll: Brukar du handla begagnad teknik? 84
- Igår Akira har tjänat en halv miljard kronor på ransomware-attacker 13
- 21 / 4 Gamers Nexus: EK Water Blocks har problem 32
Datorkomponenter
Ljud, bild och kommunikation
- Europol ställer sig emot end-to-end-kryptering100
- Dagens fynd — Diskussionstråden49463
- Enklare installera Windows-program från webben10
- Nanosys: QDEL-tekniken potentiellt redo för kommersiell lansering 202623
- Elbilar - Tråden för intresserade23173
- MacOS till Synology över Lan är ostabilt. Vad kan detta bero på?10
- LLama3 eller "Hur kan en språkmodell stapla saker?"28
- Blåskärm och andra krascher12
- Vänta på paket-tråden!4332
- Tråden om PlayStation 514550
- Säljes LG Ultragear 32" 1440p 180Hz Nano IPS (32GP850)
- Köpes grafikkort köpes, gärna frankensteinade kort eller utan fläkt
- Säljes Asus GeForce RTX 2080 ROG Strix Gaming OC 8GB
- Köpes Köpes - i7 4770-4790(K)
- Säljes Steam Deck 1 TB OLED Oöppnad/Nyskick
- Säljes Asus Rog Helious GX601 + 4st Corsair LL120 fläktar
- Köpes Pulsar X2 Mini Wireless Gamingmus - Rotobox
- Säljes Asus RTX 1060 ROG Strix OC 6GB
- Köpes 28-32" 4K 144-190 hz Gsync & Freesync
- Säljes KFA2 GeForce RTX 4070 Ti EX Gamer (1 Click-OC)
- Så ska Louqe få tillbaka chassiälskarna1
- Enklare installera Windows-program från webben10
- Nanosys: QDEL-tekniken potentiellt redo för kommersiell lansering 202623
- Europol ställer sig emot end-to-end-kryptering100
- Svenska speljätten Embracer splittras – blir tre separata bolag12
- Snabbkoll: Brukar du handla begagnad teknik?84
- Akira har tjänat en halv miljard kronor på ransomware-attacker13
- Valve uppdaterar Team Fortress 2 med 64‑bitarsstöd21
- Ny Arc-drivrutin ger kraftigt höjd DX11-prestanda i många spel18
- Världens minsta fungerande Nintendo Wii-konsol avtäckt6