ソートされたコレクションに効率的に挿入

Question

私は10個のメッセージのコレクションを持っています。 定期的に私は古いメッセージのいくつかを新しいものに置き換えてそのコレクションを更新し、その間に多くの好きなものを持っているので、コレクションには10個のメッセージが含まれ、好きな数でソートされます。

私は、既存のメンバーメッセージに対して、コレクションからメッセージを挿入または削除するAPIを持っています。 insert(message_id, relative_to, above_or_bellow)およびremove(message_id)。コレクションが常にソートされ、最後に10の長さになるように新しいメッセージを挿入する位置を最適化することで、api呼び出しの回数を最小限に抑えたい。 （プロセスの長さと順序は関係なく、プロセスの最後で）

私は新しいコレクションを計算して新しい位置には一致しないメッセージだけを置き換えることができますが、さらに最適化され、アルゴリズムが存在すると信じています既に。

編集：

は、メッセージを1つずつ付属していませんが、時間間隔で、私は新しいメッセージを集め、それらを並べ替え、そして私は、APIを介してサイト上で公開する新しいコレクションを作る意味、「定期的に」という言葉に注意してください。 。だから、私は2つのコレクションを持って、1つはメモリ内の単純な配列であり、他はサイト上にあります。

アイデアは、http API呼び出しを保存するために、保持する必要がある既に挿入されたメッセージとその順序を更新コレクションに再利用することです。既存のコレクションを、既知の結果のコレクションに変換するために再利用できる既存のアルゴリズムがあると思います。

Answer 1

まず、トップ10の好きなメッセージに含まれていないメッセージをすべて削除します。

既存のリストからほとんどを得るために、我々は今

（私たちは値 How to determine the longest increasing subsequence using dynamic programming?と同類の番号を使用して、ここで述べたアルゴリズムを使用することができます）自分の好きな順に並べられたメッセージの最長のサブシーケンスを探してください

その後、他のすべてのメッセージ（サブシーケンスではない）を削除し、欠落したメッセージをその順序で挿入します。

Answer 2

私は、メッセージのリスト/ベクトルを1つだけ保持し、新しいメッセージがあるたびに常に最新の状態に並べ替える必要があると思います。

このコレクションは常にソートされており、ランダムアクセスがあると仮定すると、バイナリ検索を使用して挿入ポイント、つまりO（log_2^M）を見つけることができます。ここでMは最大リストサイズです。しかし、ここに挿入すると、要素をシフトするのにO（M）が必要です。したがって、リンクされたリストを使用して、挿入（または更新）するメッセージが現在のものよりもあまり好きではない間に繰り返します。