I'm trying to figure out what is the optimal order for running a sequence of tasks in a pipeline.
Each task filters a percentage of the dataset.
Assuming I got the tasks t1, t2, t3, ..., ti and a dataset. Each task have an execution time per item in the dataset denoted as e1, e2, e3, ..., ei and each task filters a certain percentage of the dataset denoted as f1, f2, f3, ..., fi.
What is the optimal sequence of tasks to achieve the minimum running time ?
I've first tried to examine two tasks - t1 and t2 with their representative execution time and filter percentage - e1, f1 and e2, f2.
I want to find the ordering predicate for getting e1 + f1*e2 < e2 + f2*e1. I'll get the condition e1 / (1 - f1) < e2 / (1 - f2). And I guess that from here I'll need to prove it in induction, but I'm stuck because the equation is some kind of recursion.