Go: Сортировка слайсов
Сортировка массива — распространненая задача в программировании. Во всех языках существуют готовые решения для этой задачи, и Go — не исключение. Стандартный пакет sort
предоставляет функции для сортировки:
nums := []int{2,1,6,5,3,4}
sort.Slice(nums, func(i, j int) bool {
return nums[i] < nums[j]
})
fmt.Println(nums) // [1 2 3 4 5 6]
Рассмотрим функцию Slice(x interface{}, less func(i, j int) bool)
. В описании функции присутствует неизвестный тип данных interface{}
. Понятие интерфейса будет рассмотренно в следующих модулях курса. Следует запомнить, что пустой интерфейс interface{}
в Go означает тип данных, под который подходит любой другой тип. Например:
func Print(arg interface{}) {
fmt.Println(arg)
}
func main() {
Print("hello!")
Print(123)
Print([]int{1,5,10})
}
Вывод:
hello!
123
[1 5 10]
То есть в функцию Slice(x interface{}, less func(i, j int) bool)
передается слайс любого типа данных, как первый аргумент. Вторым аргументом передается функция, которая берет элементы по индексу и определяет должен ли элемент по индексу i
находиться перед элементом по индексу j
.
"Под капотом" в функции sort.Slice
используется быстрая сортировка. В пакете также присутствует сортировка вставками sort.SliceStable
:
nums := []int{2,1,6,5,3,4}
sort.SliceStable(nums, func(i, j int) bool {
return nums[i] < nums[j]
})
fmt.Println(nums) // [1 2 3 4 5 6]
Выбор алгоритма зависит от набора и размера данных, архитектуры процессора, скорости доступа к памяти, то есть от многих факторов. Для большинства стандартных случаев используется sort.Slice
, пока производительность или нестабильность алгоритма не станет "узким горлышком".
Задание
Реализуйте функцию UniqueSortedUserIDs(userIDs []int64) []int64
, которая возвращает отсортированный слайс, состоящий из уникальных идентификаторов userIDs
. Обработка должна происходить in-place, то есть без выделения доп. памяти.
Упражнение не проходит проверку — что делать? 😶
Если вы зашли в тупик, то самое время задать вопрос в «Обсуждениях». Как правильно задать вопрос:
- Обязательно приложите вывод тестов, без него практически невозможно понять что не так, даже если вы покажете свой код. Программисты плохо исполняют код в голове, но по полученной ошибке почти всегда понятно, куда смотреть.
В моей среде код работает, а здесь нет 🤨
Тесты устроены таким образом, что они проверяют решение разными способами и на разных данных. Часто решение работает с одними входными данными, но не работает с другими. Чтобы разобраться с этим моментом, изучите вкладку «Тесты» и внимательно посмотрите на вывод ошибок, в котором есть подсказки.
Мой код отличается от решения учителя 🤔
Это нормально 🙆, в программировании одну задачу можно выполнить множеством способов. Если ваш код прошел проверку, то он соответствует условиям задачи.
В редких случаях бывает, что решение подогнано под тесты, но это видно сразу.
Прочитал урок — ничего не понятно 🙄
Создавать обучающие материалы, понятные для всех без исключения, довольно сложно. Мы очень стараемся, но всегда есть что улучшать. Если вы встретили материал, который вам непонятен, опишите проблему в «Обсуждениях». Идеально, если вы сформулируете непонятные моменты в виде вопросов. Обычно нам нужно несколько дней для внесения правок.
Кстати, вы тоже можете участвовать в улучшении курсов: внизу есть ссылка на исходный код уроков, который можно править прямо из браузера.