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

[FraXinuS]

Her er en rekursiv og en iterativ i python.

nr.1 er raskest med vanlig python 2.7, nr.2 er raskest med pypy.

def qsort1(list):
if not list:
	return []
else:
	pivot = list[0]
	lesser = qsort1([x for x in list[1:] if x < pivot])
	greater = qsort1([x for x in list[1:] if x >= pivot])
	return lesser + [pivot] + greater

def qsort2(seq):
res = []
stack = [seq]
while stack:
	l = stack.pop(-1)
	if not l:
		pass
	elif len(l) == 1:
		res.append(l[0])
	else:
		pivot = l[0]
		stack.extend([[x for x in l[1:] if x >= pivot],
					  [pivot],
					  [x for x in l[1:] if x < pivot]])

return res

[kim009]

Her er en rekursiv og en iterativ i python.

nr.1 er raskest med vanlig python 2.7, nr.2 er raskest med pypy.

def qsort1(list):
if not list:
	return []
else:
	pivot = list[0]
	lesser = qsort1([x for x in list[1:] if x < pivot])
	greater = qsort1([x for x in list[1:] if x >= pivot])
	return lesser + [pivot] + greater

def qsort2(seq):
res = []
stack = [seq]
while stack:
	l = stack.pop(-1)
	if not l:
		pass
	elif len(l) == 1:
		res.append(l[0])
	else:
		pivot = l[0]
		stack.extend([[x for x in l[1:] if x >= pivot],
					  [pivot],
					  [x for x in l[1:] if x < pivot]])

return res

 

Testa du hvor stor forskjell det var på bruk av minne, helst på rimelig lange lister?

[zotbar1234]

Hvorfor det?

 

Fordi du etterlyste et (mot)argument. Quicksort er et skolebokeksempel på det

[zotbar1234]

Her er en rekursiv og en iterativ i python.

nr.1 er raskest med vanlig python 2.7, nr.2 er raskest med pypy.

 

Beklager, men løsningene du foreslår er hårreisende dårlige (selv når vi ser bort fra en dårlig partisjoneringsstrategi) pga nokså frisk mengde kopiering.

 

Poenget var uansett ikke å se en spesifikk implementasjon men å illustrere at det finnes en rekke algoritmer som naturlig fordrer en rekursiv implementasjon. Å skrive en løsning på et slikt problem iterativt vil ikke være spesielt raskt, hverken på implementasjons- eller lesehastighetsnivå.

[etse]

Beklager, men løsningene du foreslår er hårreisende dårlige (selv når vi ser bort fra en dårlig partisjoneringsstrategi) pga nokså frisk mengde kopiering.

 

Poenget var uansett ikke å se en spesifikk implementasjon men å illustrere at det finnes en rekke algoritmer som naturlig fordrer en rekursiv implementasjon. Å skrive en løsning på et slikt problem iterativt vil ikke være spesielt raskt, hverken på implementasjons- eller lesehastighetsnivå.

Men er viktig å få med seg at på assembly-nivå så vil den itterative måten å løse problemet på være cirka lik som den rekursive. Eneste forskjellen er at du ikke bruker den vanlige stancken - men lager en ny stack i heap-memory som du bruker. Ytelsen vil værke tilnærmet det samme om ikke bedre. Og du vil heller ikke ha problemer med stack-overflow på samme måte da du kan allokere mye større heap enn du har stack.

 

Og du ga utfordringen til LonelyMan som er kjent for å løse alt i assembly. Så koden han ville endt opp med ville nok vært nesten helt lik den rekursive.

Endret 22. desember 2012 av etse

[LonelyMan]

Her er en rekursiv og en iterativ i python.

nr.1 er raskest med vanlig python 2.7, nr.2 er raskest med pypy.

def qsort1(list):
if not list:
	return []
else:
	pivot = list[0]
	lesser = qsort1([x for x in list[1:] if x < pivot])
	greater = qsort1([x for x in list[1:] if x >= pivot])
	return lesser + [pivot] + greater

