Странное поведение срезов Golang

Question

Я изучаю Go по книге Алана Донована "Язык программирования Go". В упражнении 4.5 поствлена следующая задача:

Напишите функцию, которая без выделения дополнительной памяти удаляет все смежные дубликаты в срезе []string.

Вот код, который я написал для решения задачи:

package main

import (
    "fmt"
    "sort"
)

func delDup(strings []string) {
    if len(strings) < 2 {
        return
    }
    if len(strings) == 2 {
        if strings[0] == strings[1] {
            strings = []string{strings[0]}
        }
        return
    }
    sort.Strings(strings)
    currentStringIndex := 0
    nextNonEqualStringIndex := 1
    for {
        for strings[currentStringIndex] == strings[nextNonEqualStringIndex] {
            nextNonEqualStringIndex++
            if nextNonEqualStringIndex >= len(strings) {
                strings = strings[:currentStringIndex+1]
                fmt.Println("В этом месте всё отлично", strings)
                return
            }
        }
        currentStringIndex++
        strings = append(strings[:currentStringIndex], strings[nextNonEqualStringIndex:]...)
    }
}

func main() {
    x := []string{"one", "one", "two", "two", "two", "three", "four", "five", "five"}
    delDup(x)
    fmt.Println("Но здесь...", x)
}

При запуске видно, что срез []strings имеет разные значения в функции delDup() и main():

В этом месте всё отлично [five four one three two] // delDup()
Но здесь... [five four one three two two two two two] // main()

Мало того, что я не удаляю дубликаты, но я ещё и добавляю новые значения. Мне неясно, почему алгоритм имеет такое поведение, но, мне кажется, проблема как-то связана со ссылками.

Answer 1

В языке Go нет средств для уменьшения размера массива/среза без реаллокации. Причина - риск возникновения висящих ссылок. Представьте, где-то в программе вы взяли указатель на последний элемент в массиве строк, а затем уменьшили размер массива, от чего указатель на последний элемент стал указывать в кучу. Операции с таким висящим указателем гарантированно приведут к неимоверно сложным ошибкам. Однажды я неделю ловил такой утёкший указатель в чужой библиотеке на Си. Неделю! Ошибка проявляла себя самым причудливым образом, причём при разных прогонах симптомы были разными.

Для сохранения целостности указателей без излишних накладных расходов на подсчёт ссылок, в Go память, отведённая под массивы, освобождается только после прохода сборщика мусора. Изнутри программы вы никак не сможете изменить размер массива/среза, поэтому после удаления дубликатов у вас в исходном срезе всегда будет хвост из ненужных элементов.

Следовательно, ваша функция удаления дубликатов не может быть void. Вы должны возвращать изменённый срез уменьшенной длины.

Вот как может выглядеть ответ:

package main

import (
    "fmt"
    "strings"
)

func main() {
    test([]string{})
    test([]string{"a"})
    test([]string{"a", "a", "a", "a"})
    test([]string{"a", "a", "b", "b", "a", "a", "a", "c", "c", "c"})
}

func test(arg []string) {
    argString := strings.Join(arg, "','")
    result := removeDups(arg)
    fmt.Printf("removeDups('%s') -> '%s'\n", argString, strings.Join(result, "','"))
}

// removeDups removes consequent duplicates and returns the updated slice.
// The original slice gets damaged.
func removeDups(strings []string) []string {
    if len(strings) < 2 {
        return strings
    }

    for i := 0; i < len(strings)-1; {
        if strings[i+1] == strings[i] {
            // Update the slice - remove duplicates
            strings = remove(strings, i+1, 1)
        } else {
            // proceed to the next element
            i++
        }
    }
    return strings
}

// remove deletes elements strings[start:start+length] and returns the updated slice
func remove(strings []string, start int, length int) []string {
    if length == 0 {
        return strings
    }

    if start < 0 || length < 0 {
        panic(fmt.Sprintf("Start position or length are negative: %d/%d", start, length))
    }

    nstart := start + length
    end := len(strings)
    if nstart >= end {
        // truncate the slice
        return strings[:start]
    }
    // Shift the slice to the left by `length` elements: copy the tail of the slice to `start` position
    copy(strings[start:], strings[nstart:])
    return strings[:end-length]
}

Результат прогона на тестовых данных:

removeDups('') -> ''
removeDups('a') -> 'a'
removeDups('a','a','a','a') -> 'a'
removeDups('a','a','b','b','a','a','a','c','c','c') -> 'a','b','a','c'

Разумеется, в более-менее боевом коде стоит удалять не по одному элементу, а сразу пакетом: если наткнулся на дубликаты, подсчитать, сколько их, и затем удалить сразу непрерывный отрезок. Т.е. вместо strings = remove(strings, i+1, 1) должно быть что-то вроде strings = remove(strings, i+1, countDups(strings, i+1, strings[i])), где функция countDups подсчитывает число дубликатов, идущих подряд.

БЛОГ НА HUSL

Странное поведение срезов Golang

Ответы (1 шт):