我尝试使用 Guava 库制作不可变的优先级队列。作为队列“后端”,我使用 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();
}
}
最佳答案
这看起来更像是一个“CopyOnWrite”数据结构,至少在 Java 中是这样称呼的。您可能想看看CopyOnWriteArrayList
的实现,但它仍然不同,因为它不返回对象的副本,而是锁定内部状态并创建它的副本。
Guava 中的不可变对象(immutable对象)通常禁止对对象进行修改,即摘录自 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);
这个想法是获取第一个条目并查询一个范围,该范围是左开边界(意思是“排除”)。这打印:
original: [a x 2, b x 2, c, d]
tail: [b x 2, c, d]
您可能还需要返回一对新创建的集合和一个已弹出的元素,以免丢失已弹出的元素。这只是一个想法,我不确定这种方法是否在任何地方使用。
关于java - Guava 中的不可变优先级队列,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/20729597/