Méthode la plus efficace pour renvoyer des éléments communs à partir de deux matrices de chaînes

En Java, ce qui est le moyen le plus efficace pour retourner les éléments communs à partir de deux Tableaux de Chaîne? Je peux le faire avec une paire de boucles for, mais qui ne semble pas être très efficace. Le mieux que je pouvais venir avec a été la conversion à un List puis en appliquant retainAllbasé sur mon examen d'un semblable question:

List<String> compareList = Arrays.asList(strArr1);
List<String> baseList = Arrays.asList(strArr2);
baseList.retainAll(compareList);

source d'informationauteur JW8

5

ÉDITÉ:

C'est un one-liner:
```
compareList.retainAll(new HashSet<String>(baseList));
```
La retainAll impl (en AbstractCollection) itère sur thiset utilise contains() sur l'argument. En tournant l'argument en un HashSet entraînera rapide des recherches, de sorte que la boucle à l'intérieur de la retainAll va exécuter aussi rapidement que possible.

Aussi, le nom baseList allusion à ce qu'elle soit une constante, de sorte que vous obtiendrez une amélioration significative de la performance si vous cache ce:
```
static final Set<String> BASE = Collections.unmodifiableSet(new HashSet<String>(Arrays.asList("one", "two", "three", "etc")));

static void retainCommonWithBase(Collection<String> strings) {
    strings.retainAll(BASE);
}
```
Si vous souhaitez conserver l'original de la Liste, faites ceci:
```
static List<String> retainCommonWithBase(List<String> strings) {
   List<String> result = new ArrayList<String>(strings);
   result.retainAll(BASE);
   return result;
}
```
3

Trier les deux tableaux.

Une fois triés, vous pouvez parcourir les deux tableaux triés exactement une fois, à l'aide de deux indices.

Ce sera en O(NlogN).
3

Je voudrais utiliser HashSets (et retainAll) ensuite, ce qui rendrait l'ensemble de la case O(n) (pour chaque élément de la première série de recherche si il existe (contains()), qui est O(1) pour HashSet). Lists sont plus rapides à créer (HashSet peut avoir à traiter avec des collisions...).

Gardez à l'esprit que Set et List ont des sémantiques différentes (listes permettent de dupliquer des éléments, les valeurs null...).

conserver tout n'est pas pris en charge par liste. utiliser lieu:

import java.util.*;
public class Main {
    public static void main(String[] args) {
        String[] strings1={"a","b","b","c"},strings2={"b","c","c","d"};
        List<String> list=Arrays.asList(strings1);
        //list.retainAll(Arrays.asList(strings2)); //throws UnsupportedOperationException
        //System.out.println(list);
        Set<String> set=new LinkedHashSet<String>(Arrays.asList(strings1));
        set.retainAll(Arrays.asList(strings2));
        System.out.println(set);
    }
}

1

Ce que vous voulez est appelé intersection.
Voir que:
Intersection et l'union de ArrayLists en Java

L'utilisation d'un Hachage en fonction de la collection fournit un vraiment plus rapide méthode contains (), en particulier sur les chaînes qui ont optimisé hashcode.

Si vous pouvez importer des bibliothèques, vous pouvez envisager d'utiliser les Ensembles.intersection de la Goyave.

Edit:

Ne connaissais pas l'retainAll méthode.

Noter que le AbstractCollection mise en œuvre, qui ne semble pas surchargée pour HashSets et LinkedHashSets est:

public boolean retainAll(Collection c) {
boolean modifié = false;
Iterator it = iterator();
while (it.hasNext()) {
if (!c.contient(il.next())) {
c'.remove();
modifié = true;
}
}
retour modifiée;
}

Ce qui signifie que vous appelez contient() sur le paramètre du regroupement!
Ce qui signifie que si vous passez un paramètre de Liste, vous aurez une égale appel à de nombreux élément de la liste, pour chaque itération!

C'est pourquoi je ne pense pas que le ci-dessus implémentations utilisant retainAll sont bonnes.
```
public <T> List<T> intersection(List<T> list1, List<T> list2) {
    boolean firstIsBigger = list1.size() > list2.size();
    List<T> big =  firstIsBigger ? list1:list2;
    Set<T> small =  firstIsBigger ? new HashSet<T>(list2) : new HashSet<T>(list1);
    return big.retainsAll(small)
}
```
De choisir d'utiliser le Jeu pour les plus petits, car il est plus rapide de contruct l'ensemble, et une grande liste d'itérations très bien...

Remarquez que l'un de la liste originale paramètre peut être modifié, c'est à vous d'en faire une copie...

J'ai eu un entretien et cette question a été la chose qu'ils m'ont demandé pendant l'entretien technique. Ma réponse a été de lignes de code suivantes:

public static void main(String[] args) {

        String[] temp1 = {"a", "b", "c"};
        String[] temp2 = {"c", "d", "a", "e", "f"};
        String[] temp3 = {"b", "c", "a", "a", "f"};

        ArrayList<String> list1 = new ArrayList<String>(Arrays.asList(temp1));
        System.out.println("list1: " + list1);
        ArrayList<String> list2 = new ArrayList<String>(Arrays.asList(temp2));
        System.out.println("list2: " + list2);
        ArrayList<String> list3 = new ArrayList<String>(Arrays.asList(temp3));
        System.out.println("list3: " + list3);

        list1.retainAll(list2);
        list1.retainAll(list3);
        for (String str : list1)
            System.out.println("Commons: " + str);
}

De sortie:

list1: [a, b, c]
list2: [c, d, a, e, f]
list3: [b, c, a, a, f]
Commons: a
Commons: c

Vous devez vous connecter pour publier un commentaire.

ÉDITÉ: