Add stableSort() to the standard library.

Evolution Discussion
21

I would think that for making use of unstableSort() you would have to understand what unstable sorting means in the first place and therefore it’s not unreasonable to expect that people wanting to use an unstable sort for performance reasons would actively look for one and have no problems finding it, especially if the documentation for sort() says „see also: unstableSort()“. The latter would also help other’s not (that) aware of unstable sorting to discover it.
But I’m not strongly opposed to a parameter (the default should be .Stable in that case as well, I think). It certainly helps discoverability even more than the docs.
Maybe autocomplete should point out alternatives from the „see also“ section of the documentation as well ;-)

-Thorsten

···

Am 20.01.2016 um 21:19 schrieb Tyler Cloutier via swift-evolution <swift-evolution@swift.org>:

On Jan 20, 2016, at 9:58 AM, Dave Abrahams via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

4. I'm not a fan of adding a parameter to sort to select stability,
  because of the added API complexity. People who want a
  faster-but-unstable sort can call unstableSort, right?

I think the potential here is that people might not even be aware there is such an option. unstableSort() not terribly autocomplete friendly which I think adds to complexity. It seems like a parameter would be in line with API’s like print(_:separator:terminator:), even though the print arguments are not constants. I think the print API is very intuitive, but perhaps I’m misunderstanding what you mean by complexity?

22

Feedback very appreciated.

Add stableSort() to the standard library.

####
Introduction
####
At the time of writing the Swift standard library provides two way two
different versions of sort.
The first one is sort(), which provides a regular unstable[1] sorting algorithm.
The second one, sortInPlace(), which also provides unstable sorting with the
additional guarantee that the algorithm will operate in-place, i.e., it will
use only a constant amount of extra space (independent from the input size).
The aim of this proposal is to implement a third variant, stableSort(), in order
to provide a stable version of sorting.

A few thoughts:

1. The C++ stable sort algorithm draws on just nearly every other
  algorithm in the entire standard library, many of which we don't
  currently have in Swift. Doing something similar would expand the
  algorithms we support, which IMO would be a good thing.

2. I am very intrigued with Python's argument that, for a
  general-purpose audience, stable sorting should be the default. It's
  certainly more widely-useful than unstable sorting.

Stable sorting as the default would follow the Principle of Least
Astonishment, I think (especially for programmers coming from Python
and Java, where stable is the default). And the more widely useful
algorithm, even if it is at the expense of performance, seems like the
right choice for a standard library.

3. There are several interesting and fast stable sorting algorithms out
  there, including Python's timsort; it would take some experimentation
  to discover which one(s) to use for Swift.

I suppose one complication for Swift is that any particular algorithm
might perform well with reference types but less so with value types
if they happen to be large and the algorithm does a relatively large
amount of copying.

That's true, but if that's the case we could (and should) select the
algorithm accordingly. It's all statically-knowable, so shouldn't even
cost a branch in practice.

4. I'm not a fan of adding a parameter to sort to select stability,
  because of the added API complexity. People who want a
  faster-but-unstable sort can call unstableSort, right?

I wonder if anyone actually would be clamoring for an unstable sort
option, per se, given how well timsort seems to perform.

Maybe not. If you look around, you'll find timsort has a handful of
competitors we also ought to examine.

An algorithm, stable or unstable, with lower memory requirements or
different edge case behavior might be the most useful alternative. For
instance, an algorithm that sorts in-place without any significant
memory overhead (“in-place" not in the mutating sense, but in not
requiring temporary storage during the sort) could be handy when
dealing with large sequences on more memory-constrained
devices.

True; that's what the current algorithm does.

Still, I wonder if it will really be a pain point for anyone
if the only option is a state-of-the-art stable sort.

A real question. There's a lot of research to do, here. If someone
wanted to take on this investigation and do a thorough job of it, I'm
sure it would have a big impact.

Cheers,
Dave

···

on Thu Jan 21 2016, Charles Kissinger <crk-AT-akkyra.com> wrote:

On Jan 20, 2016, at 9:58 AM, Dave Abrahams via swift-evolution <swift-evolution@swift.org> wrote:
on Sun Jan 10 2016, Davide Italiano via swift-evolution >> <swift-evolution-m3FHrko0VLzYtjvyW6yDsg-AT-public.gmane.org> wrote:

23

Hey,

A single sort function with an enum parameter that let's you choose among
sort(), sortInPlace() and stableSort() would be nice.

enum SortOptions {
  case none
  case InPlace
  case Stable
}

func sort(items, type: SortOptions = .none)

