计算未排序数组中正值、负值和 0 值出现次数的最佳方法是什么？

Question

下面的方法可行，但我该如何优化呢？我想随着数组的增长，循环遍历数组会变得昂贵。我可以创建原始数组的映射来存储每个值的出现次数，然后在另一个循环中检查这些值是否为 +/-/0，但这更糟糕。

package main

import (

    "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)

}

Answer 1

如果您的输入结构是未排序的数组，那么 O(n) 是您能做的最好的事情，即遍历数组，比较每个元素一次。如果可以的话，您可以使用两个数组和一个整数，一个数组用于负数，一个数组用于正数，以及一个整数来计算零的数量。那么，就不再需要计数了，你可以简单地获取数组的长度。

Answer 2

最快的方法是：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)”不是线性的，我希望你的算法比我的更快。

Answer 3

注意：这是一个极其粗糙的实现。与一磅盐一起服用。为了便于阅读，省略了打包和导入。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: darwingoarch: amd64BenchmarkOrig-4             27271665            38.4 ns/op         0 B/op          0 allocs/opBenchmarkLongOrig-4               21      50343196 ns/op           0 B/op          0 allocs/opBenchmarkSorted-4            1405150           852 ns/op         272 B/op          2 allocs/opBenchmarkLongSorted-4              2     536973066 ns/op    80003104 B/op          2 allocs/opBenchmarkPresorted-4        100000000           10.9 ns/op         0 B/op          0 allocs/opBenchmarkLongPresorted-4           5     248698010 ns/op    80003104 B/op          2 allocs/op编辑找到了一种稍微更有效的返回计数的方法。我们不创建新切片，而是计算每个子切片的长度。当切片较小时，这使得预排序非常有效。但在 10M 时，简单地计数似乎是最有效的。