[SCALA] 고정 용량 및 사용자 정의 비교 사용해, PriorityQueue 구현이 있습니까?

고정 용량 및 사용자 정의 비교 사용해, PriorityQueue 구현이 있습니까?

관련 질문 :

나는 매우 큰 데이터 세트 (5 개 이상 수백만 항목)하고 난 그것에서 N 가장 큰 항목을 얻을 필요가있다. 그것을 할 수있는 가장 자연스러운 방법은 상위 N 항목을 저장하는 힙 / 우선 순위 큐를 사용하는 것입니다. 즉 JVM (스칼라 / 자바)에 대한 우선 순위 큐의 몇 가지 좋은 구현이 있습니다 :

먼저이 좋은,하지만 그들은 내 경우 중요한 메모리 오버 헤드를 제공하는 모든 항목을 저장합니다. 세 번째 (루씬 구현)는 이러한 단점을 가지고 있지 않지만, 내가 문서에서 볼 수 있듯이 그것은 또한 나를 위해 그것을 쓸모있게 사용자 정의 비교를 지원하지 않습니다.

그래서, 내 질문은 : 거기 고정 된 용량과 사용자 정의 비교 사용해, PriorityQueue 구현은?

UPD. 마지막으로 나는 베드로의 답변에 따라 내 자신의 구현을 만들었습니다 :

public class FixedSizePriorityQueue<E> extends TreeSet<E> {

    private int elementsLeft;

    public FixedSizePriorityQueue(int maxSize) {
        super(new NaturalComparator());
        this.elementsLeft = maxSize;
    }

    public FixedSizePriorityQueue(int maxSize, Comparator<E> comparator) {
        super(comparator);
        this.elementsLeft = maxSize;
    }


    /**
     * @return true if element was added, false otherwise
     * */
    @Override
    public boolean add(E e) {
        if (elementsLeft == 0 && size() == 0) {
            // max size was initiated to zero => just return false
            return false;
        } else if (elementsLeft > 0) {
            // queue isn't full => add element and decrement elementsLeft
            boolean added = super.add(e);
            if (added) {
                elementsLeft--;
            }
            return added;
        } else {
            // there is already 1 or more elements => compare to the least
            int compared = super.comparator().compare(e, this.first());
            if (compared == 1) {
                // new element is larger than the least in queue => pull the least and add new one to queue
                pollFirst();
                super.add(e);
                return true;
            } else {
                // new element is less than the least in queue => return false
                return false;
            }
        }
    }
}

(NaturalComparator이 질문에서 수행되는 곳)

해결법

1. ==============================

   1.당신은 예를 들어, SortedSet의를 사용할 수 있습니다 사용자 정의 비교와 TreeSet의와 크기가 N을 reachs 때 작은 제거

   당신은 예를 들어, SortedSet의를 사용할 수 있습니다 사용자 정의 비교와 TreeSet의와 크기가 N을 reachs 때 작은 제거

2. ==============================

   2.당신은 어떻게 루씬의 사용자 정의 비교를 지원하지 않습니다 말할 수 있습니까?

   당신은 어떻게 루씬의 사용자 정의 비교를 지원하지 않습니다 말할 수 있습니까?

   그 추상적이고 당신은 추상적 인 방법 작음를 구현해야합니다 (T의 A, T 나)

3. ==============================

   3.하지만 오래된 질문이지만 그것은 다른 사람에게 도움이 될 수 있습니다. Google의 자바 라이브러리 구아바의 minMaxPriorityQueue를 사용할 수 있습니다.

   하지만 오래된 질문이지만 그것은 다른 사람에게 도움이 될 수 있습니다. Google의 자바 라이브러리 구아바의 minMaxPriorityQueue를 사용할 수 있습니다.

4. ==============================

   4.나는 즉시 사용 하나 생각할 수 없다,하지만 당신은 유사한 요구 사항이 컬렉션의 내 구현을 확인할 수 있습니다.

   나는 즉시 사용 하나 생각할 수 없다,하지만 당신은 유사한 요구 사항이 컬렉션의 내 구현을 확인할 수 있습니다.

   차이는 비교이지만 PriorityQueue 인에서 확장하는 경우에 당신은 그것을해야합니다. 그리고 각 추가에 당신이 한계에 도달하지 않은 경우 확인하고, 당신이있는 경우 - 마지막 항목을 놓습니다.

