Le moyen le plus rapide de faire une soustraction de collection

Question

J'ai deux ensembles. Set b est le sous-ensemble de Set a. ils sont tous les deux très grands ensembles. Je veux soustraire b de a, quelle est la meilleure pratique pour faire cette opération commune? J'ai écrit de nombreux codes comme celui-ci, et je ne pense pas que ce soit efficace. Quelle est ton idée ?

pseudo-code: (ce n'est pas API Java).

for(int i = 0 ; i < a.size(); i++) { 
      for (int j=0 ; j < b.size() ;j++) { 
       // do comparison , if found equals ,remove from a 
       break; 
      } 
} 

Et je veux trouver un algorithme, non seulement s'applique aux ensembles, fonctionne également pour Array.

EDIT: L'ensemble n'est pas API JAVA ici, il est une structure de données. donc je m'en fous si Java API a une méthode removeAll(), je veux trouver une solution commune pour ce problème, j'ai rencontré beaucoup de problèmes comme ça quand j'utilise Javascript et Actionscript.

Answer 1

Je ne pense pas que vous obtiendrez beaucoup plus rapide, mais votre code ressemblera plus simple et ne deviendra pas plus lent par a.removeAll(b);. removeAll() fait partie de l'API Java. Pour l'analyse d'efficacité: Votre exemple de code donné est O (n^2), qui n'est pas très bon, mais ce n'est pas la chose la plus horrible sur terre (la complexité exponentielle est la chose que vous ne voulez pas). Tant que vous ne connaissez pas l'organisation interne des données de la collection, vous n'obtiendrez pas de meilleures performances. removeAll() est implémenté par la classe elle-même et connaît l'organisation interne. Donc, si les données sont organisées dans un Hash, vous obtiendrez de meilleurs résultats, si les données sont organisées dans un tableau non trié, la complexité sera la même. Un ensemble doit rechercher efficacement si un nouvel élément est déjà dans l'ensemble, donc je suspecte une sorte de Hash comme représentation interne, surtout si l'implémentation est appelée HashSet. :-)

EDIT: L'OP a changé sa question pour mentionner que ce n'est pas seulement pour Java. removeAll() est une API Java, donc ceci (ou quelque chose de similaire) peut ne pas être disponible dans d'autres langues. Comme dit précédemment, si les collections sont des tableaux non triés sans autres restrictions, les deux boucles sont déjà la solution la plus rapide. Mais si les données sont organisées différemment, vous avez des options plus rapides. Si les deux collections sont données triées (dans mon exemple est l'élément le plus petit en premier), vous pouvez faire ce qui suit (en réduisant la complexité à O (n)):

int bIndex = 0; 
for(int i = 0 ; i < a.size(); i++) { 
      while (a[i] < b[bIndex]) {bIndex++;} 
      if (a[i] == b[bIndex]) {markForRemoval(a[i]);} // I mark this only for removal, as the actual removal would make your index incorrect 
} 

Si les données sont organisées en tant que hachage Dans les deux collections, vous n'avez besoin que d'une boucle for, accédant directement à l'élément dans b. D'autres organisations possibles de données sont possibles.

Answer 2

Vous avez vu la méthode removeAll dans l'interface Set?

Consultez également this stack overflow question.

Answer 3

Je crois que vous trouverez java.util.HashSet.removeAll(Collection toRemove) de bien performer. D'autre part, si vous n'avez pas ensembles mais les collections triées, vous pourriez être en mesure de faire beaucoup mieux.

Answer 4

En fin de compte, il n'y a pas grand-chose d'un autre choix que de l'un par l'un des éléments de comparaison et enlever ceux qui sont dans les deux. Pour le faire autrement, vous devriez faire quelque chose de fantaisiste comme donner à tous les membres de l'ensemble un index de valeur unique, et construire un énorme tableau de booléens représentant chaque ensemble, et ensuite vous pourriez faire des opérations binaires pour soustraire B UNE.Je n'ai aucune idée si cela serait plus rapide, étant donné la surcharge de créer des indices de valeur uniques et de manipuler les très grands masques de bits.

