Python noob - forskjell på rekursiv og non-rekursiv funksjon

[Foxboron]

Jeg har skrevet det i assembler så du vil antakeligvis ikke forstå det,

 

Nå synes jeg det blir dumt å gjøre antagelser på hva folk vet og ikke vet.

 

Du kan gjerne åpne olly eller en debugger du har og verifisere at c++ genererer lik overhead.

 

Skulle jeg gjerne ha gjort, men igjen, ingen kode.

[kim009]

Er vel hovedsakelig snakk om Python her, i og med at det står "Python noob" i overskriften, en mer generell diskusjon burde vel bli flyttet ut i en annen tråd? Sammenligninger burde vel derfor også bli kjørt i Python om de skal i denne tråden?

[LonelyMan]

Nå synes jeg det blir dumt å gjøre antagelser på hva folk vet og ikke vet.

 

Jeg gjør aldri antakelser, jeg leser hva folk skriver, og så dømmer jeg ut ifra det. Jeg har lagt frem haugevis med argumenter, og har ikke fått et eneste mot argument ennå. Jeg kan legge frem omtrent en like stor haug med nye argumenter som er enda mer tekniske, men sålangt så ser jeg ikke noe poeng i det, da ingen motargumenter eksisterer, og da trådstarter er i klagemodus allerede.

 

Trådstarter, nå opererer python med bytekoder så det er egentlig ikke så veldig stort poeng å snakke om optimalisering på mikronivå uansett

[tomsi42]

@LonelyMan - det har ikke slått deg at det er ingen som gidder å høre på deg, og har gått videre, istedet for å argumentere mot deg?

[LonelyMan]

Jeg registrerer at du henger her og slenger anti-diskusjon bemerkninger, vi driter i hva du sier, dette er diskusjon.no, om du er en smukk, så stikk avgårde.

[tomsi42]

Jeg registrerer at du henger her og slenger anti-diskusjon bemerkninger, vi driter i hva du sier, dette er diskusjon.no, om du er en smukk, så stikk avgårde.

Det må du gjerne, men du bør jo kanskje reflektere litt over hvordan du fremstår i denne tråden.

• Trådstarter spør om en kodesnutt er rekursjon eller ikke.
  
• Trådstarter spesifikt snakker om python som h*n er noob i.
  
• Trådstarter får et svar fra meg og to andre som sier noe om python og rekursjon.
  
• Så kommer du med et svar der du kategorisk avviser rekursjon, og legger til noen tanker rundt implementasjon som helt tydelig ikke er python-basert; jeg mistenker assembler.
  

Vår feil var jo å bli med på den galeien og avspore tråden helt.

[LonelyMan]

Jeg var den første til å ta hintet av trådstarter etter en ivrig men litt unyansert diskusjon av mange deltakere. Jeg var den første til å anerkjenne, etter hans etterspørsel. Men du fortsetter.

 

Og når det gjelder assembler, ingen diskuterer assembler, vi diskuterer hardwaren og det er noe annet. Det stemmer at jeg laget et eksempel i assembler, men hallo? Du kommer ikke utenom assembler om du skal se på hva som er teknisk mulig å gjøre, du er nødt å involvere assembler og hardware. Det har seg slik at alle programmer bygger på maskinspråk, det er ikke slik at maskinen din spiser bytekoder, den spiser µops, ikke byte koder, det er nyttesløst å snakke om teknisk optimalisering uten å snakke maskinvare eller maskinspråk. Men nå lar vi trådstarter få drive denne tråden til sitt eget bruk

Endret 19. desember 2012 av LonelyMan

[snippsat]

Vår feil var jo å bli med på den galeien og avspore tråden helt.

Ja lett og avspore litt,jeg tok litt om tanken bak hvorfor man gjør mye rekursivt i funksjonelle språk.

Dette er vel kanskje ikke så nyttig for TS.

Jeg er hverken motstander eller fan av rekursjon,@LonelyMan har vel fått frem mange sider hvorfor han ikke liker rekursjon

 

Jeg synes dette svaret er greit.

Loops may achieve a performance gain for your computer.

Recursion may achieve a performance gain for your programmer.

Choose which is more important in your situation!

 

