> On Feb 20, 2017, at 7:38 AM, Ole Begemann <[email protected]> wrote:
>
>>
>> On 17 Feb 2017, at 01:39, Ben Cohen via swift-evolution
>> <[email protected] <mailto:[email protected]>> wrote:
>>
>> Hi swift-evolution,
>>
>> Following up on Ted’s post regarding the opening up of stage 2, I’m starting
>> a thread to discuss additive algorithms for Sequence and Collection.
>>
>> Here is a list of commonly requested algorithms to operate on Sequence or
>> Collection:
>>
>> In-place transformations:
>> transform elements in a MutableCollection using a closure i.e. in-place map
>> remove(where:) that takes a predicate i.e. in-place filter
>> remove(indices:) that takes a Sequence of Index
> Is it possible to implement this (efficiently) with
> RangeReplaceableCollection's current feature set?
In-place, I don’t think so, because of the shuffling-down-being-O(n) problem.
It is possible with a combo of MutableCollection and
RangeReplaceableCollection, because MutableCollection implies constant-time
mutation of a single element:
extension MutableCollection where Self: RangeReplaceableCollection {
mutating func remove(where predicate: (Iterator.Element) -> Bool) {
guard var i = index(where: predicate) else { return }
var j = index(after: i)
while j != endIndex {
let e = self[j]
if !predicate(e) {
// here's where you need MutableCollection...
self[i] = e
formIndex(after: &i)
}
formIndex(after: &j)
}
// and this is the part you need RRC for...
removeSubrange(i..<endIndex)
}
}
But if you tried to implement this with RRC alone, you’d hit the challenge of
single-element replacement not necessarily being O(n). String is the poster
child for this problem since the graphemes you might be wanting to remove are
variable width.
Making this a full-fledged member of one of RangeReplaceableCollection would
allow types that can’t offer constant-time single element replacement, but can
implement an algorithm that slides down values over the top of others
efficiently in one pass, to provide an efficient implementation. Additionally,
types like Array or String that are backed by contiguous storage might be able
to make use of lower-level memory operations. The default implementation could
be to rebuild self from scratch using lazy filter, which while sub-optimal can
at least be done in linear time.
> Since replaceSubrange(_:with:) potentially invalidates indices, you can't
> call it repeatedly and expect that the passed-in indices are still valid.
>
> I suppose it's possible to create a new empty collection, then iterate over
> the existing collection's indices and append each element that doesn't match
> one of the indices to be removed, but that sounds a bit awkward to me. Is
> there a better solution?
>
>> bulk operations (replace, remove, insert) on RangeReplaceableCollection for
>> a Sequence of subranges
> This relates to my question above. Is there a better way to implement this
> than creating an new empty collection and iterating over the existing
> elements, replacing/skipping/inserting at the passed-in subranges?
In-place operations avoid having to allocate/free a whole new buffer, avoid
copying the initial prefix of retained elements unnecessarily (a big deal if
you are removing a small proportion of the whole, especially if you sometimes
remove none), and also enable customized efficient implementations for specific
types. Collections that didn’t implement them could just get a default that
builds up from scratch like you describe.
If we had multi-range bulk remove, you could also implement remove(where:)
using it, at the cost of having to do it in two passes.
_______________________________________________
swift-evolution mailing list
[email protected]
https://lists.swift.org/mailman/listinfo/swift-evolution
