问题：

在Java中，当优先级相同时，使优先级队列遵循FIFO顺序

白飞飙

2023-03-14

我正在研究一种算法，在该算法中，我希望在从该优先级队列中删除元素时，保持优先级队列中具有相同优先级的元素的FIFO顺序。

虽然，我已经看到了将自动递增的序列号作为辅助键的解决方案，并使用它来打破联系，但我需要类似的链接，但我面临的问题是，我想要比较的元素-TestItemChange（下面示例中的类）没有实现Compariable，我无法（也不想）修改它以使其实现。所以现在，在优先级队列中没有FIFO排序的情况下，我使用的是在创建时发送的比较器方法。

我现在唯一需要的就是在优先级相同的情况下使用FIFO。如何在下面的解决方案中实现自动递增的序号，而不使TestItemChange实现具有可比性？我在这些界面上做得不多，这里的任何指导都会非常有用。

任何线索都会很有帮助。

代码-

import java.util.*;
import java.util.stream.Collectors;

public class PriorityQueues {

  public static void main(String []args){
    TestPriorityQueue obj = new TestPriorityQueue();
    obj.build();
  }

  static class TestPriorityQueue {
    private static final Map<String, Integer> PINNED_EVENT_TYPE_PRIORITY_REMOVAL_MAP = new HashMap<>();

    public void build(){

        PINNED_EVENT_TYPE_PRIORITY_REMOVAL_MAP.put("fashionProduct", 0);
        PINNED_EVENT_TYPE_PRIORITY_REMOVAL_MAP.put("bonusContent", 1);

        final List<TestTimedItemChange> changesCollection = new ArrayList<>();

        final List<TestEvent> eventList = getEvents();
        final Map<String, String> eventIdToTypeMap = eventList.stream().collect(
                Collectors.toMap(TestEvent::getItemId, TestEvent::getEventType));

        final Queue<TestTimedItemChange> pinnedItemsInQuickView =
                new PriorityQueue<>(getTimedItemChangeComparator(eventIdToTypeMap));

        for (final TestEvent event : eventList) {
            final TestTimedItemChange newItemToAdd = buildTimedItemChange(event.getItemId(), event.getStartTime(),
                    "add");

            if (changesCollection.size() >= 4) {
                final TestTimedItemChange oldItemToRemove = pinnedItemsInQuickView.peek();
                changesCollection.add(buildTimedItemChange(oldItemToRemove.getItemId(),
                        Math.max(newItemToAdd.getTimePosition(), oldItemToRemove.getTimePosition()),
                        "remove"));
                changesCollection.add(newItemToAdd);
                pinnedItemsInQuickView.remove(oldItemToRemove);
                pinnedItemsInQuickView.add(newItemToAdd);

            } else {
                changesCollection.add(newItemToAdd);
                pinnedItemsInQuickView.add(newItemToAdd);
            }


        }

        changesCollection.stream().forEach(cc -> System.out.println(cc));

    }

    private TestTimedItemChange buildTimedItemChange(final String itemId, final long timePosition,
                                                     final String itemChangeType) {
        TestTimedItemChange testTimedItemChange = new TestTimedItemChange();
        testTimedItemChange.setItemId(itemId);
        testTimedItemChange.setChangeType(itemChangeType);
        testTimedItemChange.setTimePosition(timePosition);

        return testTimedItemChange;
    }

    private static Comparator<TestTimedItemChange> getTimedItemChangeComparator(final Map<String, String> eventIdToTypeMap) {
        Comparator<TestTimedItemChange> comparator = new Comparator<TestTimedItemChange>() {
            @Override
            public int compare(final TestTimedItemChange timedItemChange1, final TestTimedItemChange timedItemChange2) {
                final String eventType1 = eventIdToTypeMap.get(timedItemChange1.getItemId());
                final String eventType2 = eventIdToTypeMap.get(timedItemChange2.getItemId());
                if (eventType1.equals(eventType2)) {
                    //greater timeposition should be removed last.
                    return (int) (timedItemChange1.getTimePosition() - timedItemChange2.getTimePosition());
                }
                //greater priority should be removed last.
                return PINNED_EVENT_TYPE_PRIORITY_REMOVAL_MAP.get(eventIdToTypeMap.get(timedItemChange1.getItemId())) -
                        PINNED_EVENT_TYPE_PRIORITY_REMOVAL_MAP.get(eventIdToTypeMap.get(timedItemChange2.getItemId()));
            }
        };
        return comparator;
    }