def qsort2(seq):
res = []
stack = [seq]
while stack:
	l = stack.pop(-1)
	if not l:
		pass
	elif len(l) == 1:
		res.append(l[0])
	else:
		pivot = l[0]
		stack.extend([[x for x in l[1:] if x >= pivot],
					  [pivot],
					  [x for x in l[1:] if x < pivot]])

return res

 

Hvor mange elementer sorterer du per sekund?

[GeirGrusom]

Hvor mange elementer sorterer du per sekund?

Irrelevant.

[LonelyMan]

For de av oss som forstår programmering så er det høyst relevant. 1000 sorterte elementer vs 1001 sorterte elementer kan ha årsaker utenom koden.

 

Punkt 2, sorteringsalgoritmer yter ikke jevnt fra små lister til store lister, ytelsen forandrer seg proporsjonalt.

 

Så jo det er høyst relevant. Det er mest sannsynlig riktige resultater, men jeg vil se noen tall for å få et perspektiv over HVOR mye bedre den ene er fra den andre.

Endret 10. januar 2013 av LonelyMan

[GeirGrusom]

For de av oss som forstår programmering så er det høyst relevant. 1000 sorterte elementer vs 1001 sorterte elementer kan ha årsaker utenom koden.

 

Punkt 2, sorteringsalgoritmer yter ikke jevnt fra små lister til store lister, ytelsen forandrer seg proporsjonalt.

 

Så jo det er høyst relevant. Det er mest sannsynlig riktige resultater, men jeg vil se noen tall for å få et perspektiv over HVOR mye bedre den ene er fra den andre.

 

Jeg jobber som IT konsulent. Jeg vet hva som er relevant.

 

Hastighet vil være en del av spesifikasjonen. Hvis det ikke er verdifullt i forhold til spesifikasjonen om den sorterer 1000 eller 1001 så burde man ikke henge seg opp i det.

 

Denne tråden handler om rekursjon, og hvor mange elementer du kan sortere er irrelevant i forhold til hva tråden handler om, som må være spesifikasjonen til denne quicksort implementasjonen.

 

edit: men det går ikke egentlig direkte på bare det du skrev. Jeg var alt for kjapp med å skrive innlegget fordi det var 2 minutter før jeg skulle gå for dagen.

Endret 11. januar 2013 av GeirGrusom

[FraXinuS]

Hvor mange elementer sorterer du per sekund?

De jeg postet er trege, men jeg fant en på nettet som er mye raskere:

def qsort(x, l, r):
i = l
j = r
p = x[l + (r - l) / 2] # pivot element in the middle
while i <= j:
	while x[i] < p: i += 1
	while x[j] > p: j -= 1
	if i <= j: # swap
		x[i], x[j] = x[j], x[i]
		i += 1
		j -= 1
if l < j: # sort left list
	qsort(x, l, j)
if i < r: # sort right list
	qsort(x, i, r)
return x

import os, time
LEN = 1000000
lst = list(bytearray(os.urandom(LEN)))
start = time.time()
qsort(lst, 0, len(lst)-1)
seconds = time.time() - start
print seconds
print LEN / seconds

 

På min maskin:

python2.7:

elementer, pr sekund

1000, ~450000

10000, ~360000

100000, ~290000

1000000, ~240000

 

pypy:

elementer, pr sekund

1000, ~50000

10000, ~170000

100000, ~1000000

1000000, ~2000000

[LonelyMan]

Jeg anbefaler at du bruker QueryPerformanceFrequency og QueryPerformanceCounter, timeGetTime eller andre media timere. time.time har presisjon på 16 millisekunder og fungerer ikke så veldig bra til å måle kode, det er utrolig mye en datamaskin kan gjøre i et 16 ms vakum.

 

Jeg har en assembler modul for å måle kode, om du vil ha den kan du godt få den, den er ganske nøyaktig, så importerer du den bare i python.

 

