Talk:VList: Difference between revisions
→Some problems
Line 30:
:::::: Ok... perhaps this "languages with high level arrays do not need this" concept should be included in the task description? Meanwhile, to clone the array you need to copy the data from the first (biggest) block of data, which on average will contain c*n elements, where c is a constant (perhaps 0.25) and n is the length of the array. This means that that operation needs O(n) time. --[[User:Rdm|Rdm]] 16:25, 13 September 2011 (UTC)
::::::: Hmm? If you want to make a reference to a slice of the array, just copy the pointer and set a new offset, which is O(1). If you need to copy the content, then every block that's not empty should be copied, which involves all n elements that's currently filled. The point of taking a slice reference is to avoid this copying. --[[User:Ledrug|Ledrug]] 18:26, 13 September 2011 (UTC)
:::::::: Hmm.. ok... But you need to be careful about the set of allowed operations on a slice. For example, think about what happens to a slice that omits the first character of the original and then what happens when you add another character. Note that if you add to the slice, the behavior of the original is different if it was length 2 vs. if it was length 6. Something analogous can happen with cloning: with a suitably restricted set of operations (if adding is allowed but not dropping) you do not have to clone the entire set of data and can clone only the first block. --[[User:Rdm|Rdm]] 19:50, 13 September 2011 (UTC)
| |||