3

変更リストを別のシステムにプッシュするシナリオがあります。各リストには、挿入、更新、または削除された通知が 0 個以上含まれています。

挿入は簡単です。通知には、ターゲット インデックスとアイテムへのポインターが含まれます。更新は簡単です。アイテムへのポインターを渡します。

削除は簡単に思えます。削除するアイテムのインデックスを渡す必要がありますが、どうすればインデックスを知ることができますか? インデックスはゼロから始まり、連続している必要がありますが、挿入時に作成します。そのため、各項目に対して作成したインデックスを追跡する必要があります。

たとえば、 map: でこれを行うことができますがstd::map<item*, int>、アイテムを削除すると、それ以降のすべてに番号を付け直す必要があります。これは O(N) です。

これらのアイテムのリストは、O(N) 反復が受け入れられないほど大きくなります。この問題は解決されたと確信していますが、解決策が何と呼ばれるかはわかりません。「リンクされたリスト」に関連するものを検索すると、大量のノイズが発生します。

考えられる解決策の 1 つはスキップ リストです。サブリスト内の各ノードは、スキップするメイン リスト内のノードの数を認識しています。スキップ リストの検索は O(log N) であるため、移動しながら追跡し、インデックスを見つけることができます。 O(log N)、O(log N) 内のアイテムも削除します。

ただし、スキップ リストの実装はやり過ぎのように思えます...もっと簡単な解決策はありますか?

編集：

あなたの提案に感謝しますが、スキップリストがここでこの問題を解決する正しい方法であると確信していると思います.

4

5 に答える 5

4

Hinze と Paterson によるFinger Trees: A Simple General Purpose Data Structureを参照してください。

指の木に関するMarkCC のブログ投稿の素敵なイラストも参照してください。

于 2009-11-25T06:13:39.203 に答える
1

でルックアップを行うときに、削除履歴を保持してこれを補正できませんでしたstd::map<item*, int>か？

つまり、のインデックスはstd::mapアイテムの元のインデックスを表し、std::map<int, int>特定のインデックスが削除された回数を格納する補助マップがありますか？

item* todelete; //from somewhere
std::map<int, int> history; //stored somewhere
std::map<item*, int> itemIndices; //stored somewhere
const int originalIndex = itemIndices[todelete]; //index of item at insert time
int index = originalIndex;
for (std::map<int, int>::const_iterator it = history.begin(); it != history.end() && it->first < originalIndex; ++it) {
    index -= it->second;
}
// index has now been compensated for previous deletes
// ... send the delete request with 'index'
// update the history with this delete request
std::map<int, int>::iterator it = history.find(index);
if (history.end() == it) {
    history[index] = 1;
} else {
    ++it->second;
}

もちろん、この速度は履歴のサイズによって異なります。

/ AB

于 2009-11-25T12:09:47.827 に答える
1

削除はどのくらいの頻度で行われますか? を使用してソリューションを維持することを考えていますstd::map<item*, int>が、削除時にマップを更新する代わりに、リンクされたリストのアイテムを「NULL」アイテムに置き換えて、ルックアップマップのインデックスが有効なままであることを確認します。削除が頻繁に発生し、メモリ不足になる可能性がある場合、これは適切な解決策ではない可能性があります。また、これを実行して、リンクされたリストから NULL アイテムを削除し、すべてのアイテムに新しいインデックスを割り当てる reindex() メソッドを使用することもできます。

Sidenote 1: update のように、削除されるアイテムへのポインターを渡すことはできませんか? これを行い、二重リンクリストを使用すると、削除操作は O(1) で簡単に実行できます。

boost::unordered_map補足 2: overの使用を検討してくださいstd::map。

于 2009-11-25T14:23:41.193 に答える
1

編集:私の以前のソリューションには欠陥がありました std::vector::erase() は、要素を移動するときに線形です。私の新しい提案は、私の以前のコメントをあなたの質問に拡張します。

リスト内のポインターのみを操作する場合は、ポインターで delete を呼び出した後、ポインターを 0 に設定して、インデックス/キーを有効に保つことができます。次に、次のインデックスが を超えるまで、ますます大きなインデックスを使用できるようになりますstd::numeric_limits<int>::max()。次に、リストの大部分にゼロに設定された未使用のポインター要素が含まれている場合は、通信チャネルの両側でゼロポインターの同期クリーンアップを実行し、続いてインデックスを再計算します。これについてすぐにわかるヒューリスティックはわかりませんが、ゼロポインターの数を追跡し、それをリスト全体のサイズと比較することはできます。

簡単に言えば、インデックスの計算は O(n) であるため、絶対に必要になるまで遅らせてください。

于 2009-11-25T06:42:01.893 に答える
0

スキップ リストは正しい解決策です。

于 2010-01-22T17:57:00.010 に答える