Un moyen efficace de trouver des "correspondances" dans une matrice en java

Question

J'ai une application (java) existante qui modélise un carnet de commandes, car chaque commande est visible pour tous les autres. Il est maintenant nécessaire de mettre en place (ce qui est effectivement) un ACL par ordre en place.

Un exemple pour illustrer, disons que j'ai groupes d'accès [VZ] et les commandes [AF]

 A B C D E F 
    V 1 0 0 1 1 0 
    W 0 1 1 0 0 1 
    X 0 0 0 0 1 1 
    Y 1 1 0 0 0 1 
    Z 0 1 0 1 0 0 

Une nouvelle commande arrive qui spécifie la visibilité que W & Y. Quelle serait un moyen rapide de retourner l'ensemble des valeurs qui peuvent être vus par l'ordre entrant?

Une implémentation qui a été suggérée consiste à représenter chaque ligne comme un BitSet et à faire W | Y bien que je me demande ce qui va arriver à la performance à mesure que la taille de la matrice augmente.

Un Souhaitée mais pas caractéristique essentielle est de permettre une relation parent-enfant sur une dimension comme

 A B C D E F 
    V 1 0 0 1 1 0 
    W 0 1 1 0 0 1 
    X-1 0 0 0 0 1 1 
    X-2 1 0 0 0 1 1 
    X-3 0 1 0 0 1 1 
    Y 1 1 0 0 0 1 
    Z 0 1 0 1 0 0 

Il serait idéal si elle était de la même efficace pour récupérer « W | X » comme " W | X-1 "

Tout indice dans le sens d'un algorithme et/ou d'une structure de données appropriée est très apprécié.

Answer 1

La solution simple:

class AccessGroupName { ... } 
class Order { ... } 

Map<AccessGroupName, Collection<Order>> visibility = new HashMap<AccessGroupName, Collection<Order>>(); 

addVisibility(AccessGroupName group, Order order) { 
    Collection<Order> orders = visibilities.get(group); 
    if (orders == null) { 
     orders = new ArrayList<Order>(); 
     visibility.put(group, orders); 
    } 
    if (!orders.contains(order)) orders.add(order); 
} 

public Set<Order> getVisibility(Collection<AccessGroupName> names) { 
    Set<Order> visible = new HashSet<Order>(); 
    for (AccessGroupName name: names) { 
     visible.addAll(visibilities.get(name)); 
    } 
    return visible; 
} 

recherches de HashMap sont O (1). Itérer une ArrayList est O (n). L'ajout d'éléments à un HashSet est O (n). Dans l'ensemble, ce sera O (n) où n est le nombre total d'éléments dans les listes ajoutées (qui peut être supérieur au nombre d'éléments dans l'ensemble résultant s'il y a chevauchement). La constante est, en gros, le temps nécessaire pour obtenir un élément d'un itérateur ArrayList plus le temps qu'il faut pour ajouter quelque chose à un HashSet - le premier est de l'ordre de 10 cycles, le dernier plus proche de 100.

Mémoire l'utilisation, en plus des instances AccessGroupName et Order elles-mêmes, est d'environ 14-15 mots par groupe plus 1-2 mots par commande. Principalement les en-têtes d'objet.

Ce code ne fait rien d'intelligent, mais je pense que vous aurez du mal à battre O (n) avec une constante de < 200 cycles. En particulier, si la matrice notionnelle est clairsemée (c'est-à-dire s'il y a beaucoup de groupes d'accès avec quelques ordres chacun), cela va battre l'approche bitset, ce qui gâchera énormément de choses. l'espace sur les zéros, et l'heure sur les zéros de l'OR.