Quelle collection Java permet la suppression d'élément la plus rapide?

La meilleure collection pour les performances est TreeSet parce que si vous insérez des objets selon Comparable / Comparator, la collection sera ordonnée.

Mes temps: Liste des tableaux Millisecondes pour terminer lors de la suppression du premier élément 698 Millisecondes pour terminer lors de la suppression du dernier élément 121960

TreeSet: Millisecondes pour terminer lors de la suppression du premier élément 55 Millisecondes pour terminer lors de la suppression du dernier élément 50

AVERTISSEMENT: Avec ces solutions, vous ne pouvez pas avoir d'objets en double dans la collection.

@Test
    public void testTreeSet() {
        /* RESULTS
         * Milliseconds to fisnish when removing the first element 55
         * Milliseconds to fisnish when removing the last element 50
         */

        // test array
        TreeSet<String> testArray = new TreeSet<String>();
        int numberOfElements = 100000;
        for (int i = 0; i < numberOfElements; i++) {
            testArray.add("" + Math.random());
        }

        // testing speed when removing the first element
        long startTime = System.currentTimeMillis();
        while (true) {
            if (testArray.isEmpty()) {
                System.out.println("Milliseconds to fisnish when removing the first element "
                        + (System.currentTimeMillis() - startTime));
                break;
            } else {
                //String testString = testArray.get(0);
                String testString = testArray.first();
                testArray.remove(testString);
            }
        }

        testArray = new TreeSet<String>();
        for (int i = 0; i < numberOfElements; i++) {
            testArray.add("" + Math.random());
        }
        // testing speed when removing the last element
        long startTime2 = System.currentTimeMillis();
        while (true) {
            if (testArray.isEmpty()) {
                System.out.println("Milliseconds to fisnish when removing the last element "
                        + (System.currentTimeMillis() - startTime2));
                break;
            } else {
                //String testString = testArray.get(testArray.size() - 1);
                String testString = testArray.last();
                testArray.remove(testString);
            }
        }

    }

Premièrement: il doit y avoir un problème avec votre benchmark, une ArrayList supprime les éléments beaucoup plus lentement que d'en ajouter. Cela est dû au fait que le tableau ne doit pas avoir d'espaces dans le tableau sous-jacent. Les éléments doivent donc être déplacés si vous supprimez partout mais à la fin.

Cette réponse dépend si vous voulez supprimer les index ou les valeurs. En général, les opérations basées sur des index sont plus rapides car aucune comparaison de valeur expansive ne doit être effectuée. Étant donné que si vous souhaitez supprimer des éléments, vous devez les avoir ajoutés une fois, il est également utile de prendre en compte la complexité ajoutée

• ArrayList: Ajoutez: O (n), amorti O (1) (en pratique bon marché). Remove est toujours O (n), Find O (1) si basé sur un index, O (n) si basé sur une valeur

Exemple pratique de l'effet de l'analyse amortie: l'ajout d'un million d'éléments d'affilée se traduira par 10 millions d'exemplaires. Cependant le nombre de copies est O (log n), n est le nombre d'opérations d'ajout consécutives.

• LinkedList Ajouter: O (n) à la moyenne, AddFirst / Last O (1), removeLast / First O (1), find O (n), getFirstElement / GetLastElement O (1). Notez ici: Vous devez savoir que l'élément que vous recherchez est à la fin / au début et appeler la méthode correspondante.

Jusqu'à présent, si vous avez beaucoup d'opérations d'ajout / suppression consécutives et peu d'opérations de recherche (sauf pour obtenir le premier ou le dernier élément), je vous recommande d'utiliser LinkedList .

Si vous n'avez pas deux objets identiques, c'est-à-dire que ( Object.equals (sameObject) ) renvoie true pour exactement le même objet. vous devez utiliser LinkedHashSet Il a O (1) pour toutes les opérations, mais les objets égaux ne peuvent être contenus qu'une seule fois. Malheureusement, la recherche par index n'est pas possible ici, les méthodes ne sont pas non plus snychronisées. Mais il y a toujours un compromis.

Une théorie: selon les articles mentionnés ici nous ne pouvons pas faire mieux qu'Omega amorti (log n) pour l'ajout et la suppression arbitraires d'éléments.