5. ==============================

   5.아래는 내가 전에 사용되는 구현입니다. 피터의 제안을 준수합니다.

   아래는 내가 전에 사용되는 구현입니다. 피터의 제안을 준수합니다.

    public @interface NonThreadSafe {
    }
   
   /**
    * A priority queue implementation with a fixed size based on a {@link TreeMap}.
    * The number of elements in the queue will be at most {@code maxSize}.
    * Once the number of elements in the queue reaches {@code maxSize}, trying to add a new element
    * will remove the greatest element in the queue if the new element is less than or equal to
    * the current greatest element. The queue will not be modified otherwise.
    */
   @NonThreadSafe
   public static class FixedSizePriorityQueue<E> {
       private final TreeSet<E> treeSet; /* backing data structure */
       private final Comparator<? super E> comparator;
       private final int maxSize;
   
       /**
        * Constructs a {@link FixedSizePriorityQueue} with the specified {@code maxSize}
        * and {@code comparator}.
        *
        * @param maxSize    - The maximum size the queue can reach, must be a positive integer.
        * @param comparator - The comparator to be used to compare the elements in the queue, must be non-null.
        */
       public FixedSizePriorityQueue(final int maxSize, final Comparator<? super E> comparator) {
           super();
           if (maxSize <= 0) {
               throw new IllegalArgumentException("maxSize = " + maxSize + "; expected a positive integer.");
           }
           if (comparator == null) {
               throw new NullPointerException("Comparator is null.");
           }
           this.treeSet = new TreeSet<E>(comparator);
           this.comparator = treeSet.comparator();
           this.maxSize = maxSize;
       }
   
       /**
        * Adds an element to the queue. If the queue contains {@code maxSize} elements, {@code e} will
        * be compared to the greatest element in the queue using {@code comparator}.
        * If {@code e} is less than or equal to the greatest element, that element will be removed and
        * {@code e} will be added instead. Otherwise, the queue will not be modified
        * and {@code e} will not be added.
        *
        * @param e - Element to be added, must be non-null.
        */
       public void add(final E e) {
           if (e == null) {
               throw new NullPointerException("e is null.");
           }
           if (maxSize <= treeSet.size()) {
               final E firstElm = treeSet.first();
               if (comparator.compare(e, firstElm) < 1) {
                   return;
               } else {
                   treeSet.pollFirst();
               }
           }
           treeSet.add(e);
       }
   
       /**
        * @return Returns a sorted view of the queue as a {@link Collections#unmodifiableList(java.util.List)}
        *         unmodifiableList.
        */
       public List<E> asList() {
           return Collections.unmodifiableList(new ArrayList<E>(treeSet));
       }
   }
   

   나는 BTW 어떤 의견을 보내 주셔서 감사합니다.

   편집 : 그것은 TreeSet의를 사용하는 것 같아하면 통화가 먼저 (가) sublinear 시간이 걸릴 것 같다하기 위해 결국 때문에 매우 효율적이지 않습니다. 내가 사용해, PriorityQueue에 TreeSet의 변경. 수정 된 추가 () 메소드는 다음과 같습니다 :

      /**
        * Adds an element to the queue. If the queue contains {@code maxSize} elements, {@code e} will
        * be compared to the lowest element in the queue using {@code comparator}.
        * If {@code e} is greater than or equal to the lowest element, that element will be removed and
        * {@code e} will be added instead. Otherwise, the queue will not be modified
        * and {@code e} will not be added.
        *
        * @param e - Element to be added, must be non-null.
        */
       public void add(final E e) {
           if (e == null) {
               throw new NullPointerException("e is null.");
           }
           if (maxSize <= priorityQueue.size()) {
               final E firstElm = priorityQueue.peek();
               if (comparator.compare(e, firstElm) < 1) {
                   return;
               } else {
                   priorityQueue.poll();
               }
           }
           priorityQueue.add(e);
       }
   

