Welcome to the Monastery PerlMonks

### Re^2: Evolving a faster filter? (combinatorics)

by LanX (Chancellor)
 on Jan 04, 2013 at 17:03 UTC ( #1011682=note: print w/replies, xml ) Need Help??

in reply to Re: Evolving a faster filter?
in thread Evolving a faster filter?

> record their performance in previous runs and you sort them accordingly.

OK some theoretical thoughts of how to sort them:

be c[i] the average cost to run filter[i] on 1 object

be r[i] the average ratio of remaining/checked objects after applying filter[i]

be o the number of objects, c the costs so far

so after applying a filter i

o*=r[i] and c+=o*c[i]

so with an chosen ordering 0,1,2 we get

c = o*c[0]+ o*r[0]*c[1] + o*r[0]*r[1]*c[2] + ...

after restructuring we get

c = o * ( c[0] + r[0] * ( c[1] + r[1] * ( ... ) ) )

I don't know if there is a direct solution for this optimization problem (I could ask some colleagues from uni, I'm pretty sure they know) but this equation is a good base for a "branch-and-bound"¹ - graph search algorithm:

the minimal cost-factor after the first filter is  > c[0] + r[0] * c[min] with c[min] being the minimal cost after excluding filter[0].

These are pretty good branch and bound criteria, which should lead very fast to an optimal solution w/o trying each faculty(@filters) permutation like tye did here.

That means even if your recorded performance for each filter is fuzzy and unstable you can always adapt and recalculate on the fly, even if you have more complicated models with ranges of values for c and r.

Cheers Rolf

¹) for examples of B&B applications see Possible pairings for first knockout round of UEFA champions league or Puzzle Time

Create A New User
Node Status?
node history
Node Type: note [id://1011682]
help
Chatterbox?
 [jdporter]: so that I can use the existing expand unix util. Otherwise, I'll probably use Text::Tabs. [1nickt]: pryrt I guess I don;t really care if user 42 logs on as 42.0 ... more of an academic question at this point. [LanX]: jdporter: open PIPE,'-|' ? [LanX]: oh you want the result line by line? [jdporter]: ok, LanX, then what? [jdporter]: It doesn't have to be line by line. Just "my program" "writes" to the external prog and also/then "reads" from it. LanX open (You are not allowed to open to a command that pipes both in and out, but see IPC::Open2, IPC::Open3, and Bidirectional Communication with Another Process in perlipc for alternatives.) [jdporter]: IPC::Open2, I guess [jdporter]: yes, that

How do I use this? | Other CB clients
Other Users?
Others contemplating the Monastery: (11)
As of 2017-05-24 20:29 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
My favorite model of computation is ...

Results (186 votes). Check out past polls.