Функция, которая ищет интерфейс {} по фрагменту интерфейса {} в Go

Question

Я пытаюсь реализовать функцию, которая берет элемент любого типа и фрагмент того же типа и ищет первый внутри второго, давая его позицию в качестве результата или -1 в противном случае.

IЯ не эксперт по Go, поэтому моей первой мыслью было передать элемент для поиска в качестве интерфейса {}, а фрагмент в качестве [] interface {}, но на самом деле это не сработало.

Вот что я пробовал:

package main

import (
    "fmt"
)

func IsElementInListWithPos(element interface{}, list []interface{}) int {
    for i := range list {
        if list[i] == element {
            return i
        }
    }

    return -1
}

func main() {
    list1 := []int{1, 2, 3, 4, 5, 6}
    list2 := []string{"a", "b", "c", "d"}
    pos1 := IsElementInListWithPos(3, list1)
    pos2 := IsElementInListWithPos("a", list2)
    fmt.Println(pos1, pos2)
}

Это дает мне следующие ошибки:

cannot use list (type []int) as type []interface {} in argument to IsElementInListWithPos
cannot use list2 (type []string) as type []interface {} in argument to IsElementInListWithPos

Любая идея, как я мог бы решить эту проблему, фактически не используя две разные функции?Заранее спасибо.

Answer 1

В настоящее время невозможно создать решение, отвечающее всем вашим критериям.Это станет возможным, как только generics будут внедрены.Или вы можете попробовать создать его с использованием reflect, но это приведет к сложному и потенциально медленному решению ... поэтому я обычно советую не использовать reflect для чего-то более простого (см. Второй фрагмент ниже).

То, что вы можете сделать прямо сейчас, это использовать что-то вроде:

func FindFirst(n int, f func(int) bool) int {
    for i := 0; i < n; i++ {
        if f(i) {
            return i
        }
    }
    return -1
}

// in your code (s is the slice, e the value you are searching for)
i := FindFirst(len(s), func(i int) bool {
    return s[i] == e
})
if i != -1 {
    // i is the index of the element with value e
}

Это, как вы можете себе представить, не имеет особого смысла ... так как это возможно проще, быстрее и большеидиоматично просто выписать цикл в явном виде :

// in your code (s is the slice, e the value you are searching for)
for i, v := range s {
    if v == e {
        _ = i // i is the index of the element with value e
        break
    }
}

Очевидно, что весь этот подход (линейное сканирование) является разумным, только если количество элементов в срезке мало.Если ваш срез большой и редко меняется, возможно, было бы целесообразнее (с точки зрения сложности времени) сначала отсортировать его (sort.Slice), а затем выполнить бинарный поиск (sort.Search) на отсортированный ломтик.Или, в качестве альтернативы, вы могли бы использовать map вместо этого: в этом случае (при условии, что ключи маленькие) поиск будет O (1).

Answer 2

Пакет sort демонстрирует, как можно использовать интерфейсы для реализации алгоритмов независимо от типа.

Для линейного поиска требуются две основные операции, которые зависят от типа элемента haystack, Len иРовный.Таким образом, мы можем написать следующий интерфейс Haystack и функцию поиска, использующую его:

type Haystack interface {
    Len() int
    Equal(int, interface{}) bool
}

func Search(haystack Haystack, needle interface{}) int {
    for i := 0; i < haystack.Len(); i++ {
        if haystack.Equal(i, needle) {
            return i
        }
    }
    return -1
}

Это делает написание реализаций для Haystack простым, но не безопасным для типов:

type Strings []string

func (s Strings) Len() int                        { return len(s) }
func (s Strings) Equal(i int, x interface{}) bool { return s[i] == x.(string) }

type Ints []int

func (s Ints) Len() int                        { return len(s) }
func (s Ints) Equal(i int, x interface{}) bool { return s[i] == x.(int) }

func main() {
    strings := []string{"b", "a", "c", "d"}
    fmt.Println(Search(Strings(strings), "c")) // 2
    fmt.Println(Search(Strings(strings), "e")) // -1

    ints := []int{2, 1, 3, 4}
    fmt.Println(Search(Ints(ints), 3)) // 2
    fmt.Println(Search(Ints(ints), 5)) // -1
}

Обратите внимание наутверждения типа в методах Equal.Чтобы сделать этот тип безопасным, мы должны избавиться от аргумента interface{} для Equal:

type Haystack interface {
    Len() int
    Equal(int) bool
}

func Search(haystack Haystack) int {
    for i := 0; i < haystack.Len(); i++ {
        if haystack.Equal(i) {
            return i
        }
    }
    return -1
}

type Strings struct {
    hs     []string
    needle string
}

func (s Strings) Len() int         { return len(s.hs) }
func (s Strings) Equal(i int) bool { return s.hs[i] == s.needle }

type Ints struct {
    hs     []int
    needle int
}

func (s Ints) Len() int         { return len(s.hs) }
func (s Ints) Equal(i int) bool { return s.hs[i] == s.needle }

func main() {
    strings := []string{"b", "a", "c", "d"}
    fmt.Println(Search(Strings{strings, "c"})) // 2
    fmt.Println(Search(Strings{strings, "e"})) // -1

    ints := []int{2, 1, 3, 4}
    fmt.Println(Search(Ints{ints, 3})) // 2
    fmt.Println(Search(Ints{ints, 5})) // -1
}

Это значительно усложнило как реализацию интерфейса, так и использование функции поиска.

Мораль этой истории в том, что использование интерфейсов таким образом требует достаточно сложного алгоритма, чтобы стоить проблем.Если написание реализации интерфейса для определенного типа - это больше, чем написание конкретной реализации для алгоритма, тогда просто напишите нужные вам конкретные функции:

func SearchStr(haystack []string, needle string) int {
    for i, x := range haystack {
        if x == needle {
            return i
        }
    }
    return -1
}

func SearchInt(haystack []int, needle int) int {
    for i, x := range haystack {
        if x == needle {
            return i
        }
    }
    return -1
}

func main() {
    strings := []string{"b", "a", "c", "d"}
    fmt.Println(SearchStr(strings, "c")) // 2
    fmt.Println(SearchStr(strings, "e")) // -1

    ints := []int{2, 1, 3, 4}
    fmt.Println(SearchInt(ints, 3)) // 2
    fmt.Println(SearchInt(ints, 5)) // -1
}