Доступ к LinkedHashMap по индексу против производительности

Question

Я хотел бы обсудить немного производительности конкретной коллекции, LinkedHashMap, для конкретного требования и как новые функции Java 8 или 9 могут помочь в этом.

Предположим, у меня есть следующая LinkedHashMap:

private Map<Product, Item> items = new LinkedHashMap<>();

Использование конструктора по умолчанию означает, что эта Карта следует порядку вставки, когда она повторяется.

- EDITED-- Просто чтобы прояснить это, я понимаю, что Карты не являются правильной структурой данных, к которой должен обращаться индекс, бывает, что этому классу на самом деле нужны два метода удаления, один по Product, правильный путь, который является ключом, и другой по позиции, или по индексу, что не часто, так что я беспокоюсь о производительности. Кстати, это не мое требование.

Мне нужно реализовать метод removeItem () по индексу . Для тех, кто не знает, LinkedHashMap не имеет какой-либо метод map.get(index);.

Итак, я перечислю пару решений:

Решение 1:

public boolean removeItem(int position) {
    List<Product> orderedList = new ArrayList<>(items.keySet());
    Product key = orderedList.get(position);

    return items.remove(key) != null;
}

Решение 2:

public boolean removeItem(int position) {
    int counter = 0;
    Product key = null; //assuming there's no null keys

    for(Map.Entry<Product, Item> entry: items.entrySet() ){
        if( counter == position ){
            key = entry.getKey();
            break;
        }
        counter++;
    }

    return items.remove(key) != null;
}

Соображения по поводу этих 2 решений.

S1: Я понимаю, что ArrayLists имеют быструю итерацию и доступ, поэтому я считаю, что проблема заключается в том, что создается целая новая коллекция, поэтому память будет скомпрометирована, если у меня будет огромная коллекция.

S2: Я понимаю, что итерация LinkedHashMap быстрее, чем HashMap, но не так быстро, как ArrayList, поэтому я считаю, что время итерации здесь будет скомпрометировано, если у нас будет огромная коллекция, но не память.

Учитывая все это и мои соображения верны, могу ли я сказать, что оба решения имеют O (n) сложность?

Есть ли лучшее решение для этого случая с точки зрения производительности, используя последние функции Java 8 или 9?

Ура!

Answer 1

Как сказал Стивен С , сложность по времени такая же, как в любом случае, у вас есть линейная итерация, но эффективность все равно отличается, так как второй вариант будет повторяться только до указанного элемента вместо создания полной копии.

Вы можете оптимизировать это еще больше, не выполняя дополнительный поиск после нахождения записи. Чтобы использовать указатель на фактическое местоположение в Map, вы должны использовать его Iterator в явном виде:

public boolean removeItem(int position) {
    if(position >= items.size()) return false;
    Iterator<?> it=items.values().iterator();
    for(int counter = 0; counter < position; counter++) it.next();
    boolean result = it.next() != null;
    it.remove();
    return result;
}

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

public boolean removeItem(int position) {
    if(position >= items.size()) return false;
    Iterator<?> it=items.entrySet().iterator();
    for(int counter = 0; counter <= position; counter++) it.next();
    it.remove();
    return true;
}

Вы можете получить конкретный элемент, используя Stream API, но последующая операция remove требует поиска, который делает его менее эффективным, чем вызов remove на итераторе, который уже имеет ссылку на позицию на карте для большинства реализации.

public boolean removeItem(int position) {

    if(position >= items.size() || position < 0)
        return false;

    Product key = items.keySet().stream()
        .skip(position)
        .findFirst()
        .get();

    items.remove(key);
    return true;
}

Answer 2

Учитывая все это и мои соображения верны, могу ли я сказать, что оба решения имеют O (n) сложность?

Да.Средняя сложность одинакова. В первом решении шаг new ArrayList<>(entrySet) равен O(N).

Во втором решении цикл равен O(N).

Существует различие вхотя сложность в лучшем случае.В первом решении вы всегда копируете весь список.Во втором решении вы выполняете только столько, сколько вам нужно.Так что в лучшем случае он может прекратить итерации в первом элементе.

Но хотя средняя сложность составляет O(N) в обоих случаях, я чувствую, что второе решение будет самым быстрым.(Если это имеет значение для вас, сравните это ...)

Есть ли лучшее решение для этого случая с точки зрения производительности, используя последние функции Java 8 или 9?

Java 8 и Java 9 не предлагают никаких улучшений производительности.

Если вы хотите получить среднюю сложность, превышающую O (N), вам понадобится другая структура данных.

Еще одна вещь, которую стоит отметить, это то, что индексация наборов записей карты, как правило, не является полезной вещью.сделать.Всякий раз, когда запись удаляется из набора, значения индекса для некоторых других записей change ....

Эффективное имитация этого "нестабильного" поведения индексациисложно.Если вы хотите стабильного поведения, то вы можете увеличить свой основной HashMap<K,V> / LinkedHashMap<K,V> на HashMap<Integer,K>, который вы используете для позиционного поиска / вставки / поиска.Но даже это немного неловко ... учитывая, что произойдет, если вам нужно вставить новую запись между записями в позициях i и i + 1.