Finding Unique Items in a Go Slice or Array

I'm pretty new to go and I'm really, really confused right now.

Let's say I have a list of coordinates and lets say I have some doubles in this list of coordinates. I can't for the life of me figure out how to make a unique list. Normally in Python I can "cheat" with sets and other built-ins. Not so much in Go.

package main

import (
	"fmt"
	"reflect"
)

type visit struct {
	x, y int
}

func main() {
	var visited []visit
	var unique []visit

	visited = append(visited, visit{1, 100})
	visited = append(visited, visit{2, 2})
	visited = append(visited, visit{1, 100})
	visited = append(visited, visit{1, 1})

	unique = append(unique, visit{1, 1})

	fmt.Println(unique)

	// Go through the visits and find the unique elements
	for _, v := range visited {
		for _, u := range unique {

			fmt.Printf("Here's unique: %v\n", unique)
			fmt.Printf("Comparing %v to %v is %v\n", v, u, reflect.DeepEqual(v, u))

			if reflect.DeepEqual(v, u) {
				fmt.Println("Skip")
			} else {
				unique = append(unique, v)
			}
		}
	}

	fmt.Println(unique)
}

<kbd>Run it on Playground</kbd>

There are multiple errors in your code. The most serious is that since you're comparing each specific element of the visited slice to all of the elements of unique, you will end up appending it if unique contains at least one which is different. And going forward, you will end up appending it multiple times if there are more elements in unique which differ as your inner for loop doesn't "break". This is not what you want, you want to append elements which equals to none of unique.

Also note that a struct in Go is comparable if each of its fields are comparable. Since your visit struct contains only 2 int fields, it is comparable and so you can compare values of visit type simply with the == operator, no need that ugly reflect.DeepEqual(). See Spec: Comparison operators:

> Struct values are comparable if all their fields are comparable. Two struct values are equal if their corresponding non-blank fields are equal.

Here's a simplified, correct version that applies your logic:

visited := []visit{
	visit{1, 100},
	visit{2, 2},
	visit{1, 100},
	visit{1, 1},
}
var unique []visit

for _, v := range visited {
	skip := false
	for _, u := range unique {
		if v == u {
			skip = true
			break
		}
	}
	if !skip {
		unique = append(unique, v)
	}
}

fmt.Println(unique)

Output (try it on the Go Playground):

[{1 100} {2 2} {1 1}]

Alternative

It's true that Go doesn't have a built-in set type, but you can use a map[visit]bool easily as a set. With that, it becomes really simple! Note that visit can be used as key in the map because it is comparable (see above).

visited := []visit{
	visit{1, 100},
	visit{2, 2},
	visit{1, 100},
	visit{1, 1},
}
unique := map[visit]bool{}

for _, v := range visited {
	unique[v] = true
}

fmt.Println(unique)

Output (try it on the Go Playground):

map[{2 2}:true {1 1}:true {1 100}:true]

The unique "list" is the list of keys in the map.

If you want the unique visit values as a slice, see this variant:

var unique []visit
m := map[visit]bool{}

for _, v := range visited {
	if !m[v] {
		m[v] = true
		unique = append(unique, v)
	}
}

fmt.Println(unique)

Output (as expected, try it on the Go Playground):

[{1 100} {2 2} {1 1}]

Note that this index expression: m[v] evaluates to true if v is already in the map (as a key, true is the value we stored in the map). If v is not yet in the map, m[v] yields the zero value of the value type which is false for the type bool, properly telling that the value v is not yet in the map. See Spec: Index expressions:

> For a of map type M:
>
> ...if the map is nil or does not contain such an entry, a[x] is the zero value for the value type of M

I think you can use help of Map to solve this puzzle

https://play.golang.org/p/b7JtHYQ3N8

package main

import (
	"fmt"
)

type visit struct {
	x, y int
}

func main() {
	var visited []visit
	var unique []visit

	uniqueMap := map[visit]int{}

	visited = append(visited, visit{1, 100})
	visited = append(visited, visit{2, 2})
	visited = append(visited, visit{1, 100})
	visited = append(visited, visit{1, 1})

	for _, v := range visited {
		if _, exist := uniqueMap[v]; !exist {
			uniqueMap[v] = 1
			unique = append(unique, v)
		} else {
			uniqueMap[v]++
		}
	}
	fmt.Printf("Uniques: %v\nMaps:%v\n", unique, uniqueMap)
}

i think you can make a map of visits.
Something like this

visited := make(map[visit]Boolean)

than you can set the value of the visited.

visited[visit]=true

and lastly, you can fetch all visited locations by this code

for k, _ := range visited {
    unique = append(unique, k)
}

You can sort your slice via sort.Slice() and then make the slice unique by overwriting non-unique elements with following unique ones:

func Unique[T comparable](xs []T) []T {
    n := len(xs)
    if n == 0 {
        return xs
    }
    j := 0
    for i := 1; i < n; i++ {
        if xs[j] !=  xs[i] {
            j++
            if j < i {
                xs[j] = xs[i]
                for k := i + 1; k < n; k++ {
                    if xs[j] !=  xs[k] {
                        j++
                        xs[j] = xs[k]
                    }
                }
                break
            }
        }
    }
    xs = xs[0:j+1]
    return xs
}

Making the slice unique is only linear effort, however, this is dominated by the sorting (unless your input already is sorted), which is in O(n log n).

Example usage:

visited = sort.Slice(visited, func(i, j int) bool {
        return visited[i].x < visited[j].x && visited[i].y < visited[j].y })
visited = Unique(visited)
unique := visited

Alternatively, if you don't want to sort or don't care about the element order you can store all elements in a set-like map, which eliminates duplicates.

Example:

h := map[visit]struct{} {}
for _, v := range visited {
    h[v] = struct{} {}
}
unique := make(visit[], len(h))
i := 0
for k := range h {
    unique[i] = k
    i++
}

The total runtime is linear, unless your data hashes badly.