Java时间有序数据结构

Question

我正在处理高频的时间戳事件流，没有排序保证(90% 的时间都是排序的)。我需要在程序中存储这些事件(用于缓存目的)一段时间。为了优化我的计算的性能(主要需要对事件集合进行迭代)，如果我可以通过缓存有序列表来保证顺序，那么对我来说会更容易。所以我正在寻找的是一种插入和迭代速度快并且允许重复的有序数据结构。

在我在互联网上找到的所有建议中，我尝试过:
- TreeSet -> 不起作用，因为我可能有重复的时间戳
- PriorityQueue -> 不起作用，因为迭代器不保证优先级顺序

由于 9/10 事件的顺序很好，我想我可以使用带有修改版本的 add 方法的基本 ArrayList :

public class TimeOrderedArrayList<E> extends ArrayList<E>{

private long lastTs;
private Comparator<E> comparator;
private TimeGetter<E> tsgetter;

public TimeOrderedArrayList (Comparator<E> comparator, TimeGetter<E> tsgetter) {
    super();
    this.comparator = comparator;
    this.tsgetter = tsgetter;
    this.lastTs = Long.MIN_VALUE;
}


@Override
public boolean add(E e) {
    if (tsgetter.getTime(e) >= lastTs) {
        lastTs = tsgetter.getTime(e);
        return super.add(e);
    } else {

        // VERSION 1
        int index = super.size()-1;
        while (tsgetter.getTime(super.get(index))>tsgetter.getTime(e) && index > 0) {
            index--;
        }
        super.add(index, e);

        // VERSION 2
        int index = Collections.binarySearch(this, e, comparator);
        super.add(index>-1 ? index : -index-1,e);
        return true;
    }
}

@Override
public boolean addAll(Collection<? extends E> c) {
    boolean result = super.addAll(c);
    super.sort(comparator);
    return result;
}
}

但是对于这两个版本，我的表现都非常糟糕。

有什么建议吗？

Answer 1

从问题描述来看，在我看来，只要您可以在一段时间内对事件集合进行迭代，问题就不需要严格的顺序。此外，您提到的数据类型似乎是多个客户端节点将数据发送到一台集中式服务器的数据(可能是来自多个服务的日志/事件累积)。

如果是这种情况，您可以探索使用简单的存储桶数组，其中与时间戳对应的事件仅进入特定的存储桶。您将确保所有具有非常接近时间戳的事件都被分类到相同的存储桶中，以便您可以实现事件之间的偏序。

例如:如果您需要最后 1 分钟(60 秒)的数据，您可以定义 60 个存储桶，每秒一个，并不断轮换它们。时间戳为 2016-12-08 19:59:29.538331 的事件将进入第 29 个存储桶(假设索引从 0 开始，并且您采用每个事件的秒数作为下限)。当一分钟过去后，只需清除第 i 个存储桶的过去数据，然后重新开始构建它即可。因此，在 2016-12-08 20:00:00.129845，第 0 个存储桶被重置为空数组。

由于您有高频的时间戳事件流，因此空桶等的可能性将很小。您可以根据您的具体要求调整所需的存储桶数量。