Springen naar inhoud

N variabelen met bereik overlopen


  • Log in om te kunnen reageren

#1

jhnbk

    jhnbk


  • >5k berichten
  • 6905 berichten
  • VIP

Geplaatst op 12 januari 2012 - 19:12

Om een analyse te maken van een probleem in functie van een aantal parameters heb ik een volgend situatie:
variabelen: x1, x2, ..., xn
elke variabele heeft een bepaald bereik: S1, S2, ..., Sn

voor elke mogelijke combinatie moet ik nu een functie kunnen berekenen en resultaten weergeven. Ik had volgende oplossing uitgewerkt:

def f(variables,current,index):
	if index<len(variables):
		for i in variables[index]:
			current.append(i)
			f(variables,current,index+1)
			current.pop()
	else:
		print current
#voorbeeld:
v = [range(2),range(2),range(2)]
current =[]

f(v,current,0)

met uitvoer:
[0, 0, 0]
[0, 0, 1]
[0, 1, 0]
[0, 1, 1]
[1, 0, 0]
[1, 0, 1]
[1, 1, 0]
[1, 1, 1]

Nu vraag ik mij af of die altijd werkt en of het eventueel sneller/efficiŽnter/mooier zou kunnen
Het vel van de beer kunnen verkopen vraagt moeite tenzij deze dood voor je neervalt. Die kans is echter klein dus moeten we zelf moeite doen.

Dit forum kan gratis blijven vanwege banners als deze. Door te registeren zal de onderstaande banner overigens verdwijnen.

#2

jhnbk

    jhnbk


  • >5k berichten
  • 6905 berichten
  • VIP

Geplaatst op 12 januari 2012 - 19:44

Ik heb de code intussen eens getest voor een voorbeeld op rosettacode.org:
Verborgen inhoud

max=0
max_comb=[]

problem="""map 	9 	150
compass 	13 	35
water 	153 	200
sandwich 	50 	160
glucose 	15 	60
tin 	68 	45
banana 	27 	60
apple 	39 	40
cheese 	23 	30
beer 	52 	10
suntan cream 	11 	70
camera 	32 	30
T-shirt 	24 	15
trousers 	48 	10
umbrella 	73 	40
waterproof trousers 	42 	70
waterproof overclothes 	43 	75
note-case 	22 	80
sunglasses 	7 	20
towel 	18 	12
socks 	4 	50
book 	30 	10"""
name=[]
weight=[]
value=[]
var=[]

for line in problem.split("\n"):
		a=line.split("\t")
		name.append(a[0])
		weight.append(int(a[1]))
		value.append(int(a[2]))
		var.append(range(2))

def f(variables,current,index):
	global max, max_comb,value,weight
	if index<len(variables):
		for i in variables[index]:
			current.append(i)
			f(variables,current,index+1)
			current.pop()
	else:
		if sum([i*j for i,j in zip(current,weight)])<400:
			m= sum([i*j for i,j in zip(current,value)])
			if m>max:
				max=m
				max_comb = current[:]

c=[]
f(var,c,0)
print "value:",max
print [i for i,j in zip(name,max_comb) if j==1]
print "weight:",sum([i for i,j in zip(weight,max_comb) if j==1])


Werkt dus zeker maar kan naar mijn gedacht kan dit nog sneller of efficiŽnter. Klopt dit? (Uiteraard zijn de voorbeelden sneller aangezien deze vaak onderweg al stoppen met een deel van de zoekboom omdat het maximum gewicht bereikt is. Voor mijn toepassing heb ik wel degelijk voor alle mogelijke combinaties uit het bereik een oplossing nodig.)
Het vel van de beer kunnen verkopen vraagt moeite tenzij deze dood voor je neervalt. Die kans is echter klein dus moeten we zelf moeite doen.

#3

Xenion

    Xenion


  • >1k berichten
  • 2606 berichten
  • Moderator

Geplaatst op 12 januari 2012 - 19:57

Ik ben zelf niet echt bekend met de taal (Python?) en heb je algoritme ook niet helemaal geanalyseerd, maar algemeen is recursie een vrij 'dure' aanpak.

Veel compilers kunnen wel optimaliseren voor tail-recursion. Om je huidige algoritme efficiŽnter te maken zou je de code moeten herschrijven gebruik makend van tail-recursion of een for loop.

Kijk mss hier eens.

#4

EvilBro

    EvilBro


  • >5k berichten
  • 6703 berichten
  • VIP

Geplaatst op 13 januari 2012 - 08:54

Nu vraag ik mij af of die altijd werkt en of het eventueel sneller/efficiŽnter/mooier zou kunnen

Omdat je aangeeft dat je alle mogelijkheden moet testen denk ik niet dat het veel efficienter kan. Hoe je het ook wendt of keert, je zult alle mogelijkheden moeten genereren...

Haskell:
gen [] = [[]]
gen (x:xs) = concat [map (a:) (gen xs) | a <- x]

#5

jhnbk

    jhnbk


  • >5k berichten
  • 6905 berichten
  • VIP

Geplaatst op 13 januari 2012 - 20:03

Uiteraard. Sneller is al om de append/pop er uit te halen.
Het vel van de beer kunnen verkopen vraagt moeite tenzij deze dood voor je neervalt. Die kans is echter klein dus moeten we zelf moeite doen.

#6

jhnbk

    jhnbk


  • >5k berichten
  • 6905 berichten
  • VIP

Geplaatst op 13 januari 2012 - 22:58

@Xenion: taal is inderdaad python.

Uiteindelijk is het dit geworden:

def loopThrough(var,current,index,callable):
	if index<len(var):
		for i in var[index]:
			current[index]=i
			loopThrough(var,current,index+1,callable)
	else:
		callable(current)

Callable zorgt ervoor dat klassen kunnen gebruikt worden om de analyse in te definiŽren:

class Test():
	def __init__(self):
		self.max=0
		self.comb=[]
	def __call__(self,var):
		value = var[0]*3-var[1]*4
		if value>self.max:
			self.max=value
			self.comb = var[:]

t=Test()
loopThrough([range(3),range(3)],[0,0],0,t)
print t.max

Morgen eens kijken hoe ik de recursie er kan uithalen.
Het vel van de beer kunnen verkopen vraagt moeite tenzij deze dood voor je neervalt. Die kans is echter klein dus moeten we zelf moeite doen.

#7

Xenion

    Xenion


  • >1k berichten
  • 2606 berichten
  • Moderator

Geplaatst op 13 januari 2012 - 23:14

Probeer ook eens de if en else van volgorde te wisselen zodat de recursieve call helemaal onderaan in de functie staat.

#8

jhnbk

    jhnbk


  • >5k berichten
  • 6905 berichten
  • VIP

Geplaatst op 14 januari 2012 - 10:57

Vreemd. Dit heeft zeer weinig invloed. Rekentijd is quasi analoog. Soms duurt de ene iets langer, dan weer de andere.
Het vel van de beer kunnen verkopen vraagt moeite tenzij deze dood voor je neervalt. Die kans is echter klein dus moeten we zelf moeite doen.

#9

Xenion

    Xenion


  • >1k berichten
  • 2606 berichten
  • Moderator

Geplaatst op 14 januari 2012 - 11:00

Vreemd. Dit heeft zeer weinig invloed. Rekentijd is quasi analoog. Soms duurt de ene iets langer, dan weer de andere.


Ja het was maar een idee, waarschijnlijk ziet de compiler dezelfde optimalisatiemogelijkheden in beide gevallen. Normaal kan hij dit bij het maken van de machinecode als een for loop implementeren, dus ik denk niet dat je zelf nog veel kan verbeteren.

Zoals EvilBro ook al aangeeft: je output is sowieso al exponentieel tov je input. Dat speelt ook mee.

#10

jhnbk

    jhnbk


  • >5k berichten
  • 6905 berichten
  • VIP

Geplaatst op 14 januari 2012 - 11:13

Met de module Bericht bekijken
Zoals EvilBro ook al aangeeft: je output is sowieso al exponentieel tov je input. Dat speelt ook mee.[/quote]
Daar ben ik mij zeker van bewust. Indien ik ergens kan snoeien voor een bepaalde uitwerking zal ik dat dan ook zeker doen :)
Het vel van de beer kunnen verkopen vraagt moeite tenzij deze dood voor je neervalt. Die kans is echter klein dus moeten we zelf moeite doen.

#11

Xenion

    Xenion


  • >1k berichten
  • 2606 berichten
  • Moderator

Geplaatst op 14 januari 2012 - 12:38

Ah cool, kan je dat ook eens doen voor je code in post 1?

#12

jhnbk

    jhnbk


  • >5k berichten
  • 6905 berichten
  • VIP

Geplaatst op 14 januari 2012 - 14:00

2		   0 LOAD_FAST				2 (index)
			  3 LOAD_GLOBAL			  0 (len)
			  6 LOAD_FAST				0 (variables)
			  9 CALL_FUNCTION			1
			 12 COMPARE_OP			   0 (<)
			 15 POP_JUMP_IF_FALSE	   85

  3		  18 SETUP_LOOP			  69 (to 90)
			 21 LOAD_FAST				0 (variables)
			 24 LOAD_FAST				2 (index)
			 27 BINARY_SUBSCR	   
			 28 GET_ITER			
		>>   29 FOR_ITER				49 (to 81)
			 32 STORE_FAST			   3 (i)

  4		  35 LOAD_FAST				1 (current)
			 38 LOAD_ATTR				1 (append)
			 41 LOAD_FAST				3 (i)
			 44 CALL_FUNCTION			1
			 47 POP_TOP			 

  5		  48 LOAD_GLOBAL			  2 (f)
			 51 LOAD_FAST				0 (variables)
			 54 LOAD_FAST				1 (current)
			 57 LOAD_FAST				2 (index)
			 60 LOAD_CONST			   1 (1)
			 63 BINARY_ADD		  
			 64 CALL_FUNCTION			3
			 67 POP_TOP			 

  6		  68 LOAD_FAST				1 (current)
			 71 LOAD_ATTR				3 (pop)
			 74 CALL_FUNCTION			0
			 77 POP_TOP			 
			 78 JUMP_ABSOLUTE		   29
		>>   81 POP_BLOCK		   
			 82 JUMP_FORWARD			 5 (to 90)

  8	 >>   85 LOAD_FAST				1 (current)
			 88 PRINT_ITEM		  
			 89 PRINT_NEWLINE	   
		>>   90 LOAD_CONST			   0 (None)
			 93 RETURN_VALUE


(Enkel de functie f uiteraard maar wel met print statement ipv callable)
Het vel van de beer kunnen verkopen vraagt moeite tenzij deze dood voor je neervalt. Die kans is echter klein dus moeten we zelf moeite doen.





0 gebruiker(s) lezen dit onderwerp

0 leden, 0 bezoekers, 0 anonieme gebruikers

Ook adverteren op onze website? Lees hier meer!

Gesponsorde vacatures

Vacatures