下面的方法可行，但我该如何优化呢？我想随着数组的增长，循环遍历数组会变得昂贵。我可以创建原始数组的映射来存储每个值的出现次数，然后在另一个循环中检查这些值是否为 +/-/0，但这更糟糕。package mainimport ( "fmt")func main() { arr := []int{2, 5, 6, 7, 8, 2, 4, 1, 1, 1, 2, -2, -2, 2, 2, 3, -1, 0, 0, 0, 0, 2, 5, 4, 9, 8, 7, 2, -3, -7} var p, n, z int = 0, 0, 0 for _, v := range arr { if v > 0 { p++ } else if v < 0 { n++ } else if v == 0 { z++ } } fmt.Println(p, n, z)}
3 回答
天涯尽头无女友
TA贡献1831条经验 获得超9个赞
如果您的输入结构是未排序的数组，那么 O(n) 是您能做的最好的事情，即遍历数组，比较每个元素一次。
如果可以的话，您可以使用两个数组和一个整数，一个数组用于负数，一个数组用于正数，以及一个整数来计算零的数量。那么，就不再需要计数了，你可以简单地获取数组的长度。
收到一只叮咚
TA贡献1821条经验 获得超4个赞
最快的方法是：
a) 确保数组/切片使用尽可能小的数据类型（以减少 RAM 量和所触及的缓存行数；将更多值打包到单个 SIMD 寄存器中，并减少我要进行的移位量稍后建议） - 例如，对于您可以/应该使用int8（而不是）的问题中显示的值int。
b) 在末尾添加零，以将数组/切片填充到 CPU 使用 SIMD 一次可以执行的多个元素的倍数（例如，如果您在支持 AVX2 的 80x86 CPU 上使用，则为 32 个元素）int8。当您接近数组/切片的末尾时，这主要避免了混乱的麻烦。
c) 在循环中使用SIMD：
将一组值加载到 SIMD 寄存器中
将组复制到另一个 SIMD 寄存器
对整组数字使用“无符号右移”，然后使用“AND”，以便每个数字中的最低位包含原始数字的符号位
将其结果添加到不同 SIMD 寄存器中的“负数计数器组”
使用“移位”和“或”序列，将数字的所有位合并为单个位，得到“如果原始数字非零则为 1，如果原始数字为零则为 0”
将其结果添加到不同 SIMD 寄存器中的“非零数字计数器组”
d) 毕竟（在循环之外）：
通过对“负数计数器组”进行“水平相加”来计算负数的计数
通过对“非零数计数器组”进行“水平加法”来计算正数的计数，然后减去负数的计数
通过执行“zeros = all_numbers - negative_numbers - Positive_numbers - padding_zeros”来计算零的数量
当然，要做好任何事情，您需要内联汇编，这意味着您需要类似https://godoc.org/github.com/slimsag/rand/simd的东西（它以一种很好的便携方式为您完成内联汇编） ）。
注 1：对于大型数组/切片（但不是小型数组/切片），您还需要并行使用多个 CPU（例如，如果有 N 个 CPU，则拥有 N 个线程/goroutine，并将数组/切片拆分为 N 块，其中每个块线程/goroutine 执行一件事情，然后在执行“步骤 d)”之前添加每件事情的计数。
注2：对于数据量较大的情况；我的算法是“O(n)”，并且因为您的原始算法只是“O(n)”，所以我希望我的算法在现代硬件上快 100 倍。然而，对于非常少量的数据，因为“O(n)”不是线性的，我希望你的算法比我的更快。
Qyouu
TA贡献1786条经验 获得超11个赞
注意：这是一个极其粗糙的实现。与一磅盐一起服用。
为了便于阅读，省略了打包和导入。
var slice = []int{2, 5, 6, 7, 8, 2, 4, 1, 1, 1, 2, -2, -2, 2, 2, 3, -1, 0, 0, 0, 0, 2, 5, 4, 9, 8, 7, 2, -3, -7}
func orig(s []int) (negative, zero, positive int) {
for _, v := range s {
if v > 0 {
positive++
} else if v < 0 {
negative++
} else if v == 0 {
zero++
}
}
return
}
func sorted(s []int) (negative, zero, positive int) {
// We do not want to modify the input slice,
// so we need to create a copy of it
sortedSlice := make([]int, len(s))
copy(sortedSlice, s)
sort.Ints(sortedSlice)
return preSorted(sortedSlice)
}
func preSorted(s []int) (int, int, int) {
var z, p int
var zfound bool
for i := 0; i < len(s); i++ {
if s[i] < 0 {
continue
} else if !zfound && s[i] == 0 {
zfound = true
z = i
} else if s[i] > 0 {
p = i
break
}
}
return z, p - z, len(s) - p
}
测试代码：
func BenchmarkOrig(b *testing.B) {
for i := 0; i < b.N; i++ {
orig(slice)
}
}
func BenchmarkLongOrig(b *testing.B) {
var slice = make([]int, 10000000)
for i := 0; i < 10000000; i++ {
slice[i] = rand.Intn(10)
if rand.Intn(2) == 0 {
slice[i] = slice[i] * -1
}
}
b.ResetTimer()
for i := 0; i < b.N; i++ {
orig(slice)
}
}
func BenchmarkSorted(b *testing.B) {
for i := 0; i < b.N; i++ {
sorted(slice)
}
}
func BenchmarkLongSorted(b *testing.B) {
var slice = make([]int, 10000000)
for i := 0; i < 10000000; i++ {
slice[i] = rand.Intn(10)
if rand.Intn(2) == 0 {
slice[i] = slice[i] * -1
}
}
b.ResetTimer()
for i := 0; i < b.N; i++ {
sorted(slice)
}
}
func BenchmarkPresorted(b *testing.B) {
cp := make([]int, len(slice))
copy(cp, slice)
sort.Ints(cp)
b.ResetTimer()
for i := 0; i < b.N; i++ {
preSorted(cp)
}
}
func BenchmarkLongPresorted(b *testing.B) {
var slice = make([]int, 10000000)
for i := 0; i < 10000000; i++ {
slice[i] = rand.Intn(10)
if rand.Intn(2) == 0 {
slice[i] = slice[i] * -1
}
}
sort.Ints(slice)
b.ResetTimer()
for i := 0; i < b.N; i++ {
sorted(slice)
}
}
根据基准：
goos: darwin
goarch: amd64
BenchmarkOrig-4 27271665 38.4 ns/op 0 B/op 0 allocs/op
BenchmarkLongOrig-4 21 50343196 ns/op 0 B/op 0 allocs/op
BenchmarkSorted-4 1405150 852 ns/op 272 B/op 2 allocs/op
BenchmarkLongSorted-4 2 536973066 ns/op 80003104 B/op 2 allocs/op
BenchmarkPresorted-4 100000000 10.9 ns/op 0 B/op 0 allocs/op
BenchmarkLongPresorted-4 5 248698010 ns/op 80003104 B/op 2 allocs/op
编辑找到了一种稍微更有效的返回计数的方法。我们不创建新切片，而是计算每个子切片的长度。当切片较小时，这使得预排序非常有效。但在 10M 时，简单地计数似乎是最有效的。
- 3 回答
- 0 关注
- 95 浏览
添加回答
举报
0/150
提交
取消