det er nyttesløst å snakke om teknisk optimalisering uten å snakke maskinvare eller maskinspråk

Ikke for og spore av igjen,men ikke helt enig i det.

Man kan snakke om optimalisering i koden(algoritmer) uten og snakke om hvordan dette blir løst på laveste nivå(maskinspråk).

 

I Python som jeg bruker en del er man skjermet fra mye av det som foregår på laveste nivå.

Dette syens jeg er helt greit,det betyr ikke at jeg ikke er opptatt av optimaliseringk(jeg kjørere benchmark tester på alt muilg).

Nå vil jo alltid assembler vinne alle slike benchmark tester,men som vi vet er koden lang og lite gøy og lese for mennesker.

 

Noen kloke ord av @Donald Knuth,som man ofte glemmer i jaget etter optimalisering.

We should forget about small efficiencies, say about 97% of the time:

premature optimization is the root of all evil.

Yet we should not pass up our opportunities in that critical 3%."

[LonelyMan]

Den blir endel lengre ja, men helt ærlig, det er en vanesak, jeg har kodet delphi/pascal i mange år, og det er omtrent et av de simpleste språk som er, og jeg kan med fingrene i kryss si at jeg ikke synes assembler er noe tyngre, det er fordi alt blir en vane. Jeg kan se på en assembler rutine som er 30 linjer lang, og løse problemer i den (ja omtrent) ved samme hastighet som å løse den i delphi f.eks. Det er som sagt en vanesak. Om du snakker med en biologiprofessor, og lytter til alle detaljene han eller hun snakker om, så vil det høres ut som om de må ha sittet i en hel uke å forberedt det de snakker om, men det glir bare ut av munnen fordi det er en vane og de forstår det og er trygg på det. Assembler vil alltid være vanskelig, tidssløsende for de som ikke er vant til det. Det er helt korrekt. Selvfølgelig er det tidsløsende når du må jobbe med noe du ikke er vant med, det er som sagt, helt korrekt. Men hva skjer når du er vant og komfortabel med noe? Ta for deg en som aldri har kodet assembler, han ser på en 30 linjer kode og sier "HerreGud, er det mulig". Og så tar vi en som er vant med assembler, når han ser på den samme koden så sier han "Aha, 5 linjer er relevante, resten er overhead, så simpelt"... Alt bunner ned til dette, ikke bare med asm, det gjelder alle språk.

 

Og så når denne som aldri har kodet asm ser dette, så går han ut på forum og så sier han til alle, "Du må aldri finne på å kode assembler, hvem koder egentlig assembler, herregud, det er jo helt og uimotståelig mye tidsløsing

 

Men sannheten er jo at han ikke forstår noenting, og alt han vet om det er feil.

Endret 20. desember 2012 av LonelyMan

[LonelyMan]

SNIPPSAT, siden vi allerede diskuterer, så kan vi vel diskutere litt til.

 

Apropos dette:

We should forget about small efficiencies, say about 97% of the time:

premature optimization is the root of all evil.

Yet we should not pass up our opportunities in that critical 3%."

 

Om han peker til assembler her ang. "small efficiencies", så vil jeg si at han tar feil. Du kan gjøre veldig små forandringer og få store forbedringer, og ofte så er det tilfellet. Han har et usunt forhold til maskinspråk og jeg er fristet til å si at alt han vet er basert på rykter som er halvsanne.

 

Når det gjelder "premature optimization", ikke for å være vrang her, jeg er stygt uenig. Årsaken til at prosjekter forkastes er nettopp fordi de er likegyldige i begynnelsen av et prosjekt og når det kommer til optimaliseringsfasen så er det så mye som er så dårlig kodet at de bestemmer seg for å forkaste alt sammen. Jeg mener man burde tenke layout fra begynnelsen av, potensialet for optimalisering avhenger av layout. Man burde planlegge optimalisering fra begynnelsen av.

Endret 20. desember 2012 av LonelyMan

[tomsi42]

Den blir endel lengre ja, men helt ærlig, det er en vanesak, jeg har kodet delphi/pascal i mange år, og det er omtrent et av de simpleste språk som er, og jeg kan med fingrene i kryss si at jeg ikke synes assembler er noe tyngre, det er fordi alt blir en vane. Jeg kan se på en assembler rutine som er 30 linjer lang, og løse problemer i den (ja omtrent) ved samme hastighet som å løse den i delphi f.eks. Det er som sagt en vanesak.

