I'm trying to figure out a more efficient solution to the following problem.
Dataset: A set of arrays of key-value pairs (K, V). The arrays have varying lengths, and the keys are non-zero 16-bit unsigned integers.
Examples:
[(3, 100)]
[(1, 200), (1, 100), (2, 300)]
[(2, 200), (2, 300)]
Input: A fixed-length array of key-value pairs (J, U). The keys are non-zero 16-bit unsigned integers.
Example:
[(2, a), (1, b), (5, c), (1, d)]
The example is 4 elements, in the actual implementation it's always 8.
Expected Output: An array with length equal to one of the dataset arrays. The array elements are pairs of values from the dataset and input. I'm not sure how to express this in mathematical notation, so here's some pseudocode for a naive implementation:
for arr in dataset {
let out_arr = []
for (k, v) in arr {
let result = null
for (j, u) in input {
if k == j {
result = (j, u)
break
}
}
if result == null { break }
input.remove((j, u))
out_arr.push((v, u))
}
if out_arr.length == arr.length {
return out_arr
}
}
return null
This algorithm, when ran for the above dataset and input, would produce the following array:
[(200, b), (100, d), (300, a)]
To attempt to state the algorithm in words: I need to see if there exists an array in the dataset for which every pair has a matching (by key) pair in the input. If there is such an array, I need to construct an output array of pairs of the values from each matching pair between the dataset and the input.
Caveat: The algorithm above is actually insufficient because if there are multiple valid outputs, one needs to be chosen at random, or at the very least in a way that prevents aliasing. In practice I'm doing this by shuffling the input array and using the solution below. This is also what makes it difficult to consider solutions that require sorting the input array.
The current working solution I have is to store a tree containing all possible continuation nodes given input in any order. Nodes which represent the completion of one of the dataset arrays also have the V values from the array in the order the array was traversed. For example the array [(1, 200), (1, 100), (2, 300)] may be represented by the tree in the following diagram (with the output values in red boxes):
In this case, I find the solution like this:
let node = root
for (u, j) in input {
let next = tree.get(u)
if next { node = next }
}
if node.output return node.output
The time taken to construct the data structure is not important, nor is maintenance cost or cost of any operation other than lookup, and generally there is plenty of space but I would like a structure that can be stored contiguously in memory.
Sorry if the way I've described the problem is confusing, I don't have the background in mathematics to know any of the terminology to help describe it. Please do ask for clarification in the comments.