Je sais que vous ne vous souciez pas d'une solution Java, mais comme d'autres personnes ont recommandé removeAll(), je tiens à souligner qu'il fait toujours la même chose sous les couvertures. Vérifiez la source de HashSet.

Answer 5

Si les ensembles sont maintenus de sorte que les éléments soient disponibles à un moment donné dans l'ordre de tri, vous pouvez effectuer un seul passage linéaire sur les deux ensembles et créer la différence de temps O (n). Maintenant, encore une fois, c'est si vous pouvez obtenir aux listes ordonnées des éléments gratuitement — ce qui veut dire que les opérations de maintenance (c.-à-d., Ajouter-élément et supprimer-élément) des ensembles paie le coût de garder le éléments disponibles dans l'ordre trié.

Tout type d'opération "removeAll" qui repose sur l'exécution de recherches va nécessairement être pire que O (n).

(Il me semble que la construction de la différence qui est définie —, la réponse construite à partir du passage linéaire sur les deux listes — pourrait être O (n log n) si vous n'êtes pas très prudent.)

Answer 6

Eh bien, l'idée correcte était déjà soulignée: l'ensemble devrait être implémenté en utilisant un hachage. les hachages ont idéalement un coût d'accès de O(1), donc vous pouvez obtenir le coût O(min(m,n)) pour l'opération globale en supposant que vous pouvez déterminer quel ensemble est plus grand (comme maintenir un compteur pendant les opérations d'insertion/retrait). En actioncript 3, vous utiliseriez un Dictionary. il suffit d'utiliser des éléments comme des clés et des valeurs.

suppression se présente comme suit:

for each (var key:* in set2) {//a simple for-in loop will also do the trick, since keys and values are equal, but for-each-in loops perform faster 
    delete set1[key]; 
} 

en JavaScript, vous devrez donner les entrées ids lors de l'insertion, de sorte que vous pouvez utiliser ces ids comme clés dans une carte. il suffit de mapper les identifiants aux valeurs d'origine.

suppression se présente comme suit:

for (var key in set2) { 
    delete set1[key]; 
} 

Answer 7

Étant donné que b est un sous-ensemble d'un je ne sais pas pourquoi votre pseudo-code a 2 boucles. Le mien serait simplement:

foreach b in B 
    remove b from A 

En pratique comment le temps d'exécution de cette comparaison avec le temps de fonctionnement de la vôtre dépend, entre autres, la façon dont vous avez mis en œuvre l'ensemble comme une structure de données.

Answer 8

L'opération que vous écrivez est O (N^2), mais si les ensembles sont grands, vous pouvez utiliser un hachage.

// A is some kind of array, O(1) iteration 
// B is a hash containing elements to remove, O(1) contains(elt) 
List<T> removeAll(List<T> A, Set<T> B) { 
    List<T> result; // empty, could preallocate at |A| 
    for (elt : A) { // for each 'elt' belonging to A, hence O(|A|) 
    if (! B.contains(elt)) { // O(1) thanks to hash 
     C.add(elt) ; // ensure this is O(1) with preallocation or linked list 
    } 
    } 
    return result; 
} 

Cela nécessite l'indexation de l'ensemble B, vous avez donc besoin d'une fonction de hachage. En Java, vous pouvez utiliser Set<T> Bh = new HashSet<T>(B); qui est O (| B |) dans le temps et la mémoire. Donc, globalement, nous obtenons O (| A | + | B |) dans le temps et approximativement O (2 | A | +2 | B |)) en mémoire. Sure bat le quadratique de removeAll, vous sentirez la différence (TM). Il est probablement préférable de copier les éléments dans un nouveau tableau (comme dans le pseudo-code), puisque la suppression directe des éléments de A pourrait entraîner une surcharge si les éléments sont conservés dans l'ordre (les éléments de gauche dans A sont coûteux).