Jeg tror alle finner et språk som de føler seg ekstra godt hjemme i - for min del er det faktisk Delphi utgaven av objektorientert pascal. Men jeg har programmert i en god del andre språk også (assembler, C, C++, Java, Perl, Python, Tcl osv). Og du kan nok ha rett i at alt kan bli en vanesak.

 

Men det er ikke det samme som at alle språk er egnet til alle oppgaver. Kan det være at assembler passer veldig godt til de oppgavene du skal løse? Jeg får gjort mye mer på 30 linjer med Delphi enn med 30 linje assembler, men det er fordi jeg er interessert i fancy brukergrensesnitt og SQL databaser.

 

Om du snakker med en biologiprofessor, og lytter til alle detaljene han eller hun snakker om, så vil det høres ut som om de må ha sittet i en hel uke å forberedt det de snakker om, men det glir bare ut av munnen fordi det er en vane og de forstår det og er trygg på det. Assembler vil alltid være vanskelig, tidssløsende for de som ikke er vant til det. Det er helt korrekt. Selvfølgelig er det tidsløsende når du må jobbe med noe du ikke er vant med, det er som sagt, helt korrekt. Men hva skjer når du er vant og komfortabel med noe? Ta for deg en som aldri har kodet assembler, han ser på en 30 linjer kode og sier "HerreGud, er det mulig". Og så tar vi en som er vant med assembler, når han ser på den samme koden så sier han "Aha, 5 linjer er relevante, resten er overhead, så simpelt"... Alt bunner ned til dette, ikke bare med asm, det gjelder alle språk.

Men problemet går jo andre veien også - er man ekspert i et domene så ser man oftest løsninger på andre domener ut ifra eget ståsted; løsninger som ikke nødvendigvis er optimale ...

 

Og så når denne som aldri har kodet asm ser dette, så går han ut på forum og så sier han til alle, "Du må aldri finne på å kode assembler, hvem koder egentlig assembler, herregud, det er jo helt og uimotståelig mye tidsløsing

 

Men sannheten er jo at han ikke forstår noenting, og alt han vet om det er feil.

Sannheten er vel det at assembler er et rimelig domenespesifikt språk som er for tungvindt til å løse mange av de programmeringsoppgavene som finnes der ute i dag. Det er en grunn til at vi har høynivå-språk.

[tomsi42]

Når det gjelder "premature optimization", ikke for å være vrang her, jeg er stygt uenig. Årsaken til at prosjekter forkastes er nettopp fordi de er likegyldige i begynnelsen av et prosjekt og når det kommer til optimaliseringsfasen så er det så mye som er så dårlig kodet at de bestemmer seg for å forkaste alt sammen. Jeg mener man burde tenke layout fra begynnelsen av, potensialet for optimalisering avhenger av layout. Man burde planlegge optimalisering fra begynnelsen av.

Jeg tror ikke det mangelen på tanken om "premature optimization" som er problemet at mange prosjekter strander. Det er heller andre ting som er årsaken, en av de er du er inne på - dårlig koding. Er litt usikker på hva du tenker på når du sier "mangel på layout"; hvis du sikter til at man ikke bygger opp koden strukturert i moduler, så er jeg enig i at det også er en faktor. Men dette er som oftest forårsaket av manglende forståelse for programmeringsverktøyene man har, og til tider manglene forståelse for programmering.

 

Men allikevel er ikke dette som er hovedårsakene til at prosjekter strander; viktigere årsaker er mangelfull kravspesifikasjon, endring av krav underveis, bruk av feil verktøy og manglende ressurser.

[LonelyMan]

Sannheten er vel det at assembler er et rimelig domenespesifikt språk som er for tungvindt til å løse mange av de programmeringsoppgavene som finnes der ute i dag. Det er en grunn til at vi har høynivå-språk.

 

