N variabelen met bereik overlopen

Moderators: jkien, Xilvo

Reageer

Bericht 12-01-'12, 19:12

jhnbk

Gebruikersavatar
Berichten: 6.905

N variabelen met bereik overlopen

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:

Code: Selecteer alles

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.
Omhoog

Bericht 12-01-'12, 19:44

jhnbk

Gebruikersavatar
Berichten: 6.905

Re: N variabelen met bereik overlopen

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

Verborgen inhoud

Code: Selecteer alles

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.
Omhoog

Bericht 12-01-'12, 19:57

Xenion

Gebruikersavatar
Berichten: 2.609

Re: N variabelen met bereik overlopen

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.
Omhoog

Bericht 13-01-'12, 08:54

EvilBro

Berichten: 7.068

Re: N variabelen met bereik overlopen

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:

Code: Selecteer alles

gen [] = [[]]

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

Bericht 13-01-'12, 20:03

jhnbk

Gebruikersavatar
Berichten: 6.905

Re: N variabelen met bereik overlopen

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.
Omhoog

Bericht 13-01-'12, 22:58

jhnbk

Gebruikersavatar
Berichten: 6.905

Re: N variabelen met bereik overlopen

@Xenion: taal is inderdaad python.

Uiteindelijk is het dit geworden:

Code: Selecteer alles

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:

Code: Selecteer alles

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.
Omhoog

Bericht 13-01-'12, 23:14

Xenion

Gebruikersavatar
Berichten: 2.609

Re: N variabelen met bereik overlopen

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

Bericht 14-01-'12, 10:57

jhnbk

Gebruikersavatar
Berichten: 6.905

Re: N variabelen met bereik overlopen

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.
Omhoog

Bericht 14-01-'12, 11:00

Xenion

Gebruikersavatar
Berichten: 2.609

Re: N variabelen met bereik overlopen

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.
Omhoog

Bericht 14-01-'12, 11:13

jhnbk

Gebruikersavatar
Berichten: 6.905

Re: N variabelen met bereik overlopen

Met de module
Zoals EvilBro ook al aangeeft: je output is sowieso al exponentieel tov je input. Dat speelt ook mee.
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.
Omhoog

Bericht 14-01-'12, 12:38

Xenion

Gebruikersavatar
Berichten: 2.609

Re: N variabelen met bereik overlopen

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

Bericht 14-01-'12, 14:00

jhnbk

Gebruikersavatar
Berichten: 6.905

Re: N variabelen met bereik overlopen

Code: Selecteer alles

  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.
Omhoog
Reageer

Terug naar “Informatica en programmeren”