2

データ フィードをサブスクライブし、そこから INSERT/DELETE メッセージのインデックス値を使用して構造を作成および維持します。効率的な方法で断片的な更新を処理できるアルゴリズムを知っているかどうか、集まった知識人に尋ねたいと思います。一般に、バッチ更新には 2 ～ 6 個のそのようなメッセージが含まれます。

配列の推定サイズは、約 1000 要素です。

バッチ更新は、特定のインデックスでアイテムの挿入または削除を規定する、インデックス順に並べられたメッセージのリストとして到着します。アレイ内のほとんどのチャーンは、その終了よりも開始に近いと予想されます。

いくつかの基本的な処理を行うことで、バッチの影響を受ける範囲と全体的なサイズ デルタを特定できるため、影響を受けない配列のテール セクションを 1 回だけ移動できます。

同様に、最初の要素の前と最後の要素の後に一定量の空き領域を維持して、最小限のコピーを行うことができます。

その他の最適化には、次のような更新の認識が含まれます。

DELETE 10, INSERT 10 - effectively a replace which requires no copying  
INSERT 10, DELETE 11 - as above  
DELETE 10, DELETE 10, DELETE 10 - bulk deletion can be optimised into one copy operation  
INSERT 11, INSERT 12, INSERT 13 - bulk insertion can be optimised into one copy operation

等々。

ただし、認識ステップを実行する際のオーバーヘッドには注意が必要です。単にコピーを実行するよりも時間がかかる可能性があるため、先読みとトラックバックが発生する可能性があります。

配列の予想されるサイズを考えると、ツリー構造は重量級のように見えます。いくつかの基本的なパフォーマンス テストでは、バイナリまたは自己均衡ツリー (この場合は赤黒ツリー リストの実装) は、約 15K ～ 20K 要素の後にのみパフォーマンスの利点を示し始めることが示唆されています。 : 配列のコピーは、サイズが小さいほど大幅に高速です。おそらく、この実装には Java を使用していることを付け加えておく必要があります。

ヒント、ヒント、提案は大歓迎です。

乾杯

マイク

4

8 に答える 8

2

コードの明瞭さと最適化を常に比較検討してください。現在パフォーマンスの問題がない場合は、コードが明確であることを確認してください。将来パフォーマンスの問題が発生した場合、その正確な性質を知ることができます。今の準備は当て推量です。

かなり操作する必要がある場合は、リンクされたリストが価値があるかもしれません。

ただし、単純で明確なコードの場合は、未加工の配列または arraylist に apache commons collection utils を使用します。

myArray = ArrayUtils.add(myArray, insertionIndex, newItem);

また

ArrayList<> mylist = new ArrayList<>(Arrays.asList(myArray));
myList.add(insertionIndex, newItem);
于 2010-09-01T19:36:21.970 に答える
2

一般に、変更がインデックス順にリストされている場合は、一度だけコピーする単純なループを作成できます。ここにいくつかの擬似コードがあります:

array items;
array changes; // contains a structure with index, type, an optional data members
array out; // empty, possibly with ensureCapacity(items.length)
int c = 0, delta = 0;
// c is the current change
//delta tracks how indexing has changed by previous operations
for (i = 0; i < items.length; i++) {
    if c < changes.length {
        curchange = changes[c]
        if (i + delta) == curchange.index {
            c++;
            if (curchange.type == INSERT) {
                out.add(curchange.data)
                delta--;
            } else {
                delta++;
                continue; // skip copying i
            }
        }
    }
    out.add(items[i])
}
for (; c < changes.length; c++) { // handle trailing inserts
    assert(c.index == out.length && c.type == INSERT)
    out.add(c.data);
}

これは入力配列を 1 回実行し、すべての変更を加えて出力配列を構築します。

これは、同じ場所での複数の挿入を処理しないことに注意してください。これを行うと、コードが少し複雑になりますが、それほど難しくはありません。

ただし、バッチごとに 1 回、常にアレイ全体で実行されます。少し難しい変更は、一時的なものを保持し、2 つのインデックス変数を使用してその場で変更を行うことです。次に、変更リストの最後に到達すると、ループから早期に抜け出し、リストの残りの部分に触れない可能性があります。

