Add stableSort() to the standard library.

[dcci (Davide C. C. Italiano)]

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.

####
Motivation
####
Stable sorting is useful when sorting lists by multiple keys
(primary/secondary). A classical example is provided in [2].
Other programming languages, e.g. C++ or Go provide interfaces for stable
sorting in their standard libraries (respective std::stable_sort and Stable()).

#####
Proposed solution
#####
The API proposed just mirrors the one of regular sort().

@warn_unused_result func stableSort() -> [Self.Generator.Element]
Return an Array containing the sorted elements of source.

Discussion
The sorting algorithm is stable (does not change the relative order of elements
that compare equal).

Requires: The less-than operator (func <) defined in the Comparable conformance
is a strict weak ordering over the elements in self.

Constraints
Self.Generator.Element : Comparable

#####
Impact on existing code
#####
None.

####
Alternatives considered
####
An alternative would be that of augmenting sort() to get a Bool as argument
(stable: True). I'd rather like better to mirror what almost every
other programming
language does (providing a separate API).
It's an API breaking change (I think, but I'm not entirely sure).

####
Open questions
####
Should we also provide a stableSortInPlace() implementation?

Notes:

[1] A sorting algorithm is said to be "stable" if it maintains in the output
the relative order of entries with equal keys, and "unstable" otherwise.
[2] sorting - What is the benefit for a sort algorithm to be stable? - Stack Overflow

Thanks,

--
Davide

[Charles_Kissinger]

Add stableSort() to the standard library.

I am in favor of this. I have a use for it.

An alternative would be that of augmenting sort() to get a Bool as argument
(stable: True).

This approach, probably with a default of stable: Bool = false, might be more in line with the latest API guidelines. I kind of prefer separate functions myself.

Should we also provide a stableSortInPlace() implementation?

Definitely! It doesn’t make sense to have a mutating version of the unstable sort but not a corresponding mutating stable sort.

-CK

···

On Jan 10, 2016, at 3:11 PM, Davide Italiano via swift-evolution <swift-evolution@swift.org> wrote:

[gribozavr (Dmitri Gribenko)]

Feedback very appreciated.

Add stableSort() to the standard library.

Thank you for the proposal! It is much appreciated!

####
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.

####
Motivation
####
Stable sorting is useful when sorting lists by multiple keys
(primary/secondary). A classical example is provided in [2].
Other programming languages, e.g. C++ or Go provide interfaces for stable
sorting in their standard libraries (respective std::stable_sort and Stable()).

#####
Proposed solution
#####
The API proposed just mirrors the one of regular sort().

@warn_unused_result func stableSort() -> [Self.Generator.Element]
Return an Array containing the sorted elements of source.

Discussion
The sorting algorithm is stable (does not change the relative order of elements
that compare equal).

Requires: The less-than operator (func <) defined in the Comparable conformance
is a strict weak ordering over the elements in self.

Constraints
Self.Generator.Element : Comparable

We should also add an overload that takes a comparator closure.

#####
Impact on existing code
#####
None.

####
Alternatives considered
####
An alternative would be that of augmenting sort() to get a Bool as argument
(stable: True). I'd rather like better to mirror what almost every
other programming
language does (providing a separate API).
It's an API breaking change (I think, but I'm not entirely sure).

I have been thinking about this, and even though other languages it is
a separate function, since the fundamental operation of sort() and
stableSort() seems sufficiently similar to me, the defaulted parameter
seems like the right thing to do. What other parameters could sort()
conceivably get in future? Should the parameter be a boolean flag or
a resilient option set? Foundation has NSSortOptions, which has just
"Stable" and "Concurrent". The "concurrent" part, in my opinion,
needs to be handled somehow for all algorithms in a consistent manner,
rather than adding flags for each API separately.

####
Open questions
####
Should we also provide a stableSortInPlace() implementation?

Absolutely!

Dmitri

···

On Sun, Jan 10, 2016 at 3:11 PM, Davide Italiano <dccitaliano@gmail.com> wrote:

