Combinatoire: variable accessible par deux threads

Question

Les threads A et B ont un accès simultané à une seule variable. Chaque thread effectue une séquence d'accès sur la variable (lectures et écritures). Chaque thread stocke les résultats de ses lectures dans un tableau. Le résultat de la session est défini par les deux tableaux.

Les accès effectués par un fil donné ne peuvent pas être ré-ordonnées. Cependant, les accès à partir des deux threads peuvent être entrelacés, de sorte que le résultat dépendra de cet entrelacement. Comment pouvons-nous calculer efficacement le nombre de résultats possibles, compte tenu des deux séquences d'accès? Supposons que toutes les écritures produisent des valeurs distinctes.

Example access sequences: 
     Thread A: [write(71), read()] 
     Thread B: [read(), write(72), write(73), read()] 

    Example interleaving: 
     [a_write(71), b_read(), b_write(72), a_read(), b_write(73), b_read()] 

    Example outcome: 
     a_results = [72] 
     b_results = [71, 73] 

P.s. Ce n'est pas un devoir, c'est juste un problème que j'ai moi-même conçu.

Answer 1

Cela ressemble à quelque chose qui pourrait être résolu avec la programmation dynamique.

Je suggère à la recherche d'un moyen de résoudre le sous-problème:

Combien de résultats distincts sont là étant donné que nous avons fait x les accès de fil 1, y accède à partir de fils 2, et le dernier accès était une écriture effectuée par le thread z (1 ou 2).

La matrice DP sera tridimensionnelle: DP [x] [y] [z].

Il y aura un total de 2 * (nombre d'accès en fil 1) * (nombre d'accès en fil 2) fentes pour être calculée de la DP. Pour remplir chaque entrée du tableau, vous devez additionner plusieurs entrées précédentes du tableau. Je soupçonne donc que la complexité globale sera autour de O (n^3) où n est le nombre d'accès.