on Sun Jan 15 2017, Rob Mayoff <mayoff-AT-dqd.com> wrote: > On Sat, Jan 14, 2017 at 7:41 PM, Dave Abrahams via swift-evolution < > swift-evolution@swift.org> wrote: > >> Oh... you mean that word(at:) itself would be linear, and thus >> algorithms that iterate the words linearly would be O(N^2)... yuck. >> > > Couldn't you fix this by replacing `func word(at n: Int) -> UInt` with `var > words: Sequence<UInt>`, producing the words from least to most significant?
Yeah... I thought about that... Since Sequence<UInt> isn't actually a valid type and the words are multipass, it would actually be either // probably too inefficient var words: AnyCollection<UInt> {get} or // a bit more complexity than I'd like to have for this purpose associatedtype Words : Collection /*where Iterator.Element == UInt*/ var words: Words {get} The one algorithm we currently have that uses words generically is iterating them in reverse order, but I think that's easily solvable. Slightly more concerning is that word(at:) was designed so that algorithms could index beyond countRepresentedWords and get a mathematically correct answer. So we'd need to either: 1. give that up - not a bad choice considering that it currently forces a branch into word(at:) that will (probably?) never be used if the algorithm is written in the most efficient possible way 2. keep countRepresentedWords and make words an infinite collection I guess I'm leaning towards #1. Exchanging countRepresentedWords/word(at:) for Words/words is almost an even trade in overall complexity. -- -Dave _______________________________________________ swift-evolution mailing list swift-evolution@swift.org https://lists.swift.org/mailman/listinfo/swift-evolution