On Monday, February 10, 2014 1:42:56 PM UTC-5, Steven G. Johnson wrote: > > > > On Thursday, November 29, 2012 3:24:50 PM UTC-5, Jeff Bezanson wrote: >> >> We have del(x, i) and del(x, i:j). We could add del(x, I) where I is a >> vector, but we can't do it any faster than >> for i in I del(x,i) end > > > Why can't it be done faster? Presumably you could move all of the > non-deleted entries to the beginning of the vector and then do the resizing > once, rather than a single time. This would reduce the number of moves to > O(length(I)) rather than the O(length(I)^2) of "for i in I del(x,i) end" >
Sorry, that should be O(length(x)) rather than O(length(x) * length(I)). Assuming you pay the O(n log n) cost to sort I first.