于 2010-09-01T19:55:50.873 に答える
0

最も簡単な方法は、更新を実行し、更新の適用中に配列を新しい配列にコピーすることです。

1000 はそれほど大きくないため、これ以上最適化する価値はおそらくありません。

そして、あなたの人生をより簡単にするために、ArrayList.

于 2010-09-01T19:23:43.793 に答える
0

個々の更新を並べ替えて (既に述べたように) 物事を統合しようとする以外に、あまり気にする必要があるかどうかはわかりません。1000 要素は、率直に言って、大規模な範囲では何もありません。私は単純な一括コピーを使用して 25M の要素を持つシステムを持っています。

したがって、「時期尚早の最適化」という帽子をかぶるつもりはありませんが、最初に本棚でそれをちらりと見るかもしれません。

于 2010-09-01T19:26:44.490 に答える
0

スペースが制約ではなく、重複する予定がない場合は、データ構造の設定、特に Java のHashSet. このデータ構造の力は、挿入と削除が O(1) 時間で行われることです。これは、パフォーマンスが「the」基準である場合に最適です。

さらに、高速検索以外に配列について話すときはいつでも、（配列の成長のために）スペースを占有するだけでなく、挿入/削除には O(n) 時間がかかる場合があります。

于 2010-09-01T19:41:48.303 に答える
0

リンクされたリスト ( java.util.LinkedList) を使用することを検討する必要があるかもしれません。もちろん、特定のインデックスで要素を取得するのはコストがかかりますが、配列のコピーを実行するよりはましかもしれません。

于 2010-09-01T19:32:39.390 に答える
0

それが本当にあなたのデータセットがどのように見えるかである場合は、コレクション (HashMap など) を使用した重複追跡を検討することができます。配列は、各アクティビティが順番にリストされた順序付きリストになり、コレクションは配列へのインデックスになります。

例えば：

クラス EventQueue
{
  ベクトル eventQueue;
  HashMap eventMap;

  パブリック同期イベント getNextEvent()
  {
      イベント event = eventQueue.remove(0);
      eventMap.remove(event.getId()); // これは 'INSERT 10' から 10 になります
                                       // OP のサンプルで
  }

  公開同期 addEvent(Event e)
  {
     if( eventMap.containsKey(e.getId())
     {
        // すでに存在するイベントを置き換える
        int idx = eventMap.get(e.getId());
        eventQueue.removeElementAt(idx);
        eventQueue.add(idx, e);
     } そうしないと {
        // 新しいイベントを追加
        eventQueue.add(e);
        eventMap.add(e.getId(), eventQueue.size()); // 1 つずれている可能性があります...
     }
  }

  public boolean isReady()
  {
    eventQueue.size() > 0 を返します。
  }
}

クラス FeedListener はスレッドを拡張します {
 EventQueue キュー。
 EventFeed フィード。
 ...
 public void run()
 {
    while(実行中) {
       スリープ (スリープ時間);
       if( feed.isEventReady() ) {
         queue.addEvent(feed.getEvent());
       }
    }
 }
}

抽象クラス EventHandler extends Thread {
 EventQueue キュー。
 ...
 public void run()
 {
   ながら（実行中）
   {
     スリープ (スリープ時間);
     if( queue.isReady() )
     {
       イベント event = queue.getNextEvent();
       handleEvent(イベント);
     }
   }
 }

 public abstract void handleEvent(イベント イベント);
}
于 2010-09-01T20:01:50.900 に答える
0

O(log N) 配列の分割、連結、挿入、および削除 (およびその他多数) を可能にする、「デカルト ツリー」または「Treaps」という名前の非常に簡単に実装できるデータ構造があります。

2 ～ 3 個のツリーは実装も非常に簡単で (私の実装ではやや複雑な機能で、最初のコンパイル後にバグが 1 つしかありませんでした)、目的に適合します。

于 2010-09-01T19:37:58.250 に答える