aboutsummaryrefslogtreecommitdiff
path: root/src/sort/sort_test.go
AgeCommit message (Collapse)Author
2024-07-16sort: add example for Findcui fliter
Change-Id: Id7b12356dd2114dfbab260cff00114b6055ee011 Reviewed-on: https://go-review.googlesource.com/c/go/+/561175 TryBot-Result: Gopher Robot <gobot@golang.org> Reviewed-by: Cherry Mui <cherryyz@google.com> Run-TryBot: shuang cui <imcusg@gmail.com> Reviewed-by: Ian Lance Taylor <iant@google.com> Auto-Submit: Ian Lance Taylor <iant@google.com> LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>
2024-03-07sort: fix typo in sort_test.goAlex Driuk
Change-Id: Ibc1344b678d5f7c730b924c697717305c90c26e9 Reviewed-on: https://go-review.googlesource.com/c/go/+/569537 Commit-Queue: Ian Lance Taylor <iant@google.com> LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com> Auto-Submit: Ian Lance Taylor <iant@google.com> Reviewed-by: Ian Lance Taylor <iant@google.com>
2024-02-08sort: use math/rand/v2 in tests and benchmarksTobias Klauser
This allows to drop the use of deprecated rand.Seed in benchmarks. Fixes #61142 Change-Id: I628848c0d4a500dc9a361930c393e47c3361a95c Reviewed-on: https://go-review.googlesource.com/c/go/+/551155 Reviewed-by: Eli Bendersky <eliben@google.com> Auto-Submit: Ian Lance Taylor <iant@google.com> Reviewed-by: Ian Lance Taylor <iant@google.com> Run-TryBot: Tobias Klauser <tobias.klauser@gmail.com> Auto-Submit: Tobias Klauser <tobias.klauser@gmail.com> TryBot-Result: Gopher Robot <gobot@golang.org> Reviewed-by: Robert Griesemer <gri@google.com> LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>
2023-08-07sort: use the builtin min functionMuhammad Falak R Wani
Change-Id: I9603de9abff8d5c8fb9efdf688ff1a5f8c7d19b2 GitHub-Last-Rev: c6fe3acc41a3a9c7d07e3c291985867a704013b1 GitHub-Pull-Request: golang/go#61808 Reviewed-on: https://go-review.googlesource.com/c/go/+/516635 Auto-Submit: Keith Randall <khr@golang.org> Run-TryBot: Keith Randall <khr@golang.org> Reviewed-by: Michael Knyszek <mknyszek@google.com> Reviewed-by: Keith Randall <khr@golang.org> TryBot-Result: Gopher Robot <gobot@golang.org> Reviewed-by: Keith Randall <khr@google.com>
2023-07-21sort: forward fixed-type slice sorting to slices packageEli Bendersky
Forwards the following functions to the slices package: sort.Ints sort.Strings sort.Float64s sort.IntsAreSorted sort.StringsAreSorted sort.Float64sAreSorted benchstat results on the sort package's benchmarks: goos: linux goarch: amd64 pkg: sort cpu: 11th Gen Intel(R) Core(TM) i5-1135G7 @ 2.40GHz SearchWrappers-8 58.10n ± 0% 58.43n ± 1% +0.57% (p=0.004 n=10) SortString1K-8 76.53µ ± 1% 66.04µ ± 2% -13.71% (p=0.000 n=10) SortString1K_Slice-8 71.99µ ± 1% 72.32µ ± 2% ~ (p=0.481 n=10) StableString1K-8 92.66µ ± 1% 92.10µ ± 2% -0.61% (p=0.019 n=10) SortInt1K-8 34.31µ ± 0% 11.49µ ± 2% -66.50% (p=0.000 n=10) SortInt1K_Sorted-8 2699.5n ± 1% 959.0n ± 3% -64.47% (p=0.000 n=10) SortInt1K_Reversed-8 3.990µ ± 1% 1.429µ ± 4% -64.19% (p=0.000 n=10) SortInt1K_Mod8-8 13.695µ ± 1% 5.129µ ± 2% -62.55% (p=0.000 n=10) StableInt1K-8 46.22µ ± 1% 46.80µ ± 1% ~ (p=0.109 n=10) StableInt1K_Slice-8 44.12µ ± 1% 44.32µ ± 2% ~ (p=0.315 n=10) SortInt64K-8 3.848m ± 0% 1.857m ± 2% -51.76% (p=0.000 n=10) SortInt64K_Slice-8 3.690m ± 0% 3.740m ± 0% +1.36% (p=0.002 n=10) StableInt64K-8 3.901m ± 0% 3.917m ± 0% +0.42% (p=0.003 n=10) Sort1e2-8 32.22µ ± 2% 32.40µ ± 2% ~ (p=0.529 n=10) Stable1e2-8 54.11µ ± 1% 54.11µ ± 1% ~ (p=0.796 n=10) Sort1e4-8 5.998m ± 1% 5.993m ± 1% ~ (p=0.579 n=10) Stable1e4-8 15.23m ± 0% 15.32m ± 0% +0.59% (p=0.000 n=10) Sort1e6-8 902.8m ± 0% 904.3m ± 0% ~ (p=0.075 n=10) Stable1e6-8 3.089 ± 0% 3.089 ± 0% ~ (p=0.971 n=10) geomean 259.8µ 200.0µ -22.99% Most of the benchmarks are unaffected. The ones with significant reductions are precisely for the functions that were forwarded. This CL has to move some things around to avoid a circular dependency between sort and slices. Since sort depends on slices now, nothing in slices can depend on sort - not even in tests. Fixes #61180 Change-Id: Ic0e5f519863d96a139fada08aefb1bcdf4c7a9a3 Reviewed-on: https://go-review.googlesource.com/c/go/+/508135 Run-TryBot: Ian Lance Taylor <iant@google.com> Reviewed-by: Ian Lance Taylor <iant@google.com> Reviewed-by: Eli Bendersky <eliben@google.com> TryBot-Result: Gopher Robot <gobot@golang.org>
2022-04-13sort: use pdqsortzhangyunhao
- Across all benchmarks, pdqsort is never significantly slower than the previous algorithm. - In common patterns, pdqsort is often faster (i.e. 10x faster in sorted slices). The pdqsort is described at https://arxiv.org/pdf/2106.05123.pdf This CL is inspired by both C++ implementation and Rust implementation. - C++ implementation: https://github.com/orlp/pdqsort - Rust implementation: https://docs.rs/pdqsort/latest/pdqsort/ For #50154 name old time/op new time/op delta SearchWrappers-16 72.8ns ± 3% 75.1ns ± 2% +3.25% (p=0.000 n=20+10) SortString1K-16 85.2µs ± 3% 86.2µs ± 5% ~ (p=0.247 n=19+10) SortString1K_Slice-16 84.6µs ± 4% 86.1µs ± 4% ~ (p=0.120 n=20+10) StableString1K-16 112µs ± 5% 112µs ± 5% ~ (p=0.604 n=19+10) SortInt1K-16 44.8µs ± 3% 43.2µs ± 2% -3.68% (p=0.000 n=20+10) SortInt1K_Sorted-16 28.2µs ± 3% 3.3µs ± 3% -88.16% (p=0.000 n=19+10) SortInt1K_Reversed-16 29.4µs ± 3% 4.8µs ± 2% -83.59% (p=0.000 n=20+10) SortInt1K_Mod8-16 25.1µs ± 2% 20.0µs ± 2% -20.35% (p=0.000 n=18+10) StableInt1K-16 51.3µs ± 3% 50.9µs ± 2% ~ (p=0.562 n=20+9) StableInt1K_Slice-16 49.5µs ± 2% 50.7µs ± 4% +2.55% (p=0.009 n=19+10) SortInt64K-16 4.73ms ± 3% 4.49ms ± 4% -5.08% (p=0.000 n=20+10) SortInt64K_Slice-16 4.51ms ± 3% 4.35ms ± 1% -3.42% (p=0.000 n=20+8) StableInt64K-16 4.85ms ± 2% 4.82ms ± 2% ~ (p=0.267 n=20+10) Sort1e2-16 27.9µs ± 1% 28.1µs ± 2% ~ (p=0.198 n=20+10) Stable1e2-16 56.6µs ± 2% 55.0µs ± 2% -2.88% (p=0.000 n=20+10) Sort1e4-16 5.51ms ± 1% 5.36ms ± 1% -2.58% (p=0.000 n=19+9) Stable1e4-16 17.8ms ± 1% 17.3ms ± 1% -2.40% (p=0.000 n=20+10) Sort1e6-16 833ms ± 1% 807ms ± 1% -3.02% (p=0.000 n=20+10) Stable1e6-16 3.49s ± 2% 3.44s ± 1% -1.41% (p=0.001 n=20+10) Change-Id: Iecded047d237b9330b5a4101001a5fdc2f50646a Reviewed-on: https://go-review.googlesource.com/c/go/+/371574 Reviewed-by: Emmanuel Odeke <emmanuel@orijtech.com> Run-TryBot: Ian Lance Taylor <iant@golang.org> Reviewed-by: Keith Randall <khr@golang.org> Run-TryBot: Keith Randall <khr@golang.org> Auto-Submit: Keith Randall <khr@golang.org> Reviewed-by: Keith Randall <khr@google.com> TryBot-Result: Gopher Robot <gobot@golang.org> Reviewed-by: Eli Bendersky <eliben@google.com>
2019-03-22sort: replace Errorf+FailNow with FatalfIskander Sharipov
Change-Id: I4f8d0178e780b86d1f551b367e2ddac3789be5aa Reviewed-on: https://go-review.googlesource.com/c/go/+/168880 Run-TryBot: Ian Lance Taylor <iant@golang.org> Reviewed-by: Ian Lance Taylor <iant@golang.org>
2018-06-01all: update comment URLs from HTTP to HTTPS, where possibleTim Cooper
Each URL was manually verified to ensure it did not serve up incorrect content. Change-Id: I4dc846227af95a73ee9a3074d0c379ff0fa955df Reviewed-on: https://go-review.googlesource.com/115798 Reviewed-by: Ian Lance Taylor <iant@golang.org> Run-TryBot: Ian Lance Taylor <iant@golang.org>
2018-03-19sort: fix typo, was a mixup between identifiers 'unsorted' and 'data'Neven Sajko
Change-Id: If9ad8ae663f007efe43cc35631713565fa754e93 Reviewed-on: https://go-review.googlesource.com/93237 Run-TryBot: Ian Lance Taylor <iant@golang.org> TryBot-Result: Gobot Gobot <gobot@golang.org> Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
2017-08-25sort: fix TestAdversaryTom Levy
There are some major problems with TestAdversary (based on "A Killer Adversary for Quicksort"[1] by M. D. McIlroy). See #21581 for details. Rewrite the test to closely match the version in the paper so it can be verified as correct by virtue of similarity. The only major difference between this new version and the version in the paper is that this version swaps the values directly instead of permuting an array of indices because we don't need to recover the original permutation. This new version also counts the number of calls to Less() and fails the test if there are too many. Fixes #21581. [1]: http://www.cs.dartmouth.edu/~doug/mdmspe.pdf Change-Id: Ia94b5b6d288b8fa3805a5fa27661cebbc5bad9a7 Reviewed-on: https://go-review.googlesource.com/58330 Run-TryBot: Ian Lance Taylor <iant@golang.org> TryBot-Result: Gobot Gobot <gobot@golang.org> Reviewed-by: Ian Lance Taylor <iant@golang.org>
2016-10-05sort: fix a slice benchmark not using the stable variant, add anotherBrad Fitzpatrick
Change-Id: I9783d8023d453a72c4605a308064bef98168bcb8 Reviewed-on: https://go-review.googlesource.com/30360 Reviewed-by: Ian Lance Taylor <iant@golang.org> Run-TryBot: Ian Lance Taylor <iant@golang.org> TryBot-Result: Gobot Gobot <gobot@golang.org>
2016-10-03sort: add Slice, SliceStable, and SliceIsSortedBrad Fitzpatrick
Add helpers for sorting slices. Slice sorts slices: sort.Slice(s, func(i, j int) bool { if s[i].Foo != s[j].Foo { return s[i].Foo < s[j].Foo } return s[i].Bar < s[j].Bar }) SliceStable is the same, but does a stable sort. SliceIsSorted reports whether a slice is already sorted. Fixes #16721 Change-Id: I346530af1c5dee148ea9be85946fe08f23ae53e7 Reviewed-on: https://go-review.googlesource.com/27321 Run-TryBot: Brad Fitzpatrick <bradfitz@golang.org> TryBot-Result: Gobot Gobot <gobot@golang.org> Reviewed-by: Russ Cox <rsc@golang.org>
2016-09-14sort: cut 140 seconds off race build testsBrad Fitzpatrick
No coverage is gained by running the 1e6 versions of the test over the 1e4 versions. It just adds 140 seconds of race overhead time. Updates #17104 Change-Id: I41408aedae34a8b1a148eebdda20269cdefffba3 Reviewed-on: https://go-review.googlesource.com/29159 Run-TryBot: Brad Fitzpatrick <bradfitz@golang.org> TryBot-Result: Gobot Gobot <gobot@golang.org> Reviewed-by: Josh Bleecher Snyder <josharian@gmail.com>
2016-02-24all: fix typos and spellingMartin Möhrmann
Change-Id: Icd06d99c42b8299fd931c7da821e1f418684d913 Reviewed-on: https://go-review.googlesource.com/19829 Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org> Run-TryBot: Brad Fitzpatrick <bradfitz@golang.org> TryBot-Result: Gobot Gobot <gobot@golang.org>
2016-02-24sort: fix for nondeterministic less function in quicksort pivotJure Ham
Fixes #14377 Change-Id: I130a6e1b8bc827db44efd0a74e759b894ecc4977 Reviewed-on: https://go-review.googlesource.com/19823 Reviewed-by: Ian Lance Taylor <iant@golang.org> Run-TryBot: Ian Lance Taylor <iant@golang.org> TryBot-Result: Gobot Gobot <gobot@golang.org>
2014-09-08build: move package sources from src/pkg to srcRuss Cox
Preparation was in CL 134570043. This CL contains only the effect of 'hg mv src/pkg/* src'. For more about the move, see golang.org/s/go14nopkg.
generated by cgit v1.3 (git 2.53.0) at 2026-04-15 14:37:37 +0000