couverture de document xml avec des variables et des chemins

Question

Pour la couverture, j'ai un ensemble de variables d'exécution de mon programme d'exécution. Il arrive que je l'obtienne d'une série d'exécutions (tests automatisés). c'est à dire. est un vector<vector<var,value>>

J'ai un ensemble limité de variables avec des valeurs et générer combinaison s, qui est je vector<vector<var,value>(smaller than the execution vector)> prévu. Maintenant, j'ai besoin de comparer et dire lequel de la combinaison que j'ai généré a été exécuté exactement dans l'un des tests.

Mon algo est O (n^4). Y a-t-il un moyen de l'abattre? Quelque chose comme définir l'intersection. J'utilise Java, et les vecteurs en raison de la sécurité des threads. Eloboration: J'ai un très gros morceau de variables dans mon programme. Je me fous de tous. Tout ce qui m'importe, c'est un ensemble de variables avec des valeurs que je connais (valeurs Edge et valeurs données par le développeur). Ce que je fais, c'est de générer un ensemble de combinaisons pour les variables avec des valeurs, ce qui pourrait être significatif car je pense qu'il sera utile après un test automatique de me dire que ces combinaisons ont été exécutées et que d'autres ne l'étaient pas. Comme le test est automatisé, j'ai effectué une série d'exécutions (< 20) avec toutes les variables et toutes les valeurs dans le DS I donné dans la question. Mon problème est de comparer un petit ensemble de combinaisons avec un grand ensemble. Le Hash pourrait fonctionner si le non. des variables sont les mêmes, je suppose. Mon algo est une force brute

Answer 1

Je générerais des hachages à partir de la combinaison de paires de sorte que si deux combinaisons sont égales alors elles ont le même hachage. Si votre ensemble de combinaisons attendues est petit, vous pouvez utiliser ce hachage comme clé pour une Hashmap.

Pour chaque combinaison de votre vecteur d'exécution, générez la clé de hachage et recherchez-la dans le hashmap. La recherche Hashmap a amorti le temps O (1), de sorte que pour n entrées d'exécution et k combinaisons attendues, le temps total est O (n + k).

Un certain soin doit être pris dans le choix de la fonction de hachage pour éviter les collisions, mais cela ne devrait pas être trop difficile.