Is there any way to efficiently reconstruct a collection based on a sequence of inserts/removals?
Note: the below code happens to be C#, but really an answer in any language would be helpful for me.
Suppose rather than an actual collection (e.g., a List<T>
), I have a sequence of operations, each looking something like this:
struct ListOperation<T>
{
public enum OperationType { Insert, Remove }
publ开发者_如何学Cic OperationType Type;
public T Element; // irrelevant for OperationType.Remove
public int Index;
}
Is there some way to efficiently "reconstruct" a collection based on a sequence of such operations?
In particular, I'm looking to avoid the obvious (inefficient) implementation of basically just creating a List<T>
and calling Insert
and RemoveAt
—both O(N) operations—for every element.
Update: Let's say the "sequence" of operations is in fact a concrete collection whose count is known and which is randomly accessible by index (so, like a ListOperation<T>[]
, for example). Let's also say the actual count of the resulting collection is already known (but really, that would be trivial to figure out in O(N) anyway, by counting insertions and removals). Any other ideas?
I think you can do this in O(n lg n) by using an indexed balanced binary tree (a binary tree where each node stores the number of nodes to its left and right). With this structure, you can get worst-case O(lg n) insertion or deletion at any point by walking the tree to find the position at which the new element belongs, then doing whatever fixup is necessary to maintain the balance condition (for example, if it's a red-black tree, you'd do a red-black tree fixup).
Given this setup, you could replay all the operations into a tree structure like this in O(n lg n) because each individual operation takes at most O(lg n) to complete. Once you have the tree, you can then do an inorder traversal of the elements to get them back in the proper order, and can append all the values to a resulting list in O(n) time, for a net of O(n lg n).
I'm going to think about this more and see if I can come up with a way of doing this in linear time. In the meantime, this at least shows that it's possible to do this in subquadratic time.
I have a hunch that there might be an O(n) algorithm.
Step 1:
Radix-sort digitally on the index. Takes O(n) time. This is a stable sort if done from the LSB side.
Step 2:
Let say there are operations with index i but no operations with a smaller index that has not been done. We can then replay operations at index i in the correct order. Specifically what the operations 'insert' and 'remove' are doing is not clear to me. Worst case is O(n lg n) with the ideas of a binary tree, but maybe the replaying can be done in O(n) because it is local.
Step 3:
Lift step 2 to an inductive argument as a proof of correctness. After the steps at index i there is an invariant to be maintained and a shorter list of operations, so by induction, ... (details) ...
精彩评论