    private List<TestEvent> getEvents() {
        List<TestEvent> eventList = new ArrayList<>();
        TestEvent event4 = new TestEvent();
        event4.setItemId("bts-0");
        event4.setEventType("bonusContent");
        event4.setStartTime(0L);
        eventList.add(event4);

        TestEvent event1 = new TestEvent();
        event1.setItemId("xst-prd-210");
        event1.setEventType("fashionProduct");
        event1.setStartTime(0L);
        eventList.add(event1);

        TestEvent event2 = new TestEvent();
        event2.setItemId("xst-prd-211");
        event2.setEventType("fashionProduct");
        event2.setStartTime(200L);
        eventList.add(event2);

        TestEvent event3 = new TestEvent();
        event3.setItemId("xst-prd-212");
        event3.setEventType("fashionProduct");
        event3.setStartTime(200L);
        eventList.add(event3);

        TestEvent event8 = new TestEvent();
        event8.setItemId("xst-prd-216");
        event8.setEventType("fashionProduct");
        event8.setStartTime(200L);
        eventList.add(event8);

        TestEvent event9 = new TestEvent();
        event9.setItemId("xst-prd-217");
        event9.setEventType("fashionProduct");
        event9.setStartTime(200L);
        eventList.add(event9);

        TestEvent event10 = new TestEvent();
        event10.setItemId("xst-prd-218");
        event10.setEventType("fashionProduct");
        event10.setStartTime(200L);
        eventList.add(event10);


        return eventList;
    }

    private class TestEvent {
        private String itemId;
        private String eventType;
        private Long startTime;

        public String getItemId() {
            return itemId;
        }

        public void setItemId(String itemId) {
            this.itemId = itemId;
        }

        public String getEventType() {
            return eventType;
        }

        public void setEventType(String eventType) {
            this.eventType = eventType;
        }

        public Long getStartTime() {
            return startTime;
        }

        public void setStartTime(Long startTime) {
            this.startTime = startTime;
        }

        
    }

    private class TestTimedItemChange {
        private String itemId;
        private String eventType;
        private Long timePosition;
        private String changeType;

        public String getChangeType() {
            return changeType;
        }

        public void setChangeType(String changeType) {
            this.changeType = changeType;
        }


        public String getItemId() {
            return itemId;
        }

        public void setItemId(String itemId) {
            this.itemId = itemId;
        }

        public String getEventType() {
            return eventType;
        }

        public void setEventType(String eventType) {
            this.eventType = eventType;
        }

        public Long getTimePosition() {
            return timePosition;
        }

        public void setTimePosition(Long timePosition) {
            this.timePosition = timePosition;
        }

        
    }
}

}

输出-

TimedItemChange(changeType=add, timePosition=0, itemId=bts-0)
TimedItemChange(changeType=add, timePosition=0, itemId=xst-prd-210)
TimedItemChange(changeType=add, timePosition=200, itemId=xst-prd-211)
TimedItemChange(changeType=add, timePosition=200, itemId=xst-prd-212)

TimedItemChange(changeType=remove, timePosition=200, itemId=xst-prd-210) //correct removal based on starttime/timeposition
TimedItemChange(changeType=add, timePosition=200, itemId=xst-prd-216)

TimedItemChange(changeType=remove, timePosition=200, itemId=xst-prd-212)//wrong removal - should have been 211 as it was inserted before 212  
TimedItemChange(changeType=add, timePosition=200, itemId=xst-prd-217)

TimedItemChange(changeType=remove, timePosition=200, itemId=xst-prd-216) //wrong removal
TimedItemChange(changeType=add, timePosition=200, itemId=xst-prd-218)

共有1个答案

年良骏

2023-03-14

我工作了，这似乎正在工作-基本上包装了TestTimeItemChange类-Entry类-并分别获得了比较器。

有没有其他方法不添加包装器类？

工作代码-

package com.amazon.atv.xray.vending.service.assemblerV2.builder.change;

import java.util.*;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.stream.Collectors;

public class PriorityQueues {

  public static void main(String []args){
    TestPriorityQueue obj = new TestPriorityQueue();
    obj.build();
  }

 static class TestPriorityQueue {

    private static class Entry {

        private final static AtomicInteger seq = new AtomicInteger(0);
        final int order;
        final TestTimedItemChange timedItemChange;

        public int getOrder() {
            return order;
        }

        public TestTimedItemChange getTimedItemChange() {
            return timedItemChange;
        }

        public Entry(final TestTimedItemChange timedItemChange) {
            this.timedItemChange = timedItemChange;
            order = seq.incrementAndGet();
        }