--
main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
(j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr@gmail.com>*/

[Adriano_Ferreira]

Perhaps instead of declaring new functions, just pass the `stability option` as a parameter to `sort` and `sortInPlace`. Makes sense?

Best,

— A

···

On Jan 10, 2016, at 6:11 PM, Davide Italiano via swift-evolution <swift-evolution@swift.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.

####
Motivation
####
Stable sorting is useful when sorting lists by multiple keys
(primary/secondary). A classical example is provided in [2].
Other programming languages, e.g. C++ or Go provide interfaces for stable
sorting in their standard libraries (respective std::stable_sort and Stable()).

#####
Proposed solution
#####
The API proposed just mirrors the one of regular sort().

@warn_unused_result func stableSort() -> [Self.Generator.Element]
Return an Array containing the sorted elements of source.

Discussion
The sorting algorithm is stable (does not change the relative order of elements
that compare equal).

Requires: The less-than operator (func <) defined in the Comparable conformance
is a strict weak ordering over the elements in self.

Constraints
Self.Generator.Element : Comparable

#####
Impact on existing code
#####
None.

####
Alternatives considered
####
An alternative would be that of augmenting sort() to get a Bool as argument
(stable: True). I'd rather like better to mirror what almost every
other programming
language does (providing a separate API).
It's an API breaking change (I think, but I'm not entirely sure).

####
Open questions
####
Should we also provide a stableSortInPlace() implementation?

Notes:

[1] A sorting algorithm is said to be "stable" if it maintains in the output
the relative order of entries with equal keys, and "unstable" otherwise.
[2] sorting - What is the benefit for a sort algorithm to be stable? - Stack Overflow

Thanks,

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

[hexdreamer (Kenny Leung)]

I can’t imagine a case where one wouldn’t want this, so why not just replace the existing sort with the stable sort?

-Kenny

···

On Jan 10, 2016, at 3:11 PM, Davide Italiano via swift-evolution <swift-evolution@swift.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.

####
Motivation
####
Stable sorting is useful when sorting lists by multiple keys
(primary/secondary). A classical example is provided in [2].
Other programming languages, e.g. C++ or Go provide interfaces for stable
sorting in their standard libraries (respective std::stable_sort and Stable()).

#####
Proposed solution
#####
The API proposed just mirrors the one of regular sort().

@warn_unused_result func stableSort() -> [Self.Generator.Element]
Return an Array containing the sorted elements of source.

Discussion
The sorting algorithm is stable (does not change the relative order of elements
that compare equal).

Requires: The less-than operator (func <) defined in the Comparable conformance
is a strict weak ordering over the elements in self.

Constraints
Self.Generator.Element : Comparable

#####
Impact on existing code
#####
None.

####
Alternatives considered
####
An alternative would be that of augmenting sort() to get a Bool as argument
(stable: True). I'd rather like better to mirror what almost every
other programming
language does (providing a separate API).
It's an API breaking change (I think, but I'm not entirely sure).

####
Open questions
####
Should we also provide a stableSortInPlace() implementation?

Notes:

[1] A sorting algorithm is said to be "stable" if it maintains in the output
the relative order of entries with equal keys, and "unstable" otherwise.
[2] sorting - What is the benefit for a sort algorithm to be stable? - Stack Overflow

Thanks,

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

[Janosch_Hildebrand]

Strong +1 for adding a stable sort to the stdlib.

Should we also provide a stableSortInPlace() implementation?

Yes!

···

On 11 Jan 2016, at 04:39, Dmitri Gribenko via swift-evolution <swift-evolution@swift.org> wrote:

####
Alternatives considered
####
An alternative would be that of augmenting sort() to get a Bool as argument
(stable: True). I'd rather like better to mirror what almost every
other programming
language does (providing a separate API).
It's an API breaking change (I think, but I'm not entirely sure).

I have been thinking about this, and even though other languages it is
a separate function, since the fundamental operation of sort() and
stableSort() seems sufficiently similar to me, the defaulted parameter
seems like the right thing to do. What other parameters could sort()
conceivably get in future? Should the parameter be a boolean flag or
a resilient option set? Foundation has NSSortOptions, which has just
"Stable" and "Concurrent". The "concurrent" part, in my opinion,
needs to be handled somehow for all algorithms in a consistent manner,
rather than adding flags for each API separately.

This seems like the right direction to me.

Are there other compelling options for 'sort' though?
More input towards the sort strategy/algorithm(s) employed is what I can think of but that has relatively limited applicability.
Then again this is going to exist anyway whether it is in the stdlib or not...

