下面的方法可行，但我該如何優化呢？我想隨著數組的增長，循環遍歷數組會變得昂貴。我可以創建原始數組的映射來存儲每個值的出現次數，然后在另一個循環中檢查這些值是否為 +/-/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條經驗 獲得超5個贊
最快的方法是：
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 關注
- 188 瀏覽
添加回答
舉報
0/150
提交
取消