2
$\begingroup$

I'm reposting this because people found the last description to be too hard to follow.

  1. The data unit I'm working with is a pair of 2 numbers. The numbers can be any integer that is bigger than 0. Example:
    [X, Y]
  2. The input is 2 arrays of these pairs, each array can have any length. Example:
    A = {[1, 2], [3, 2], [5, 1]}
    B = {[2, 3], [4, 5], [5, 3]}
  3. If I combine 2 pairs, one from each array, I get a new pair like this:
    [X1, Y1] + [X2, Y2] = [X1 + X2, Y1 + Y2]
  4. The output is a result of all combinations between the elements of the 2 input's where each element is the "best" and is ordered as ascending by Y

What "best" means in this case is that given [X, Y],

  1. this pair would have the highest or equal to highest X compared to all the other pairs that might have the same Y Example: [2, 2], [2, 2],[1, 2]
  2. it cannot have an X equal or lower than the maximum of any other pair that has a lower Y Example: [2, 1], [4, 2],[2, 4]


To illustrate how the output can be reached

  1. Lets take this example input:
    A = {[1, 2], [3, 2], [5, 1]}
    B = {[2, 3], [4, 5], [5, 3]}
  2. First we combine every item in A with every item in B
    A[1] + B[1] = [3, 5], A[1] + B[2] = [5, 7], A[1] + B[3] = [6, 5]
    A[2] + B[1] = [5, 5], A[2] + B[2] = [7, 7], A[2] + B[3] = [8, 5]
    A[3] + B[1] = [7, 4], A[3] + B[2] = [9, 6], A[3] + B[3] = [10, 4]
  3. Next we order the combinations by Y
    [7, 4], [10, 4], [3, 5], [6, 5], [5, 5], [8, 5], [9, 6], [5, 7], [7, 7]
  4. Filter the combinations by the rules described above
    [10, 4]

So in this example, the output is an array with the length of 1 because all other pairs with Y of 4 have lower X and all other pairs with Y > 4 have equal or lower X.

I didn't include it in the example because its not necessary but the process can be optimized by prefiltering A and B by the same rules.

Now to my problem: I'm not dealing with arrays with the length of 3 but rather several hundred and the input count isn't 2 but 5+, as you can imagine, this process can be nested like this:
result5 = process(process(process(process(A, B), C), D, E)

So in practice, the potential memory use is A.size * B.size * C.size * D.size * E.size.. which is a lot more than fits in the 20something kB i have available.

What I'm looking for is an algorithm that will fetch me the same results, in the same order, one by one. The fetches will be sequential and will start from 0 so I think any algorithm that can produce all the results in the right order without sorting in the end can be modified for this. Does anybody know how this could be achieved?

$\endgroup$
  • $\begingroup$ Thank you for the re-statement! I personally found this presentation much easier to understand. $\endgroup$ – D.W. Mar 24 '15 at 5:13
1
$\begingroup$

Negate the Y values. Then you are looking for the Pareto-optimal frontier of the set of combinations.

There are standard algorithms for computing the Pareto-optimal frontier of any set. In particular, see the last part of this answer for an overview of algorithms (the simple cull algorithm, divide-and-conquer, and hybrids between those two). Those algorithms should be much more efficient than what you were considering before. For example, the simple cull algorithm has $O(n^2)$ running time to compute the Pareto-optimal frontier of a set of size $n$ (or $O(nm)$ time, if you know the output is of length $m$).

Here's how you can use this in your setting. First, compute the Pareto-optimal frontier of A and the Pareto-optimal frontier of B. Then, enumerate all combinations of those two frontiers. Finally, compute the Pareto-optimal frontier of that list of combinations. If you use the simple cull algorithm, the running time will be at worst $O(n^4)$, where $n$ is the length of the input lists. If the output has size $m$, the running time will be at worst $O(n^2 m)$. In either case, the memory consumption will be $O(n^2)$. The algorithms might perform better than that in practice, depending on your data.

If you want the output to be in sorted order, you can sort by Y value after computing the set.

I would recommend that you try these algorithms and see what the memory consumption looks like. If the memory consumption is still too much, then you can let us know.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.