Вы в значительной степени в оптимальном решении. Сначала я применил предложение @ bserdar о сортировке и провел с ним тест.
Примечание: это очень грубая реализация. Возьми это с фунтом соли.
Упаковка и импорт опущены для удобства чтения.
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, простое подсчет кажется наиболее эффективным.
qed