Priority Queue 와 Queue 의 변체 실현
예 를 들 어 우 리 는 시간 에 따라 순 위 를 매 긴 가장 가 까 운 로그 인 사이트 의 20 명 을 기록 해 야 한다.점수 순 으로 가장 높 은 30 명;예 를 들 어 게임 에서 두 개의 PK 의 전투 에서 가장 높 은 점 수 를 받 은 6 명;이러한 기능 을 실현 하려 면 필요 한 데이터 구 조 는 자바 라 이브 러 리 에 기 존 클래스 가 없습니다.우 리 는 기 존의 라 이브 러 리 를 이용 하여 그것들 을 실현 해 야 한다.
1. 고정 크기 의 '먼저 나 가기' 대기 열
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.concurrent.LinkedBlockingQueue;
public class TopQueue {
private final LinkedBlockingQueue blockQueue;
public TopQueue(int size){
this.blockQueue = new LinkedBlockingQueue(size);
}
public synchronized void put(E e) throws InterruptedException{
if(blockQueue.offer(e)){
return;
}else{
blockQueue.take();
blockQueue.offer(e);
}
}
public List getAll(){
return new ArrayList(blockQueue);
}
public static void main(String[] args) throws InterruptedException{
TopQueue tq = new TopQueue(3);
tq.put(1);
tq.put(2);
tq.put(3);
System.out.println(Arrays.toString(tq.getAll().toArray()));
tq.put(4);
System.out.println(Arrays.toString(tq.getAll().toArray()));
tq.put(5);
System.out.println(Arrays.toString(tq.getAll().toArray()));
tq.put(6);
System.out.println(Arrays.toString(tq.getAll().toArray()));
}
} 출력 결과:
[1, 2, 3]
[2, 3, 4]
[3, 4, 5]
[4, 5, 6]위의 TopQueue 는 '고정 크기 의 스 레 드 안전' 대기 열 을 실현 합 니 다.몇 개의 스 레 드 가 있 든 TopQueue 에 몇 개의 요 소 를 넣 었 는 지, TopQueue 에 서 는 마지막 으로 넣 은 n 개의 요소 만 유지 합 니 다.
2. 고정 크기 의 우선 순위 대기 열 (구현 1)
import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.PriorityBlockingQueue;
import com.alibaba.fastjson.JSON;
public class TopPriorityQueue {
private final PriorityBlockingQueue blockQueue;
private final int size;
public TopPriorityQueue(int size){
this.blockQueue = new PriorityBlockingQueue(size + 1);
this.size = size + 1; // 1 put ， ， 1 " "
}
public synchronized void put(E e) throws InterruptedException{
if(blockQueue.size() >= size)
blockQueue.take();
blockQueue.offer(e);
}
public List getAll() throws InterruptedException{
synchronized(this){
if(blockQueue.size() >= size)
blockQueue.take(); // 1，
}
return new ArrayList(blockQueue);
}
public static void main(String[] args) throws InterruptedException{
final TopPriorityQueue tq = new TopPriorityQueue(3);
User u1 = new User(1, "bbb", 10);
User u2 = new User(2, "ccc", 20);
User u3 = new User(3, "ddd", 30);
User u4 = new User(4, "fff", 40);
User u5 = new User(5, "fff", 50);
User u6 = new User(6, "ddd", 60);
User u7 = new User(7, "ggg", 70);
User u8 = new User(8, "hhh", 80);
tq.put(u4); //4
System.out.println(JSON.toJSONString(tq.getAll()));
tq.put(u8); //4,8
System.out.println(JSON.toJSONString(tq.getAll()));
tq.put(u7); //4,8,7
System.out.println(JSON.toJSONString(tq.getAll()));
tq.put(u5); //5,8,7
System.out.println(JSON.toJSONString(tq.getAll()));
tq.put(u2); //5,8,7
System.out.println(JSON.toJSONString(tq.getAll()));
tq.put(u3); //5,8,7
System.out.println(JSON.toJSONString(tq.getAll()));
tq.put(u1); //5,8,7
System.out.println(JSON.toJSONString(tq.getAll()));
tq.put(u6); //6,8,7
System.out.println(JSON.toJSONString(tq.getAll()));
}
} User 클래스:
import java.util.Comparator;
public class User implements Comparable{
private int id;
private String name;
private long score; //
// ... ...
public User(int id, String name, long score){
this.id = id;
this.name = name;
this.score = score;
}
public int getId() {
return id;
}
public void setId(int id) {
this.id = id;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public long getScore() {
return score;
}
public void setScore(long score) {
this.score = score;
}
@Override
public int compareTo(User o) {
return this.getScore() > o.getScore() ? 1 : this.getScore() < o.getScore() ? -1 : 0;
}
} 입력 한 결 과 는:
[{"id":4,"name":"fff","score":40}]
[{"id":4,"name":"fff","score":40},{"id":8,"name":"hhh","score":80}]
[{"id":4,"name":"fff","score":40},{"id":8,"name":"hhh","score":80},{"id":7,"name":"ggg","score":70}]
[{"id":5,"name":"fff","score":50},{"id":8,"name":"hhh","score":80},{"id":7,"name":"ggg","score":70}]
[{"id":5,"name":"fff","score":50},{"id":8,"name":"hhh","score":80},{"id":7,"name":"ggg","score":70}]
[{"id":5,"name":"fff","score":50},{"id":8,"name":"hhh","score":80},{"id":7,"name":"ggg","score":70}]
[{"id":5,"name":"fff","score":50},{"id":8,"name":"hhh","score":80},{"id":7,"name":"ggg","score":70}]
[{"id":6,"name":"ddd","score":60},{"id":8,"name":"hhh","score":80},{"id":7,"name":"ggg","score":70}]TopPriority Queue 는 '고정 크기 의 우선 대기 열' 을 실 현 했 습 니 다. 실현 원 리 는 다음 과 같 습 니 다.
public synchronized void put(E e) throws InterruptedException{ if(blockQueue.size() >= size) blockQueue.take(); blockQueue.offer(e); }
대기 열 이 가득 찼 을 때, 또 삽입 해 야 할 때, 대기 열 중 가장 작은 하 나 를 삭제 한 다음 삽입 합 니 다. 그러나 여기에 문제 가 있 습 니 다. 만약 에 이 삽입 할 요소 의 우선 순위 가 삭 제 된 요소 의 우선 순위 보다 낮다 면, 그것 은 큰 것 을 삭제 하 는 것 이 아니 라 오히려 작은 것 을 삽입 하 는 것 입 니 다. 그래서 여기 서 우리 가 취 하 는 방법 은 실제 요구 하 는 size 를 바탕 으로 하 는 것 입 니 다.하 나 를 더 남 겨 두 고 '호루라기 카드' 로 사용 합 니 다. 대기 열 이 가득 찼 을 때, 우 리 는 '호루라기 카드' 를 삭제 한 후에 우리 의 요 소 를 삽입 합 니 다. 그리고 대기 열 에 있 는 새로운 가장 작은 요 소 는 새로운 '호루라기 카드' 가 됩 니 다. 그리고 '호루라기 카드' 입 니 다.가장 작은 것 이기 때문에 우리 가 필요 로 하 는 것 이 아니 라 최종 결 과 를 되 돌 릴 때 삭 제 됩 니 다. 따라서 큰 것 을 삭제 하고 작은 문 제 를 삽입 하지 않 습 니 다. 여기 에는 작은 기술 이 있 습 니 다.
3. 고정 크기 의 우선 대기 열 (구현 2)
위의 실현 은 우리 가 대기 열 에 있 는 요소 인 Comparable 인 터 페 이 스 를 삽입 해 야 합 니 다. 그러나 실제 환경 에서 우 리 는 이러한 수정 을 할 수 없습니다. 그래서 우 리 는 또 다른 방법 이 있 습 니 다. Comparator 를 사용 하여 해결 하고 코드 를 봅 니 다.
import java.util.Comparator;
import com.coin.User;
public class MyComparator implements Comparator {
@Override
public int compare(User u1, User u2) {
if(u1.getScore() > u2.getScore())
return 1;
if(u1.getScore() < u2.getScore())
return -1;
return 0;
}
} import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.concurrent.PriorityBlockingQueue;
import com.alibaba.fastjson.JSON;
public class TopPriorityQueue {
private final PriorityBlockingQueue blockQueue;
private final int size;
public TopPriorityQueue(int size, Comparator comparator){
this.blockQueue = new PriorityBlockingQueue(size + 1, comparator);
this.size = size + 1; // 1 put ， ， 1 " "
}
public synchronized void put(E e) throws InterruptedException{
if(blockQueue.size() >= size)
blockQueue.take();
blockQueue.offer(e);
}
public List getAll() throws InterruptedException{
synchronized(this){
if(blockQueue.size() >= size)
blockQueue.take(); // 1，
}
return new ArrayList(blockQueue);
}
public static void main(String[] args) throws InterruptedException{
MyComparator myComparator = new MyComparator();
final TopPriorityQueue tq = new TopPriorityQueue(3, myComparator);
User u1 = new User(1, "bbb", 10);
User u2 = new User(2, "ccc", 20);
User u3 = new User(3, "ddd", 30);
User u4 = new User(4, "fff", 40);
User u5 = new User(5, "fff", 50);
User u6 = new User(6, "ddd", 60);
User u7 = new User(7, "ggg", 70);
User u8 = new User(8, "hhh", 80);
tq.put(u4); //4
System.out.println(JSON.toJSONString(tq.getAll()));
tq.put(u8); //4,8
System.out.println(JSON.toJSONString(tq.getAll()));
tq.put(u7); //4,8,7
System.out.println(JSON.toJSONString(tq.getAll()));
tq.put(u5); //5,8,7
System.out.println(JSON.toJSONString(tq.getAll()));
tq.put(u2); //5,8,7
System.out.println(JSON.toJSONString(tq.getAll()));
tq.put(u3); //5,8,7
System.out.println(JSON.toJSONString(tq.getAll()));
tq.put(u1); //5,8,7
System.out.println(JSON.toJSONString(tq.getAll()));
tq.put(u6); //6,8,7
System.out.println(JSON.toJSONString(tq.getAll()));
}
} 그래서 우 리 는 Priority BlockingQueue 를 사용 할 때 우리 가 삽입 한 요소 가 Comparable 이라는 인 터 페 이 스 를 실현 하거나 Comparator 를 정의 하여 Priority BlockingQueue 의 구조 함수 에 들 어가 면 Priority BlockingQueue. offer (e) 방법의 소스 코드 를 볼 수 있 습 니 다. 이 두 가지 상황 을 판단 할 수 있 습 니 다.
public boolean offer(E e) {
if (e == null)
throw new NullPointerException();
final ReentrantLock lock = this.lock;
lock.lock();
int n, cap;
Object[] array;
while ((n = size) >= (cap = (array = queue).length))
tryGrow(array, cap);
try {
Comparator super E> cmp = comparator;
if (cmp == null)
siftUpComparable(n, e, array);
else
siftUpUsingComparator(n, e, array, cmp);
size = n + 1;
notEmpty.signal();
} finally {
lock.unlock();
}
return true;
}그 중의 코드:
Comparator super E> cmp = comparator;
if (cmp == null)
siftUpComparable(n, e, array);
else
siftUpUsingComparator(n, e, array, cmp);Priority BlockingQueue 의 구조 함수 에 Comparator 가 들 어 왔 는 지 여 부 를 판단 하 는 것 입 니 다. 그러면 User 류 는 Comparable 인 터 페 이 스 를 실현 할 필요 가 없습니다.
그리고 우 리 는 링크 드 블록 링 큐 에 주의해 야 한다. 화해시키다 Priority BlockingQueue 는 조금 다 릅 니 다. BlockingQueue. offer (e) 는 대기 열 이 가득 찼 을 때 false 로 돌아 갑 니 다. Priority BlockingQueue. offer () 는 대기 열 이 가득 찼 더 라 도 확장 되 어 true 로 만 영원히 돌아 갑 니 다.
LinkedBlockingQueue .offer () 의 원본 코드 는 다음 과 같 습 니 다.
/**
* Inserts the specified element at the tail of this queue if it is
* possible to do so immediately without exceeding the queue's capacity,
* returning {@code true} upon success and {@code false} if this queue
* is full.
* When using a capacity-restricted queue, this method is generally
* preferable to method {@link BlockingQueue#add add}, which can fail to
* insert an element only by throwing an exception.
*
* @throws NullPointerException if the specified element is null
*/
public boolean offer(E e) {
if (e == null) throw new NullPointerException();
final AtomicInteger count = this.count;
if (count.get() == capacity)
return false;
int c = -1;
Node node = new Node(e);
final ReentrantLock putLock = this.putLock;
putLock.lock();
try {
if (count.get() < capacity) {
enqueue(node);
c = count.getAndIncrement();
if (c + 1 < capacity)
notFull.signal();
}
} finally {
putLock.unlock();
}
if (c == 0)
signalNotEmpty();
return c >= 0;
} 가득 찼 을 때 false 로 돌아 가기:
if (count.get() == capacity) return false;
Priority BlockingQueue. offer () 의 원본 코드 는 다음 과 같 습 니 다.
/**
* Inserts the specified element into this priority queue.
* As the queue is unbounded, this method will never return {@code false}.
*
* @param e the element to add
* @return {@code true} (as specified by {@link Queue#offer})
* @throws ClassCastException if the specified element cannot be compared
* with elements currently in the priority queue according to the
* priority queue's ordering
* @throws NullPointerException if the specified element is null
*/
public boolean offer(E e) {
if (e == null)
throw new NullPointerException();
final ReentrantLock lock = this.lock;
lock.lock();
int n, cap;
Object[] array;
while ((n = size) >= (cap = (array = queue).length))
tryGrow(array, cap);
try {
Comparator super E> cmp = comparator;
if (cmp == null)
siftUpComparable(n, e, array);
else
siftUpUsingComparator(n, e, array, cmp);
size = n + 1;
notEmpty.signal();
} finally {
lock.unlock();
}
return true;
}꽉 찼 을 때 용량 을 늘 립 니 다.
while ((n = size) >= (cap = (array = queue).length)) tryGrow(array, cap);
As the queue is unbounded, this method will never return {@code false}.
또한 TopQueue 와 TopPriority Queue 는 모두 스 레 드 가 안전 하지만 대기 열 에 삽 입 된 요소 자체 의 스 레 드 안전성 을 보장 하지 않 습 니 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
