NSMutableArray does provide O(1) insertion and removal from the start and the end of the array (http://ciechanowski.me/blog/2014/03/05/exposing-nsmutablearray/).
I think the reason Swift doesn't use this design is because it stores the data in a contiguous block of memory. Elia Cereda > Il giorno 18 set 2017, alle ore 04:48, Jon Shier via swift-users > <swift-users@swift.org> ha scritto: > > Yes, it seems to fly in the face of protocols as they exist in Swift at > the moment. Given the inability of protocols to guarantee performance > characteristics, breaking conformant types like this seems like a bad way to > try and fulfill a separate axis of concern. Wouldn’t a better idea be to move > things like popFirst(), and other methods requiring O(1) performance, to a > separate protocol? I’m also pretty sure it’s possible to implement popFirst > in O(1) for an Array, but Swift’s Array isn't generally very fast, at least > compared to C / C++. > > > > Jon > >>> On Sep 17, 2017, at 9:45 PM, Rick Mann via swift-users >>> <swift-users@swift.org> wrote: >>> >>> >>> On Sep 17, 2017, at 03:25 , Quinn The Eskimo! via swift-users >>> <swift-users@swift.org> wrote: >>> >>> >>> On 15 Sep 2017, at 21:35, Vladimir.S via swift-users >>> <swift-users@swift.org> wrote: >>> >>>> … for me it is very strange decision to disallow a method because it is >>>> 'expensive'. >>> >>> That’s pretty normal for Swift standard library protocols, which define not >>> just the behaviour of the routine but expected performance. `popFirst()` >>> is expected to be O(1) and that’s not possible with `Array`. >>> >>> The rationale behind this decision is, I believe, related to generic >>> algorithms. If I write generic code that uses `popFirst()`, I can only >>> guarantee the complexity of my code if I can rely on `popFirst()` being >>> O(1). If someone implements `popFirst()` as O(n), my generic algorithm >>> might go from O(n^2) to O(n^3), which is quite a change. >>> >>>> On 16 Sep 2017, at 01:44, Rick Mann via swift-users >>>> <swift-users@swift.org> wrote: >>>> >>>> Is the compiler looking at the name "pop" and adding additional >>>> constraints (and then spewing a bogus error message)? >>> >>> I’m not sure what’s going on here mechanically but, yes, the error message >>> is bogus. This is exactly what SR-5515 is talking about. >>> >>> If I were in your shoes I’d call this method something other than >>> `popFirst()`. This falls under my standard “if you change the semantics, >>> change the name” rule. Your implementation of `popFirst()` doesn’t conform >>> to the semantics of `popFirst()` — it’s O(n) because `removeFirst()` is >>> O(n) — and thus you want to avoid calling it `popFirst()`. >> >> All right, I'm happy to change the name to "safeRemoveFirst()", but I'm a >> bit irritated that there's an implicit performance constraint based on the >> name alone, without any obvious decorator syntax. >> >> >> -- >> Rick Mann >> rm...@latencyzero.com >> >> >> _______________________________________________ >> swift-users mailing list >> swift-users@swift.org >> https://lists.swift.org/mailman/listinfo/swift-users > > _______________________________________________ > swift-users mailing list > swift-users@swift.org > https://lists.swift.org/mailman/listinfo/swift-users
_______________________________________________ swift-users mailing list swift-users@swift.org https://lists.swift.org/mailman/listinfo/swift-users