En annen ting, er om du måler delta tid, så bør du vente til sekundtelleren endrer verdi og ikke begynne midt i en verdi. Om tiden står f.eks på 1.1 og du begynner med en gang, så kan det hende at den egentlig stod på 1.15 (om vi antar den ikke måler presisjon etter 1 tallet)

 

Pseudokoden blir slik:

 

1. Hent tiden og lagre tiden i X

2. Hent tiden kontinuerlig i en loop og lagre i Y. Avslutt loopen når X og Y er forskjellige

3. Lagre den nye tiden i X

4. Kjør rutinen du vil måle

5. Hent tiden og lagre i Y

6. Resultat = Y - X

 

Men så bør du også prefetche rutinen du vil måle, ellers kan resultat i test 2 bli forskjellig fra test 1.

 

Kjør funksjonen du vil måle i en dummy-loop, 10 ganger før du kjører første resultat. Slik som dette:

 

Loop 10

Call Min funksjon

End loop

 

Så begynner du testen her, for nå er funksjonen prefetchet.

Endret 11. januar 2013 av LonelyMan

[GeirGrusom]

Jeg anbefaler at du bruker QueryPerformanceFrequency og QueryPerformanceCounter, timeGetTime eller andre media timere. time.time har presisjon på 16 millisekunder og fungerer ikke så veldig bra til å måle kode, det er utrolig mye en datamaskin kan gjøre i et 16 ms vakum.

 

Jeg har en assembler modul for å måle kode, om du vil ha den kan du godt få den, den er ganske nøyaktig, så importerer du den bare i python.

time.clock() eller timeit.

[LonelyMan]

Hastighet vil være en del av spesifikasjonen. Hvis det ikke er verdifullt i forhold til spesifikasjonen om den sorterer 1000 eller 1001 så burde man ikke henge seg opp i det.

 

Nettopp, og det er derfor jeg ville vite antall per sekund, for om han hadde veldig lav terskel så ville det ikke være noe å henge seg opp i.

 

time.clock() eller timeit.

 

Ikke si det til meg, si det til han andre. Disse funksjonene wrapper tilbake til plattformen's egne metoder, som igjen peker på mine forslag.

 

Denne tråden handler om rekursjon, og hvor mange elementer du kan sortere er irrelevant i forhold til hva tråden handler om, som må være spesifikasjonen til denne quicksort implementasjonen.

 

Inni denne tråden så oppstår det en diskusjon om hastighet ang rekursiv quicksort og iterativ quicksort, vi forbeholder oss retten til å diskutere dette.

[Foxboron]

Inni denne tråden så oppstår det en diskusjon om hastighet ang rekursiv quicksort og iterativ quicksort, vi forbeholder oss retten til å diskutere dette.

 

Som merkelig nok du startet fordi du ikke liker rekursive funksjoner.

[GeirGrusom]

Ikke si det til meg, si det til han andre. Disse funksjonene wrapper tilbake til plattformen's egne metoder, som igjen peker på mine forslag.

Hvilken plattform? Performance timer API-et funker ikke på alle Windows versjoner engang, og eksisterer ikke i andre operativsystemer (med unntak av ReactOS). Hvorfor tar du deg ikke da de par sekundene det tar å google hvordan man måler kode i Python? Det var det jeg gjorde.

[LonelyMan]

Jeg nevnte media timere og timegettime også, i tillegg til performance countere. Det at ikke alle windows versjoner støtter performance countere peker tilbake til at man skal bruke det beste som er tilgjengelig, og derfor jeg nevner alternativer. Jeg behøver ikke bruke google jeg visste om time.clock. Og som alltid så bruker jeg windows som default facto plattform da det er den mest utbredte, om han avveier fra den mest brukte så kan han bruke et alternativ til windows sin performancecounter da den benytter hardware timere, og det har lite å gjøre med windows.

[GeirGrusom]

