下面的方法可行，但我該如何優(yōu)化呢？我想隨著數(shù)組的增長(zhǎng)，循環(huán)遍歷數(shù)組會(huì)變得昂貴。我可以創(chuàng)建原始數(shù)組的映射來(lái)存儲(chǔ)每個(gè)值的出現(xiàn)次數(shù)，然后在另一個(gè)循環(huán)中檢查這些值是否為 +/-/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 回答
天涯盡頭無(wú)女友
TA貢獻(xiàn)1831條經(jīng)驗(yàn) 獲得超9個(gè)贊
如果您的輸入結(jié)構(gòu)是未排序的數(shù)組，那么 O(n) 是您能做的最好的事情，即遍歷數(shù)組，比較每個(gè)元素一次。
如果可以的話，您可以使用兩個(gè)數(shù)組和一個(gè)整數(shù)，一個(gè)數(shù)組用于負(fù)數(shù)，一個(gè)數(shù)組用于正數(shù)，以及一個(gè)整數(shù)來(lái)計(jì)算零的數(shù)量。那么，就不再需要計(jì)數(shù)了，你可以簡(jiǎn)單地獲取數(shù)組的長(zhǎng)度。
收到一只叮咚
TA貢獻(xiàn)1821條經(jīng)驗(yàn) 獲得超5個(gè)贊
最快的方法是：
a) 確保數(shù)組/切片使用盡可能小的數(shù)據(jù)類型（以減少 RAM 量和所觸及的緩存行數(shù)；將更多值打包到單個(gè) SIMD 寄存器中，并減少我要進(jìn)行的移位量稍后建議） - 例如，對(duì)于您可以/應(yīng)該使用int8（而不是）的問(wèn)題中顯示的值int。
b) 在末尾添加零，以將數(shù)組/切片填充到 CPU 使用 SIMD 一次可以執(zhí)行的多個(gè)元素的倍數(shù)（例如，如果您在支持 AVX2 的 80x86 CPU 上使用，則為 32 個(gè)元素）int8。當(dāng)您接近數(shù)組/切片的末尾時(shí)，這主要避免了混亂的麻煩。
c) 在循環(huán)中使用SIMD：
將一組值加載到 SIMD 寄存器中
將組復(fù)制到另一個(gè) SIMD 寄存器
對(duì)整組數(shù)字使用“無(wú)符號(hào)右移”，然后使用“AND”，以便每個(gè)數(shù)字中的最低位包含原始數(shù)字的符號(hào)位
將其結(jié)果添加到不同 SIMD 寄存器中的“負(fù)數(shù)計(jì)數(shù)器組”
使用“移位”和“或”序列，將數(shù)字的所有位合并為單個(gè)位，得到“如果原始數(shù)字非零則為 1，如果原始數(shù)字為零則為 0”
將其結(jié)果添加到不同 SIMD 寄存器中的“非零數(shù)字計(jì)數(shù)器組”
d) 畢竟（在循環(huán)之外）：
通過(guò)對(duì)“負(fù)數(shù)計(jì)數(shù)器組”進(jìn)行“水平相加”來(lái)計(jì)算負(fù)數(shù)的計(jì)數(shù)
通過(guò)對(duì)“非零數(shù)計(jì)數(shù)器組”進(jìn)行“水平加法”來(lái)計(jì)算正數(shù)的計(jì)數(shù)，然后減去負(fù)數(shù)的計(jì)數(shù)
通過(guò)執(zhí)行“zeros = all_numbers - negative_numbers - Positive_numbers - padding_zeros”來(lái)計(jì)算零的數(shù)量
當(dāng)然，要做好任何事情，您需要內(nèi)聯(lián)匯編，這意味著您需要類似https://godoc.org/github.com/slimsag/rand/simd的東西（它以一種很好的便攜方式為您完成內(nèi)聯(lián)匯編） ）。
注 1：對(duì)于大型數(shù)組/切片（但不是小型數(shù)組/切片），您還需要并行使用多個(gè) CPU（例如，如果有 N 個(gè) CPU，則擁有 N 個(gè)線程/goroutine，并將數(shù)組/切片拆分為 N 塊，其中每個(gè)塊線程/goroutine 執(zhí)行一件事情，然后在執(zhí)行“步驟 d)”之前添加每件事情的計(jì)數(shù)。
注2：對(duì)于數(shù)據(jù)量較大的情況；我的算法是“O(n)”，并且因?yàn)槟脑妓惴ㄖ皇恰癘(n)”，所以我希望我的算法在現(xiàn)代硬件上快 100 倍。然而，對(duì)于非常少量的數(shù)據(jù)，因?yàn)椤癘(n)”不是線性的，我希望你的算法比我的更快。
Qyouu
TA貢獻(xiàn)1786條經(jīng)驗(yàn) 獲得超11個(gè)贊
注意：這是一個(gè)極其粗糙的實(shí)現(xiàn)。與一磅鹽一起服用。
為了便于閱讀，省略了打包和導(dǎo)入。
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
}
測(cè)試代碼：
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)
? ? }
}
根據(jù)基準(zhǔn)：
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
編輯找到了一種稍微更有效的返回計(jì)數(shù)的方法。我們不創(chuàng)建新切片，而是計(jì)算每個(gè)子切片的長(zhǎng)度。當(dāng)切片較小時(shí)，這使得預(yù)排序非常有效。但在 10M 時(shí)，簡(jiǎn)單地計(jì)數(shù)似乎是最有效的。
- 3 回答
- 0 關(guān)注
- 203 瀏覽
添加回答
舉報(bào)
0/150
提交
取消