Personally I wouldn't mind `foo.sort(.stable)` so I'm pro option set if there is a reasonable case for keeping our options open, so to speak.

- Janosch

[dabrahams (Dave Abrahams)]

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.

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.

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?

-Dave

···

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.

[dcci (Davide C. C. Italiano)]

It does. In fact, as you may see, I proposed that as 'alternative
considered'. I'm not completely sure about API/ABI stability
consequences, so I left that as an option.

···

On Sun, Jan 10, 2016 at 9:39 PM, Adriano Ferreira <adriano.ferreira@me.com> wrote:

Perhaps instead of declaring new functions, just pass the `stability option` as a parameter to `sort` and `sortInPlace`. Makes sense?

[dcci (Davide C. C. Italiano)]

So, thank you all for the feedback.
I'll refine this proposal further, but I have a question.
Should we continue here (and I should paste a new version of the
proposal) -- or should I submit a new pull request to
apple/swift-evolution on github so that interested parties can comment
there?

Thanks,

···

On Sun, Jan 10, 2016 at 10:39 PM, Dmitri Gribenko <gribozavr@gmail.com> wrote:

On Sun, Jan 10, 2016 at 3:11 PM, Davide Italiano <dccitaliano@gmail.com> wrote:

Feedback very appreciated.

Add stableSort() to the standard library.

Thank you for the proposal! It is much appreciated!

####
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.

####
Motivation
####
Stable sorting is useful when sorting lists by multiple keys
(primary/secondary). A classical example is provided in [2].
Other programming languages, e.g. C++ or Go provide interfaces for stable
sorting in their standard libraries (respective std::stable_sort and Stable()).

#####
Proposed solution
#####
The API proposed just mirrors the one of regular sort().

@warn_unused_result func stableSort() -> [Self.Generator.Element]
Return an Array containing the sorted elements of source.

Discussion
The sorting algorithm is stable (does not change the relative order of elements
that compare equal).

Requires: The less-than operator (func <) defined in the Comparable conformance
is a strict weak ordering over the elements in self.

Constraints
Self.Generator.Element : Comparable

We should also add an overload that takes a comparator closure.

#####
Impact on existing code
#####
None.

####
Alternatives considered
####
An alternative would be that of augmenting sort() to get a Bool as argument
(stable: True). I'd rather like better to mirror what almost every
other programming
language does (providing a separate API).
It's an API breaking change (I think, but I'm not entirely sure).

I have been thinking about this, and even though other languages it is
a separate function, since the fundamental operation of sort() and
stableSort() seems sufficiently similar to me, the defaulted parameter
seems like the right thing to do. What other parameters could sort()
conceivably get in future? Should the parameter be a boolean flag or
a resilient option set? Foundation has NSSortOptions, which has just
"Stable" and "Concurrent". The "concurrent" part, in my opinion,
needs to be handled somehow for all algorithms in a consistent manner,
rather than adding flags for each API separately.

####
Open questions
####
Should we also provide a stableSortInPlace() implementation?

Absolutely!

Dmitri

--
main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
(j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr@gmail.com>*/

--
Davide

[Charles_Kissinger]

I can’t imagine a case where one wouldn’t want this, so why not just replace the existing sort with the stable sort?

-Kenny

It’s primarily a performance issue, I think. The best unstable sort algorithms are faster and/or use less memory, as I understand it. Are they enough faster to make a difference to most people? I don’t know.

-CK

···

On Jan 11, 2016, at 9:51 AM, Kenny Leung via swift-evolution <swift-evolution@swift.org> wrote:

On Jan 10, 2016, at 3:11 PM, Davide Italiano via swift-evolution <swift-evolution@swift.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.

####
Motivation
####
Stable sorting is useful when sorting lists by multiple keys
(primary/secondary). A classical example is provided in [2].
Other programming languages, e.g. C++ or Go provide interfaces for stable
sorting in their standard libraries (respective std::stable_sort and Stable()).

#####
Proposed solution
#####
The API proposed just mirrors the one of regular sort().

@warn_unused_result func stableSort() -> [Self.Generator.Element]
Return an Array containing the sorted elements of source.

Discussion
The sorting algorithm is stable (does not change the relative order of elements
that compare equal).

Requires: The less-than operator (func <) defined in the Comparable conformance
is a strict weak ordering over the elements in self.

Constraints
Self.Generator.Element : Comparable

#####
Impact on existing code
#####
None.

####
Alternatives considered
####
An alternative would be that of augmenting sort() to get a Bool as argument
(stable: True). I'd rather like better to mirror what almost every
other programming
language does (providing a separate API).
It's an API breaking change (I think, but I'm not entirely sure).