        @Override
        public String toString() {
            StringBuilder ret = new StringBuilder();
            ret.append("Entry(");

            ret.append("timedItemChange=");
            ret.append(timedItemChange.toString());
            ret.append(", ");

            ret.append("seq=");
            ret.append(String.valueOf(order));

            ret.append(")");

            return ret.toString();
        }

    }

   private static Comparator<Entry> getTimedItemChangeComparatorFIFO(final Map<String, String> eventIdToTypeMap) {
        Comparator<Entry> comparator = new Comparator<Entry>() {
            @Override
            public int compare(final Entry entry1, final Entry entry2) {
                int result = PINNED_EVENT_TYPE_PRIORITY_REMOVAL_MAP.get(eventIdToTypeMap.get(entry1.getTimedItemChange().getItemId())) -
                        PINNED_EVENT_TYPE_PRIORITY_REMOVAL_MAP.get(eventIdToTypeMap.get(entry2.getTimedItemChange().getItemId()));
                if (result == 0)
                    return Integer.compare(entry1.getOrder(), entry2.getOrder());
                return result;
            }
        };
        return comparator;
    }

    private static final Map<String, Integer> PINNED_EVENT_TYPE_PRIORITY_REMOVAL_MAP = new HashMap<>();

    public void build(){

        PINNED_EVENT_TYPE_PRIORITY_REMOVAL_MAP.put("fashionProduct", 0);
        PINNED_EVENT_TYPE_PRIORITY_REMOVAL_MAP.put("bonusContent", 1);

        final List<TestTimedItemChange> changesCollection = new ArrayList<>();

        final List<TestEvent> eventList = getEvents();
        final Map<String, String> eventIdToTypeMap = eventList.stream().collect(
                Collectors.toMap(TestEvent::getItemId, TestEvent::getEventType));

        final Queue<Entry> pinnedItemsInQuickView =
                new PriorityQueue<>(getTimedItemChangeComparatorFIFO(eventIdToTypeMap));

        for (final TestEvent event : eventList) {
            final TestTimedItemChange newItemToAdd = buildTimedItemChange(event.getItemId(), event.getStartTime(),
                    "add");

            if (changesCollection.size() >= 4) {
                //System.out.println(pinnedItemsInQuickView.remove());
                final TestTimedItemChange oldItemToRemove = pinnedItemsInQuickView.remove().getTimedItemChange();
                changesCollection.add(buildTimedItemChange(oldItemToRemove.getItemId(),
                        Math.max(newItemToAdd.getTimePosition(), oldItemToRemove.getTimePosition()),
                        "remove"));
                changesCollection.add(newItemToAdd);
                //pinnedItemsInQuickView.remove();
                pinnedItemsInQuickView.add(new Entry(newItemToAdd));

            } else {
                changesCollection.add(newItemToAdd);
                pinnedItemsInQuickView.add(new Entry(newItemToAdd));
            }


        }

        changesCollection.stream().forEach(cc -> System.out.println(cc));

    }

    private TestTimedItemChange buildTimedItemChange(final String itemId, final long timePosition,
                                                     final String itemChangeType) {
        TestTimedItemChange testTimedItemChange = new TestTimedItemChange();
        testTimedItemChange.setItemId(itemId);
        testTimedItemChange.setChangeType(itemChangeType);
        testTimedItemChange.setTimePosition(timePosition);

        return testTimedItemChange;
    }

    private List<TestEvent> getEvents() {
        List<TestEvent> eventList = new ArrayList<>();
        TestEvent event4 = new TestEvent();
        event4.setItemId("bts-0");
        event4.setEventType("bonusContent");
        event4.setStartTime(0L);
        eventList.add(event4);

        TestEvent event1 = new TestEvent();
        event1.setItemId("xst-prd-210");
        event1.setEventType("fashionProduct");
        event1.setStartTime(0L);
        eventList.add(event1);

        TestEvent event2 = new TestEvent();
        event2.setItemId("xst-prd-211");
        event2.setEventType("fashionProduct");
        event2.setStartTime(200L);
        eventList.add(event2);

        TestEvent event3 = new TestEvent();
        event3.setItemId("xst-prd-212");
        event3.setEventType("fashionProduct");
        event3.setStartTime(200L);
        eventList.add(event3);

        TestEvent event8 = new TestEvent();
        event8.setItemId("xst-prd-216");
        event8.setEventType("fashionProduct");
        event8.setStartTime(200L);
        eventList.add(event8);

        TestEvent event9 = new TestEvent();
        event9.setItemId("xst-prd-217");
        event9.setEventType("fashionProduct");
        event9.setStartTime(200L);
        eventList.add(event9);

        TestEvent event10 = new TestEvent();
        event10.setItemId("xst-prd-218");
        event10.setEventType("fashionProduct");
        event10.setStartTime(200L);
        eventList.add(event10);


        return eventList;
    }

