如何在for循环中检查唯一性?

huangapple go评论106阅读模式
英文:

How to check the uniqueness inside a for-loop?

问题

有没有一种方法可以检查切片/映射中是否存在某个值?

我想要将一个值添加到切片中,但只有在切片中不存在该值时才添加。

这个方法可以工作,但似乎有点冗长。有没有更好的方法来做到这一点?

orgSlice := []int{1, 2, 3}
newSlice := []int{}
newInt := 2
    
newSlice = append(newSlice, newInt)
for _, v := range orgSlice {
	if v != newInt {
		newSlice = append(newSlice, v)
	}
}

newSlice == [2 1 3]
英文:

Is there a way to check slices/maps for the presence of a value?

I would like to add a value to a slice only if it does not exist in the slice.

This works, but it seems verbose. Is there a better way to do this?

orgSlice := []int{1, 2, 3}
newSlice := []int{}
newInt := 2
    
newSlice = append(newSlice, newInt)
for _, v := range orgSlice {
	if v != newInt {
		newSlice = append(newSlice, v)
	}
}

newSlice == [2 1 3]

答案1

得分: 134

你的方法对于每次插入都需要线性时间。更好的方法是使用map[int]struct{}。另外,你也可以使用map[int]bool或类似的东西,但是空的struct{}有一个优点,它不占用任何额外的空间。因此,map[int]struct{}是一个常用的整数集合的选择。

示例:

set := make(map[int]struct{})
set[1] = struct{}{}
set[2] = struct{}{}
set[1] = struct{}{}
// ...

for key := range(set) {
  fmt.Println(key)
}
// 每个值将只被打印一次,顺序不确定


// 你可以使用 ,ok 惯用法来检查是否存在键
if _, ok := set[1]; ok {
  fmt.Println("找到元素")
} else {
  fmt.Println("未找到元素")
}
英文:

Your approach would take linear time for each insertion. A better way would be to use a map[int]struct{}. Alternatively, you could also use a map[int]bool or something similar, but the empty struct{} has the advantage that it doesn't occupy any additional space. Therefore map[int]struct{} is a popular choice for a set of integers.

Example:

set := make(map[int]struct{})
set[1] = struct{}{}
set[2] = struct{}{}
set[1] = struct{}{}
// ...

for key := range(set) {
  fmt.Println(key)
}
// each value will be printed only once, in no particular order


// you can use the ,ok idiom to check for existing keys
if _, ok := set[1]; ok {
  fmt.Println("element found")
} else {
  fmt.Println("element not found")
}

答案2

得分: 53

最有效的方法可能是遍历切片并在找不到时添加。

func AppendIfMissing(slice []int, i int) []int {
    for _, ele := range slice {
        if ele == i {
            return slice
        }
    }
    return append(slice, i)
}

这个方法简单明了,对于小列表来说速度很快。

此外,它始终比您当前的基于映射的解决方案更快。无论如何,基于映射的解决方案都会遍历整个切片;而这个解决方案在找到新值已经存在时立即返回。两种解决方案都在迭代时进行元素比较。(每个映射赋值语句在内部肯定至少进行一次映射键比较。)只有在可以在多次插入之间保持映射时,映射才有用。如果您在每次插入时都重新构建它,那么所有的优势都会丧失。

如果您确实需要高效处理大型列表,请考虑以排序顺序维护列表。(我猜您不在乎顺序,因为您的第一个解决方案在列表开头添加,而最新的解决方案在列表末尾添加。)如果始终保持列表排序,那么可以使用sort.Search函数进行高效的二进制插入。

英文:

Most efficient is likely to be iterating over the slice and appending if you don't find it.

func AppendIfMissing(slice []int, i int) []int {
    for _, ele := range slice {
        if ele == i {
            return slice
        }
    }
    return append(slice, i)
}

It's simple and obvious and will be fast for small lists.

Further, it will always be faster than your current map-based solution. The map-based solution iterates over the whole slice no matter what; this solution returns immediately when it finds that the new value is already present. Both solutions compare elements as they iterate. (Each map assignment statement certainly does at least one map key comparison internally.) A map would only be useful if you could maintain it across many insertions. If you rebuild it on every insertion, then all advantage is lost.

If you truly need to efficiently handle large lists, consider maintaining the lists in sorted order. (I suspect the order doesn't matter to you because your first solution appended at the beginning of the list and your latest solution appends at the end.) If you always keep the lists sorted then you you can use the sort.Search function to do efficient binary insertions.

答案3

得分: 1

另一个选项:

package main
import "golang.org/x/tools/container/intsets"

func main() {
   var (
      a intsets.Sparse
      b bool
   )
   b = a.Insert(9)
   println(b) // true
   b = a.Insert(9)
   println(b) // false
}

https://pkg.go.dev/golang.org/x/tools/container/intsets

英文:

Another option:

package main
import "golang.org/x/tools/container/intsets"

func main() {
   var (
      a intsets.Sparse
      b bool
   )
   b = a.Insert(9)
   println(b) // true
   b = a.Insert(9)
   println(b) // false
}

https://pkg.go.dev/golang.org/x/tools/container/intsets

答案4

得分: 1

如果缺失数字的数量未知,则选择此选项

AppendIfMissing := func(sl []int, n ...int) []int {
    cache := make(map[int]int)
    for _, elem := range sl {
        cache[elem] = elem
    }
    for _, elem := range n {
        if _, ok := cache[elem]; !ok {
            sl = append(sl, elem)
        }
    }
    return sl
}
英文:

This option if the number of missing numbers is unknown

AppendIfMissing := func(sl []int, n ...int) []int {
    cache := make(map[int]int)
    for _, elem := range sl {
        cache[elem] = elem
    }
    for _, elem := range n {
        if _, ok := cache[elem]; !ok {
            sl = append(sl, elem)
        }
    }
    return sl
}

答案5

得分: -2

区分一个结构体数组:

func distinctObjects(objs []ObjectType) (distinctedObjs []ObjectType){
    var output []ObjectType
    for i:= range objs{
        if output==nil || len(output)==0{
            output=append(output,objs[i])
        } else {
            founded:=false
            for j:= range output{
                if output[j].fieldname1==objs[i].fieldname1 && output[j].fieldname2==objs[i].fieldname2 &&......... {
                    founded=true
                }
            }
            if !founded{
                output=append(output,objs[i])
            }
        }
    }
    return output
}

这里的结构体如下所示:

type ObjectType struct {
    fieldname1 string
    fieldname2 string
    .........
}

对象将通过检查的字段进行区分:

if output[j].fieldname1==objs[i].fieldname1 && output[j].fieldname2==objs[i].fieldname2 &&......... {
英文:

distincting a array of a struct :

func distinctObjects(objs []ObjectType) (distinctedObjs [] ObjectType){
	    var output []ObjectType
    for i:= range objs{
	    if output==nil || len(output)==0{
		    output=append(output,objs[i])
	    } else {
		    founded:=false
		    for j:= range output{
		    	    if output[j].fieldname1==objs[i].fieldname1 && output[j].fieldname2==objs[i].fieldname2 &&......... {
				    founded=true
			    }
		    }
		    if !founded{
			    output=append(output,objs[i])
		    }
	    }
    }
    return output
}

where the struct here is something like :

type ObjectType struct {
    fieldname1 string
    fieldname2 string
    .........
}

the object will distinct by checked fields here :

if output[j].fieldname1==objs[i].fieldname1 && output[j].fieldname2==objs[i].fieldname2 &&......... {

huangapple
  • 本文由 发表于 2012年2月13日 02:05:56
  • 转载请务必保留本文链接:https://go.coder-hub.com/9251234.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定