N variabelen met bereik overlopen

[jhnbk]

Om een analyse te maken van een probleem in functie van een aantal parameters heb ik een volgend situatie:

variabelen: x₁, x₂, ..., x_n

elke variabele heeft een bepaald bereik: S₁, S₂, ..., S_n

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

[jhnbk]

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

[Xenion]

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.

[EvilBro]

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]

[jhnbk]

Uiteraard. Sneller is al om de append/pop er uit te halen.

[jhnbk]

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

[Xenion]

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

[jhnbk]

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

[Xenion]

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.

[jhnbk]

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

[Xenion]

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

[jhnbk]

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)