6. ==============================

   6.정확히 내가 무엇을 찾고 있었다. 그러나, 구현은 버그를 포함 :

   정확히 내가 무엇을 찾고 있었다. 그러나, 구현은 버그를 포함 :

   즉 : elementsLeft> 0 및 전자 경우 이미 TreeSet의에 포함되어 있습니다. 이 경우, elementsLeft 감소되지만 TreeSet의 요소의 수는 동일하게 유지.

   나는에 의해 추가 () 메소드에서 해당 라인을 대체하는 제안

           } else if (elementsLeft > 0) {
           // queue isn't full => add element and decrement elementsLeft
           boolean added = super.add(e);
           if (added) {
               elementsLeft--;
           }
           return added;
   

7. ==============================

   7.이 코드를보십시오 :

   이 코드를보십시오 :

   public class BoundedPQueue<E extends Comparable<E>> {
   /**
    * Lock used for all public operations
    */
   private final ReentrantLock lock;
   
   PriorityBlockingQueue<E> queue ;
   int size = 0;
   
   public BoundedPQueue(int capacity){
       queue = new PriorityBlockingQueue<E>(capacity, new CustomComparator<E>());
       size = capacity;
       this.lock = new ReentrantLock();
   
   }
   
   public boolean offer(E e) {
   
   
       final ReentrantLock lock = this.lock;
       lock.lock();
       E vl = null;
       if(queue.size()>= size)  {
           vl= queue.poll();
           if(vl.compareTo(e)<0)
               e=vl;
       }
   
       try {
           return queue.offer(e);
       } finally {
           lock.unlock();
       }
   
   
   }
   
   public E poll()  {
   
       return queue.poll();
   }
   
   public static class CustomComparator<E extends Comparable<E>> implements Comparator<E> {
   
   
       @Override
       public int compare(E o1, E o2) {
           //give me a max heap
            return o1.compareTo(o2) *-1;
   
       }
   }
   
   }
   

8. ==============================

   8.다음은 구아바이있는 경우 내가 함께 넣어 하나입니다. 나는 꽤 완전한 생각합니다. 내가 뭔가를 놓친 경우 알려주세요.

   다음은 구아바이있는 경우 내가 함께 넣어 하나입니다. 나는 꽤 완전한 생각합니다. 내가 뭔가를 놓친 경우 알려주세요.

   당신은 모든 다른 방법을지도 할 필요가 없습니다 당신은 대기열을 차단 구아바의 전달을 사용할 수 있습니다.

   import com.google.common.util.concurrent.ForwardingBlockingQueue;
   
   public class PriorityBlockingQueueDecorator<E> extends
           ForwardingBlockingQueue<E> {
   
       public static final class QueueFullException extends IllegalStateException {
   
           private static final long serialVersionUID = -9218216017510478441L;
   
       }
   
       private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
   
       private int maxSize;
   
       private PriorityBlockingQueue<E> delegate;
   
       public PriorityBlockingQueueDecorator(PriorityBlockingQueue<E> delegate) {
           this(MAX_ARRAY_SIZE, delegate);
       }
   
       public PriorityBlockingQueueDecorator(int maxSize,
               PriorityBlockingQueue<E> delegate) {
           this.maxSize = maxSize;
           this.delegate = delegate;
       }
   
       @Override
       protected BlockingQueue<E> delegate() {
           return delegate;
       }
   
       @Override
       public boolean add(E element) {
           return offer(element);
       }
   
       @Override
       public boolean addAll(Collection<? extends E> collection) {
           boolean modified = false;
           for (E e : collection)
               if (add(e))
                   modified = true;
           return modified;
       }
   
       @Override
       public boolean offer(E e, long timeout, TimeUnit unit)
               throws InterruptedException {
           return offer(e);
       }
   
       @Override
       public boolean offer(E o) {
           if (maxSize > size()) {
               throw new QueueFullException();
           }
           return super.offer(o);
       }
   }
   

9. ==============================

   9.크기 제한이 사용해, PriorityQueue를 작성합니다. 그것은 N 최대 번호를 저장합니다.

   크기 제한이 사용해, PriorityQueue를 작성합니다. 그것은 N 최대 번호를 저장합니다.

   import java.util.*;
   
   class Demo
   {
       public static <E extends Comparable<E>> PriorityQueue<E> getPq(final int n, Comparator<E> comparator)
       {
           return new PriorityQueue<E>(comparator)
           {
               boolean full()
               {
                   return size() >= n;
               }
   
               @Override 
               public boolean add(E e)
               {
                   if (!full())
                   {
                       return super.add(e);
                   }
                   else if (peek().compareTo(e) < 0)
                   {
                       poll();
                       return super.add(e);
                   }
                   return false;
               }
   
               @Override
               public boolean offer(E e)
               {
                   if (!full())
                   {
                       return super.offer(e);
                   }
                   else if (peek().compareTo(e) < 0)
                   {
                       poll();
                       return super.offer(e);
                   }
                   return false;
               }
           };
       }
   
       public static void printq(PriorityQueue pq)
       {
           Object o = null;
           while ((o = pq.poll()) != null)
           {
               System.out.println(o);
           }
       }
   
       public static void main (String[] args)
       {
           PriorityQueue<Integer> pq = getPq(2, new Comparator<Integer>(){
           @Override
           public int compare(Integer i1, Integer i2)
           {
               return i1.compareTo(i2);
           }
           });
           pq.add(4);
           pq.add(1);
           pq.add(5);
           pq.add(2);
           printq(pq);
       }
   }
   

from https://stackoverflow.com/questions/7878026/is-there-a-priorityqueue-implementation-with-fixed-capacity-and-custom-comparato by cc-by-sa and MIT license