Printable View
Hello,
I am looking for a structure that allows me to:
1. Append in O(logN) or better
2. Delete in O(logN) or better
3. Access the ith item in O(1)
I don't need any other operations
In addition, new items are always greater (>) than existing items (the structure is always sorted) and no item appears twice.
Maybe, I think it is impossible...
c# SortedDictionary removal and insertion and retrieval is O(log n)
see more information here and some comparison between c# SortedDictionary and SortedList.
MSDN:
http://msdn.microsoft.com/en-us/library/ms132319.aspx
what do you mean by access O(1) i think it is not possible !
if you mean access by KEY, index all Array-Like structures apply to it but something like any kind of Linked-List (recursive-Two way- with header/ without header) don't apply to it.
Deletion and Append O(N), Access O(1), that is an array.
You can improve the first two to O(logN) by making access more expensive. For any kind of item. I know that.
What I want, is to make the first two cheaper, but keeping access at O(1), by abusing the fact that I only need delete/append (and not insert). and the values are increasing. If it's possible...
If you use a sorted array, append would also be in O(1) due to the nature of your data, but deletion not at the end would still be in O(n).
That's right, I meanto to say Deletion and Insertion are O(N).
Basically what I am trying to avoid is the effect that deleting at the start requires moving all items in front to move one back. But I guess there is no way around it if you want to keep access at O(1).
What about something like
n items, m (already done) deletions, or gaps
O(m) access, O(1) append, O(logN) delete... possible? hmm
Are those worst case or average?
The primary operations of a VList are:
* Locate the kth element (O(1) average, O(log n) worst-case)
* Add an element to the front of the VList (O(1) average, with an occasional allocation)
* Obtain a new array beginning at the second element of an old array (O(1))
* Compute the length of the list (O(log n))
You haven't specified whether it's deletiog from one end, from either end or from the middle you want to be scalable.
Deletion from everywhere.
I had a look at VLists, but it seems a bit flawed. What happens if you delete lots of elements in the middle? The VList will turn into a linked list? Or is there some magical "rebalancing" going on? I will read the paper on it.
Also, if you have 2^20 elements, in the first node there will be 2^10 items. What happens if you delete the 2^9th element? Still need to move lots of elements.