// call to sort function
sort([1,2,3,4], type: .Stable)

This way a single sort function handles all three cases and enums provide
autocompletion while calling the function.

···

On Fri, Jan 22, 2016 at 3:22 AM, Dave Abrahams via swift-evolution < swift-evolution@swift.org> wrote:

on Thu Jan 21 2016, Charles Kissinger <crk-AT-akkyra.com> wrote:

>> On Jan 20, 2016, at 9:58 AM, Dave Abrahams via swift-evolution < > swift-evolution@swift.org> wrote:
>>
>>
>> on Sun Jan 10 2016, Davide Italiano via swift-evolution > >> <swift-evolution-m3FHrko0VLzYtjvyW6yDsg-AT-public.gmane.org> wrote:
>
>>
>>> Feedback very appreciated.
>>>
>>> Add stableSort() to the standard library.
>>>
>>> ####
>>> Introduction
>>> ####
>>> At the time of writing the Swift standard library provides two way two
>>> different versions of sort.
>>> The first one is sort(), which provides a regular unstable[1] sorting
algorithm.
>>> The second one, sortInPlace(), which also provides unstable sorting
with the
>>> additional guarantee that the algorithm will operate in-place, i.e.,
it will
>>> use only a constant amount of extra space (independent from the input
size).
>>> The aim of this proposal is to implement a third variant,
stableSort(), in order
>>> to provide a stable version of sorting.
>>
>> A few thoughts:
>>
>> 1. The C++ stable sort algorithm draws on just nearly every other
>> algorithm in the entire standard library, many of which we don't
>> currently have in Swift. Doing something similar would expand the
>> algorithms we support, which IMO would be a good thing.
>>
>> 2. I am very intrigued with Python's argument that, for a
>> general-purpose audience, stable sorting should be the default. It's
>> certainly more widely-useful than unstable sorting.
>
> Stable sorting as the default would follow the Principle of Least
> Astonishment, I think (especially for programmers coming from Python
> and Java, where stable is the default). And the more widely useful
> algorithm, even if it is at the expense of performance, seems like the
> right choice for a standard library.
>
>>
>> 3. There are several interesting and fast stable sorting algorithms out
>> there, including Python's timsort; it would take some experimentation
>> to discover which one(s) to use for Swift.
>
> I suppose one complication for Swift is that any particular algorithm
> might perform well with reference types but less so with value types
> if they happen to be large and the algorithm does a relatively large
> amount of copying.

That's true, but if that's the case we could (and should) select the
algorithm accordingly. It's all statically-knowable, so shouldn't even
cost a branch in practice.

>> 4. I'm not a fan of adding a parameter to sort to select stability,
>> because of the added API complexity. People who want a
>> faster-but-unstable sort can call unstableSort, right?
>
> I wonder if anyone actually would be clamoring for an unstable sort
> option, per se, given how well timsort seems to perform.

Maybe not. If you look around, you'll find timsort has a handful of
competitors we also ought to examine.

> An algorithm, stable or unstable, with lower memory requirements or
> different edge case behavior might be the most useful alternative. For
> instance, an algorithm that sorts in-place without any significant
> memory overhead (“in-place" not in the mutating sense, but in not
> requiring temporary storage during the sort) could be handy when
> dealing with large sequences on more memory-constrained
> devices.

True; that's what the current algorithm does.

> Still, I wonder if it will really be a pain point for anyone
> if the only option is a state-of-the-art stable sort.

A real question. There's a lot of research to do, here. If someone
wanted to take on this investigation and do a thorough job of it, I'm
sure it would have a big impact.

Cheers,
Dave
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

24

Is it mutating or non-mutating?

···

on Fri Jan 22 2016, ankit goel <swift-evolution@swift.org> wrote:

Hey,

A single sort function with an enum parameter that let's you choose among
sort(), sortInPlace() and stableSort() would be nice.

--
-Dave

25

This seems interesting, simple and clean. Also, this kinda reminds me of the Strategy Pattern <https://en.wikipedia.org/wiki/Strategy_pattern&gt;:

protocol SortingStrategy { /* declare `sort()` */ }

class StableSort: SortingStrategy { /* implement a stable `sort()` */ }

class UnstableSort: SortingStrategy { /* implement a unstable `sort()` */ }

class Sorter {

    let strategy: SortingStrategy

    init(using strategy: SortingStrategy) { self.strategy = strategy }

    func sort( /* ... */ ) { return self.strategy.sort( /* ... */ ) }
}

let stableSort = Sorter(using: StableSort())
stableSort.sort( /* ... */ )

