coverage of xml document with variables and paths

Question

For coverage, I've a set of run time variables of from my program execution. It happens that I get it from a series of executions(Automated testing). ie. its a vector<vector<var,value>>

I've a limited set of variables with expected values and generate combination s, that is I have vector<vector<var,value>(smaller than the execution vector)>. Now I need to compare and tell which of the combination I generated were exactly executed in one of the tests.

My algo is O(n^4). Is there any way to bring it down. Something like set intersection. I'm using java, and vectors because of thread safety.

Eloboration: I have a very big chunk of variables in my program. I don't care about all of them. All I care about is a set of variables with values that I know abt them(Edge values,and developer given values). What I do is, generate a set of combinations for those variables with values, which i think might be meaningful since, it will be useful after an automated test, to tell me that these combinations were excecuted and some were not.

Since, the test is automated i have a series (<20) executions with all variables and values in the DS I gave in the question. My problem is comparing a small set of combinations with a large set. The Hash might work if the no. of variables are same, i suppose. My algo is brute force

Answer 1

I would generate hashes from the combination of pairs such that if two combinations are equal then they have the same hash. If your set of expected combinations is small then you could use this hash as a key to a Hashmap.

For each combination in your execution vector, generate the hash key and look for it in the hashmap. Hashmap lookup has amortized time O(1), so that for n execution entries and k expected combinations, the total time is O(n+k).

Some care must be taken in the choice of hash-function to avoid collisions, but this shouldn't be too hard a problem.