1 van 1
N variabelen met bereik overlopen
Geplaatst: do 12 jan 2012, 19:12
door jhnbk
Om een analyse te maken van een probleem in functie van een aantal parameters heb ik een volgend situatie:
variabelen: x
1, x
2, ..., x
n
elke variabele heeft een bepaald bereik: S
1, S
2, ..., 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
Re: N variabelen met bereik overlopen
Geplaatst: do 12 jan 2012, 19:44
door jhnbk
Ik heb de code intussen eens getest voor een voorbeeld op
rosettacode.org:
Verborgen inhoudCode: 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.)
Re: N variabelen met bereik overlopen
Geplaatst: do 12 jan 2012, 19:57
door 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.
Re: N variabelen met bereik overlopen
Geplaatst: vr 13 jan 2012, 08:54
door 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]
Re: N variabelen met bereik overlopen
Geplaatst: vr 13 jan 2012, 20:03
door jhnbk
Uiteraard. Sneller is al om de append/pop er uit te halen.
Re: N variabelen met bereik overlopen
Geplaatst: vr 13 jan 2012, 22:58
door 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.
Re: N variabelen met bereik overlopen
Geplaatst: vr 13 jan 2012, 23:14
door Xenion
Probeer ook eens de if en else van volgorde te wisselen zodat de recursieve call helemaal onderaan in de functie staat.
Re: N variabelen met bereik overlopen
Geplaatst: za 14 jan 2012, 10:57
door jhnbk
Vreemd. Dit heeft zeer weinig invloed. Rekentijd is quasi analoog. Soms duurt de ene iets langer, dan weer de andere.
Re: N variabelen met bereik overlopen
Geplaatst: za 14 jan 2012, 11:00
door 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.
Re: N variabelen met bereik overlopen
Geplaatst: za 14 jan 2012, 11:13
door 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
Re: N variabelen met bereik overlopen
Geplaatst: za 14 jan 2012, 12:38
door Xenion
Ah cool, kan je dat ook eens doen voor je code in post 1?
Re: N variabelen met bereik overlopen
Geplaatst: za 14 jan 2012, 14:00
door 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)