J'ai une situation où j'ai deux tableaux et je dois les partitionner pour que je me retrouve avec 3 tableaux:

  • éléments qui ne sont que dans A
  • éléments qui ne sont qu'en B
  • éléments qui sont à la fois dans A et B

Exemple:

A = [1, 4, 3, 2]
B = [2, 6, 5, 3]
3part(A,B) => [[1,4], [6,5], [2,3]] # the order of the elements in each array doesn't matter

J'ai trouvé une solution correcte, mais je me demande si cela pourrait être plus rapide. C'est (en pseudocode):

3part(A,B) =>
    a_only = []
    b_only = []
    intersect = []

    foreach a in A
        if B.contains(a)
            intersect.push(a)
        else
            a_only.push(a)

    foreach b in B
        if not intersect.contains(b)
            b_only.push(b)

    return [a_only, b_only, intersect]

Dans mon cas, A & B contiendront chacun jusqu'à 5000 structures complexes (au lieu de ints) et cela dure environ 1,5 secondes. Il est utilisé dans le cadre d'une interaction utilisateur qui peut se produire fréquemment, donc idéalement, cela prendrait <.5sec.

BTW, y a-t-il un nom pour cette opération dans son ensemble, autre que "différence-différence-intersection"?

Merci!

ÉDITER:

Sur la base des suggestions d'utilisation d'un hachage, mon code mis à jour s'exécute en moins de 40 ms :-D

Voici le pseudocode:

(disons que "clé" est l'élément que j'utilise pour la comparaison)

array_to_hash(A, Key)
    h = {}
    foreach a in A
        h[a[Key]] = a
    return h

3part(A,B) =>
    a_only = []
    b_only = []
    intersect = {} // note this is now a hash instead of array

    Ah = array_to_hash(A, 'key')
    Bh = array_to_hash(B, 'key')

    foreach ak in Ah.keys()
        if Bh.hasKey(ak)
            intersect[ak] = Ah[ak]
        else
            a_only.push(Ah[ak])

    foreach bk in Bh.keys()
        if not intersect.hasKey(bk)
            b_only.push(Bh[bk])

    return [a_only, b_only, intersect.values]

Merci à tous pour les suggestions.

3
dgbillotte 15 août 2017 à 19:08

2 réponses

Meilleure réponse

Je sens que vous vous permettez d'être handicapé par des hypothèses d'opérations primitives. Le matériel actuel comprend une excellente prise en charge du hachage et des opérations GEMM.

  1. Hash les valeurs de A et B dans un seul espace, avec une plage de l'ordre de | A + B |.
  2. Convertissez les deux tableaux en encodage à chaud dans cette plage.
  3. Appliquez des opérations vectorielles ET-OU-NON pour obtenir vos trois résultats.
1
Prune 15 août 2017 à 16:32

Votre pseudo-code est bon SI vous utilisez une structure de données hachée pour tous les "tableaux".

Je suppose que tous les environnements de programmation actuels ont une prise en charge décente des collections, y compris des ensembles basés sur le hachage. Voici deux exemples comment le faire en Java, fonctionnant en plus ou moins O (n + m). En Java, pour que les collections hachées fonctionnent correctement, il est important que vos objets complexes implémentent les méthodes hashCode() et equals() de manière conforme (elles peuvent souvent être générées automatiquement par votre IDE).

La première version repose entièrement sur l'implémentation set-algebra de votre bibliothèque, ce qui devrait aboutir à O (n) si la bibliothèque est OK:

private static void test1() {
    Integer[] a = {1, 4, 3, 2};
    Integer[] b = {2, 6, 5, 3};

    Set<Integer> aOnly = new HashSet<>(Arrays.asList(a));
    Set<Integer> bOnly = new HashSet<>(Arrays.asList(b));

    Set<Integer> ab = new HashSet<>(aOnly);
    ab.retainAll(bOnly);
    aOnly.removeAll(ab);
    bOnly.removeAll(ab);

    System.out.println("A only: " + aOnly);
    System.out.println("A and B: " + ab);
    System.out.println("B only: " + bOnly);
}

Le second utilise le fait qu'en Java, la méthode remove () retourne true si l'élément était présent avant de le supprimer. Si votre bibliothèque ne fait pas cela, vous devez

private static void test2() {
    Integer[] a = {1, 4, 3, 2};
    Integer[] b = {2, 6, 5, 3};

    Set<Integer> aOnly = new HashSet<>(Arrays.asList(a));
    Set<Integer> bOnly = new HashSet<>();
    Set<Integer> ab = new HashSet<>();

    for (int bElem : b) {
        if (aOnly.remove(bElem)) {
            ab.add(bElem);
        } else {
            bOnly.add(bElem);
        }
    }

    System.out.println("A only: " + aOnly);
    System.out.println("A and B: " + ab);
    System.out.println("B only: " + bOnly);
}
3
Ralf Kleberhoff 15 août 2017 à 17:18