####
Open questions
####
Should we also provide a stableSortInPlace() implementation?

Notes:

[1] A sorting algorithm is said to be "stable" if it maintains in the output
the relative order of entries with equal keys, and "unstable" otherwise.
[2] sorting - What is the benefit for a sort algorithm to be stable? - Stack Overflow

Thanks,

--
Davide
_______________________________________________
swift-evolution mailing list
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

[dcci (Davide C. C. Italiano)]

I think you convinced me that passing a parameter to sort() is the
right way to go. About NSortOptions -- I'm not completely sure
(still).
I think it largely depends on the number of options we want to
provide, and I see pro/cons in both the approaches.

* If we change sort to take a Bool as argument, and then suddenly
realize we need another option (as you noted, Concurrent), then we
need to break the API again and make that more verbose. If the number
of options grows under a certain number the verboseness of the API
might start becoming a problem (although I don't think this is the
case for sort()).

* If we change sort to take NSOptions -- and then the number of
options to pass doesn't grow (in the worst, somewhat terrible case, we
don't introduce any other options other than `stable`), then we lose
in usability. It's sort of goofy providing an API with Options which
take a single option.

So, my preference is for passing a Bool to sort(), and *eventually*
re-evaluate if needed. I think my guiding principle is trying to not
violate the YAGNI/KISS principles. But I'm open to comments if
somebody disagrees =)

Thanks!

···

On Sun, Jan 10, 2016 at 7:39 PM, Dmitri Gribenko <gribozavr@gmail.com> wrote:

On Sun, Jan 10, 2016 at 3:11 PM, Davide Italiano <dccitaliano@gmail.com> wrote:

Feedback very appreciated.

Add stableSort() to the standard library.

Thank you for the proposal! It is much appreciated!

####
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.

####
Motivation
####
Stable sorting is useful when sorting lists by multiple keys
(primary/secondary). A classical example is provided in [2].
Other programming languages, e.g. C++ or Go provide interfaces for stable
sorting in their standard libraries (respective std::stable_sort and Stable()).

#####
Proposed solution
#####
The API proposed just mirrors the one of regular sort().

@warn_unused_result func stableSort() -> [Self.Generator.Element]
Return an Array containing the sorted elements of source.

Discussion
The sorting algorithm is stable (does not change the relative order of elements
that compare equal).

Requires: The less-than operator (func <) defined in the Comparable conformance
is a strict weak ordering over the elements in self.

Constraints
Self.Generator.Element : Comparable

We should also add an overload that takes a comparator closure.

#####
Impact on existing code
#####
None.

####
Alternatives considered
####
An alternative would be that of augmenting sort() to get a Bool as argument
(stable: True). I'd rather like better to mirror what almost every
other programming
language does (providing a separate API).
It's an API breaking change (I think, but I'm not entirely sure).

I have been thinking about this, and even though other languages it is
a separate function, since the fundamental operation of sort() and
stableSort() seems sufficiently similar to me, the defaulted parameter
seems like the right thing to do. What other parameters could sort()
conceivably get in future? Should the parameter be a boolean flag or
a resilient option set? Foundation has NSSortOptions, which has just
"Stable" and "Concurrent". The "concurrent" part, in my opinion,
needs to be handled somehow for all algorithms in a consistent manner,
rather than adding flags for each API separately.

--
Davide

[dcci (Davide C. C. Italiano)]

Unstable sort and stable sort come with different time/space
computational complexity tradeoffs. In general you might be faster if
you don't care about relative order of elements with the same keys and
some (most?) consumers don't. So, I don't think it's an option
providing only stable sort.

···

On Mon, Jan 11, 2016 at 9:51 AM, Kenny Leung via swift-evolution <swift-evolution@swift.org> wrote:

I can’t imagine a case where one wouldn’t want this, so why not just replace the existing sort with the stable sort?

[maven (Daniel Vollmer)]

Hello,

[snip]

