array.first vs. array[0]


(Adriano Ferreira) #1

Hi everyone!

I’ve been tinkering with a few sorting algorithms in Swift <https://github.com/adrfer/Sort> and noticed a diference in behaviour when it comes to accessing the first element of a collection.

If the method `first` from `CollectionType` is used, one needs to unwrap the returned optional to use it. Pretty standard stuff... However, if one uses subscripting, no unwrapping is required.

For example, when using subscripting:

func quickSort(array: [Int]) -> [Int] {

    guard array.count > 1 else { return array }

    let (pivot, rest) = (array[0], array.dropFirst()) // no need to unwrap `pivot` for further use

    let lessThan = rest.filter({ $0 < pivot })

    let greaterThanOrEqual = rest.filter({ $0 >= pivot })

    return quickSort(lessThan) + [pivot] + quickSort(greaterThanOrEqual)
}

But, when using the method `first`:

func quickSort(array: [Int]) -> [Int] {

    guard array.count > 1 else { return array }

    let (pivot, rest) = (array.first, array.dropFirst())

    let lessThan = rest.filter({ $0 < pivot }) // unwrapping `pivot` is not required here

    let greaterThanOrEqual = rest.filter({ $0 >= pivot }) // unwrapping `pivot` is not required here

    return quickSort(lessThan) + [pivot!] + quickSort(greaterThanOrEqual) // unwrapping `pivot` is now required here
}

Isn’t the subscript supposed to return an optional as well?

Why unwrapping isn't required when `pivot` is used within the `filter` call?

Best,

— A


(David Turnbull) #2

Isn’t the subscript supposed to return an optional as well?

Not arrays. They stop your program when out of bounds.

Why unwrapping isn't required when `pivot` is used within the `filter`
call?

Type inference on the closure. $0 is made optional as part of the call.

-david

···

On Sat, Jan 16, 2016 at 2:46 PM, Adriano Ferreira via swift-users < swift-users@swift.org> wrote:


(Jordan Rose) #3

For the record, this isn't a difference between arrays and other collections. All Collections return a non-optional value when subscripted by an Index, with the assumption that you shouldn't be putting random indexes into a collection unless they came from that collection in the first place, or have been already validated in some way. With 'first', on the other hand, it's very convenient to be able to say "collection.first ?? defaultValue".

"But what about dictionaries?" Ah, but a dictionary key is not an Index (note the capital). The relation between a Collection and an Index is that there must be a constant-time operation to get to a value from an Index. There's a separate DictionaryIndex that represents a position in a dictionary for that purpose.

Jordan

···

On Jan 16, 2016, at 15:07, David Turnbull via swift-users <swift-users@swift.org> wrote:

On Sat, Jan 16, 2016 at 2:46 PM, Adriano Ferreira via swift-users <swift-users@swift.org <mailto:swift-users@swift.org>> wrote:
Isn’t the subscript supposed to return an optional as well?

Not arrays. They stop your program when out of bounds.


(Dave Abrahams) #4

Well, but that also applies to dictionary keys. The difference is that
a sequence of consecutive indices can be used to access all the elements
of the collection.

-Dave

···

on Wed Jan 20 2016, Jordan Rose via swift-users <swift-users-AT-swift.org> wrote:

On Jan 16, 2016, at 15:07, David Turnbull via swift-users <swift-users@swift.org> wrote:

On Sat, Jan 16, 2016 at 2:46 PM, Adriano Ferreira via swift-users >> <swift-users@swift.org <mailto:swift-users@swift.org>> wrote:
Isn’t the subscript supposed to return an optional as well?

Not arrays. They stop your program when out of bounds.

For the record, this isn't a difference between arrays and other
collections. All Collections return a non-optional value when
subscripted by an Index, with the assumption that you shouldn't be
putting random indexes into a collection unless they came from that
collection in the first place, or have been already validated in some
way. With 'first', on the other hand, it's very convenient to be able
to say "collection.first ?? defaultValue".

"But what about dictionaries?" Ah, but a dictionary key is not an
Index (note the capital). The relation between a Collection and an
Index is that there must be a constant-time operation to get to a
value from an Index.


(Jens Alfke) #5

Not necessarily. It does if the dictionary is based on a [well-implemented] hash table. But if it’s implemented as a search tree (as C++’s std::map is), it’s not — lookup time is O(log n).

Quibbling aside, there are significant differences between looking up array items and lookup up dictionary keys. It’s extremely common to look up a key that might validly not exist in the dictionary, but it’s pretty rare to do the same with an array — usually if the array index is out of bounds it’s a programmer error.

—Jens

···

On Jan 20, 2016, at 12:28 PM, Dave Abrahams via swift-users <swift-users@swift.org> wrote:

"But what about dictionaries?" Ah, but a dictionary key is not an
Index (note the capital). The relation between a Collection and an
Index is that there must be a constant-time operation to get to a
value from an Index.

Well, but that also applies to dictionary keys.


(Dave Abrahams) #6

Swift Dictionaries are documented as having O(1) lookup.

···

on Wed Jan 20 2016, Jens Alfke <jens-AT-mooseyard.com> wrote:

On Jan 20, 2016, at 12:28 PM, Dave Abrahams via swift-users <swift-users@swift.org> wrote:

"But what about dictionaries?" Ah, but a dictionary key is not an
Index (note the capital). The relation between a Collection and an
Index is that there must be a constant-time operation to get to a
value from an Index.

Well, but that also applies to dictionary keys.

Not necessarily. It does if the dictionary is based on a
[well-implemented] hash table. But if it’s implemented as a search
tree (as C++’s std::map is), it’s not — lookup time is O(log n).


(David Turnbull) #7

Only the lookup by index is O(1). Lookup by key is not specified. You can't
O(1) by key without a perfect hash function.

-david

···

On Thu, Jan 21, 2016 at 12:23 PM, Dave Abrahams via swift-users < swift-users@swift.org> wrote:

Swift Dictionaries are documented as having O(1) lookup.


(Jens Alfke) #8

Hash tables are generally considered O(1) even without perfect hashing. If the table grows sufficiently as items are added, so that there are few collisions, it will almost always take 1 probe to find a value. If it sometimes takes 2 or 3 or more, that just raises the average a little, and an average of (say) 1.053 probes is still O(1) because it doesn’t increase as the data set grows.

My point earlier was that the built-in Dictionary class is not the only possible class with associative-array semantics, and other implementations of associative arrays can have very different performance characteristics.

—Jens

···

On Jan 21, 2016, at 1:02 PM, David Turnbull <dturnbull@gmail.com> wrote:

Only the lookup by index is O(1). Lookup by key is not specified. You can't O(1) by key without a perfect hash function.


(Dave Abrahams) #9

Then that's a bug in our documentation; please file a ticket! It should
guarantee O(1) as long as the Dictionary isn't backed by NSDictionary
and the hash function is good.

···

on Thu Jan 21 2016, David Turnbull <dturnbull-AT-gmail.com> wrote:

On Thu, Jan 21, 2016 at 12:23 PM, Dave Abrahams via swift-users < > swift-users@swift.org> wrote:

Swift Dictionaries are documented as having O(1) lookup.

Only the lookup by index is O(1). Lookup by key is not specified.


(David Turnbull) #10

The documentation is correct. Thinking about key lookups as O(1) is what
led to this problem...
http://www.ocert.org/advisories/ocert-2011-003.html

-david

···

On Thu, Jan 21, 2016 at 1:36 PM, Dave Abrahams <dabrahams@apple.com> wrote:

on Thu Jan 21 2016, David Turnbull <dturnbull-AT-gmail.com> wrote:

> On Thu, Jan 21, 2016 at 12:23 PM, Dave Abrahams via swift-users < > > swift-users@swift.org> wrote:
>
>> Swift Dictionaries are documented as having O(1) lookup.
>>
>
> Only the lookup by index is O(1). Lookup by key is not specified.

Then that's a bug in our documentation; please file a ticket! It should
guarantee O(1) as long as the Dictionary isn't backed by NSDictionary
and the hash function is good.


(Dave Abrahams) #11

The documentation is correct. Thinking about key lookups as O(1) is what
led to this problem...
http://www.ocert.org/advisories/ocert-2011-003.html

Sorry, no, the documentation isn't correct, in that it doesn't reflect
our intention. It should say that Dictionary lookups are amortized O(1)
when the dictionary isn't backed by an NSDictionary, subject to the
quality of the hash function (which as we all know, is a big caveat).

···

on Thu Jan 21 2016, David Turnbull <dturnbull-AT-gmail.com> wrote:

-david

On Thu, Jan 21, 2016 at 1:36 PM, Dave Abrahams <dabrahams@apple.com> wrote:

on Thu Jan 21 2016, David Turnbull <dturnbull-AT-gmail.com> wrote:

> On Thu, Jan 21, 2016 at 12:23 PM, Dave Abrahams via swift-users < >> > swift-users@swift.org> wrote:
>
>> Swift Dictionaries are documented as having O(1) lookup.
>>
>
> Only the lookup by index is O(1). Lookup by key is not specified.

Then that's a bug in our documentation; please file a ticket! It should
guarantee O(1) as long as the Dictionary isn't backed by NSDictionary
and the hash function is good.


(Jens Alfke) #12

Isn’t NSDictionary O(1) too? It’s definitely a hash table.

—Jens

···

On Jan 21, 2016, at 2:51 PM, Dave Abrahams <dabrahams@apple.com> wrote:

It should say that Dictionary lookups are amortized O(1)
when the dictionary isn't backed by an NSDictionary


(Jordan Rose) #13

The default implementation of NSDictionary is a hash table, but because you're allowed to subclass it (if discouraged <https://developer.apple.com/library/mac/documentation/Cocoa/Reference/Foundation/Classes/NSDictionary_Class/index.html#//apple_ref/doc/uid/20000140-DontLinkElementID_1>) we can't 100% promise anything about a bridged dictionary's behavior.

Jordan

···

On Jan 21, 2016, at 16:36 , Jens Alfke via swift-users <swift-users@swift.org> wrote:

On Jan 21, 2016, at 2:51 PM, Dave Abrahams <dabrahams@apple.com <mailto:dabrahams@apple.com>> wrote:

It should say that Dictionary lookups are amortized O(1)
when the dictionary isn't backed by an NSDictionary

Isn’t NSDictionary O(1) too? It’s definitely a hash table.