From 9fbee359d7eb3a621604bc2067a375f6d4b757e5 Mon Sep 17 00:00:00 2001 From: varkor Date: Thu, 1 Mar 2018 13:39:52 +0000 Subject: Add a test for sort_by_key --- src/liballoc/tests/slice.rs | 5 +++++ 1 file changed, 5 insertions(+) (limited to 'src/liballoc/tests') diff --git a/src/liballoc/tests/slice.rs b/src/liballoc/tests/slice.rs index d9e9d91cea8..300f6abaa7f 100644 --- a/src/liballoc/tests/slice.rs +++ b/src/liballoc/tests/slice.rs @@ -425,6 +425,11 @@ fn test_sort() { v.sort_by(|a, b| b.cmp(a)); assert!(v.windows(2).all(|w| w[0] >= w[1])); + // Sort in lexicographic order. + let mut v = orig.clone(); + v.sort_by_key(|x| x.to_string()); + assert!(v.windows(2).all(|w| w[0].to_string() <= w[1].to_string())); + // Sort with many pre-sorted runs. let mut v = orig.clone(); v.sort(); -- cgit 1.4.1-3-g733a5 From f41a26f2040dfa752825a7d1fdfbd5a8ae3310cf Mon Sep 17 00:00:00 2001 From: varkor Date: Fri, 16 Mar 2018 14:37:17 +0000 Subject: Add sort_by_cached_key method --- src/liballoc/slice.rs | 61 +++++++++++++++++++++++++++++++++++++-------- src/liballoc/tests/slice.rs | 9 ++++--- 2 files changed, 56 insertions(+), 14 deletions(-) (limited to 'src/liballoc/tests') diff --git a/src/liballoc/slice.rs b/src/liballoc/slice.rs index fbd8d879308..306c467f048 100644 --- a/src/liballoc/slice.rs +++ b/src/liballoc/slice.rs @@ -1301,6 +1301,45 @@ impl [T] { merge_sort(self, |a, b| compare(a, b) == Less); } + /// Sorts the slice with a key extraction function. + /// + /// This sort is stable (i.e. does not reorder equal elements) and `O(m n log m n)` + /// worst-case, where the key function is `O(m)`. + /// + /// For expensive key functions (e.g. functions that are not simple property accesses or + /// basic operations), [`sort_by_cached_key`](#method.sort_by_cached_key) is likely to be + /// significantly faster, as it does not recompute element keys. + /// + /// When applicable, unstable sorting is preferred because it is generally faster than stable + /// sorting and it doesn't allocate auxiliary memory. + /// See [`sort_unstable_by_key`](#method.sort_unstable_by_key). + /// + /// # Current implementation + /// + /// The current algorithm is an adaptive, iterative merge sort inspired by + /// [timsort](https://en.wikipedia.org/wiki/Timsort). + /// It is designed to be very fast in cases where the slice is nearly sorted, or consists of + /// two or more sorted sequences concatenated one after another. + /// + /// Also, it allocates temporary storage half the size of `self`, but for short slices a + /// non-allocating insertion sort is used instead. + /// + /// # Examples + /// + /// ``` + /// let mut v = [-5i32, 4, 1, -3, 2]; + /// + /// v.sort_by_key(|k| k.abs()); + /// assert!(v == [1, 2, -3, 4, -5]); + /// ``` + #[stable(feature = "slice_sort_by_key", since = "1.7.0")] + #[inline] + pub fn sort_by_key(&mut self, mut f: F) + where F: FnMut(&T) -> K, K: Ord + { + merge_sort(self, |a, b| f(a).lt(&f(b))); + } + /// Sorts the slice with a key extraction function. /// /// During sorting, the key function is called only once per element. @@ -1308,6 +1347,10 @@ impl [T] { /// This sort is stable (i.e. does not reorder equal elements) and `O(m n + n log n)` /// worst-case, where the key function is `O(m)`. /// + /// For simple key functions (e.g. functions that are property accesses or + /// basic operations), [`sort_by_key`](#method.sort_by_key) is likely to be + /// faster. + /// /// # Current implementation /// /// The current algorithm is an adaptive, iterative merge sort inspired by @@ -1315,19 +1358,19 @@ impl [T] { /// It is designed to be very fast in cases where the slice is nearly sorted, or consists of /// two or more sorted sequences concatenated one after another. /// - /// The algorithm allocates temporary storage in a `Vec<(K, usize)` the length of the slice. + /// The algorithm allocates temporary storage in a `Vec<(K, usize)>` the length of the slice. /// /// # Examples /// /// ``` /// let mut v = [-5i32, 4, 1, -3, 2]; /// - /// v.sort_by_key(|k| k.abs()); + /// v.sort_by_cached_key(|k| k.abs()); /// assert!(v == [1, 2, -3, 4, -5]); /// ``` - #[stable(feature = "slice_sort_by_key", since = "1.7.0")] + #[unstable(feature = "slice_sort_by_uncached_key", issue = "34447")] #[inline] - pub fn sort_by_key(&mut self, f: F) + pub fn sort_by_cached_key(&mut self, f: F) where F: FnMut(&T) -> K, K: Ord { // Helper macro for indexing our vector by the smallest possible type, to reduce allocation. @@ -1432,9 +1475,6 @@ impl [T] { /// Sorts the slice with a key extraction function, but may not preserve the order of equal /// elements. /// - /// Note that, currently, the key function for [`sort_unstable_by_key`] is called multiple times - /// per element, unlike [`sort_by_key`]. - /// /// This sort is unstable (i.e. may reorder equal elements), in-place (i.e. does not allocate), /// and `O(m n log m n)` worst-case, where the key function is `O(m)`. /// @@ -1446,8 +1486,9 @@ impl [T] { /// randomization to avoid degenerate cases, but with a fixed seed to always provide /// deterministic behavior. /// - /// Due to its key calling strategy, [`sort_unstable_by_key`] is likely to be slower than - /// [`sort_by_key`] in cases where the key function is expensive. + /// Due to its key calling strategy, [`sort_unstable_by_key`](#method.sort_unstable_by_key) + /// is likely to be slower than [`sort_by_cached_key`](#method.sort_by_uncached_key) in + /// cases where the key function is expensive. /// /// # Examples /// @@ -1458,8 +1499,6 @@ impl [T] { /// assert!(v == [1, 2, -3, 4, -5]); /// ``` /// - /// [`sort_by_key`]: #method.sort_by_key - /// [`sort_unstable_by_key`]: #method.sort_unstable_by_key /// [pdqsort]: https://github.com/orlp/pdqsort #[stable(feature = "sort_unstable", since = "1.20.0")] #[inline] diff --git a/src/liballoc/tests/slice.rs b/src/liballoc/tests/slice.rs index 300f6abaa7f..7d4dac1c5ec 100644 --- a/src/liballoc/tests/slice.rs +++ b/src/liballoc/tests/slice.rs @@ -426,9 +426,12 @@ fn test_sort() { assert!(v.windows(2).all(|w| w[0] >= w[1])); // Sort in lexicographic order. - let mut v = orig.clone(); - v.sort_by_key(|x| x.to_string()); - assert!(v.windows(2).all(|w| w[0].to_string() <= w[1].to_string())); + let mut v1 = orig.clone(); + let mut v2 = orig.clone(); + v1.sort_by_key(|x| x.to_string()); + v2.sort_by_cached_key(|x| x.to_string()); + assert!(v1.windows(2).all(|w| w[0].to_string() <= w[1].to_string())); + assert!(v1 == v2); // Sort with many pre-sorted runs. let mut v = orig.clone(); -- cgit 1.4.1-3-g733a5 From b430cba343743783cee517bf93c7f255827cccc5 Mon Sep 17 00:00:00 2001 From: varkor Date: Fri, 16 Mar 2018 16:35:27 +0000 Subject: Fix use of unstable feature in test --- src/liballoc/lib.rs | 1 + src/liballoc/slice.rs | 4 ++-- src/liballoc/tests/lib.rs | 1 + 3 files changed, 4 insertions(+), 2 deletions(-) (limited to 'src/liballoc/tests') diff --git a/src/liballoc/lib.rs b/src/liballoc/lib.rs index b93e128d508..253b8acc16c 100644 --- a/src/liballoc/lib.rs +++ b/src/liballoc/lib.rs @@ -113,6 +113,7 @@ #![feature(slice_get_slice)] #![feature(slice_patterns)] #![feature(slice_rsplit)] +#![feature(slice_sort_by_cached_key)] #![feature(specialization)] #![feature(staged_api)] #![feature(str_internals)] diff --git a/src/liballoc/slice.rs b/src/liballoc/slice.rs index 306c467f048..db890066447 100644 --- a/src/liballoc/slice.rs +++ b/src/liballoc/slice.rs @@ -1368,7 +1368,7 @@ impl [T] { /// v.sort_by_cached_key(|k| k.abs()); /// assert!(v == [1, 2, -3, 4, -5]); /// ``` - #[unstable(feature = "slice_sort_by_uncached_key", issue = "34447")] + #[unstable(feature = "slice_sort_by_cached_key", issue = "34447")] #[inline] pub fn sort_by_cached_key(&mut self, f: F) where F: FnMut(&T) -> K, K: Ord @@ -1487,7 +1487,7 @@ impl [T] { /// deterministic behavior. /// /// Due to its key calling strategy, [`sort_unstable_by_key`](#method.sort_unstable_by_key) - /// is likely to be slower than [`sort_by_cached_key`](#method.sort_by_uncached_key) in + /// is likely to be slower than [`sort_by_cached_key`](#method.sort_by_cached_key) in /// cases where the key function is expensive. /// /// # Examples diff --git a/src/liballoc/tests/lib.rs b/src/liballoc/tests/lib.rs index 285cba0270c..27f3028a513 100644 --- a/src/liballoc/tests/lib.rs +++ b/src/liballoc/tests/lib.rs @@ -23,6 +23,7 @@ #![feature(pattern)] #![feature(placement_in_syntax)] #![feature(rand)] +#![feature(slice_sort_by_cached_key)] #![feature(splice)] #![feature(str_escape)] #![feature(string_retain)] -- cgit 1.4.1-3-g733a5 From eca1e18cd7021f01757640c0c5ef63717870686c Mon Sep 17 00:00:00 2001 From: varkor Date: Mon, 19 Mar 2018 00:11:47 +0000 Subject: Add stability test for sort_by_cached_key --- src/liballoc/tests/slice.rs | 11 ++++++++--- 1 file changed, 8 insertions(+), 3 deletions(-) (limited to 'src/liballoc/tests') diff --git a/src/liballoc/tests/slice.rs b/src/liballoc/tests/slice.rs index 7d4dac1c5ec..66c7dd75c87 100644 --- a/src/liballoc/tests/slice.rs +++ b/src/liballoc/tests/slice.rs @@ -485,7 +485,7 @@ fn test_sort_stability() { // the second item represents which occurrence of that // number this element is, i.e. the second elements // will occur in sorted order. - let mut v: Vec<_> = (0..len) + let mut orig: Vec<_> = (0..len) .map(|_| { let n = thread_rng().gen::() % 10; counts[n] += 1; @@ -493,16 +493,21 @@ fn test_sort_stability() { }) .collect(); - // only sort on the first element, so an unstable sort + let mut v = orig.clone(); + // Only sort on the first element, so an unstable sort // may mix up the counts. v.sort_by(|&(a, _), &(b, _)| a.cmp(&b)); - // this comparison includes the count (the second item + // This comparison includes the count (the second item // of the tuple), so elements with equal first items // will need to be ordered with increasing // counts... i.e. exactly asserting that this sort is // stable. assert!(v.windows(2).all(|w| w[0] <= w[1])); + + let mut v = orig.clone(); + v.sort_by_cached_key(|&(x, _)| x); + assert!(v.windows(2).all(|w| w[0] <= w[1])); } } } -- cgit 1.4.1-3-g733a5