Неизменяемая очередь приоритетов в Guava

Question

Я пытаюсь сделать неизменяемую очередь приоритетов с помощью библиотеки Guava. В качестве «backend» в очереди я использовал ImmutableSortedMultiset. Но у меня проблема с производительностью - толчок работы и поп очень медленные. Каков наилучший способ добавить и удалить отдельный элемент из сортированной неизменяемой коллекции? Спасибо!

Это мой код:

public class ImmutablePriorityQueue<T extends Comparable<T>> implements PriorityQueue<T> { 

    private final ImmutableSortedMultiset<T> multiset; 

    private ImmutablePriorityQueue() { 
     this(ImmutableSortedMultiset.<T>of()); 
    } 

    private ImmutablePriorityQueue(ImmutableSortedMultiset<T> multiset) { 
     this.multiset = multiset; 
    } 

    public static <T extends Comparable<T>> PriorityQueue<T> createEmpty() { 
     return new ImmutablePriorityQueue<T>(); 
    } 

    @Override 
    public T peek() { 
     if (isEmpty()) throw new EmptyCollectionException(); 
     return multiset.firstEntry().getElement(); 
    } 

    @Override 
    public PriorityQueue<T> push(T element) { 
     ImmutableSortedMultiset.Builder<T> builder = multiset.naturalOrder(); 
     return new ImmutablePriorityQueue<T>(builder.add(element).addAll(multiset.asList()).build()); 
    } 

    @Override 
    public PriorityQueue<T> pop() { 
     if (isEmpty()) throw new EmptyCollectionException(); 
     ImmutableSortedMultiset.Builder<T> builder = multiset.naturalOrder(); 
     return new ImmutablePriorityQueue<T>(builder.addAll(multiset.asList().subList(1, size())).build()); 
    } 

    @Override 
    public PriorityQueue<T> clear() { 
     return new ImmutablePriorityQueue<T>(); 
    } 

    @Override 
    public int size() { 
     return multiset.size(); 
    } 

    @Override 
    public boolean isEmpty() { 
     return multiset.isEmpty(); 
    } 
} 

Answer 1

Это больше похоже на структуру данных «CopyOnWrite», по крайней мере, это то, как это называется в Java. Возможно, вам стоит взглянуть на реализацию CopyOnWriteArrayList, но все же это отличается тем, что она не возвращает копию объекта, а блокирует внутреннее состояние и создает его копию.

Неизменные объекты гуавы обычно запрещают изменения, внесенные в объект, то есть отрывок из ImmutableList:

@Deprecated 
@Override 
public final E set(int index, E element) { 
    throw new UnsupportedOperationException(); 
} 

Теперь, что касается производительности pop() операции asList() создаст временный массив для хранения элементов, так создавая копию таким образом, предположительно, имеют меньшие накладные расходы:

TreeMultiset<String> original = TreeMultiset.create(Arrays.asList("a", "b", "a", "c", "b", "d")); 
System.out.println("original: " + original); 

SortedMultiset<String> tail = ImmutableSortedMultiset.copyOfSorted(original.tailMultiset(original.firstEntry().getElement(), BoundType.OPEN)); 
System.out.println("tail: " + tail); 

идея заключается в том, чтобы взять первую запись и запрос для диапазона с ним быть оставлена ​​открытой границей (меня aning "исключая"). Эта печать:

original: [a x 2, b x 2, c, d] 
tail: [b x 2, c, d] 

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