I have been thinking about this, and even though other languages it is
a separate function, since the fundamental operation of sort() and
stableSort() seems sufficiently similar to me, the defaulted parameter
seems like the right thing to do. What other parameters could sort()
conceivably get in future? Should the parameter be a boolean flag or
a resilient option set?

Whether a sort should be stable or not doesn’t really strike me as a (variable) parameter (i.e. context of the sort() call determines whether a stable sort is needed). I would also assume that the algorithms implemented would be different for stable vs. unstable (unless of course unstable sort is implemented in terms of stable sort). Both of these would make me (very slightly) prefer separate methods.

That being said, once additional variations / flags come into play, it seems like a bad idea to have distinct methods for all compile-time fixed “parameter”-combinations.

*shrug*

  Daniel.

···

On 11 Jan 2016, at 04:39, Dmitri Gribenko via swift-evolution <swift-evolution@swift.org> wrote:

[cloutiertyler (Tyler Cloutier)]

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.

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.

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?

Tyler

···

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 <http://swift-evolution-m3fhrko0vlzytjvyw6ydsg-at-public.gmane.org/&gt;&gt; wrote:

-Dave

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

[trs (Thorsten Seitz)]

+1 to all points

-Thorsten

···

Am 20.01.2016 um 18:58 schrieb Dave Abrahams via swift-evolution <swift-evolution@swift.org>:

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.

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.

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?

-Dave

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

[Charles_Kissinger]

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.

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.

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. 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.

—CK

···

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:

-Dave

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

[gribozavr (Dmitri Gribenko)]

The general rule is that discussions should happen on the mailing
list, so we should continue here.

Dmitri

···

On Sun, Jan 10, 2016 at 7:45 PM, Davide Italiano <dccitaliano@gmail.com> wrote:

So, thank you all for the feedback.
I'll refine this proposal further, but I have a question.
Should we continue here (and I should paste a new version of the
proposal) -- or should I submit a new pull request to
apple/swift-evolution on github so that interested parties can comment
there?

--
main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
(j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr@gmail.com>*/

[gribozavr (Dmitri Gribenko)]

Hello,

[snip]

I have been thinking about this, and even though other languages it is
a separate function, since the fundamental operation of sort() and
stableSort() seems sufficiently similar to me, the defaulted parameter
seems like the right thing to do. What other parameters could sort()
conceivably get in future? Should the parameter be a boolean flag or
a resilient option set?

Whether a sort should be stable or not doesn’t really strike me as a (variable) parameter (i.e. context of the sort() call determines whether a stable sort is needed).

Yes, I understand this. However, consider other cases when you would
typically pass a constant at the call site --
Array.removeAll(keepCapacity:), for example. The 'keepCapacity'
argument is typically a constant. Do you feel like this API would be
better expressed as two methods?

I would also assume that the algorithms implemented would be different for stable vs. unstable (unless of course unstable sort is implemented in terms of stable sort).

Also true, but even the unstable sort will check the array length and
use different implementations based on that. So while a naive
implementation of `sort(stable:)` will only check the flag and switch
algorithms based on that, the implementation used in practice will be
more complex.

But, one thing that we need to ensure is that the generic specializer
and inliner are good enough to not produce extra code bloat for the
case when `sort(stable:)` is passed a constant.

Dmitri

···

On Mon, Jan 11, 2016 at 7:40 AM, Daniel Vollmer via swift-evolution <swift-evolution@swift.org> wrote:

On 11 Jan 2016, at 04:39, Dmitri Gribenko via swift-evolution <swift-evolution@swift.org> wrote:

--
main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
(j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr@gmail.com>*/

[gribozavr (Dmitri Gribenko)]

I agree.

Dmitri

···

On Mon, Jan 11, 2016 at 10:26 AM, Davide Italiano <dccitaliano@gmail.com> wrote:

So, my preference is for passing a Bool to sort(), and *eventually*
re-evaluate if needed.

--
main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
(j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr@gmail.com>*/

[dabrahams (Dave Abrahams)]

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.

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.

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.

sortFasterButUnstably, then ;-)

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?

No, I think you understand me.

-Dave

···

on Wed Jan 20 2016, Tyler Cloutier <cloutiertyler-AT-aol.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 > >> <http://swift-evolution-m3fhrko0vlzytjvyw6ydsg-at-public.gmane.org/&gt;&gt; >> wrote: