Какая коллекция Java позволяет быстрее всего удалять элементы?

Question

Я ищу коллекцию, которая позволяет быстро удалять элементы. Я протестировал ArrayList на 1 млн строк, и оказалось, что удаление первого элемента происходит быстрее, чем удаление последнего. Удаление одного миллиона элементов занимает около 50 секунд

import java.util.ArrayList;

public class TestArray {

    final int numberOfElements = 1000000; 

    public void testArray () { 

    // test array 
    ArrayList<String> testArray = new ArrayList<String>(); 
    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); 
            testArray.remove(testString); 
        }
    } 

    testArray = new ArrayList<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); 
                testArray.remove(testString); 
            }
        }



    } 

}

Но я не уверен, что это самый быстрый способ. 50 секунд самый быстрый способ? Или есть лучшая коллекция, например, LinkedList сделает это быстрее? Или какая коллекция быстрее всего удаляет элементы один за другим?

Answer 1

1) Вы должны рассмотреть LinkedList , который имеет O (1) Big O производительность для удалить операция (пояснение ниже) ,ArrayList равен O (n).
2) Вы можете попробовать HashSet, если вас не интересуют дубликаты.

Удаление LinkedList:

1) Удаление LinkedList в начале и конце является постоянным временем, так как обход не требуется.

2) Для удаления средних элементов требуется больше временипотому что элемент должен быть найден первым.

3) Если у вас есть итератор в том месте, которое вы хотите удалить, тогда удалить это постоянное время.

Answer 2

Во-первых: Должно быть что-то не так с вашим тестом: ArrayList удаляет элементы намного медленнее, чем добавляет некоторые.Это связано с тем, что в массиве не должно быть пробелов в нижележащем массиве.Поэтому элементы должны быть смещены, если вы удалите их везде, но в конце.

Этот ответ зависит от того, хотите ли вы удалить на основе индекса или значения.В целом, операции на основе индексов выполняются быстрее, поскольку не требуется проводить обширные сравнения значений.Поскольку, если вы хотите удалить элементы, вы должны были добавить их один раз, поэтому полезно учитывать сложность добавления:

• ArrayList: Add: O (n), амортизированный O(1) (на практике дешево).Удалить всегда O (n), Найти O (1), если основано на индексе, O (n), если основано на значении

Практический пример эффекта амортизированного анализа: добавление одного миллиона элементов вСтрока приведет к 10 миллионам копий.Однако количество копий равно O (log n), n - количество последовательных операций добавления.

• LinkedList Добавить: в среднем O (n), AddFirst / Last O (1), removeLast / First O (1), найти O (n), getFirstElement / GetLastElementO (1).Обратите внимание: вы должны знать, что искомый элемент находится в конце / начале, и вызывать соответствующий метод.

Пока у вас много последовательных операций добавления / удаления иНесколько поисковых операций (кроме получения первого или последнего элемента), я рекомендую вам использовать LinkedList .

Если у вас нет двух одинаковых объектов, то есть (Object.equals(sameObject)) возвращает true точно для того же объекта.Вы должны использовать LinkedHashSet Он имеет O (1) для всех операций, но одинаковые объекты могут содержаться только один раз.К сожалению, поиск по индексу здесь невозможен, методы также не синхронизированы.Но всегда есть компромисс.

Некоторая теория: Согласно упомянутым работам здесь , мы не можем сделать лучше, чем амортизированная Омега (log n) для произвольного добавления и удаления элементов.

Answer 3

Лучшей коллекцией для производительности является TreeSet, потому что если вы вставляете объекты в соответствии с Comparable / Comparator, коллекция будет упорядочена.

Мои времена: ArrayList Миллисекунды до финиша при удалении первого элемента 698 Миллисекунды до финиша при удалении последнего элемента 121960

TreeSet: Миллисекунды до финиша при удалении первого элемента 55 Миллисекунды до финиша при удалении последнего элемента 50

ПРЕДУПРЕЖДЕНИЕ: С этим решением вы не можете иметь дубликаты объектов в коллекции.

@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);
            }
        }

    }