Slices

With the release of Go 1.21, the Go standard library introduced several new features. While we’ve already discussed some of them in previous articles, in this episode, we’ll dive into more advanced enhancements. Naturally, we’ll focus on the new functions designed for sorting slices, which are part of the new slices package. This article will provide a deeper look into the implementation of these three new functions and touch on benchmarking as well. Sort # The Sort function is the first one we’d like to explore. This implementation is built upon the enhanced Pattern-defeating Quicksort, positioning it as one of the best-known unstable sorting algorithms. Don’t worry; we will discuss this “instability” aspect in this article. But first, let’s take a look at the function’s signature: Sort function func Sort[S ~[]E, E cmp.Ordered](x S) As we’ve seen in some other articles, nearly all improvements in the Go standard library are built upon generics, a feature introduced in Go version 1.18, almost three years ago. Similar to other functions, the Sort function also expects a slice of a generic type as an argument, where each item must adhere to the Ordered constraint. The function doesn’t return a new value but sorts the original slice in place. Below, you’ll find some basic examples: Sort function examples ints := []int{1, 2, 3, 5, 5, 7, 9} slices.Sort(ints) fmt.Println(ints) // Output: // 1 2 3 5 5 7 9 ints2 := []int{9, 7, 5, 5, 3, 2, 1} slices.Sort(ints2) fmt.Println(ints2) // Output: // 1 2 3 5 5 7 9 floats := []float64{9, 3, 5, 7, 1, 2, 5} slices.Sort(floats) fmt.Println(floats) // Output: // 1 2 3 5 5 7 9 strings := []string{"3", "9", "2", "5", "1", "7", "5"} slices.Sort(strings) fmt.Println(strings) // Output: // 1 2 3 5 5 7 9 In the example above, we can observe the result of the Sort method. All the outputs consist of sorted slices, arranged in ascending order. However, what makes this function particularly intriguing is its ability to handle various data types using a single function, distinguishing it from the implementations we already possess in the sort package. Now that we’ve examined the results, let’s proceed to compare the performance benchmarks with the existing package. Benchmark # In this section, we aim to evaluate the performance of the new function by comparing it to the already existing sort package. Below, you’ll find the benchmark test results:

As part of the new Go release, several exciting changes have been introduced to the Go ecosystem. While we’ve explored some of these changes in other articles about the maps package and the cmp package, there’s much more to discover beyond these two packages. In this article, we’ll focus on the first part of the slices package, specifically its new search functionality. Like many other updates and newly introduced packages, this one is also built upon the foundation of generics, which were introduced in Go 1.18. BinarySearch and BinarySearchFunc # Let’s start by exploring the first pair of functions designed for efficiently searching a target value within sorted slices. In this context, we’re referring to the well-known Binary Search algorithm, which is renowned as one of the most significant algorithms and is frequently used in coding interviews. Below, you’ll find the signatures of both of these functions: BinarySearch function func BinarySearch[S ~[]E, E cmp.Ordered](x S, target E) (int, bool) BinarySearchFunc function func BinarySearchFunc[S ~[]E, E, T any](x S, target T, cmp func(E, T) int) (int, bool) Looking at the signatures of both functions, we can identify some small differences between them, and these differences serve specific purposes. The first function, BinarySearch, expects two arguments. The first argument should be a slice of sorted items, and it must adhere to the Ordered constraint. When the items are ordered, the algorithm can efficiently compare them using the Compare function from the cmp package. On the other hand, the second function, BinarySearchFunc, is more versatile. It allows searching within slices where the items don’t necessarily conform to the Ordered constraint. This flexibility is achieved by introducing a third argument, the comparison function. This function is responsible for comparing items and determining their order. It will be called by the BinarySearchFunc itself to make comparisons. Both functions return two values. The first value is the index of the item within the slice, and the second is a boolean value indicating whether the item was found in the slice or not. Let’s explore some examples below: BinarySearch examples fmt.Println(slices.BinarySearch([]int{1, 3, 5, 6, 7}, 5)) // Output: // 2 true fmt.Println(slices.BinarySearch([]int{1, 3, 5, 6, 7}, 9)) // Output: // 5 false fmt.Println(slices.BinarySearch([]int{1, 3, 5, 6, 7}, -5)) // Output: // 0 false fmt.Println(slices.BinarySearch([]string{"1", "3", "5", "6", "7"}, "5")) // Output: // 2 true fmt.Println(slices.BinarySearch([]string{"1", "3", "5", "6", "7", "8"}, "9")) // Output: // 6 false fmt.Println(slices.BinarySearch([]string{"1", "3", "5", "6", "7"}, "4")) // Output: // 2 false Take a close look at the results returned by the BinarySearch function, especially when the item doesn’t exist in the slice. In our examples, we encountered four such cases where the function returned 0, 2, 5, and 6. When the requested item isn’t present in the slice, the function indicates where it should be positioned if it were to be added to the slice. Since the slice is sorted, it’s possible to determine the appropriate position for the item within the slice.