Beefy Boxes and Bandwidth Generously Provided by pair Networks
Keep It Simple, Stupid
 
PerlMonks  

comment on

( #3333=superdoc: print w/replies, xml ) Need Help??
> 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

UPDATES:

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


In reply to Re^2: Evolving a faster filter? (combinatorics) by LanX
in thread Evolving a faster filter? by Ovid

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • Are you posting in the right place? Check out Where do I post X? to know for sure.
  • Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
    <code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>
  • Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
  • Want more info? How to link or or How to display code and escape characters are good places to start.
Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others exploiting the Monastery: (3)
As of 2022-05-21 12:52 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    Do you prefer to work remotely?



    Results (76 votes). Check out past polls.

    Notices?