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
- Igår Nvidia släpper uppdaterad programvara med automatisk överklockning 12
- Igår Musmatta med trådlös laddning från Zagg – Dålig på det mesta 6
- 5 / 6 Seasonic samarbetar med Noctua på specialaggregat 29
- 5 / 6 Duellen: Premium-kylare vs. budgetfavorit 24
- 5 / 6 Apple uppgav fel antal kärnor för Ipad Airs gpu 19
Mjukvara
Datorkomponenter
Ljud, bild och kommunikation
- Hur ska man tänka kring tjänstetelefon30
- Nvidia släpper uppdaterad programvara med automatisk överklockning12
- Fanboy-quiz: Vad kan du om Microsoft?67
- Utomhushögtalare, 4 högtalare från en surroundförstärkare, kablar13
- Hjälp mig, GPU fungerar ej i PCIE slot 14
- Radeon 7900gre5
- Intel visar Lunar Lake – "den mest effektiva arkitekturen någonsin"111
- Sämre uppkoppling över ethernet än över Wifi3
- Byta grafikkort i en Laptop.12
- RTX 3080 lamporna slocknat0
- Säljes Komplett gamingdator
- Köpes Grafikkort för 3000-4000 sökes.
- Säljes Steam Deck OLED 1 TB
- Säljes Epos H3 Hybrid Wireless + Epos GSX 300 DAC
- Säljes Dell Precision 5820
- Säljes Logitech G560 halva nypriset
- Säljes MSI B550M PRO-VDH WIFI Defekt?
- Säljes SteelSeries Apex 7 Blue Switch
- Köpes Söker gamingdator till sonen
- Säljes Fractal Design Torrent TG x EKWB Quantum radiator
- Nvidia släpper uppdaterad programvara med automatisk överklockning12
- Musmatta med trådlös laddning från Zagg – Dålig på det mesta6
- Falska VPN-program spred skadlig kod i botnät under tio års tid8
- Fanboy-quiz: Vad kan du om Microsoft?67
- Enkelt knep öppnar gamla Utforskaren i Windows 1118
- Microsoft återstartar Windows 10-betatester27
- Seasonic samarbetar med Noctua på specialaggregat29
- Duellen: Premium-kylare vs. budgetfavorit24
- Apple uppgav fel antal kärnor för Ipad Airs gpu19
- Fractal visar upp stilrena stolar och hörlurar24