1
タイムスタンプ付きのイベントの高頻度ストリームを処理していますが、オーダーの保証はありません（時間の90％が順序付けされています）。私はこれらのイベントを私のプログラムに何度か保存する必要があります。私の計算のパフォーマンスを最適化するためには、順序付きリストをキャッシュすることでオーダーを保証できれば、はるかに簡単です。だから私が探しているのは、挿入と反復が速く、重複を許す順序付けられたデータ構造です。私はインターネット上で発見したすべての命題の中で
は、私が試してみました：
- TreeSetの - 私は重複したタイムスタンプを持っているかもしれないので>は動作しません
- 優先度つきキュー - イテレータが優先順位
を保証するものではありませんので>は動作しません
Javaタイムオーダーのデータ構造
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;
}
}
しかし、私は本当に悪いパフォーマンスを得る両方のバージョン： 9/10以降のイベントはよく私はaddメソッドの修正バージョンと基本のArrayListを使用することができると思った順に並べられます。
提案がありますか？
データ構造内の要素にランダムアクセスする必要がありますか、それとも常にすべてを繰り返していますか？ –
独自のヒープデータ構造を使用してみませんか？ – SMA
同じタイムスタンプのイベントが「同じ」ものとして表示されないようにするカスタムコンパレータを作成することは可能でしょうか？ – GhostCat