    private class TestEvent {
        private String itemId;
        private String eventType;
        private Long startTime;

        public String getItemId() {
            return itemId;
        }

        public void setItemId(String itemId) {
            this.itemId = itemId;
        }

        public String getEventType() {
            return eventType;
        }

        public void setEventType(String eventType) {
            this.eventType = eventType;
        }

        public Long getStartTime() {
            return startTime;
        }

        public void setStartTime(Long startTime) {
            this.startTime = startTime;
        }

        @Override
        public String toString() {
            StringBuilder ret = new StringBuilder();
            ret.append("XrayEvent(");

            ret.append("startTime=");
            ret.append(String.valueOf(startTime));
            ret.append(", ");

            ret.append("eventType=");
            ret.append(String.valueOf(eventType));
            ret.append(", ");

            ret.append("itemId=");
            ret.append(String.valueOf(itemId));
            ret.append(")");
            return ret.toString();
        }
    }

    private class TestTimedItemChange {
        private String itemId;
        private String eventType;
        private Long timePosition;
        private String changeType;

        public String getChangeType() {
            return changeType;
        }

        public void setChangeType(String changeType) {
            this.changeType = changeType;
        }


        public String getItemId() {
            return itemId;
        }

        public void setItemId(String itemId) {
            this.itemId = itemId;
        }

        public String getEventType() {
            return eventType;
        }

        public void setEventType(String eventType) {
            this.eventType = eventType;
        }

        public Long getTimePosition() {
            return timePosition;
        }

        public void setTimePosition(Long timePosition) {
            this.timePosition = timePosition;
        }

        @Override
        public String toString() {
            StringBuilder ret = new StringBuilder();
            ret.append("TimedItemChange(");

            ret.append("changeType=");
            ret.append(String.valueOf(changeType));
            ret.append(", ");

            ret.append("timePosition=");
            ret.append(String.valueOf(timePosition));
            ret.append(", ");

            ret.append("itemId=");
            ret.append(String.valueOf(itemId));
            ret.append(")");

            return ret.toString();
        }
    }
}

}

类似资料：

Python中优先级较高的优先级队列

我需要一个优先级队列，它首先获得具有最高优先级值的项目。我当前正在使用队列库中的PriorityQueue类。但是，这个函数只先返回值最小的项。我尝试了一些很难看的解决方案，比如（sys.maxint-priority）作为优先级，但我只是想知道是否存在更优雅的解决方案。
Java优先级队列堆

注意：我知道可以用比较器创建优先级队列，然后重复调用Add。
Java优先级队列排序

我有一个，名为，其中包含类型的对象。您可以在所有车辆上调用该方法。我要做的是排序，这样车辆被赋予更高的优先级，并被放在队列的前面。我假设我必须在这里使用一个比较器，但不知道怎么做。
按相反顺序创建优先级队列

我创建了一个名为Element的新o类对象，它有很多值“degree” 我想创建一个包含以下元素的优先级队列：程序将打印：但我想：所以我想做的是，度值越大的元素优先级越高，被优先考虑。第二个问题是：如果两个元素具有相同的度值，那么它们将按哪个顺序取？
定义优先级队列

考虑下面的优先级类声明<代码>类优先级队列我的想法：我能想到的一件事是，这将强制优先级队列使用对象比较器，并且不会提供实现其自定义比较器的能力，因为类的用户可能希望基于某个不同的比较器构建队列。
优先级队列(Priority Queue)

优先级队列(Priority Queue) 注：队列是一种特征为FIFO的数据结构，每次从队列中取出的是最早加入队列中的元素。但是，许多应用需要另一种队列，每次从队列中取出的应是具有最高优先权的元素，这种队列就是优先级队列(Priority Queue)，也称为优先权队列。 1. 优先级队列的概念 1.1 优先级队列的定义优先级队列是不同于先进先出队列的另一种队列。每次从队列中取出的是具有最高优

在Java中，当优先级相同时，使优先级队列遵循FIFO顺序

共有1个答案

相关问答

相关文章

相关阅读

相关工具

相关文档