Jeg behøver ikke bruke google jeg visste om time.clock.

 

Åja. Det er derfor du poster så utrolig mye Pythonkode som viser at du har det minste fnugg med kompetanse i Python.

 

Ikke? Poster du bare forslag om løsning i andre programmeringsspråk enn det tråden handler om, og snakker ut av rumpehullet om iterative mot rekursive algoritmer, og når du blir motsagt, så blir du bare stille og bytter emne, eller forsøkre å vri det sånn at det ser ut som du ikke tok feil?

 

Fasinerende.

[LonelyMan]

Man behøver ikke kunne python for å vite om en funksjon, jeg visste om time.clock fra før, jeg stumpet over den tidligere for noen dager siden. Jeg har ikke blitt motsagt, med unntak av deg og jeg har svart på alle argumentene dine, nå argumenterer du for "google", det tyder på hvor tynne argumentene dine henger nå som du må karre deg til å diskutere google. Da er det lite igjen å diskutere.

[GeirGrusom]

Man behøver ikke kunne python for å vite om en funksjon, jeg visste om time.clock fra før, jeg stumpet over den tidligere for noen dager siden. Jeg har ikke blitt motsagt, med unntak av deg og jeg har svart på alle argumentene dine, nå argumenterer du for "google", det tyder på hvor tynne argumentene dine henger nå som du må karre deg til å diskutere google. Da er det lite igjen å diskutere.

Jeg brukte google for å sjekke om det var fornuftig å bruke en assemblymodul for timing av kode i Python, det var det derimot ikke. Dette fant jeg ut i løpet av sekunder. Python har allerede et bibliotek som heter timeit for å gjøre dette. Dersom den kommentaren om å bruke assembly for å time hadde gått igjennom, så hadde alle tapt på det, fordi det er en idiotisk løsning på et åpenbart trivielt problem.

 

Jeg har forklart hvorfor dette er dustete: det finnes python bibliotek for å gjøre det, og det å skrive det i 32-bit x86 assembly gjør at den ikke kan flyttes mellom hverken operativsystem eller prosessorer, noe som er temmelig idiotisk for et scriptspråk.

[LonelyMan]

Dette er et diskusjonsforum hvor vi diskuterer erfaringer, dette er ikke en extension for google hvor du får et spørsmål og så google opp et svar. Det er hele meningen med diskusjonsforum at man gir svar på det man kan, det er ikke slik at A: man får et spørsmål fra venstre side, B: Man strekker høyre hånden ut til google, søker etter svar, C: Legger ut svaret på forumet. Du har misforstått hele poenget med diskusjonsforum. Problemet når man skal diskutere gjennom google er at man da aldri kan være helt sikker på hva man snakker om. Om du vet noe, svar tilbake, om du ikke vet, så er det best å gå videre til neste tråd for da kan man aldri være helt sikker på hva man skriver, og jeg ser gang på gang at du ikke vet hva du snakker om. Jeg husker du var i assembler forumet og skulle gi hint om GetASyncKeyState, da måtte jeg korrektere deg kraftig og du hadde googlet det opp på msdn og lest halve artikkelen, men glemte å lese type defiinisjonen på funksjonen. Det er et godt eksempel på hvorfor google-diskusjoner ikke fungerer, kan du noe så skriv gjerne, må du google det opp så bare gå til neste tråd.

 

Det biblioteket mitt var bare et forslag for å få en noenlunde god tidsmåling i quicksort eksemplet vi brukte, ikke for å gjenbrukes, men nå har jeg faktisk skrevet det for å være portabelt mellom ganske mange plattformer så det går likevel an å gjenbruke det om det skulle vært et mål. Du tenker altfor prinsippielt og er ikke løsningsorientert.

 

Slik som når du skrev det dumme argumentet om at tidsmåling var irrelevant, så begrunner jeg klart og tydelig hvorfor det er relevant, så begrunner du det tilbake med at du er it konsulent, dette er dårlig argumentering.