Java: сортированная коллекция, которая позволяет дубликаты, является эффективной памятью и обеспечивает быструю вставку + обновление

Ответ 1

Я решил опрокинуть свое собственное, но не оптимальное решение, просто вариант TreeMap. Я сохраню это обновление, если я точно настрою эту коллекцию на память. Скорость уже намного лучше, чем предыдущая попытка PriorityQueue, поскольку мне нужен метод collection.remove(Object) (для обновления записи):

package com.graphhopper.coll;

import gnu.trove.iterator.TIntIterator;
import gnu.trove.set.hash.TIntHashSet;
import java.util.Map.Entry;
import java.util.TreeMap;

/**
 * A priority queue implemented by a treemap to allow fast key update. Or should we use a standard
 * b-tree?
 */
public class MySortedCollection {

    private int size;
    private int slidingMeanValue = 20;
    private TreeMap<Integer, TIntHashSet> map;

    public MySortedCollection(int size) {
        map = new TreeMap<Integer, TIntHashSet>();
    }

    void remove(int key, int value) {
        TIntHashSet set = map.get(value);
        if (set == null || !set.remove(key))
            throw new IllegalStateException("cannot remove key " + key + " with value " + value
                    + " - did you insert " + key + "," + value + " before?");
        size--;
        if (set.isEmpty())
            map.remove(value);
    }

    public void update(int key, int oldValue, int value) {
        remove(key, oldValue);
        insert(key, value);
    }

    public void insert(int key, int value) {
        TIntHashSet set = map.get(value);
        if (set == null)
            map.put(value, set = new TIntHashSet(slidingMeanValue));
//        else
//            slidingMeanValue = Math.max(5, (slidingMeanValue + set.size()) / 2);
        if (!set.add(key))
            throw new IllegalStateException("use update if you want to update " + key);
        size++;
    }

    public int peekValue() {
        if (size == 0)
            throw new IllegalStateException("collection is already empty!?");
        Entry<Integer, TIntHashSet> e = map.firstEntry();
        if (e.getValue().isEmpty())
            throw new IllegalStateException("internal set is already empty!?");
        return map.firstEntry().getKey();
    }

    public int peekKey() {
        if (size == 0)
            throw new IllegalStateException("collection is already empty!?");
        TIntHashSet set = map.firstEntry().getValue();
        if (set.isEmpty())
            throw new IllegalStateException("internal set is already empty!?");
        return set.iterator().next();
    }

    public int pollKey() {
        size--;
        if (size < 0)
            throw new IllegalStateException("collection is already empty!?");
        Entry<Integer, TIntHashSet> e = map.firstEntry();
        TIntHashSet set = e.getValue();
        TIntIterator iter = set.iterator();
        if (set.isEmpty())
            throw new IllegalStateException("internal set is already empty!?");
        int val = iter.next();
        iter.remove();
        if (set.isEmpty())
            map.remove(e.getKey());
        return val;
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public int getSlidingMeanValue() {
        return slidingMeanValue;
    }

    @Override
    public String toString() {
        return "size " + size + " min=(" + peekKey() + "=>" + peekValue() + ")";
    }
}

Ответ 2

Когда вам нужна сортированная коллекция, вы должны тщательно проанализировать свои потребности.
Если большинство операций вставляются, и только некоторые из них должны искать, то используя отсортированную коллекцию, то есть постоянно сохраняйте элементы, отсортированные в коллекции, не будет хорошим вариантом (из-за накладных расходов на сохранение элементов, отсортированных по вставке, которые будут наиболее распространенная операция).
В этом случае было бы лучше сохранить несортированную коллекцию и выполнить сортировку только тогда, когда это необходимо. То есть перед поиском. Вы даже можете использовать простой List и отсортировать его (используя Collections.sort i.e. mergesort), когда это необходимо. Но я рекомендую это с осторожностью, так как для этого важно, чтобы вы работали над большими данными. В действительно небольших данных даже линейный поиск достаточно хорош.

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

Ответ 3

Как насчет guava TreeMultiset? Что вы просили: сортированная коллекция, которая принимает дубликаты. Однако не знаю ничего о его производительности.

Ответ 4

Вам нужно решить, хотите ли вы внешние зависимости или нет. Я бы не сделал свою собственную реализацию для чего-то вроде этого.

Тем не менее, вы почти ничего не сказали нам о том, для чего вы это используете, и о том, что вы собираетесь с ним делать. Без достаточного количества данных, мы можем только сказать вам, действительно ли вам нужно получить доступ к элементам в случайном порядке? Насколько вы ожидаете от этой коллекции? У нас действительно недостаточно данных, чтобы выбрать одну правильную структуру данных для ваших нужд.

Тем не менее, вот некоторые варианты, которые я бы рассмотрел.

• ArrayList или PriorityQueue, в зависимости от того, действительно ли вам нужно поддерживать remove(Object). Вы? Ты уверен? (Даже если вам нужно поддерживать remove(Object), я бы выбрал этот вариант, если коллекция, вероятно, останется малой.)
• Не привязан к TreeList, а вместо Apache Commons Collections TreeList. Несмотря на название, он фактически не поддерживает отсортированный порядок, но то, что он делает, это поддержка O (log n), добавление, удаление и получение из любого места в списке. Используя бинарный поиск, вы можете потенциально достичь O ((log n) ^ 2) времени для добавления, удаления или поиска в соответствии с отсортированной частью ваших значений.
• TreeList, с которым вы связаны, или - если вы похожи на меня и заботитесь о контракте List - пользовательский Guava ListMultimap, полученный с помощью Multimaps.newListMultimap(new TreeMap<K, Collection<V>>, new Supplier<List<V>>() { public List<V> get() { return new ArrayList<V>(); }}).

Если вы также заботитесь о примитивном боксе или не можете мириться со сторонними зависимостями, у вас не будет выбора, кроме как написать свою собственную структуру данных. Я бы только адаптировал одну из реализаций выше к вашему примитивному типу, но это будет боль в королевстве.

Наконец: мне бы очень хотелось услышать ваш случай использования. У Guava нет поддержки для таких вещей, потому что у нас не было достаточного спроса или было замечено использование, для которого действительно уместна более сложная структура данных.

Ответ 5

Я бы пошел с skiplist - больше памяти, чем дерево, позволяет дублировать, обеспечивает O (logn) для вставок и удалений. Вы даже можете реализовать индексированный скипист, это позволит вам иметь индексированный доступ, что трудно получить с деревом.

Ответ 6

У меня есть хороший опыт работы с TreeMultimap http://guava-libraries.googlecode.com/svn/tags/release05/javadoc/com/google/common/collect/TreeMultimap.html