let unstableSort = Sorter(using: UnstableSort())
unstableSort.sort( /* ... */ )

One could go further and, instead of `StableSort` and `UnstableSort`, provide different options of sorting algorithms:

class IntroSort: SortingStrategy { /* intro sort implementation */ }
class QuickSort: SortingStrategy { /* quick sort implementation */ }
class MergeSort: SortingStrategy { /* merge sort implementation */ }
// ...

Not sure, however, if having those in the language itself would be make sense. Perhaps a separate library would be a better place.

Wonder if using protocol with default implementations above, rather than classes, would’ve been better...

Best,

— A

···

On Jan 22, 2016, at 8:03 AM, ankit goel via swift-evolution <swift-evolution@swift.org> wrote:

Hey,

A single sort function with an enum parameter that let's you choose among sort(), sortInPlace() and stableSort() would be nice.

enum SortOptions {
  case none
  case InPlace
  case Stable
}

func sort(items, type: SortOptions = .none)

// call to sort function
sort([1,2,3,4], type: .Stable)

This way a single sort function handles all three cases and enums provide autocompletion while calling the function.

On Fri, Jan 22, 2016 at 3:22 AM, Dave Abrahams via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

on Thu Jan 21 2016, Charles Kissinger <crk-AT-akkyra.com> wrote:

>> On Jan 20, 2016, at 9:58 AM, Dave Abrahams via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:
>>
>>
>> on Sun Jan 10 2016, Davide Italiano via swift-evolution > >> <swift-evolution-m3FHrko0VLzYtjvyW6yDsg-AT-public.gmane.org <http://swift-evolution-m3fhrko0vlzytjvyw6ydsg-at-public.gmane.org/&gt;&gt; wrote:
>
>>
>>> Feedback very appreciated.
>>>
>>> Add stableSort() to the standard library.
>>>
>>> ####
>>> Introduction
>>> ####
>>> At the time of writing the Swift standard library provides two way two
>>> different versions of sort.
>>> The first one is sort(), which provides a regular unstable[1] sorting algorithm.
>>> The second one, sortInPlace(), which also provides unstable sorting with the
>>> additional guarantee that the algorithm will operate in-place, i.e., it will
>>> use only a constant amount of extra space (independent from the input size).
>>> The aim of this proposal is to implement a third variant, stableSort(), in order
>>> to provide a stable version of sorting.
>>
>> A few thoughts:
>>
>> 1. The C++ stable sort algorithm draws on just nearly every other
>> algorithm in the entire standard library, many of which we don't
>> currently have in Swift. Doing something similar would expand the
>> algorithms we support, which IMO would be a good thing.
>>
>> 2. I am very intrigued with Python's argument that, for a
>> general-purpose audience, stable sorting should be the default. It's
>> certainly more widely-useful than unstable sorting.
>
> Stable sorting as the default would follow the Principle of Least
> Astonishment, I think (especially for programmers coming from Python
> and Java, where stable is the default). And the more widely useful
> algorithm, even if it is at the expense of performance, seems like the
> right choice for a standard library.
>
>>
>> 3. There are several interesting and fast stable sorting algorithms out
>> there, including Python's timsort; it would take some experimentation
>> to discover which one(s) to use for Swift.
>
> I suppose one complication for Swift is that any particular algorithm
> might perform well with reference types but less so with value types
> if they happen to be large and the algorithm does a relatively large
> amount of copying.

That's true, but if that's the case we could (and should) select the
algorithm accordingly. It's all statically-knowable, so shouldn't even
cost a branch in practice.

>> 4. I'm not a fan of adding a parameter to sort to select stability,
>> because of the added API complexity. People who want a
>> faster-but-unstable sort can call unstableSort, right?
>
> I wonder if anyone actually would be clamoring for an unstable sort
> option, per se, given how well timsort seems to perform.

Maybe not. If you look around, you'll find timsort has a handful of
competitors we also ought to examine.

> An algorithm, stable or unstable, with lower memory requirements or
> different edge case behavior might be the most useful alternative. For
> instance, an algorithm that sorts in-place without any significant
> memory overhead (“in-place" not in the mutating sense, but in not
> requiring temporary storage during the sort) could be handy when
> dealing with large sequences on more memory-constrained
> devices.

True; that's what the current algorithm does.

> Still, I wonder if it will really be a pain point for anyone
> if the only option is a state-of-the-art stable sort.

A real question. There's a lot of research to do, here. If someone
wanted to take on this investigation and do a thorough job of it, I'm
sure it would have a big impact.

Cheers,
Dave
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution