I wasn’t saying a SparseArray type should be part of the standard library, but possibly it’s something which could be added to Foundation or some 3rd-party “Common Collections” package.
Like all data structures, the most efficient one depends on how well you can predict what it will store and how it will be accessed/modified. A Dictionary<Integer> might be great for large collections that are exceptionally sparse, but it may also be wasteful depending on your circumstance.
As for unsafe initialisation, that’s something I badly, badly want. Basically, I want to be able to tell Array or String to allocate an internal buffer of size N, then fill it myself (perhaps using POSIX functions like read or recv, or concurrently with no guaranteed order), and tell it how much data I actually initialised. Then you could stroll off in to the sunshine with a real Array<T> or String that you read from a file or socket without copying. That’s the point when Array becomes as good as a C Array for me.
Of course, String being UTF16 would be an issue. There aren’t many files stored in UTF16, and even for sockets, if the server isn’t also Swift, you’ll probably be getting fed UTF8. You will still need to copy as you read in to a buffer of UTF8 before initialising the String’s backing storage with the corresponding UTF16 code-units. Perhaps the new String model/unicode encodings can help make that easier in some way.
Still, unsafe initialisation would be totally badass; In Objective-C, NSString needs to have a special method to read its data from a file to handle that one particular use-case, so it can use private knowledge to more efficiently read the file directly in to an internal buffer (I presume…). The alternative is to read the bytes in as an NSData and copy them in to an NSString (before throwing the NSData away, most likely). In Swift, we can have a better, more generalised solution.
- Karl
···
On 17 Apr 2017, at 18:35, Dave Abrahams via swift-evolution <swift-evolution@swift.org> wrote:
on Fri Apr 14 2017, Karl Wagner <swift-evolution@swift.org> wrote:
Personally, the only valid use-case I can think of is when you want to
initialise an Array’s elements out-of-order - i.e., you want to set a
value for myArray[2] despite myArray[0] and [1] not being
populated. In that case, it would be better to have some kind of
SparseArray type, and for us to have a proper API for unsafe
initialisation of stdlib types.
That is a point in the design space, but there's really no need to
expose unsafe initialization in order to get that functionality. You
could simply build ArrayOfOptional<T> that would present the same API as
Array<T?> but would use a separate inline buffer of bits to denote which
of the optionals were non-nil.
My bad, should have phrased my response better :^)
Under what circumstances would you need to be able to assign elements in an array out of order, while also requiring Array size/performance? (Genuinely curious, not trying to attack).
IMO, if the differences between Array and Dictionary would cause that much of an issue for your implementation, my guess is you have more important priorities than the need to assign elements out-of-order I don't think we'd need to add another type to the standard library for this use case.
···
On Apr 16, 2017, at 11:22 AM, Saagar Jha <saagar@saagarjha.com> wrote:
A Dictionary uses a lot more space than an Array, though, and allow for bogus keys like “-1”, etc.
Saagar Jha
On Apr 16, 2017, at 10:34, Riley Testut via swift-evolution <swift-evolution@swift.org> wrote:
Personally, the only valid use-case I can think of is when you want to initialise an Array’s elements out-of-order - i.e., you want to set a value for myArray[2] despite myArray[0] and [1] not being populated. In that case, it would be better to have some kind of SparseArray type, and for us to have a proper API for unsafe initialisation of stdlib types.
Wouldn't the same functionality be accomplished by a Dictionary with Int as the key type?
On Apr 14, 2017, at 10:00 AM, Karl Wagner via swift-evolution <swift-evolution@swift.org> wrote:
I'd actually say the #1 reason not to add this feature is that a lot of developers don't seem to understand this, and they're likely to use the feature to make their code try to continue in the face of programmer error instead of trapping like it properly should. A program in an inconsistent state is dangerous; best to stop it quickly before it does some damage.)
Right, so I think the reason is actually that a lot of developers don’t understand what an Array is. There are two use-cases for an Array:
1) As a string of items, don’t care about the length. The maximum prior knowledge you can have is that the order may or may not be significant. This includes operations like iteration, mapping, reducing and filtering.
2) As a string of items of specific length. You have prior knowledge about what you expect to find at each location. This includes operations like random-access subscripting, which is what we’re talking about.
Basically, the interesting part of a statement such as “let someValue = myArray[2]” is: why index 2? What’s so special about that element; why couldn't someValue be the item at any index N instead? It’s because we know to expect something of special significance at index 2.
In that case, the only time myArray[2] will fail is when your prior knowledge breaks down. The type-system has no way to encode and check for the length of an Array, and that has allowed somebody to pass in a bad value. So what to do?
A) If you absolutely require a value for myArray[2]: Insert a precondition check.
B) If you can still continue without myArray[2]: Check the length of the Array. Your logic will be branching anyway in this case, to account for the value (and subsequent values) being/not being present.
Personally, the only valid use-case I can think of is when you want to initialise an Array’s elements out-of-order - i.e., you want to set a value for myArray[2] despite myArray[0] and [1] not being populated. In that case, it would be better to have some kind of SparseArray type, and for us to have a proper API for unsafe initialisation of stdlib types.
Personally, the only valid use-case I can think of is when you want to
initialise an Array’s elements out-of-order - i.e., you want to set a
value for myArray[2] despite myArray[0] and [1] not being
populated. In that case, it would be better to have some kind of
SparseArray type, and for us to have a proper API for unsafe
initialisation of stdlib types.
That is a point in the design space, but there's really no need to
expose unsafe initialization in order to get that functionality. You
could simply build ArrayOfOptional<T> that would present the same API as
Array<T?> but would use a separate inline buffer of bits to denote which
of the optionals were non-nil.
I wasn’t saying a SparseArray type should be part of the standard
library, but possibly it’s something which could be added to
Foundation or some 3rd-party “Common Collections” package.
I think it probably should be.
Like all data structures, the most efficient one depends on how well
you can predict what it will store and how it will be
accessed/modified. A Dictionary<Integer> might be great for large
collections that are exceptionally sparse, but it may also be wasteful
depending on your circumstance.
As for unsafe initialisation, that’s something I badly, badly
want.
Me too. I'm just saying it's an orthogonal concern.
···
on Mon Apr 17 2017, Karl Wagner <swift-evolution@swift.org> wrote:
On 17 Apr 2017, at 18:35, Dave Abrahams via swift-evolution <swift-evolution@swift.org> wrote:
on Fri Apr 14 2017, Karl Wagner <swift-evolution@swift.org> wrote:
On Apr 16, 2017, at 19:33, Riley Testut <rileytestut@gmail.com> wrote:
My bad, should have phrased my response better :^)
Under what circumstances would you need to be able to assign elements in an array out of order, while also requiring Array size/performance? (Genuinely curious, not trying to attack).
IMO, if the differences between Array and Dictionary would cause that much of an issue for your implementation, my guess is you have more important priorities than the need to assign elements out-of-order I don't think we'd need to add another type to the standard library for this use case.
On Apr 16, 2017, at 11:22 AM, Saagar Jha <saagar@saagarjha.com <mailto:saagar@saagarjha.com>> wrote:
A Dictionary uses a lot more space than an Array, though, and allow for bogus keys like “-1”, etc.
Saagar Jha
On Apr 16, 2017, at 10:34, Riley Testut via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:
Personally, the only valid use-case I can think of is when you want to initialise an Array’s elements out-of-order - i.e., you want to set a value for myArray[2] despite myArray[0] and [1] not being populated. In that case, it would be better to have some kind of SparseArray type, and for us to have a proper API for unsafe initialisation of stdlib types.
Wouldn't the same functionality be accomplished by a Dictionary with Int as the key type?
On Apr 14, 2017, at 10:00 AM, Karl Wagner via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:
I'd actually say the #1 reason not to add this feature is that a lot of developers don't seem to understand this, and they're likely to use the feature to make their code try to continue in the face of programmer error instead of trapping like it properly should. A program in an inconsistent state is dangerous; best to stop it quickly before it does some damage.)
Right, so I think the reason is actually that a lot of developers don’t understand what an Array is. There are two use-cases for an Array:
1) As a string of items, don’t care about the length. The maximum prior knowledge you can have is that the order may or may not be significant. This includes operations like iteration, mapping, reducing and filtering.
2) As a string of items of specific length. You have prior knowledge about what you expect to find at each location. This includes operations like random-access subscripting, which is what we’re talking about.
Basically, the interesting part of a statement such as “let someValue = myArray[2]” is: why index 2? What’s so special about that element; why couldn't someValue be the item at any index N instead? It’s because we know to expect something of special significance at index 2.
In that case, the only time myArray[2] will fail is when your prior knowledge breaks down. The type-system has no way to encode and check for the length of an Array, and that has allowed somebody to pass in a bad value. So what to do?
A) If you absolutely require a value for myArray[2]: Insert a precondition check.
B) If you can still continue without myArray[2]: Check the length of the Array. Your logic will be branching anyway in this case, to account for the value (and subsequent values) being/not being present.
Personally, the only valid use-case I can think of is when you want to initialise an Array’s elements out-of-order - i.e., you want to set a value for myArray[2] despite myArray[0] and [1] not being populated. In that case, it would be better to have some kind of SparseArray type, and for us to have a proper API for unsafe initialisation of stdlib types.
Wouldn’t you then be able to use Array(repeating:count:) and repeat 0 (or something else) to achieve this then?
Yes, less performant than alloc’ing array (since we need to fill in default values), but doing otherwise would go against Swift’s safety model. If you truly wanted that behavior, you can use the UnsafePointer methods anyway (AFAIK).
···
On Apr 16, 2017, at 9:18 PM, Saagar Jha <saagar@saagarjha.com> wrote:
Dynamic programming comes to mind.
Saagar Jha
On Apr 16, 2017, at 19:33, Riley Testut <rileytestut@gmail.com <mailto:rileytestut@gmail.com>> wrote:
My bad, should have phrased my response better :^)
Under what circumstances would you need to be able to assign elements in an array out of order, while also requiring Array size/performance? (Genuinely curious, not trying to attack).
IMO, if the differences between Array and Dictionary would cause that much of an issue for your implementation, my guess is you have more important priorities than the need to assign elements out-of-order I don't think we'd need to add another type to the standard library for this use case.
On Apr 16, 2017, at 11:22 AM, Saagar Jha <saagar@saagarjha.com <mailto:saagar@saagarjha.com>> wrote:
A Dictionary uses a lot more space than an Array, though, and allow for bogus keys like “-1”, etc.
Saagar Jha
On Apr 16, 2017, at 10:34, Riley Testut via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:
Personally, the only valid use-case I can think of is when you want to initialise an Array’s elements out-of-order - i.e., you want to set a value for myArray[2] despite myArray[0] and [1] not being populated. In that case, it would be better to have some kind of SparseArray type, and for us to have a proper API for unsafe initialisation of stdlib types.
Wouldn't the same functionality be accomplished by a Dictionary with Int as the key type?
On Apr 14, 2017, at 10:00 AM, Karl Wagner via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:
I'd actually say the #1 reason not to add this feature is that a lot of developers don't seem to understand this, and they're likely to use the feature to make their code try to continue in the face of programmer error instead of trapping like it properly should. A program in an inconsistent state is dangerous; best to stop it quickly before it does some damage.)
Right, so I think the reason is actually that a lot of developers don’t understand what an Array is. There are two use-cases for an Array:
1) As a string of items, don’t care about the length. The maximum prior knowledge you can have is that the order may or may not be significant. This includes operations like iteration, mapping, reducing and filtering.
2) As a string of items of specific length. You have prior knowledge about what you expect to find at each location. This includes operations like random-access subscripting, which is what we’re talking about.
Basically, the interesting part of a statement such as “let someValue = myArray[2]” is: why index 2? What’s so special about that element; why couldn't someValue be the item at any index N instead? It’s because we know to expect something of special significance at index 2.
In that case, the only time myArray[2] will fail is when your prior knowledge breaks down. The type-system has no way to encode and check for the length of an Array, and that has allowed somebody to pass in a bad value. So what to do?
A) If you absolutely require a value for myArray[2]: Insert a precondition check.
B) If you can still continue without myArray[2]: Check the length of the Array. Your logic will be branching anyway in this case, to account for the value (and subsequent values) being/not being present.
Personally, the only valid use-case I can think of is when you want to initialise an Array’s elements out-of-order - i.e., you want to set a value for myArray[2] despite myArray[0] and [1] not being populated. In that case, it would be better to have some kind of SparseArray type, and for us to have a proper API for unsafe initialisation of stdlib types.
I don't think we'd need to add another type to the standard library for this use case.