Ali menite, da sta ti dve možnosti za preizkušanje pogojev znotraj zanke enakovredni v zmogljivosti?
if a > b && c*2 > d {
....
}
// и
if a <= b {
continue;
}
if c*2 > d {
....
}
Vse se je začelo z »ogrevanjem možganov«; moral sem navesti primer optimalnega iskanja največjega sodega števila v nizu celih števil [-x....x]. Spraševal sem se, koliko boljša bi bila učinkovitost, če bi uporabil logično množenje z 1, da bi ugotovil, ali je število sodo ali ne.
//у четных чисел последний бит всегда равен 0
value & 1 == 0
//vs классический метод
value % 2 == 0
Moje izkušnje s programiranjem v Go niso zelo obsežne, nekaj več kot leto in pol, uporabljal sem ga, čeprav pogosto, vendar izključno za utilitarne namene (no, morda razen enega projekta, povezanega z visoko obremenjeno storitvijo http), tako da sem začel s tem. Odprite GoLand in napišite preprost test
package main
import (
"fmt"
"log"
"math"
"math/rand"
"time"
)
const size = 100000000 //math.MaxInt32*2
type Result struct {
Name string
Duration time.Duration
Value int32
}
func main() {
log.Println("initial array capacity: " + fmt.Sprint(size))
var maxValue int32
// Будем варьировать диапазон чисел от минимального
// до максимального. Чем меньше диапазон, тем больше
// процессорного времени будет уходить на операцию
// сравнения текущего числа, с ранее найденным и наоборот
for maxValue = 128; maxValue < math.MaxInt32/2+1; maxValue = maxValue * 2 {
test(maxValue)
}
}
func test(maxValue int32) {
log.Println("max threshold: " + fmt.Sprint(maxValue))
arr := make([]int32, size)
for i := range arr {
arr[i] = rand.Int31n(maxValue)
// в тестовых данных нам нужны и отрицательные числа
sign := rand.Intn(2)
if sign == 1 {
arr[i] = -arr[i]
}
}
// запускаем тест "деление с остатком"
result := maxEvenDividing("maxEvenDividing", arr)
log.Printf(result.Name+"t result: "+fmt.Sprint(result.Value)+"ttduration %s", result.Duration)
// запускаем тест "конъюнкции"
result = maxEvenConjunction("maxEvenConjunction", arr)
log.Printf(result.Name+"t result: "+fmt.Sprint(result.Value)+"ttduration %s", result.Duration)
}
func maxEvenDividing(name string, arr []int32) Result {
start := time.Now()
var current int32 = math.MinInt32
for _, value := range arr {
if value > current && value%2 == 0 {
current = value
}
}
duration := time.Since(start)
result := Result{name, duration, current}
return result
}
func maxEvenConjunction(name string, arr []int32) Result {
start := time.Now()
var current int32 = math.MinInt32
for _, value := range arr {
if value > current && value&1 == 0 {
current = value
}
}
duration := time.Since(start)
result := Result{name, duration, current}
return result
}
Dobimo rezultat, ki kaže, da višji kot je prag, pogostejša so nihanja v uspešnosti.
Primerjajmax threshold: 128
maxEvenDividing result: 126 duration 116.0067ms
maxEvenConjunction result: 126 duration 116.0066ms
max threshold: 16384
maxEvenDividing result: 16382 duration 115.0066ms
maxEvenConjunction result: 16382 duration 111.0064ms
......
max threshold: 8388608
maxEvenDividing result: 8388606 duration 109.0063ms
maxEvenConjunction result: 8388606 duration 109.0062ms
max threshold: 16777216
maxEvenDividing result: 16777214 duration 108.0062ms
maxEvenConjunction result: 16777214 duration 109.0062ms
max threshold: 33554432
maxEvenDividing result: 33554430 duration 114.0066ms
maxEvenConjunction result: 33554430 duration 110.0063ms
max threshold: 67108864
maxEvenDividing result: 67108860 duration 111.0064ms
maxEvenConjunction result: 67108860 duration 109.0062ms
max threshold: 134217728
maxEvenDividing result: 134217726 duration 108.0062ms
maxEvenConjunction result: 134217726 duration 109.0063ms
max threshold: 268435456
maxEvenDividing result: 268435446 duration 111.0063ms
maxEvenConjunction result: 268435446 duration 110.0063ms
Jasno je, da imamo v tem primeru za različne pragove različne nize testnih podatkov, obremenitev procesorja (na mojem prenosnem računalniku i5-2540M) se giblje okoli 20..30 %, pomnilnik, ki ga zaseda aplikacija, ki se izvaja iz GoLand, je v povprečju približno 813 MB - to vpliva tudi na zanesljivost rezultata, testne primere morate shraniti na disk in zagnati vse teste za vsak prag ločeno drug od drugega.
In zdaj, ko razmišljam o tem, kako vse to izvesti z minimalnimi stroški, samodejno popravim preverjanje stanja
if value > current && value&1 == 0 {
current = value
}
o
if value <= current {
continue;
}
if value&1 == 0 {
current = value
}
Spet izvajam teste ... in nič ne razumem :)
Čas, porabljen za izvedbo, se ne začne več razlikovati v odstotkih/delih odstotka, ampak za 10..15%.Na hitro dodam še 2 testa:
func maxEvenDividing2(name string, arr []int32) Result {
start := time.Now()
var current int32 = math.MinInt32
for _, value := range arr {
if value <= current {
continue
}
if value%2 == 0 {
current = value
}
}
duration := time.Since(start)
result := Result{name, duration, current}
return result
}
func maxEvenConjunction2(name string, arr []int32) Result {
start := time.Now()
var current int32 = math.MinInt32
for _, value := range arr {
if value <= current {
continue
}
if value&1 == 0 {
current = value
}
}
duration := time.Since(start)
result := Result{name, duration, current}
return result
}
Zaženem ga in dobim to sliko:začetna zmogljivost polja: 100000000
najvišji prag: 128
maxEvenDividing rezultat: 126 trajanje 116.0066ms
rezultat maxEvenDividing2: 126 trajanje 79.0045 ms
Rezultat maxEvenConjunction: 126 trajanje 114.0065 ms
rezultat maxEvenConjunction2: 126 trajanje 83.0048 ms
najvišji prag: 256
maxEvenDividing rezultat: 254 trajanje 111.0063ms
rezultat maxEvenDividing2: 254 trajanje 77.0044 ms
Rezultat maxEvenConjunction: 254 trajanje 110.0063 ms
rezultat maxEvenConjunction2: 254 trajanje 80.0046 ms
najvišji prag: 512
maxEvenDividing rezultat: 510 trajanje 114.0066ms
rezultat maxEvenDividing2: 510 trajanje 80.0045 ms
Rezultat maxEvenConjunction: 510 trajanje 110.0063 ms
rezultat maxEvenConjunction2: 510 trajanje 80.0046 ms
najvišji prag: 1024
maxEvenDividing rezultat: 1022 trajanje 109.0063ms
rezultat maxEvenDividing2: 1022 trajanje 77.0044 ms
Rezultat maxEvenConjunction: 1022 trajanje 111.0063 ms
rezultat maxEvenConjunction2: 1022 trajanje 81.0047 ms
najvišji prag: 2048
maxEvenDividing rezultat: 2046 trajanje 114.0065ms
rezultat maxEvenDividing2: 2046 trajanje 79.0045 ms
Rezultat maxEvenConjunction: 2046 trajanje 113.0065 ms
rezultat maxEvenConjunction2: 2046 trajanje 81.0046 ms
najvišji prag: 4096
maxEvenDividing rezultat: 4094 trajanje 114.0065ms
rezultat maxEvenDividing2: 4094 trajanje 80.0046 ms
Rezultat maxEvenConjunction: 4094 trajanje 111.0063 ms
rezultat maxEvenConjunction2: 4094 trajanje 78.0045 ms
najvišji prag: 8192
maxEvenDividing rezultat: 8190 trajanje 107.0062ms
rezultat maxEvenDividing2: 8190 trajanje 77.0044 ms
Rezultat maxEvenConjunction: 8190 trajanje 111.0063 ms
rezultat maxEvenConjunction2: 8190 trajanje 77.0044 ms
najvišji prag: 16384
maxEvenDividing rezultat: 16382 trajanje 109.0063ms
rezultat maxEvenDividing2: 16382 trajanje 77.0044 ms
Rezultat maxEvenConjunction: 16382 trajanje 108.0062 ms
rezultat maxEvenConjunction2: 16382 trajanje 77.0044 ms
najvišji prag: 32768
maxEvenDividing rezultat: 32766 trajanje 112.0064ms
rezultat maxEvenDividing2: 32766 trajanje 77.0044 ms
Rezultat maxEvenConjunction: 32766 trajanje 109.0062 ms
rezultat maxEvenConjunction2: 32766 trajanje 78.0045 ms
najvišji prag: 65536
maxEvenDividing rezultat: 65534 trajanje 109.0062ms
rezultat maxEvenDividing2: 65534 trajanje 75.0043 ms
Rezultat maxEvenConjunction: 65534 trajanje 109.0063 ms
rezultat maxEvenConjunction2: 65534 trajanje 79.0045 ms
najvišji prag: 131072
maxEvenDividing rezultat: 131070 trajanje 108.0061ms
rezultat maxEvenDividing2: 131070 trajanje 76.0044 ms
Rezultat maxEvenConjunction: 131070 trajanje 110.0063 ms
rezultat maxEvenConjunction2: 131070 trajanje 80.0046 ms
najvišji prag: 262144
maxEvenDividing rezultat: 262142 trajanje 110.0063ms
rezultat maxEvenDividing2: 262142 trajanje 76.0044 ms
Rezultat maxEvenConjunction: 262142 trajanje 107.0061 ms
rezultat maxEvenConjunction2: 262142 trajanje 78.0044 ms
najvišji prag: 524288
maxEvenDividing rezultat: 524286 trajanje 109.0062ms
rezultat maxEvenDividing2: 524286 trajanje 78.0045 ms
Rezultat maxEvenConjunction: 524286 trajanje 109.0062 ms
rezultat maxEvenConjunction2: 524286 trajanje 80.0046 ms
najvišji prag: 1048576
maxEvenDividing rezultat: 1048574 trajanje 109.0063ms
rezultat maxEvenDividing2: 1048574 trajanje 80.0045 ms
Rezultat maxEvenConjunction: 1048574 trajanje 114.0066 ms
rezultat maxEvenConjunction2: 1048574 trajanje 78.0044 ms
najvišji prag: 2097152
maxEvenDividing rezultat: 2097150 trajanje 111.0064ms
rezultat maxEvenDividing2: 2097150 trajanje 79.0045 ms
Rezultat maxEvenConjunction: 2097150 trajanje 112.0064 ms
rezultat maxEvenConjunction2: 2097150 trajanje 77.0044 ms
najvišji prag: 4194304
maxEvenDividing rezultat: 4194302 trajanje 111.0063ms
rezultat maxEvenDividing2: 4194302 trajanje 78.0045 ms
Rezultat maxEvenConjunction: 4194302 trajanje 111.0063 ms
rezultat maxEvenConjunction2: 4194302 trajanje 77.0044 ms
najvišji prag: 8388608
maxEvenDividing rezultat: 8388606 trajanje 109.0062ms
rezultat maxEvenDividing2: 8388606 trajanje 78.0045 ms
Rezultat maxEvenConjunction: 8388606 trajanje 114.0065 ms
rezultat maxEvenConjunction2: 8388606 trajanje 78.0045 ms
najvišji prag: 16777216
maxEvenDividing rezultat: 16777214 trajanje 109.0062ms
rezultat maxEvenDividing2: 16777214 trajanje 77.0044 ms
Rezultat maxEvenConjunction: 16777214 trajanje 109.0063 ms
rezultat maxEvenConjunction2: 16777214 trajanje 77.0044 ms
najvišji prag: 33554432
maxEvenDividing rezultat: 33554430 trajanje 113.0065ms
rezultat maxEvenDividing2: 33554430 trajanje 78.0045 ms
Rezultat maxEvenConjunction: 33554430 trajanje 110.0063 ms
rezultat maxEvenConjunction2: 33554430 trajanje 80.0045 ms
najvišji prag: 67108864
maxEvenDividing rezultat: 67108860 trajanje 112.0064ms
rezultat maxEvenDividing2: 67108860 trajanje 77.0044 ms
Rezultat maxEvenConjunction: 67108860 trajanje 112.0064 ms
rezultat maxEvenConjunction2: 67108860 trajanje 80.0046 ms
najvišji prag: 134217728
maxEvenDividing rezultat: 134217726 trajanje 109.0063ms
rezultat maxEvenDividing2: 134217726 trajanje 78.0044 ms
Rezultat maxEvenConjunction: 134217726 trajanje 114.0065 ms
rezultat maxEvenConjunction2: 134217726 trajanje 81.0047 ms
najvišji prag: 268435456
maxEvenDividing rezultat: 268435446 trajanje 111.0064ms
rezultat maxEvenDividing2: 268435446 trajanje 79.0045 ms
Rezultat maxEvenConjunction: 268435446 trajanje 114.0065 ms
rezultat maxEvenConjunction2: 268435446 trajanje 79.0045 ms
najvišji prag: 536870912
maxEvenDividing rezultat: 536870910 trajanje 107.0062ms
rezultat maxEvenDividing2: 536870910 trajanje 76.0043 ms
Rezultat maxEvenConjunction: 536870910 trajanje 109.0062 ms
rezultat maxEvenConjunction2: 536870910 trajanje 80.0046 ms
Nisem našel jasne razlage, zakaj prevajalnik Go ne optimizira kode in vedno preveri drugi pogoj, tudi če je prvi napačen. Ali pa so moje oči samo zamegljene in ne vidim nobene očitne napake? Ali pa morate prevajalniku dati nekaj posebnih navodil? Vesela bom pametnih komentarjev.
PS: Da, samo za šalo sem izvajal podobne teste na Javi 5 in Javi 7/8 - vse je jasno, čas izvajanja je enak.
Vir: www.habr.com