Golang如何根据第二个切片定义的组切分子切片

Golang如何根据第二个切片定义的组切分子切片 我是一名偶尔使用Go语言的程序员，需要一些关于如何改进以下任务的帮助/建议。

我有两个切片：

  • 第一个切片 s 包含字符串，这些字符串不是唯一的，因为相同的字符串会时不时地重复出现两次或多次。
  • 第二个切片 n 包含整数，其内容指的是每个字符串在上方循环中生成时的迭代次数。

一个最小示例如下：

s := []string{"a", "b", "c", "c", "e", "c", "e", "d", "e"} // 字符串
n := []int{1, 1, 1, 2, 2, 3, 3, 4, 4}                      // 生成字符串时的迭代次数

本质上，字符串 “a” 是在第 1 次迭代中生成的，“b” 也是如此，而 “c” 是在第 1、2 和 3 次迭代中生成的…

我现在需要根据 ‘分组’ 切片 s 将切片 n 分割成子切片：

// 我期望的最终结果是
r := [][]int{{1}, {1}, {1, 2, 3}, {4}, {2, 3, 4}}

本质上，第一个子切片基于字符串 “a”，它只在第 1 次迭代中生成；第二个子切片是 “b”，同样只在第 1 次迭代中生成；然后是 “c”，在第 1、2 和 3 次迭代中生成…

我考虑过使用映射（map），因为键是唯一的。 再次说明：

// 我期望的映射最终结果
m := make(map[string][]int)
m["a"] = []int{1}
m["b"] = []int{1}
m["c"] = []int{1, 2, 3}
m["d"] = []int{4}
m["e"] = []int{2, 3, 4}

下面的代码工作得很好，但当输入切片（s 和 n）有数千个元素时，它非常慢。

package main

import (
	"fmt"
)

func main() {
	s := []string{"a", "b", "c", "c", "e", "c", "e", "d", "e"}
	n := []int{1, 1, 1, 2, 2, 3, 3, 4, 4}

	computedm := make(map[string][]int)
	for i := 0; i < len(s); i++ {
		x := indexof(s, s[i])
		var y []int
		for _, p := range x {
			y = append(y, n[p])
		}
		computedm[s[i]] = y
	}
	fmt.Println(computedm)
}

func indexof(ss []string, s string) []int {
	var res []int
	for i, j := range ss {
		if j == s {
			res = append(res, i)
		}
	}
	return res
}

我怎样才能让它更快？快到极致…


更多关于Golang如何根据第二个切片定义的组切分子切片的实战教程也可以访问 https://www.itying.com/category-94-b0.html

2 回复

在不深入查看或运行任何性能分析的情况下，我猜测循环内的切片创建和追加操作是开销最大的部分。如果你能预先分配所需的空间，这可能会加快速度。

更多关于Golang如何根据第二个切片定义的组切分子切片的实战系列教程也可以访问 https://www.itying.com/category-94-b0.html


你可以通过一次遍历同时构建映射，避免重复的索引查找。以下是优化后的代码：

package main

import "fmt"

func main() {
	s := []string{"a", "b", "c", "c", "e", "c", "e", "d", "e"}
	n := []int{1, 1, 1, 2, 2, 3, 3, 4, 4}

	computedm := make(map[string][]int)
	for i, str := range s {
		computedm[str] = append(computedm[str], n[i])
	}
	
	fmt.Println(computedm)
}

输出：

map[a:[1] b:[1] c:[1 2 3] d:[4] e:[2 3 4]]

如果你需要保持原始顺序，可以使用切片来记录首次出现的顺序：

package main

import "fmt"

func main() {
	s := []string{"a", "b", "c", "c", "e", "c", "e", "d", "e"}
	n := []int{1, 1, 1, 2, 2, 3, 3, 4, 4}

	computedm := make(map[string][]int)
	var order []string
	
	for i, str := range s {
		if _, exists := computedm[str]; !exists {
			order = append(order, str)
		}
		computedm[str] = append(computedm[str], n[i])
	}
	
	// 按首次出现顺序输出结果
	for _, key := range order {
		fmt.Printf("%s: %v\n", key, computedm[key])
	}
}

输出：

a: [1]
b: [1]
c: [1 2 3]
e: [2 3 4]
d: [4]

这个解决方案的时间复杂度是 O(n)，只需要一次遍历即可完成所有操作。

回到顶部