什么数据结构适合事件和监听器的顺序事件调度系统？

Question

我需要为以下情况找到合适的数据结构.我编写了一个包含事件和监听器的简单事件调度系统.系统是完全顺序的,因此没有任何并发​​和同步问题.

要求和想法

• 每个侦听器向预定义(编译时)注册一种或多种类型的事件.
• 监听器可以在运行时注册和注销.
• 必须维护侦听器注册的顺序,因为它是接收事件的顺序(侦听器总是在末尾添加,但可以从任何地方删除).
• 事件类型可以随时注册0个或更多侦听器以接收它.

这种关系的可视化可以解释为表格:

       | Listener1 | Listener2 | Listener3 | Listner5
-----------------------------------------------------
Event1 |     X     |           |     X     |    X
-----------------------------------------------------
Event2 |           |     X     |     X     |    X
-----------------------------------------------------
Event3 |           |           |           |
-----------------------------------------------------
Event4 |           |           |           |    X
-----------------------------------------------------

• 行的顺序无关紧要.
• 必须保持列的顺序.
• 可以添加和删除列.
• 行数在运行时是常量.

我的想法是:

• 调度事件时,我需要知道注册哪些侦听器才能接收事件类型.我正在考虑一个Event -> Collection<Listener>键是无序的映射.侦听器集合需要维护插入顺序(或者,如果可以使用以下点,则不需要).
• 我需要保留一组维护插入顺序的侦听器,而不管它们注册的事件(此要求来自侦听器附加到的对象).因为即使Collection<Listener>上面是插入排序的,它也是每个事件类型而不是全局的.我正在考虑一个OrderedCollection<Listener>.
• 取消注册时,我需要找到一个监听器已注册的所有事件类型,以便可以将其删除.我正在考虑a Listener -> Collection<Event>,除非第一个点中的映射可以removeAll(Listener)对值位置中的列表执行操作,但是这可以留下空列表而不是完全删除键.

在我看来,双向多图适合这种情况.支持多重映射是一个UnorderedMap<Event, OrderedCollection<Listener>>和一个OrderedMap<Listener, UnorderedCollection<Event>>.该OrderedCollection<Listener>可能不需要进行排序,如果从排序OrderedMap可以使用.显然,可以订购任何无序数据结构,但这是不必要的.

或者,我已经看到了带有reverse/ invertoperation 的单个多图的想法,以获得相反的映射.我关心的是双重的:

1. 我不知道一方是否可以订购其钥匙而另一方则没有.
2. 这似乎是一个昂贵的操作,如果我需要一直反转映射它可能是低效的.

伪代码用法

注册一个监听器:

// somewhere
Listener1 listener = new Listener1();
listener.register(); 

// class definition
class Listener1 extends AbstractListener {

    void register() {

        DataStructure.put(Event1.class, this);
        DataStructure.put(Event2.class, this);

        // or
                                 // some collection
        DataStructure.put(this, [Event1.class, Event2.class])
    }
}

派遣活动:

// somewhere
EventManager.dispatch(new Event2());

// class definition
class EventManager {

    static void dispatch(Event event) {

        OrderedCollection<Listener> listeners = DataStructure.get(event);
        listeners.forEach(l -> l.processEvent(event)); // forEach maintains the order
    }
}

取消注册一个监听器:

Listener2 listener = ...;        // got it from somewhere
DataStructure.remove(listener);  // remove from everywhere and if a key is left with an empty list remove that key

最后的细节和问题

如果重要的话,大约有30种事件类型,并发注册监听器的数量是O(10),尽管在程序的生命周期内可能有O(100)个监听器 - 其中大部分都是注销和GC.

关于订购的说明.由于侦听器具有增量唯一int id字段,因此我可以确保按ID号排序等同于按注册(插入)顺序排序.当前的差异是id在侦听器的初始化时设置,而注册在之后完成(并且可以在该间隙中创建和注册另一个侦听器).如果在这种情况下使用有序集合的排序集合有一个优势,我可以做一些工作来保证按id排序等同于插入顺序.

哪些数据结构符合我的需求？我是否需要自己编写(我宁愿不重新发明轮子)还是已经实现了(番石榴,我正在看着你)？

Answer 1

我研究了几种选择，并通过一些基本的理论考虑找到了解决方案。

Map<Event, Collection<Listener>> // Event stands for Class<? extends Event>

其中键和每个键的侦听器都是有序的。

理论考虑

给定 的映射（多重映射）Map<Event, Collection<Listener>>，如果键和值集合都是按插入顺序排列的，则可以获得侦听器的（全局）插入顺序。我不会在这里给出证明，只做一个简短的解释。这种数据结构相当于有序集合的有序集合。执行展平操作将产生具有重复项的单个有序集合。然后通过消除后续出现的情况来删除重复项将产生按插入顺序排序的集合。

有趣的是，当映射和值集合中的一个或两个不维护插入顺序时，如何不维护全局侦听器插入顺序。

抛开理论不谈，这样的数据结构：

• 在插入和删除操作期间，全局和每个键维护侦听器的插入顺序。
• Event -> <Listener>借助地图可以轻松地进行事件调度。
• 不允许轻易注销Listener -> <Event>（非双向）。
• 维护某种无关的事件顺序。

伪代码使用

登记、调度和注销：

class EventDispatcher {

    static Map<Event, Collection<Listener>> map;

    static void registerListener(Collection<Event> eventTypes, Listener listener) {

        eventTypes.forEach(et -> map.put(et, listener));
    }

    static void dispatch(SomeEvent event) {

        map.get(SomeEvent.getClass()).forEach(l -> l.trigger(event));
    }

    static void deregisterListener(Listener listener) {

        while (map.values().remove(listener));
    }
}

获取全局插入顺序侦听器是通过以下方式完成的：

new LinkedHashSet<>(map.values());

asmap.values()返回一个展平的集合并Set折叠重复项。

如上所述，调度是高效的，因为只有注册接收事件的侦听器才会接收该事件。注销存在不知道从哪些key中删除指定监听的问题，因此需要遍历所有key，效率不高。可以反转映射，但我相信它不能更快​​。

相反，维持逆映射，

Map<Listener, Collection<Event>>

当

• 与事件分派相比，侦听器注销/注册的频率较高。
• 与（并发）注册侦听器的数量相比，事件类型的数量较多。
• 与事件类型的数量相比，侦听器注册的事件类型的数量较少。

实施

Java Collections 框架提供了几种维护插入顺序的实现。对于地图来说，只有LinkedHashMap可行。对于值集合，ArrayList、LinkedList和LinkedHashSet是可行的。

其中，Guava 提供了with或的多重映射实现。后者保证没有重复的值。由于我的听众在设计上是独一无二的（如上所述，它们有一个独特的用途），因此不需要明确的保证。它们之间也存在迭代顺序差异，但我相信只有当侦听器可以部分注销（从特定事件类型）时它们才会显现，这不是我的情况。LinkedHashMapLinkedListLinkedHashSetint idequals

对于我正在处理的 O(10-100) 数量级，几乎没有考虑性能差异，而且我还没有选择具体的实现。