具有优先级和时间的多字段排序的队列

Question

意图

实现具有基于1)优先级和2)时间的排序的任务队列,具体地,创建任务的时间或时间戳(未插入队列中),优先考虑具有较旧时间戳的任务.

试着

这是我到目前为止所得到的; 比我想象的要简单得多,不仅仅需要一个PriorityQueue.在比较器中,如果两个优先级相等,则进行另一个比较Task.time,否则,比较基于just Task.priority.

import java.util.Comparator;
import java.util.PriorityQueue;

public class QueueWithPriorityAndTimeSort {
   enum TaskPriority {
      High, Medium, Low
   }

   class Task implements Comparable<Task> {   
      long time;
      TaskPriority priority;

      Task(TaskPriority p, long t) {      
         time = t;
         priority = p;
      }

      public int compareTo(Task task2) {
         return priority.compareTo(task2.priority);
      }
   }

   class HighPriorityWithTimeComparator implements Comparator<Task> {
      public int compare(Task task1, Task task2) {
         int compareResult = task1.compareTo(task2);
         if( compareResult == 0){           
            //same priority, now compare on time
            if( task2.time < task1.time)
               compareResult = 1;
            else 
               compareResult = -1;
         }                          
         return compareResult;
      }
   }

   public void buildAndTestQueue(){
      PriorityQueue<Task> queue = 
            new PriorityQueue<Task>(3, new HighPriorityWithTimeComparator());
      queue.add(new Task(TaskPriority.High, 9));
      queue.add(new Task(TaskPriority.Low, 7));
      queue.add(new Task(TaskPriority.Low, 3));
      queue.add(new Task(TaskPriority.High, 2));
      queue.add(new Task(TaskPriority.Medium, 5));
      queue.add(new Task(TaskPriority.Medium, 4));
      queue.add(new Task(TaskPriority.High, 6));
      queue.add(new Task(TaskPriority.High, 8));
      queue.add(new Task(TaskPriority.Low, 15));
      queue.add(new Task(TaskPriority.Low, 10));

      Task m = null;
      while ((m = queue.poll()) != null)
         System.out.println(
            String.format("Priority: %s, %d", m.priority, m.time));     
   }

   public static void main(String args[]) {
      QueueWithPriorityAndTimeSort queueTest = 
         new QueueWithPriorityAndTimeSort();
      queueTest.buildAndTestQueue();
   }
}

题

这是一种有效的方法吗？我不相信增加的比较器逻辑会改变时间复杂度; 除此之外,我没有看到任何明显的问题.

Answer 1

我的回答将解决您所做的以下评论:

将这些问题分开可以根据特定需求进行分类,从而提高灵活性

有更好的方法可以分离关注点并使代码更加灵活,这样您就可以在不更改代码的情况下更改排序策略.听起来很令人兴奋？

让我们首先定义一个比较器,用于比较优先级:

class HighPriorityComparator implements Comparator<Task> {
        public int compare(Task task1, Task task2) {
            return task1.priority.compareTo(task2.priority);
        }
    }

让我们定义一个比较器来比较时间:

class TimeComparator implements Comparator<Task> {
        public int compare(Task task1, Task task2) {
            int compareResult = 0;
            if (task2.time < task1.time)
                compareResult = 1;
            else
                compareResult = -1;

            return compareResult;
        }
    }

现在是最好的部分.让我们定义一个比较器,它允许您混合和匹配比较逻辑.

class MixAndMatchComparator implements Comparator<Task> {

        List<Comparator<Task>> comparators;

        public MixAndMatchComparator(List<Comparator<Task>> comparators) {
            this.comparators=comparators;
        }

        @Override
        public int compare(Task o1, Task o2) {
            int compareResult = 0;
            for(Comparator<Task> comparator : comparators) {
                if(comparator.compare(o1, o2)!=0) {
                    return comparator.compare(o1, o2);
                }
            }
            return compareResult;
        }

    }

现在让我们按优先级排序,如果优先级相等,那么按时排序:

List<Comparator<Task>> comparators = new ArrayList<Comparator<Task>>();
//first sort on priority            
comparators.add(new HighPriorityComparator());
//then on time
comparators.add(new TimeComparator());
MixAndMatchComparator orComparator = new MixAndMatchComparator(comparators);
PriorityQueue<Task> queue = new PriorityQueue<Task>(3, orComparator);

等待!你改变了主意？您现在想要按时间排序,如果时间相等,那么优先级是多少？只需更改将编译器添加到列表的顺序:

List<Comparator<Task>> comparators = new ArrayList<Comparator<Task>>();
//first sort on time    
comparators.add(new TimeComparator());
//then on priority
comparators.add(new HighPriorityComparator());
MixAndMatchComparator orComparator = new MixAndMatchComparator(comparators);
PriorityQueue<Task> queue = new PriorityQueue<Task>(3, orComparator);