Ja det er sant, men der hvor jeg aldri kommer til å forlate asm, er muligheten for å skrive viktige og kritiske rutiner i separate dll'er og så bruke de i hvilket som helst språk, helt uvurderlig, å bare knatre en del av høynivå koden, kode den delen i asm, og importere det. Helt uvurderlig mtp optimalisering. Når det er snakk om f.eks en veldig kritisk loop, så lager jeg bare det i en dll og så kan det gjenbrukes i alle språk. Og det tar ikke mye effort å gjøre det kompatibelt over plattformer og prosessorer. Men nå er det litt dumt å diskutere asm i en python tråd, python er så langt unna asm som det går an å komme.

[tomsi42]

Men nå er det litt dumt å diskutere asm i en python tråd, python er så langt unna asm som det går an å komme.

Sant nok.

Endret 20. desember 2012 av tomsi42

[snippsat]

Men nå er det litt dumt å diskutere asm i en python tråd, python er så langt unna asm som det går an å komme.

Ja og det er greit,det finnes måter til og få Python til og få mye større fart enkelt som PyPy.

PyPy er veldig bra prosjekt og i enkelte tilfeller har man kjørt kode i Python(PyPy) ned mot C kode sin fart.

Her kan man være litt slapp og la PyPy gjengen ta seg av optimalisering

 

Ettersom posten handler om rekursjon,kan jeg ta en liten demo med Fibonacci nummer.

Dette den vanlige fib rekursive koden,som er veldig lite effektivt og har O(2n) i tid.

import timeit

def fib(n):
if n == 0 or n == 1:
	return 1
return fib(n-1) + fib(n-2)

print timeit.Timer("fib(40)",'from __main__ import fib').timeit(number=1)

Kjører same kode først i Python deretter PyPy.

C:\pypy>python time_fib.py
40.8018933924

C:\pypy>pypy-c time_fib.py
4.69886514624

Får en grei 10x speedUp.

 

Viss noen er interessert vite litt mere om PyPy er denne

med David Beazley bra og artig. Endret 20. desember 2012 av SNIPPSAT

[zotbar1234]

Jeg har lagt frem haugevis med argumenter, og har ikke fått et eneste mot argument ennå.

 

Kunne du skrive en iterativ quicksort?

[LonelyMan]

Jeg har skrevet en rekursiv quicksort, og den er ganske rask som den er, jeg er ingen motstander av rekursive kall, men jeg tror jeg kunne gjort den om til en ren iterativ quicksort. For hver gang man fragmenterer en linje med data så dobler fragmentene seg og du vet antall counts du skal øke, så det er fullt mulig.

 

Mitt syn på rekursive kall er at man bør bruke de på rutiner som man ikke kommer til å gjenbruke så ofte, rutiner man vil gjenbruke og som blir del av et bibliotek bør man gjøre det beste med det, og styre unna latskap. Eller man bør styre unna rekursive kall hvis programmet handler utelukkende om den delen rekursive kall berører, f.eks i et sorteringsprogram vil du ikke gjøre annet enn å sortere, da ville jeg laget en rask sorteringsfunksjon istedet for å ta det lette valget.

Endret 21. desember 2012 av LonelyMan

[zotbar1234]

Jeg har skrevet en rekursiv quicksort, og den er ganske rask som den er, jeg er ingen motstander av rekursive kall, men jeg tror jeg kunne gjort den om til en ren iterativ quicksort.

 

Igjen, kunne du presentere en iterativ quicksort?

[LonelyMan]

Hvorfor det? Jeg er opptatt nå, kan ikke drive prosjekt oppdrag bare fordi du vil ha det.

 

Jeg mener det er bedre at, om du mener å ha et poeng bak det hele, så er det bedre å legge frem dette poenget slik at det kan diskuteres, det er en mye bedre fremgangsmåte enn å spørre tilfeldige personer om de kan lage quicksort rutiner for deg.

Endret 21. desember 2012 av LonelyMan

[etse]

Igjen, kunne du presentere en iterativ quicksort?

Man kan fint skrive en iterativ quicksort. "Alle rekursive problemer kan løses med en while-loop og en stack".

 

Et eksempel på iterativ implementasjon av quicksort: http://www.softwareandfinance.com/CSharp/QuickSort_Iterative.html

 

Men nå finnes det jo helt klart bedre metoder enn der der å sortere elementer på iterativt.